亲宝软件园·资讯

展开

C++实现求N!中末尾0的个数 用C++实现求N!中末尾0的个数的方法详解

神楽桜 人气:0

题目描述:

输入一个正整数n,求n!(即阶乘)末尾有多少个0? 比如: n = 10; n! = 3628800,所以答案为2

输入描述:

输入为1行,n(1≤n≤1000)

输出描述:

输出一个整数

样例:

输入:10

输出:2

看到这个题,常规思路就是先把阶乘算出来,再用算出来的结果求余,余数为0则个数加1,代码如下:

#include<iostream>
using namespace std;
int main(void)
{
 int n, m = 1;
 cin >> n;
 for (int i = n; i > 0; i--)
 {
  m = m * i;
 }
 int sum = 0;
 int t;
 for (int i = 0; m > 0; i++)
 {
  t = m % 10;
  m = m / 10;
  if (t != 0) //要是0前面的数字不是0,则直接结束
  {
   cout << sum;
   return 0;
  }
  else
  {
   sum++;
  }
 }
 return 0;
}

注意一点,就是题目要求是算出末尾的0的个数,而不是整个数字中有多少0,所以要注意当余数不是0的时候就要结束代码。

但是这样做其实是不对的,因为我们注意到题目的输入描述为n(1≤n≤1000),也就是说当n很大的时候,就会越界,超出int表示的范围。所以也就不能用这种方法进行求解。

正确思路:我们先看一下末尾的0是怎么来的:末尾有0,就说明这个数可以被10整除,而再对10进行因数分解,不难看出10=5*2,而5乘以任何一个偶数,所得结果都会被10整除,所以问题就转化为这个阶乘里面含有多少个能被5整除的数字。当然还要注意一点,那就是25,125,625这三个数字,25本质上是2个5(平方),125本质上是3个5(立方),625本质上是4个5(4次方),所以在算到这些数字的时候要把他们本身含有的多的5算进去。

代码如下:

#include<iostream>
using namespace std;
int main(void)
{
 int n,sum=0;
 cin>>n;
 while(n)
 {
  sum=sum+n/5;
  n=n/5;
 }
 cout<<sum;
 return 0;
}

加载全部内容

相关教程
猜你喜欢
用户评论