求階乘的第一個非零數字
Problem statement:
問題陳述：
Find the number of trailing zeros in n! (Where, n is the given input).
在n中找到尾隨零的數目！ (其中， n是給定的輸入)。
Solution:
解：
Computing a factorial is of course expansive. Though using dynamic programming the computing expanse can be managed, for the large value of n, the factorial value is going exceed normal data size. Needless to say, computing the whole factorial is not the way to find the number of trailing zeros. There must be some advanced algorithm to find the no of trailing zeros.
計算階乘當然是可擴展的。 盡管使用動態編程可以管理計算范圍，但是對于較大的n值，階乘值將超過正常數據大小。 不用說，計算整個階乘不是找到尾隨零的數量的方法 。 必須有一些高級算法來找到尾隨零 。
Firstly, we need to understand what causes trailing zeroes. A pair of 2 & 5 is the reason behind a trailing zero. Thus a pair of 2 & 5 in the factorial expression leads to a trailing zero. Thus we simply need to check how many pairs (different) of 2 & 5 are there.
首先，我們需要了解導致尾隨零的原因。 一對2和5是尾隨零后面的原因。 因此，階乘表達式中的2和5對導致尾隨零。 因此，我們只需要檢查2和5有多少對(不同)。
Let's say 5!
5!= 5*4*3*2*1 (thus only one pair)
5!=120 ( only one trailing zero)
假設5！
5！= 5 * 4 * 3 * 2 * 1 (因此只有一對)
5！= 120 (僅一個尾隨零)
Intuition says that we don’t even need to find the number of pairs as the occurrence of 2 as a factor is obvious if a 5 is present as a factor. Thus we only need to check how many 5 is there as a factor in the factorial.
直覺說，我們甚至不需要找到對的數量，因為如果5作為一個因素，則2作為一個因素的出現就很明顯。 因此，我們僅需要檢查階乘中有5個因素。
Algorithm:
算法：
Set count to 0
For(i=5;n/i>0;i=i*5)
count=count+ n/i;
Return count
C ++代碼查找數字階乘中的尾隨零 (C++ code to find trailing zeros in factorial of a number)
#include<bits/stdc++.h>
using namespace std;
int trailingZeros(int n){
int count=0;
if(n<0)
return -1;
for(int i=5;n/i>0;i*=5){
count+=n/i;
}
return count;
}
int main(){
int n;
cout<<"enter input,n"<<endl;
cin>>n;
if(trailingZeros(n))
cout<<"no of trailing zero in "<<n<<"! is "<<trailingZeros(n)<<endl;
else
cout<<"input is negative, can't proceed"<<endl;
return 0;
}
Output
輸出量
First run:
enter input,n
15
no of trailing zero in 15! is 3
Second run:
enter input,n
100
no of trailing zero in 100! is 24
翻譯自: https://www.includehelp.com/algorithms/find-trailing-zeros-in-factorial-of-a-number.aspx
求階乘的第一個非零數字
