判断N!阶乘中末尾0的个数

如果我们要判断出0的个数,如果我们直接求N!那么数据会很大,数据可能溢出

那么为了得到0的个数我们知道可以从10的角度进行判断,如果我们知道N!中10的个数

我们就可以判断出0的个数,


如果N!=K*10^n,K是不能被10整除的数,那么我们可以根据n就可以得到0的个数,

考虑10的个数,我们必须对N!进行质因数的分解,N!=(2^x)*(3^y)(5^z)………..,由于2*5=10,

所以n只与x和z相关,

于是n=min(x,z),我们可以判断出x的个数必然大于z的个数,因为被2整除的数的频率大于被5整除的数的频率高,

所以n=z;


下面我们要判断出N1中5的个数,

因为N!=N*N-1*N-2*N-3…………………………………

所以我们要判断出5的个数,我们可以对每个N,N-1,N-2,进行判断,就可以得到5的个数了

判断5的个数代码:

[cpp] 
view plain  
copy

  1. <span style=“font-size:18px;”>#include<iostream>  
  2. using namespace std;  
  3.   
  4. int main()  
  5. {  
  6.     int a = 100;  
  7.     int num = 0;  
  8.     for (int i = 1; i <= a; i++)  
  9.     {  
  10.         int j = i;  
  11.         while (j % 5 == 0)  
  12.         {  
  13.             num++;  
  14.             j = j / 5;  
  15.         }  
  16.     }  
  17.     cout << num << endl;  
  18.     system(“pause”);  
  19.     return 0;  
  20. }</span>  


我们还可以用另一种方法进行5的个数进行求解:

z=N/5+N/25+N/5^3+………………..

知道N/5^k为0;

代码:

[cpp] 
view plain  
copy

  1. <span style=“font-size:18px;”>#include<iostream>  
  2. using namespace std;  
  3.   
  4. int main()  
  5. {  
  6.     int a = 100;  
  7.     int num = 0;  
  8.     while (a)  
  9.     {  
  10.         num += a / 5;  
  11.         a = a / 5;  
  12.     }  
  13.     cout << num << endl;  
  14.     system(“pause”);  
  15.     return 0;  
  16. }</span>  


    原文作者:momo_mo520
    原文地址: https://blog.csdn.net/momo_mo520/article/details/80535190
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