为什么我的代码不能用于测试输入？ - 项目欧拉549

此问题，可以发现here和如下：为什么我的代码不能用于测试输入？ - 项目欧拉549

的最小数目m，使得10将米！是m = 5。

最小的数m如25分m！是m = 10。设s（n）为最小的数m，使n除以m !.

因此s（10）= 5和s（25）= 10。

设S（n）为Σs（i），2≤i≤n。

S（100）= 2012。

找到S（10⁸）。

这是我的代码，你可以看到，它是一个完全蛮力的解决方案，它似乎在几分钟内运行10 ** 8，除此之外，s（10）= 5和S（25）= 10（根据我的程序），因为这个问题说，除了这个，我也产生了一些随机数，并检查了他们：

def is_int(x): return int(x) == x 

factorials = [1] 
for i in range(1, 25): 
    factorials.append(factorials[-1] * i) 

def s(n): 
    i = 2 
    while not is_int(factorials[i]/n): i += 1 
    return i 

def S(x): 
    S = 0 

    for n in range(2, x + 1): 
     if n % 10 ** 5 == 0: print("{0}% done!".format(n/x * 100)) 
     S += s(n) 

    return S

我已经检查了预先计算阶乘值，他们是正确的。

的输出S（100）是1221，当它应该是2012年，这里有我的价值观为S（N）：

s(2) = 2 
s(3) = 3 
s(4) = 4 
s(5) = 5 
s(6) = 3 
s(7) = 7 
s(8) = 4 
s(9) = 6 
s(10) = 5 
s(11) = 11 
s(12) = 4 
s(13) = 13 
s(14) = 7 
s(15) = 5 
s(16) = 6 
s(17) = 17 
s(18) = 6 
s(19) = 19 
s(20) = 5 
s(21) = 7 
s(22) = 11 
s(23) = 19 
s(24) = 4 
s(25) = 10 
s(26) = 13 
s(27) = 9 
s(28) = 7 
s(29) = 20 
s(30) = 5 
s(31) = 19 
s(32) = 8 
s(33) = 11 
s(34) = 17 
s(35) = 7 
s(36) = 6 
s(37) = 19 
s(38) = 19 
s(39) = 13 
s(40) = 5 
s(41) = 20 
s(42) = 7 
s(43) = 20 
s(44) = 11 
s(45) = 6 
s(46) = 19 
s(47) = 19 
s(48) = 6 
s(49) = 14 
s(50) = 10 
s(51) = 17 
s(52) = 13 
s(53) = 19 
s(54) = 9 
s(55) = 11 
s(56) = 7 
s(57) = 19 
s(58) = 20 
s(59) = 20 
s(60) = 5 
s(61) = 20 
s(62) = 20 
s(63) = 7 
s(64) = 8 
s(65) = 13 
s(66) = 11 
s(67) = 20 
s(68) = 17 
s(69) = 20 
s(70) = 7 
s(71) = 19 
s(72) = 6 
s(73) = 20 
s(74) = 20 
s(75) = 10 
s(76) = 19 
s(77) = 11 
s(78) = 13 
s(79) = 19 
s(80) = 6 
s(81) = 9 
s(82) = 20 
s(83) = 19 
s(84) = 7 
s(85) = 17 
s(86) = 20 
s(87) = 20 
s(88) = 11 
s(89) = 20 
s(90) = 6 
s(91) = 13 
s(92) = 19 
s(93) = 20 
s(94) = 19 
s(95) = 19 
s(96) = 8 
s(97) = 20 
s(98) = 14 
s(99) = 11 
s(100) = 10

可以请你说为什么代码不能正常工作？

来源

2017-07-15 Karan Elangovan

蟒蛇2或Python 3？ python 2将需要投入浮动。 –

它很可能这个功能是所有问题的根源：

def is_int(x): 
    return int(x) == x

如果你尝试检查一个数是否是另一个数整除，这是不是做到这一点的最好办法。特别是对于更高阶的数字，浮点数表示倾向于冒险。只需使用%运营商，像这样：

def s(n): 
    i = 2 
    while factorials[i] % n: 
     i += 1 
    return i

另外，如果你想S（100），你可能要一路存储阶乘到100！太？

factorials = [1] 
for i in range(1, 101): # note this 
    factorials.append(factorials[-1] * i)

现在：

In[]: 
S(100) 

Out[]: 
2012

来源

2017-07-15 19:50:58

当使用错误代码时，s（n）总是<= 24，对于n <= 10 ** 8，所以我只计算为24，但现在s（n）函数实际工作，我需要计算一路达到100！ –

您的比较函数def is_int(x): return int(x) == x会遇到浮点精度有限的问题。

for i in range(1,100): 
    fraction = 10**i/(10**i-1) 
    if fraction == int(fraction): 
     print(i) 
     break

返回16。

你的计算将是安全的，如果不是检查浮点值和整数之间的平等

while not is_int(factorials[i]/n): 
    i += 1

你检查，如果模数为0，从而factorials[i]可以通过n可分为：

while not (factorials[i] % n == 0): 
    i += 1

然后，在增加计算阶乘的数量后，根据需要S(100)返回2012。

编辑： while not (factorials[i] % n == 0):可以利用0的故障，因此缩短为while factorials[i] % n: COLDSPEED指出。

来源

2017-07-15 19:49:27

为什么我的代码不能用于测试输入？ - 项目欧拉549

回答

相关问题