我试着从www.spoj.com:FCTRL - Factorial解决这个习题
你真的不必读它,如果你好奇的话就go 读:)
首先,我在C++中实现了它(以下是我的解决方案):
#include <iostream>
using namespace std;
int main() {
unsigned int num_of_inputs;
unsigned int fact_num;
unsigned int num_of_trailing_zeros;
std::ios_base::sync_with_stdio(false); // turn off synchronization with the C library’s stdio buffers (from https://stackoverflow.com/a/22225421/5218277)
cin >> num_of_inputs;
while (num_of_inputs--)
{
cin >> fact_num;
num_of_trailing_zeros = 0;
for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
num_of_trailing_zeros += fact_num/fives;
cout << num_of_trailing_zeros << "\n";
}
return 0;
}
我上传了它作为g++ 5.1的解决方案
结果是:Time0.18Mem3.3M
但后来我看到一些 comments ,声称他们的执行时间小于0.1.因为我想不出更快的算法,所以我try 在C中实现相同的代码:
#include <stdio.h>
int main() {
unsigned int num_of_inputs;
unsigned int fact_num;
unsigned int num_of_trailing_zeros;
scanf("%d", &num_of_inputs);
while (num_of_inputs--)
{
scanf("%d", &fact_num);
num_of_trailing_zeros = 0;
for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
num_of_trailing_zeros += fact_num/fives;
printf("%d", num_of_trailing_zeros);
printf("%s","\n");
}
return 0;
}
我上传了它作为gcc 5.1的解决方案
现在代码是almost the same,我按照建议的here将std::ios_base::sync_with_stdio(false);
添加到C++代码中,以关闭与C库的Stdio缓冲区的同步.我还将printf("%d\n", num_of_trailing_zeros);
分成printf("%d", num_of_trailing_zeros); printf("%s","\n");
,以补偿cout << num_of_trailing_zeros << "\n";
中operator<<
的双重调用.
但是我仍然看到C和C++代码中内存使用率低x9 better performance.
为什么?
EDIT
我在C代码中将unsigned long
改为unsigned int
.它应该是unsigned int
,上面显示的结果与新(unsigned int
)版本相关.