سلام. رسیدیم به چالش 18 سایت پروژه اویلر که سوال بانمکی داره!
با شروع از بالای مثلث زیر و حرکت به اعداد مجاور در ردیف زیرین ، حداکثر مجموع از بالا به پایین 23 است.
3
7 4
2 4 6
8 5 9 33 + 7 + 4 + 9 = 23
حداکثر کل مثلث زیر را پیدا کنید.
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
خوب سوال خواسته از بالای مثلث حرکت کنیم و جمع اعداد رو تا پایین مثلث به این صورت که هر عدد فقط با اعداد نزدیک زیرین خودش جمع بشه رو پیدا کنیم و در انتها مسیری که بیشترین مجموع اعداد رو به ما میده رو به برنامه بدیم.
من اول گفتم که کل مسیرهای ممکن رو جمع بزنم و درانتها ماکزیمم بگیرم، اما این کار بنظرم وقتگیر باشه و البته پیاده سازیش هم یکم پیچیده. به جای اون من مسئله رو طور دیگه ای حل کردم! من از ردیف یکی مونده به آخر شروع کردم و رو به بالا حرکت کردم چون از اون ردیف هر عدد فقط دو حرکت داره که میتونم جمعش رو با عدد بزرگتر بگیرم و درون عددم بگذارم و همینطور به عقب برگردم تا به راحتی بزرگترین مسیر پیدا بشه.
پس کد من در زبان برنامه نویسی پایتون این کدخواهد بود:
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],
[ 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
]
for i in range(13, -1, -1):
for j in range(i+1):
triangle[i][j]=max(triangle[i+1][j] , triangle[i+1][j+1])+triangle[i][j]
print(triangle[0])