gpt4 book ai didi

python - 欧拉计划问题 18 : What mistake did I make in my code?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:40:46 27 4
gpt4 key购买 nike

https://projecteuler.net/problem=18

给定一个整数三角形,问题是找到从上到下的最大路径和(其中路径中的所有数字必须相邻)。

我有一个算法的想法:从最顶层开始,计算左右路径的总和(一直向下,一直向下,一直向下),如果左边的总和更大,则跳转到左边相邻的数字,如果右边的和更大,则跳转到右边相邻的数字,从当前数字开始重复算法,依此类推,直到到达底行。

triangle = ['75', '9564', '174782', '18358710', '2004824765', '190123750334', '88027773076367', '9965042806167092', '414126568340807033', '41487233473237169429', '5371446525439152975114', '701133287773177839681757', '91715238171491435850272948', '6366046889536730731669874031', '046298272309709873933853600423']

maximumPath = [75]
maxSum = 75 #Start it with the starting element of the triangle.

def triNum(row, index): #Returns the number at given row, number in row
return(int(triangle[row][2*index:2*(index+1)])) #Nota bene: returns an integer.

def options(row, index): #Rows start at 0, index starts at 0
return(triNum(row+1, index), triNum(row+1, index+1))

def criticalPathSum(startRow, startIndex, direction):
critPath = []
if direction == 'left':
directionNum = 0
else:
directionNum = 1
sum = triNum(startRow, startIndex) #Starting sum of left and right paths is just the number at the start of both paths.
for i in range(startRow + 1, len(triangle)):
startIndex += directionNum
sum += triNum(i, startIndex)
critPath.append(triNum(i, startIndex))
#print(triNum(i, startIndex + directionNum))
return(sum, critPath)

pathIndex = 0
for row in range(0, len(triangle)-1):
print('These are my options: ' + str(options(row, pathIndex)))
print('Left Sum: ' + str(criticalPathSum(row, pathIndex, 'left')) + ', ' + 'Right Sum: ' + str(criticalPathSum(row, pathIndex, 'right')))
if criticalPathSum(row, pathIndex, 'left') > criticalPathSum(row, pathIndex, 'right'):
maximumPath.append(triNum(row + 1, pathIndex))
print('Left. ' + str(triNum(row + 1, pathIndex)))
else:
print('Right. ' + str(triNum(row + 1, pathIndex + 1)))
pathIndex += 1
maximumPath.append(triNum(row + 1, pathIndex))
maxSum += triNum(row + 1, pathIndex)
print('_______________________________')
print('\n')
print(maximumPath)
print(maxSum)

答案是1067,但我得到883。根据算法,这是最大路径:

[75, 95, 17, 35, 82, 75, 7, 16, 80, 37, 91, 17, 91, 67, 98].

最佳答案

你的算法是错误的:在像这样的三角形中

   1
1 4
1 4 1
9 1 4 1

它太受9(总是向左走)的诱惑,无法看到最优的1+4+4+4 = 13 路线.

关于python - 欧拉计划问题 18 : What mistake did I make in my code?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56227635/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com