题目18：找出从三角形顶端走到底端的最大和,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

欧拉计划 发表于 2015-4-21 16:51:42

题目18：找出从三角形顶端走到底端的最大和

Maximum path sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
题目：

从下面的三角形的顶端开始，向下面一行的相邻数字移动，从顶端到底端的最大总和为 23.

也就是 3 + 7 + 4 + 9 = 23.

找出从以下三角形的顶端走到底端的最大总和：

huomqh 发表于 2016-7-3 02:09:25

本帖最后由 huomqh 于 2016-7-3 02:20 编辑

def f(r,c,sss,link):
if r==14:
   y=
   k.append(y)
   return 1
else:
   f(r+1,c,sss+a,link+"+"+str(c))
   f(r+1,c+1,sss+a,link+"+"+str(c+1))



a=[,,,,,,,,,,,,,,]
k=[]
result=[]
f(0,0,a,'0')
m=0
for i in k:
if i>m:
   m=i
   result=i[:]
print (result)
b=result.split("+")
l=str(a)
for z in range(1,len(b)):
l=l+"+"+str(a)])
print(l)

这次应该对了
1074
75+64+82+87+82+75+73+28+83+32+91+78+58+73+93

huomqh 发表于 2016-7-3 02:10:13

本帖最后由 huomqh 于 2016-7-3 02:40 编辑

随便写写的，可读性很差，大家见谅。
附一张分布图吧
http://xxx.fishc.com/album/201607/03/023924e3l22kjjmf2c6tt6.png

Plusenxue 发表于 2016-8-27 14:21:03

a=[,
,
,
,
,
,
,
,
,
,
,
,
,
,
]
for i in range(1,15):
for j in range(15-i):
   if a < a:
         a = a+a
   else:
         a = a+a

print(a)

迷雾少年 发表于 2016-8-28 12:25:04

1074 应该是吧。。
#include <iostream>
using namespace std;
int myMaxNumber = 0;
/* 数组线性保存 */
int myArry[]={
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,9,70,98,73,93,38,53,60,04,23

};
int myArry2[]={3,7,4,2,4,6,8,5,9,3};

/* 获取第h行第1个数 */
/*递归关系 f(1) = 1f(x) = f(x-1) + 1 */
int getNumber(int h)
{
int n = 0;
if(1==h)
{
return 1;
}
n = getNumber(h-1);
return n+(h-1);
}
int getNum(int h,int l)
{
return myArry;
}
int getMaxNum(int l,int h,int result)
{
int j,k;
j = l;
k = l + 1;
//如果到达最底层算出结果
if( 15 == h )
{
int a = result + getNum(h,l);
if( myMaxNumber < a)
{
myMaxNumber = a;
}
return a;
}

/* 接着上一层的开始*/
getMaxNum(j,h+1,result+getNum(h,l));
getMaxNum(k,h+1,result+getNum(h,l));
}
int main(void)
{
getMaxNum(1,1,0);
std::cout<<myMaxNumber;
return 0;
}

渡风发表于 2017-1-18 15:59:58

此代码使用matlab编程
Problem18所用时间为2.0008秒
Problem18的答案为1074
%题目18：找出从三角形顶端走到底端的最大和
%本质上是二叉树
function Output=Problem18(Input)
tic
if nargin==0
Input=[75,zeros(1,14);...
      95,64,zeros(1,13);...
      17,47,82,zeros(1,12);...
      18,35,87,10,zeros(1,11);...
      20,04,82,47,65,zeros(1,10);...
      19,01,23,75,03,34,zeros(1,9);...
      88,02,77,73,07,63,67,zeros(1,8);...
      99,65,04,28,06,16,70,92,zeros(1,7);...
      41,41,26,56,83,40,80,70,33,zeros(1,6);...
      41,48,72,33,47,32,37,16,94,29,zeros(1,5);...
      53,71,44,65,25,43,91,52,97,51,14,zeros(1,4);...
      70,11,33,28,77,73,17,78,39,68,17,57,zeros(1,3);...
      91,71,52,38,17,14,91,43,58,50,27,29,48,zeros(1,2);...
      63,66,04,68,89,53,67,30,73,16,69,87,40,31,zeros(1,1);...
      04,62,98,27,23,9,70,98,73,93,38,53,60,04,23];
