你的分享就是我们的动力 ---﹥

百姓网的一个笔试题

时间:2013-06-07 15:28来源:www.chengxuyuans.com 点击:

最近做了百姓网的一个笔试题,题目是求n! 末尾0的个数;

个数 n 的阶乘末尾有多少个 0 取决于从 1 到 n 的各个数的因子中 2 和 5 的个数, 而 2 的个数是远远多余 5 的个数的, 因此求出 5 的个数即可. 题解中给出的求解因子 5 的个数的方法是用 n 不断除以 5, 直到结果为 0, 然后把中间得到的结果累加. 例如, 100/5 = 20, 20/5 = 4, 4/5 = 0, 则 1 到 100 中因子 5 的个数为 (20 + 4 + 0) = 24 个, 即 100 的阶乘末尾有 24 个 0. 其实不断除以 5, 是因为每间隔 5 个数有一个数可以被 5 整除, 然后在这些可被 5 整除的数中, 每间隔 5 个数又有一个可以被 25 整除, 故要再除一次, ... 直到结果为 0, 表示没有能继续被 5 整除的数了.

我的代码是:

#include<iostream>
using namespace std;


//合法性判断函数/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool Check(float k)
{
if((k-(int)k)<-0.000001|| (k-(int)k)>0.00001)
{
cout<<"必须输入整数"<<endl;
return 0;
}
if(k<=0)
{
cout<<"输入的数字必须为正数"<<endl;
return 0;
}
return 1;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//求正整数n中因子5的个数函数
int Count_zero(float n)
{
int temp = 1;
int count = 0;
while(0 != temp)
{
temp = n/5;
count += temp;
n = temp;
}
/*int count = 0;
for(int i=5;i<=n;i=i*5)
{
count += n/i;
cout<<count<<endl;
}*/
return count;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main(void)
{
float n = 0;//要输入的数n
int num = 0;//n!末尾0的个数
do{
cout<<"请输入n"<<endl;
cin>>n;
}
while( 1 != Check(n) );//判断输入数字n的合法性
num = Count_zero(n);//求n!末尾0的个数
cout<<n<<"!末尾的0的个数是:"<<num<<endl;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

  这样做的结果当然是死翘翘啦!我回email问我那里没有做好,得到这样的回复:您的程序虽然正确的完成了功能,但是您在程序的细节处理上过于粗糙(关键代码如上粗线);这样我当然不服啦,我就上网找,看到一个比较好的算法关键代码如下:

        1. intnumOfZero(intn)
        2. {
        3. intnum=0,i;
        4. for(i=5;i<=n;i*=5)
        5. {
        6. num+=n/i;
        7. }
        8. returnnum;
        9. }
        10. 这个算法是用i=5,25,125,625……这样的5的n次方来作为循环条件,这样效率确实比我的高。而且我想应该这也是效率最高的算法吧!!
        11. 替换回去,得到如蓝色标记的代码。

        总结:现在很多笔试题都是在《编程之美》上面的题,找工作前此书必看。再推荐一本书就是《C++高质量编程》。。。

转载注明地址:http://www.chengxuyuans.com/job_interview/64110.html