首先，这里是原题目：
写一个程序，计算N!以10进制数形式表示的数中最右的非零数字，并找出在它有边又几个零。
（程序应适用于N <= 30000的正整形数）
方案1 ——fail
那么，拿到这个题目，我首先给出了我的第一个程序，由于这个程序很快就被删掉重写，所以这里就不拿出来展示，只简单讲一讲逻辑。
首先，输入N；随后for循环计算N的阶乘；再用while循环从得数的最右边开始，寻找非零数字，并且一边找，一边记录0的个数。
这一程序对于较小的N值而言是没有问题的，比如题目中给出的示例12，由于12的阶乘仅为479001600，所以在程序运行时并不会出现问题。
但一旦N开始变大，变量fac（阶乘结果）就无法储存阶乘后的值了，所以，我开始思考新的解决方法。
方案2——fail
阶乘末尾零的个数是可以通过计算得出的，所以，我可以用这样的方式在程序开头计算出末尾零的个数：
int ..., five = 1;
while(pow(5, five) <= n){
zeros += n / int(pow(5, five));
five++;
}
由于阶乘结果中，5的因子必然比2少，所以这里不需要考虑2，可以直接计算因子5的个数，便能知道末尾零的个数。
随后，知道了末尾0的个数，我们就可以知道我们要求的最末非零数字在倒数第几位了，这样，我们就能够抹掉计算过程中前面的位数，只考虑需要使用的最末几位即可。完整的程序如下：
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n, zeros = 0, fac = 1, five = 1;
cin >> n;
while(pow(5, five) <= n){
zeros += n / int(pow(5, five));
five++;
}
for(int i = 2; i <= n; i++){
fac *= i;
fac = fac % int(pow(10, zeros + 1));
}
cout << fac / pow(10, zeros) << " " << zeros;
return 0;
}
的确，这一程序缩小了fac的值，能够处理更大的N，但是，还不够大。测试表明，即使将fac的类型设为long long，当N超过30，仍会发生溢出。这离题目所要求的N <= 30000还相差太远。
大概估算一下，按照这一程序，计算30000的阶乘，fac需要储存超过7000位的数据，明显不现实。
方案3——success
当时脑子短路，所以把程序放了一下，先去干别的事情。然后，下午查了下教程，看了求n得阶乘得最后一位非零数字 - butterflier这篇blog，虽然没完全搞懂，其中的数组、函数也是现在也不能使用（尽管我会，但是老师没教，所以不能用，我会是因为我自学过，而且有python和swift的基础），不过我还是从中受到了启发。
所以，这最后的一个方案，我会在计算阶乘的过程中，删去阶乘结果中的因子2和5，这样，计算结果末尾的0就会被全部抹掉，所以，我就可以让fac永远仅储存1位的数据，计算30000便毫无问题。
#include<iostream>
using namespace std;
int main(){
int n, zeros = 0, two = 0, fac = 1, si;
cin >> n;
for(int i = 2; i <= n; i++){
// cout << i << " -> ";
si = i;
while(si % 2 == 0){ //首先去掉 i 中所有的2，因为2与5相乘后会在末尾增加零
si /= 2;
two += 1;
// cout << si << " -> ";
}
while(si % 5 == 0){ //去掉 i 中所有的5，由于因子2永远比因子5多，所以在配对的时候可以直接去掉一个2
si /= 5;
two -= 1;
zeros += 1; //与2配对后，末尾就多一个0
// cout << si << " -> ";
}
fac *= si;
fac %= 10; //只需要考虑最末尾的数
// cout << "fac: " << fac << " two: " << two << endl;
}
for(int i = 1; i <= two; i++){ //将未被配对的2乘回结果
fac *= 2;
fac %= 10;
}
cout << fac << " " << zeros;
return 0;
}
这段代码显然比blog中的那段代码要简单很多，但是我并不清楚哪段的运行效率更高，反正不管怎么说，这道题目已经完成了。
将调试代码前的//去掉，你就能够看到程序运算的全过程。拿26举例：
26
2 -> 1 -> fac: 1 two: 1
3 -> fac: 3 two: 1
4 -> 2 -> 1 -> fac: 3 two: 3
5 -> 1 -> fac: 3 two: 2
6 -> 3 -> fac: 9 two: 3
7 -> fac: 3 two: 3
8 -> 4 -> 2 -> 1 -> fac: 3 two: 6
9 -> fac: 7 two: 6
10 -> 5 -> 1 -> fac: 7 two: 6
11 -> fac: 7 two: 6
12 -> 6 -> 3 -> fac: 1 two: 8
13 -> fac: 3 two: 8
14 -> 7 -> fac: 1 two: 9
15 -> 3 -> fac: 3 two: 8
16 -> 8 -> 4 -> 2 -> 1 -> fac: 3 two: 12
17 -> fac: 1 two: 12
18 -> 9 -> fac: 9 two: 13
19 -> fac: 1 two: 13
20 -> 10 -> 5 -> 1 -> fac: 1 two: 14
21 -> fac: 1 two: 14
22 -> 11 -> fac: 1 two: 15
23 -> fac: 3 two: 15
24 -> 12 -> 6 -> 3 -> fac: 9 two: 18
25 -> 5 -> 1 -> fac: 9 two: 16
26 -> 13 -> fac: 7 two: 17
4 6
其实说句实话，这道题目难吗？也还好，离信息学竞赛还远得很。经过这一番摸索，我得出了一个结论——我好菜[doge]。
最近真的忙死了，同学也在催着改程序，我都没时间搞，GitHub一片白色……这是部分聊天记录（惨~）：
聊天记录
网友评论