end
Pro=2^(length(Input(1,:))-1);%有多少种可能
A=Input;
L=length(Input(1,:))-1;
Result=0;
for ii=1:Pro
V=Get2bit(ii-1,L);%V=Vector,一个数二进制表示的向量
Sum=A(1,1);
for jj=1:L
   Sum=Sum+A(jj+1,1+sum(V(1:jj)));
end
if Sum>Result
   Result=Sum;
end
end
toc
Output=Result;
disp('此代码使用matlab编程')
disp(['Problem18所用时间为',num2str(toc),'秒'])
disp(['Problem18的答案为',num2str(Output)])
end
%% 子程序
%输入一个数Input，得到其二进制表示，L为期长度
function Output=Get2bit(Input,L)
if nargin==0
L=14;
Input=56;
end
Temp=Input;
Rank=[];
while (Temp>=1)
Rank_Temp=;
Rank=Rank_Temp;
Temp=floor(Temp/2);
end
if length(Rank)<L
Output=;
else
Output=Rank;
end
end

永丨恒 发表于 2017-2-21 10:09:24

temp = '''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'''

temp =

for i in range(len(temp) - 2, -1, -1):
for j in range(len(temp)):
temp = max(int(temp) + int(temp), int(temp) + int(temp))
print temp
从下往上算比较高效，此代码适用于第67题，只要把上面的数字替换即可。

zzzgod 发表于 2018-6-28 20:10:00

#include <iostream>
#include <cmath>
using namespace std;
int max1=0;
int map={
{00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00},
{00,75,00,00,00,00,00,00,00,00,00,00,00,00,00,00},
{00,95,64,00,00,00,00,00,00,00,00,00,00,00,00,00},
{00,17,47,82,00,00,00,00,00,00,00,00,00,00,00,00},
{00,18,35,87,10,00,00,00,00,00,00,00,00,00,00,00},
{00,20, 4,82,47,65,00,00,00,00,00,00,00,00,00,00},
{00,19, 1,23,75, 3,34,00,00,00,00,00,00,00,00,00},
{00,88, 2,77,73, 7,63,67,00,00,00,00,00,00,00,00},
{00,99,65, 4,28, 6,16,70,92,00,00,00,00,00,00,00},
{00,41,41,26,56,83,40,80,70,33,00,00,00,00,00,00},
{00,41,48,72,33,47,32,37,16,94,29,00,00,00,00,00},
{00,53,71,44,65,25,43,91,52,97,51,14,00,00,00,00},
{00,70,11,33,28,77,73,17,78,39,68,17,57,00,00,00},
{00,91,71,52,38,17,14,91,43,58,50,27,29,48,00,00},
{00,63,66, 4,68,89,53,67,30,73,16,69,87,40,31,00},
{00, 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23}
};
void count(int x,int y,int sum)
{
if(y==16)
{
max1=max(max1,sum);
}
else
{
sum+=map;
count(x,y+1,sum);
count(x+1,y+1,sum);
}
}

int main()
{
count(1,1,0);
cout<<"最大的和是："<<max1;
}

DetConan 发表于 2018-9-15 20:18:26

python3 用时0.000216秒
结果是1074, 75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93
import time

start = time.clock()
nums = [,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ]

lens = len(nums)
biglist = []
for i in range(lens):
biglist += [, nums]]

for i in range(lens - 1):
temp = biglist
n = lens - 2 - i
biglist = []
for j in range(n + 1):
   tempn = nums
   if temp > temp:
         biglist += [] + + temp]
   else:
         biglist += [] + + temp]
