我正在尝试以大西洋的方式学习Python,并卡在了欧拉计划#18上。
我在网络上找到的所有东西(除此之外还有更多的谷歌搜索)都是一些变体“虽然你可以暴力解决,但这里是一个更优雅的解决方案”...
我明白了,真的有很棒的解决方案,我期待着有一天'无环图'这个词会在我的脑海中呈现出更清晰的画面。但我需要先从基础开始看看状态,尝试使用暴力方法。所以问题来了:如何生成(枚举?)欧拉计划#18题中三角形的所有有效路径,并将它们存储在适当的Python数据结构中?(列表的列表是我最初的想法?)我不想要答案 - 我想知道如何暴力地遍历所有路径并将它们存储到数据结构中。这是我得到的内容。我肯定是在错误地循环数据集。期望的行为应该是进行“深度优先(?)”而不仅仅是无效地循环每一行。我读了Norvig书的第3章,但无法翻译伪代码。尝试阅读AIMA python library的第三章,但它跨度太大。
triangle = [
[75],
[95, 64],
[17, 47, 82],
[18, 35, 87, 10],
[20, 4, 82, 47, 65],
[19, 1, 23, 75, 3, 34],
[88, 2, 77, 73, 7, 63, 67],
[99, 65, 4, 28, 6, 16, 70, 92],
[41, 41, 26, 56, 83, 40, 80, 70, 33],
[41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
[63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
[04, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
]
def expand_node(r, c):
return [[r+1,c+0],[r+1,c+1]]
all_paths = []
my_path = []
for i in xrange(0, len(triangle)):
for j in xrange(0, len(triangle[i])):
print 'row ', i, ' and col ', j, ' value is ', triangle[i][j]
??my_path = somehow chain these together???
if my_path not in all_paths
all_paths.append(my_path)
最好避免使用外部库(如itertools)的答案。