美文网首页程序员互联网科技我用 Linux
小朋友学数学(23):求2000!末尾有多少个0

小朋友学数学(23):求2000!末尾有多少个0

作者: 海天一树X | 来源:发表于2019-02-10 22:26 被阅读26次

一、思路

一个数末尾的0是由2和5乘出来的,而1到2000里2多得是,主要看1到2000中有多少个5或5的n次方的倍数。
(1)统计5的倍数
2000/5=400,比如5、10、15、20、25等等。这些数,要么直接含了0,要么与2的倍数相乘会得到0,所以共有400个0。
(2)统计25的倍数
2000/25=80,比如25、50、75等等,这些数与4或4的倍数相乘,会得到两个0,但因为上一步中经加过一次0了,所以这里只能加80个0,而不是80 * 2 = 160个0。
(3)统计125的倍数:
2000/125=16,比如125、250、375等等,这些数与8或8的倍数相乘,会得到3个0。但是因为前两步算过两次了,这里只能再加一次。所以会增加16个0,而不是16 * 3 = 48个0。
(4)统计625的倍数
2000/625=3。这三个数分别数是625,1250和1875。这些数与16或16的倍数相乘,会得到4个0。但是前面已经计算过3次了,所以只会增加3个0,而不是3 * 4 = 12个 0。
(5)最后结果:400+80+16+3 = 499

二、编程实现

(一)用C++实现

考虑到2000!的阶乘是个很大的数,C++中的long long型变量存放不下,只能考虑用数组实现。但是数组实现会比较烦琐。若结合上面的数学思路,可以直接写出代码:

#include <iostream>
using namespace std;

int main()
{
    cout << 499 << endl;
    return 0;
}

(二)用Python实现

在Python中,有一种bignum的数据类型,可以存放很大的数。当数很大时,将自动使用bignum类型。

product = 1
count = 0
for i in range(1, 2001):
    product *= i
    
strPro = str(product)

for i in range(len(strPro) - 1, 0, -1):
    if '0' == strPro[i]:
        count += 1
    else:
        break

print(count)

少儿编程答疑、算法答疑请加微信307591841或QQ307591841


诺依曼算法公众号.jpg

相关文章

  • 小朋友学数学(23):求2000!末尾有多少个0

    一、思路 一个数末尾的0是由2和5乘出来的,而1到2000里2多得是,主要看1到2000中有多少个5或5的n次方的...

  • 算法训练4

    题目描述输入一个正整数n,求n!(即阶乘)末尾有多少个0? 比如: n = 10; n! = 3628800,所以...

  • java——末尾0的个数

    【题目描述】输入一个正整数n,求n!(即阶乘)末尾有多少个0? 比如: n =10; n! = 3628800,所...

  • 算法

    N的阶乘末尾有多少个0 http://blog.chinaunix.net/uid/20766194/cid-71...

  • Leetcode.172.Factorial Trailing

    题目 求出n的阶乘末尾有多少个0. 思路 如果强行求解n的阶乘, 时间复杂度太高.求解多少个0, 就需要对10进行...

  • POJ 1401

    POJ 1401 题意 求n!的末位有多少个0; 思路 计算有多少5的因子。

  • 末尾0

    原题出处

  • 算法--求n!末尾的0的个数

    给定一个整数n,求解它的阶乘的乘积里末尾0的个数。举个例子,比如3! = 1 * 2 * 3 = 6,末尾0的个数...

  • lintcode 求n!中末尾0 的个数

    我们只需要考虑哪些数相乘可以得到10即可,因为2*5 = 10,因此我们只需要找到2和5的个数的较小的一个值,因为...

  • 计算阶乘n!末尾所含0的个数

    今天在网上看到这么一个题目,怎么计算阶乘n!末尾有多少个零呢.对于想我这种数学只在初中水平的人来说就只知道阶乘是类...

网友评论

    本文标题:小朋友学数学(23):求2000!末尾有多少个0

    本文链接:https://www.haomeiwen.com/subject/wlxfeqtx.html