欧拉计划34题求助 [Python]

Question

问题是：

145是一个奇特的数字，因为1！+ 4！+ 5！= 1 + 24 + 120 = 145。

找出所有等于其各位数字的阶乘之和的数字的总和。

注意：由于1！= 1和2！= 2不是和，因此它们不包括在内。

# Project Euler Problem 34
def factorial(num):
    """Factorial"""
    product = num
    for i in range(2, num):
        product *= i
    return product

def check_sum(number):
    list_digits = list(str(number))
    check_sum = 0
    for digit in list_digits:
        check_sum += factorial(int(digit))
    if check_sum == number:
        return True

def find_final_sum():
    """Find the sum of all the numbers."""
    final_list = []
    final_sum = 0
    counter = 3
    while counter < 200000:
        if check_sum(counter):
            final_list.append(counter)
            counter += 1
        else:
            counter += 1

    for j in final_list:
        final_sum += j
    print(final_sum)

find_final_sum()

我定义了一个函数来找阶乘。 然后我定义了一个函数来检查一个数字是否等于其各位数字的阶乘之和。 最后，我检查从3到200000的数字。如果一个数字符合条件，我就把它放进一个列表里。 最后，我对列表求和并打印出来。

这段代码只给我145作为答案。我不知道我做错了什么，有人可以帮忙吗？

我不是要发布Euler问题的解决方案。

- RandomCoder

---

你有一个变量和一个函数的名称相同（final_sum）。 - lakshayg

有限的好奇数。请参见 阶乘数字：上界。 - Peter Wood

Project Euler 的要点是不使用暴力方法。 - Peter Wood

请注意：a）您可以制表计算阶乘（将0-9的阶乘计算为数字-> int的列表或甚至字典），b）如果检查和大于数字，则提前退出“ if check_sum> number”，c） “ return check_sum == number” ；d）使用“ for counter in range（3，200000）”。 - Antti Haapala -- Слава Україні

Answer 1

你的阶乘函数有误，因为它错误地计算 0! 为 0。你可以这样修复它：

def factorial(num):
    """Factorial"""
    if num < 2:
        return 1
    ...

如果你的代码是正确的，它将会打印出40730。

附注：在你所选范围内唯一其他的奇特数字是40585。

- Selcuk

---

非常感谢！所以我只需要检查到50000左右的数字吗？ - RandomCoder

他也可以使用 math.factorial()。 - Reti43

我完全不了解欧拉计划；你被禁止使用内置方法吗？此外，可能存在超过200,000的其他好奇数字。 - Selcuk

@Reti43 我不知道有一个 math.factorial() 函数。我现在会尝试一下。 - RandomCoder

我没有看到任何这样的限制。事实上，我看到很多人选择语言是因为它们内置的功能，例如Python的任意整数精度。为了澄清我的评论，这只是在解释他的错误之上的另一个建议。重新发明轮子是学习算法的好方法，以及可能犯的常见错误，例如OP所犯的错误。 - Reti43

Answer 2

您不应该在函数和变量中使用相同的名称。但这并不是问题所在。问题出在阶乘函数上。

import math

def check_sum(number):
    list_digits = list(str(number))
    check_sum = sum([math.factorial(int(digit)) for digit in list_digits])
    return check_sum == number

def final_sum(counter_min=3, counter_max=200000):
    """Find the sum of all the numbers."""
    final_sum = 0
    for counter in xrange(counter_min, counter_max):
        if check_sum(counter):
             final_sum += counter
    return final_sum

if __name__ == '__main__':
    print(final_sum())

- qvpham

---

是的，我刚用math.factorial()尝试了一下。我的原始阶乘函数不能正确计算0!。 - RandomCoder

xrange()是Python2的函数吗？我使用的是Python3。 - RandomCoder

Python3没有xrange()。在Python3中，您可以使用range()。 - qvpham

Answer 3

你的代码检查了145、154、415、451、514和541。这意味着你计算了相同的阶乘和6次。随着位数的增加，这种重复会增加。尝试仅计算唯一的数字组合，并测试是否以任何顺序包含这些数字的总和。

import math
def compare_digits( val, arr, nesting_depth ):
  digits = [int(d) for d in str(val)]
  digits.sort()
  return arr[0:sz] == digits

f = [math.factorial(i) for i in range(10)]
idx = [ 0,0,0,0,0,0,0 ]
for idx[0] in range(10):
  for idx[1] in range(idx[0], 10):
    sum = f[idx[0]] + f[idx[1]]
    if compare_digits( sum, idx, 2 ):
      total += sum
    for idx[2] in range(idx[1], 10):
      sum = f[idx[0]] + f[idx[1]] + f[idx[2]]
      if compare_digits( sum, idx, 3 ):
        total += sum
      # for idx[3] etc.

请注意，数组 idx 总是按循环嵌套深度排序。

- Justin Finnerty