算法篇 —— 末尾0的个数

题目描述

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

输入描述:

输入为一行，n(1 ≤ n ≤ 1000)

输出描述:

输出一个整数,即题目所求

解题思路

1.第一种方法是直接将 n！ 求出来，然后查看末尾有几个0 ，此方法思路简单，但是不能称之为一个最优的解决方案！

需要用到大数相乘，在此不做过多讲述

2.第二种方法

.第二种方法

.第二种方法（重要的事情说三遍）

首先我们要思考，“0”是怎么产生的，经过本人三天三夜的思考发现，所有的"0"都是“5”与偶数相乘得到的，也就是说0~n有多少个5，末尾就会产生多少个0。但是有小伙伴就会说了，如果n<5，有0个“5”，n>5,有1个“5”。

如果真的是这样，那么这篇文章将毫无意义…

例如10=5X2 那么在10就可以用5X2来代替，也就是说“10”相当于1个“5”

“25=5X5”相当于2个“5”

“100 = 5X5X4”，相当于2个“5”

所以此题就会变成求出0~n之间有多少个5的问题

代码如下：

#include <iostream>

using namespace std;

int main()
{
	int n, i,sum =0;
	cin>>n;

	for(; n>0 ; n--)
	{
		i = n;
		while(1)
		{
			if(i%5 == 0)
			{
				sum++;
				i = i/5;
			}
			else
				break;
		}
	}
	cout << sum << endl;


	return 0;
}