Ubuntu中文论坛

发表于： **2009-07-18 19:09**

阶乘问题
问题描述：
从输入文件中读取一个数n，求出n！中末尾0的个数。
输入：
输入有若干行。每一行上有一个整数m，指明接下来的数字的个数。然后是m行，每一行包含一个确定的正整数n，1£n£1000000000。
输出：
对输入行中的每一个数据n，输出一行，其内容是n！中末尾0的个数。
输入样例：
3
3
100
1024

输出样例：
0
24
253

下面是我写的程序

#include<iostream>
using namespace std;
int main()
{
int m;
cin>>m;
int *x=new int[m];
for(int i=0;i<m;i++)
{
cin>>x;
}
for(int j=0;j<m;j++)
{
int temp=x[j];
int sum=0;
for(int n=x[j]-1;n>=0;n--)
{
while(temp%10==0)
{
sum++;
temp/=10;
}
temp%=10;
temp*=n;
}
cout<<sum<<endl;
}
delete []x;
return 0;
}

算出来的结果跟样例不一样，我的算法哪里出错了么

发表于： **2009-07-18 21:02**

你的阶乘运算在哪？

发表于： **2009-07-18 21:02**

#include<iostream>
using namespace std;
int main()
{
int m;
cin>>m;
int *x=new int[m];
for(int i=0;i<m;i++)
{
cin>>x;
}
for(int j=0;j<m;j++)
{
int temp=x[j];
int sum=0;
for(int n=x[j]-1;n>=0;n--)
{
while(temp%10==0)
{
sum++;
temp/=10;
}
temp%=10;
temp*=n;
}
cout<<sum<<endl;
}
delete []x;
return 0;
}

这句有问题！
比如说你的temp此处为25的奇数倍，它乘以4的倍数，至少有2个零；你对10取模，再乘以4的倍数，0的个数就少了

发表于： **2009-07-19 8:57**

对啊
楼上说的有道理，谢谢
我再把程序改改

发表于： **2009-07-19 14:45**

其实就是统计因子5的个数
因为2比5多，所以有一个5，必然产生一个0，有一个0，必然是因为一个2和一个5的结果。

从1到n,可以先计算 n/5,那些5的倍数的数，都变成原来的1/5
举个例子 1到100，全体除以5，去掉不能整除的得到 1,2,3,4....,20
这就转变为 f(n) = n/5 + f(n/5)

这样就可以了

代码：全选

    int total=0;
    while (n) {
        total += n/=5;
    }

发表于： **2009-07-19 15:32**

精辟
看来我还是得多想想

发表于： **2009-07-19 15:47**

我将我的程序完全重写了一下，提交到了我学校的判题系统上，通过了

代码：全选

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int *x=new int[n];
	for(int i=0;i<n;i++)
		cin>>x[i];
	for(int i=0;i<n;i++)
	{
		int sum=0;
		for(int j=x[i];j>0;j--)
		{
			int temp=j;
			while(temp%5==0&&temp>0)
			{
				sum++;
				temp/=5;
			}
		}
		cout<<sum<<endl;
	}
	delete []x;
	return 0;
}

我觉得这种思路很好，还要好好学习

Ubuntu中文论坛

从输入文件中读取一个数n，求出n！中末尾0的个数。C++

从输入文件中读取一个数n，求出n！中末尾0的个数。C++

Re: 从输入文件中读取一个数n，求出n！中末尾0的个数。C++

Re: 从输入文件中读取一个数n，求出n！中末尾0的个数。C++

Re: 从输入文件中读取一个数n，求出n！中末尾0的个数。C++

Re: 从输入文件中读取一个数n，求出n！中末尾0的个数。C++

Re: 从输入文件中读取一个数n，求出n！中末尾0的个数。C++

Re: 从输入文件中读取一个数n，求出n！中末尾0的个数。C++