print(biglist)

end = time.clock()
print("read:%f s" % (end - start))

cwhsmile 发表于 2019-4-25 23:57:08

import time
import math

def test1():
nums = [,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ,
   ]
last_len = len(nums[-1])
nums = nums[::-1]
li = nums

for i in range(1,last_len):
   new = li[:]
   li = []
   for j in range(len(nums)):
         front = nums + new
         #print(front,end=',')
         rear = nums + new
         #print(rear)
         if front > rear:
            li.append(front)
         else:
            li.append(rear)
   #print(li)
new = li[:]

return max(new)

start = time.perf_counter()
print(test1())
end = time.perf_counter()
print(end-start)

成为极客 发表于 2019-5-29 23:43:14

import time as t
start = t.perf_counter()
a=[,
,
,
,
,
,
,
,
,
,
,
,
,
,
]
for i in range(14,-1,-1):
for j in range(i):
   if a>a:
      a += a
   else:
      a += a
print(a)
end = t.perf_counter()
print(end-start)
1074
8.210900000000035e-05

永恒的蓝色梦想 发表于 2020-4-29 18:37:01

C++ 0ms#include<iostream>
using namespace std;
#define max(a,b) (a>b?a:b)

int main() {
char i = 14, j;
int arr = {
   {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, 9, 70, 98, 73, 93, 38, 53, 60, 04, 23}
};

while (j = i--) {
   while (j--) {
         arr += max(arr, arr);
   }
}

cout << arr << endl;
return 0;
}

数据小随从 发表于 2020-6-30 17:23:53

本帖最后由永恒的蓝色梦想于 2020-6-30 17:59 编辑

我不知道错在哪里，为什么大家的答案都是1074，我算的是1064

#include<stdio.h>
#include<stdlib.h>

#define N 15

void main()
{
int a = { {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 (int i = 0; i < N; i++)//打印三角形
{
printf("%*d", 45 - 3 * i, a);
for (int j = 1; j <= i; j++)
{
printf("%6d", a);
}
printf("\n");
}

int k = 1;
int nums = { 0 };
int t = 0;
nums = a;
int res = 0;
while (k < N)
{
if (a > a)
{
nums = a;
}
else
{
nums = a;
t = t + 1;
}
k++;
}
printf("产生的序列是\n");
for (int i = 0; i < N; i++)
{
printf("%4d", nums);
}
printf("\n");
for (int i = 0; i < N; i++)
{
res += nums;
}
printf("三角形顶端走到底端的最大和为 %d\n", res);

system("pause");
}
输出结果：
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
产生的序列是
759547878275732883474373916798
三角形顶端走到底端的最大和为 1064

永恒的蓝色梦想 发表于 2020-6-30 17:59:28

数据小随从发表于 2020-6-30 17:23
我不知道错在哪里，为什么大家的答案都是1074，我算的是1064
#include
#include

用 <> 发代码！

数据小随从 发表于 2020-7-1 21:08:11

永恒的蓝色梦想发表于 2020-6-30 17:59
用发代码！

谢谢，我以前一直不知道他们这个怎么发的，我以为要特殊的软件编辑

mathtimes 发表于 2022-2-6 12:38:28

#include <iostream>
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))
int Array[]={
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, 9,70,98,73,93,38,53,60,04,23
};
#define width 15
void setmax(int i,int j)
{
if(j == 0)
   Array += Array;
else if(j == i)
   Array += Array;
else
Array += max(Array,Array);
}
int main()
{
for(int i=1;i<width;i++)
   for(int j=0;j<=i;j++)
         setmax(i,j);
int maxum = 0;
for(int i=width*(width-1)/2+0;i<width*(width-1)/2+15;i++)
   if(maxum<Array)
         maxum = Array;
cout << maxum;
}

页: [1]

鱼C论坛's Archiver

题目18：找出从三角形顶端走到底端的最大和