首页 > 代码库 > 不要被阶乘吓倒

不要被阶乘吓倒

2024-07-02 14:23:04   223人阅读

阶乘是个很有意思的函数，我们来看看两个跟阶乘相关的问题。
1、给定一个整数N，那么N的阶乘N!末尾有多少个0呢？例如：N=10，N! = 3628800，末尾就有两个0
2、求N! 的二进制表示中最低位1的位置
 
我们先分析第一个问题
我们发现0的个数，就是10的个数，而10是由2跟5组成的，但是，5的个数明显少于2，所以问题就转换为求5的个数。
 1 #include <iostream>
 2 using namespace std;
 3 // O(nlogn)，思路：找0的个数，就是找10的个数，就是2*5的个数，2比5多，所以就是找5的个数，首先找到5的倍数，再判断这些数里面有多少个5
 4 int numOfZeros1(int n)
 5 {
 6     //i从1开始，当n为26时，那么i就是1,2,3,4,5
 7     //j就是5*i，所以对于的j就是5,10,15,20,25，第二个while循环找的就是j中有多少个5，像数字25，就有2个5
 8     //count表示的5的个数，即0的个数
 9     int i, j, count;
10     i = 1;
11     count = 0;
12     while (5 * i <= n)
13     {
14         j = 5 * i;
15         while (j % 5 == 0)
16         {
17             count++;
18             j = j / 5;
19         }
20         i++;
21     }
22     return count;
23 }
24 // o(logn)，从时间复杂度上来说，优化的多。思路：n=26时，0的个数就是[26/25]+[26/5]=1+5=6
25 int numOfZeros2(int n)
26 {
27     int i, count;
28     i = 0;
29     count = 0;
30     while (n / 5)
31     {
32         count += n / 5;
33         n /= 5;
34     }
35     return count;
36 }
37 int main()
38 {
39     int n;
40     n = 125;
41     //test
42     cout<<numOfZeros1(n)<<endl;
43     cout<<numOfZeros1(n)<<endl;
44     system("pause");
45     return 0;
46 }

 


联系
我们