项目欧拉 - 问题160

对于任何N，令f（N）是最后五个数字在 N！中的尾随零之前。例如，项目欧拉 - 问题160
9! = 362880 so f(9)=36288 
10! = 3628800 so f(10)=36288 
20! = 2432902008176640000 so f(20)=17664 
查找F（1,000,000,000,000）

我已经成功地解决了这个问题，对于给定的例子，我的功能能够正确地找到F（9），F（10）等。然而，它与更大的数字斗争，特别是问题要求的数量 - f（10^12）。

我当前优化如下：我除去从乘法器和总和尾随零，并缩短每个相乘后的总和5个位数。在Python代码如下：

def SFTR (n): 
sum, a = 1, 2 
while a < n+1: 
    mul = int(re.sub("0+$","",str(a))) 
    sum *= mul 
    sum = int(re.sub("0+$","",str(sum))[-5:]) 
    a += 1 
return sum

谁能告诉我为什么这个功能缩放从而在很大程度上，为什么它这么久。此外，如果任何人都可以提示我正确的方向来优化我的算法。（一般主题的名称就足够了）谢谢。

更新：

我已经做了一些优化的变化，这是显著快，但它仍然是速度不够快F（10^12）。任何人都可以告诉我什么让我的代码变慢或如何让它变得更快？

def SFTR (n): 
    sum, a = 1, 2 
    while a < n+1: 
     mul = a 

     while(mul % 10 == 0): mul = mul/10 
     mul = mul % 100000 

     sum *= mul 

     while(sum % 10 == 0): sum = sum/10 
     sum = sum % 100000 

     a += 1 
    return sum

来源

2010-06-29 Khaled

10^12是一个很大的数字。在普通电脑上，你不能在一分钟内完成10^12的操作。 – starblue 2010-06-29 20:02:29

mul可以得到非常大的。这是必要的吗？如果我问你要计算的1278348572934847283948561278387487189900038 * 38758 最后5非零数字用手，到底有多少位数字的第一个数字你真的需要知道什么？

来源

2010-06-29 12:42:53 unutbu

非常好的提示问题的本质。 – 2010-06-29 12:52:11

它的最后五位数字（所以它的38 * 38758）。感谢您的帮助。 – Khaled 2010-06-29 13:01:21

@Khaled：小心！这有点复杂。考虑“112125 * 38758”=“74075”与“212125 * 38758”=“54075”。 – unutbu 2010-06-29 13:17:45

大厦字符串经常是昂贵的。截断到最后五位数字时，我宁愿使用模运算符。

python -m timeit 'x = str(111111111111111111111111111111111)[-5:]' 
1000000 loops, best of 3: 1.09 usec per loop 
python -m timeit 'x = 111111111111111111111111111111111 % 100000' 
1000000 loops, best of 3: 0.277 usec per loop

这同样适用于剥离尾随零。应该有一个更有效的方法来做到这一点，你可能不需要每一步都做到这一点。

我没有检查你的算法的正确性，但是，它只是一个优化的提示。

来源

2010-06-29 12:28:12

假设INT（应用re.sub（ “0 + $”， “”，STR（A）））可以用一段时间（一个10％== 0）被替换为：A = A/10然后 – Robus 2010-06-29 12:31:43

@Robus：是的，事像那样。 – 2010-06-29 12:34:10

事实上，你甚至可能会注意到，目前只有有限的一组可能的拖尾非零数字。如果我没有记错，只有几千个可能的非零数字组合，当你只看最后5位数字时。例如，有可能最后的非零数字是奇数吗？（忽略0！和1的特殊情况！）

来源

2010-06-29 15:02:18

项目欧拉 - 问题160

回答

相关问题