1

欧拉计划问题 18要求我们找到一个三角形网格的从上到下的路线,并具有最大和。

我的程序应该能够接受如下所示的输入。测试用例的数量 (2) 出现在第一行,然后为每个测试用例给出行数 (4),然后是测试用例的数据,每行一行。

2 
4 
3 
7 4
2 4 6
8 5 9 3
6
690
650 901
65 774 67
435 248 677 385
878 90 378 191 703
141 296 143 756 938 529

程序应该为每个测试用例产生一行输出,给出最大和的路由:

23 
4176

我尝试使用 python 来实现它。

代码如下:

def triangle(rows):
    PrintingList = list()
    for rownum in range (rows ):     
        PrintingList.append([])
        newValues = raw_input().strip().split()
        PrintingList[rownum] += newValues
    return PrintingList

def routes(rows,current_row=0,start=0): 
        for i,num in enumerate(rows[current_row]): 
            if abs(i-start) > 1:   
                continue
            if current_row == len(rows) - 1: 
                yield [num]
            else:
                for child in routes(rows,current_row+1,i):
                    yield [num] + child

testcases = int(raw_input())
for num in range(testcases):
    rows= int(raw_input())
    triangleinput = triangle(rows)
    max_route = max(routes(triangleinput),key=sum)
    sum(max_route)

当我输入这个:

1
3
1
2 3
4 5 6

我收到此错误:

Traceback (most recent call last):
  File "Maximum Route.py", line 23, in <module>
    max_route = max(routes(triangleinput),key=sum)
TypeError: unsupported operand type(s) for +: 'int' and 'str'

需要一些指导..如果有其他错误请指出...谢谢...

4

1 回答 1

2

这是问题所在:

newValues = raw_input().strip().split()

您需要将输入转换为整数:

newValues = map(int, raw_input().split())
于 2012-09-12T10:44:46.417 回答