4

我正在为编程练习做一个Project Euler问题，以便自学。我非常清楚如何以数学方式解决问题，以及如何以编程方式解决问题。

但是，我必须想出一些疯狂的代码才能做到这一点；100 个嵌套循环和 Python 在 100 个缩进级别上有趣地引发了这个错误，而且可能是正确的：

IndentationError: too many levels of indentation



tally = 0
ceiling = 100
for integer_1 in range(0, 100, 1):
    for integer_2 in range(0, 100 - integer_1, 2):
        for integer_3 in range(0, 100 - integer_1 - integer_2, 3):
            for integer_4 ....
                for integer_5 ....
                    etc.
                        etc.
                            all the way to integer_100

我已经通过谷歌寻找解决方案，但这个问题非常罕见，几乎没有关于该主题的文献，我只能找到另一个堆栈溢出问题（Python IndentationError: too many levels of indentation），我找不到太多有用的我的问题。

我的问题是 - 有没有办法采用我的解决方案并找到一些解决方法或以一种可行的方式对其进行重构？我真的很难过。

编辑：

感谢 nneonneo 的回答，我能够解决这个问题。我的代码在这里仅供寻找正确重构代码的方法的人们将来参考。

from time import time
t = time()
count_rec_dict = {}

# for finding ways to sum to 100
def count_rec(cursum, level):
    global count_rec_dict

    # 99 is the last integer that we could be using,
    # so prevent the algorithm from going further. 
    if level == 99:
        if cursum == 100:
            return 1
        else:
            return 0

    res = 0

    for i in xrange(0, 101-cursum, level+1):

        # fetch branch value from the dictionary
        if (cursum+i, level+1) in count_rec_dict:
            res += count_rec_dict[(cursum+i, level+1)]

        # add branch value to the dictionary
        else:
            count_rec_dict[(cursum+i, level+1)] = count_rec(cursum+i, level+1)
            res += count_rec_dict[(cursum+i, level+1)]        

    return res}

print count_rec(0, 0)
print time() - t

它在我的电脑上运行了惊人的 0.041 秒。哇！！！！！我今天学到了一些新东西！

4

4 回答 4

5

递归解决方案应该做得很好，尽管我确信对于不需要这种操作的问题有一个完全不同的解决方案。

def count_rec(cursum, level):
    if level == 100:
        return 1
    res = 0
    for i in xrange(0, 100-cursum, level+1):
        res += count_rec(cursum+i, level+1)
    return res

print count_rec(0, 0)

有趣的是，如果你记住这个函数，它实际上会有一个合理的运行时间（这就是动态编程的威力）。玩得开心！

于 2012-09-26T00:08:30.050 回答
1

避免缩进错误的一种方法是将循环放在单独的函数中，每个函数只嵌套一层。

或者，您可以使用递归一遍又一遍地调用函数，每次都使用更小的范围和更高的嵌套级别。

话虽这么说，无论您如何编码，您的算法都将具有难以置信的长运行时间。你需要一个更好的算法:-)

于 2012-09-26T00:12:34.493 回答
1

要完全使用您的算法来做到这一点（将每个下一个数字限制为可能适合所需总和的一个），您确实需要递归 - 但真正的蛮力方法可以是单线：

sum(sum(i) == 100 for i in itertools.product(xrange(100), repeat=100))

自然，这将比真正重构您的算法要慢一些（事实上，正如评论中所提到的，它变得难以处理）。

于 2012-09-26T00:36:50.567 回答
0

最有效的解决方案是基于算术进位的思想。您有最大值和步骤的列表，以及当前值的列表。每次要更新这 100 个变量时，请执行以下操作：

inc_index = -1
currentvalue[inc_index] += stepval[inc_index]
# I use >= rather than > here to replicate range()s behaviour that range(0,100) generates numbers from 0 to 99.
while currentvalue[inc_index] >= maxval[inc_index]:
    currentvalue[inc_index] = 0
    inc_index -= 1
    currentvalue[inc_index] += stepval[inc_index]
# now regenerate maxes for all subordinate indices
while inc_index < -1:
    maxval[inc_index + 1] = 100 - sum (currentvalue[:inc_index])
    inc_index += 1

当引发 IndexError 时，您已经完成了循环（用完“数字”可以进入。）

于 2012-09-26T01:29:26.740 回答