回上方

(18)最大路徑和

一個給定的4層數字三角形（第n層有n個數），從最頂數位出發每次只能移動到左下或右下的直到最底層。在所有的路徑中，經過路徑數字和最大值是3+7+4+9=23。

【最後目標】

一個給定的15層數字三角形（第n層有n個數），從最頂數位出發每次只能移動到左下或右下的直到最底層。請找出最大的經過路徑數字和。

【討論】

每次移動只有左下和右下兩種不同走法，若是左下用0表示，右下用1表示，則走3層有幾種不同走法呢?

用0和1組成長度3的數列有000,001,010,011,100,101,110,111，共有2^3=8種


練習1:用0和1組成長度14的數列有16384種不同的排列法

1
2
3
4
5
6
7
import itertools
x = [0,1]
routes = []
for p in itertools.product(x, repeat=14):
    routes.append(p)

print(len(routes))

下載數字

練習2：讀進15層數字，並且求某一特定條路徑的數字和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# -*- coding: UTF-8 -*-
numbers = []

# 打開檔案
file = open("d:/numbers4.txt", "r")

# 讀取檔案
for line in file.readlines():    #依序讀取每行
    line = line.strip()    #去掉每行頭尾空白
    number_list = []
    for number in line.split():
        number_list.append(int(number))
    numbers.append(number_list)

# 關閉檔案
file.close()

print(numbers)

route = "01100110101011"
i = 0
j = 0
sum = 75
for digit in route:
    i = i + 1
    if digit == "0":
        sum = sum + numbers[i][j]
    else :
        j = j + 1
        sum = sum + numbers[i][j]
print(sum)

本單元課程自2018.4.23日起已被瀏覽 386 次