题目:求1×2×3×…×n所得数的末尾有多少个0?n由键盘输入,且1000<n<10000。
答:思路1:考虑末尾0的来源。阶乘结果末尾的零是由于因数10的存在,10分解质因数:2×5。在阶乘的计算中,偶数(含有因数2)的出现频率显然高于5的倍数的出现频率。因此,我们只需要关注5,每遇到一个5,就能找到一个2与之配对。1~n个数中,每隔5,出现一个质因数含5的数,即n/5(需要向下取整)个,分别是5,10,15,20,25,30,35,40,45,50,55,…。这n/5个数中,例如25、50、75中不止一个5,有两个5,也是每隔5出现一个,共有(n/5)÷5个……所以,使用层除法可以得到所有的5。
具体代码:
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int sum=n/5,temp=n/5;
while(temp>0){
temp=temp/5;
sum+=temp;
}
cout<<n<<"!的末尾有 "<<sum<<" 个0"<<endl;
}
思路2:用一个一维数组a存放阶乘值,将阶乘值的个位数存放于数组的最后一个元素a[N]中,十位数放在a[N-1]中,最高位放在a[1]中。初始值应该为1,即a[N]=1,a[1..N-1]=0。通过以下方式实现高精度数的累乘a[]=a[]*k:
void ak(int a[],int k){
int carry=0,x;
for(int i=N;i>=1;i--){
x=a[i]*k+carry;
carry=x/10;
a[i]=x%10;
}
}
具体代码:
#include<iostream>
using namespace std;
const int N=200000;
int a[N+1];
void ak(int a[],int k){
int carry=0,x;
for(int i=N;i>=1;i--){
x=a[i]*k+carry;
carry=x/10;
a[i]=x%10;
}
}
int main(){
int n;
cin>>n;
a[N]=1;
//计算阶乘
for(int k=1;k<=n;k++){
ak(a,k);
}
int j=1;
for(int i=N;i>=1;i--){
if(a[j]!=0) break;
j++;
}
cout<<n<<"!=";
for(int i=j;i<=N;i++){
cout<<a[i];
}
cout<<endl;
int i=N;
while(a[i]==0){
i--;
}
cout<<n<<"的阶乘末尾有 "<<N-i<<" 个0"<<endl;
return 0;
}
也可以逆序存a[]=a[]*k求大数阶乘:
#include<iostream>
using namespace std;
const int N=1e5;
int a[N+5];
void ak(int a[],int k){
int x,carry=0;
for(int i=1;i<=N;i++){
x=a[i]*k+carry;
carry=x/10;
a[i]=x%10;
}
}
int main(){
int n;
cin>>n;
a[1]=1;
for(int i=1;i<=n;i++){
ak(a,i);
}
int j=N;
while(a[j]==0){
j--;
}
for(int i=j;i>=1;i--){
cout<<a[i];
}
return 0;
}