欢迎加入我们，一同切磋技术。 &
用户名： &&&
密　码： &
共有 1263 人关注过本帖
标题：数字三角形问题，求走过路径的数值最大的答案。
等　级：业余侠客
帖　子：413
专家分：233
结帖率：94.83%
&&已结贴√
&&问题点数：20&&回复次数：21&&&
数字三角形问题，求走过路径的数值最大的答案。
示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1&三角形行数&25；三角形中的数字为整数&1000；&&路径所经过的数字的总和最大的答案
&&偶然看到的一题，，，该怎么做？？
附件: 您没有浏览附件的权限，请
搜索更多相关主题的帖子:
来　自：长长久久
等　级：贵宾
威　望：22
帖　子：3848
专家分：10955
方法有很多~一个是递归~另一个是贪心算法(实质就是简单的运用广度搜索原理求局部最优解集合)最近敲数据结构敲多了~竟然想到了广度搜索和遍历二叉树(玩笑~应该考算法没那么复杂)~好像中间一部分数字取不了~可以排除~
思路~每一个可以走到的位置都有一个唯一确定的步数~这个步数可以轻易算出~然后求从步数从小到大的每个步数的最优解~感觉这是一个动态规划问题~
[此贴子已经被作者于 17:53编辑过]
[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~更~*/[/code]
来　自：长长久久
等　级：贵宾
威　望：22
帖　子：3848
专家分：10955
附加简单算法~
&&&&&4&&&&&4
5&&&&&& 5&&&&&5
&&& 6&&&&&& 6&&&&&6
7&&&&&7&&&&&&&&7&&&&&7
&&& 8&&&&&8&&&&&&&&8&&&&&8
9&&& 9&&&&&&&&9&&&&&& 9&&&&&&9
这些数字代表走到该点的步数~
递推出这些数字的最优解~
好像这样不用递归也行耶~思路一目了然了~
[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~更~*/[/code]
等　级：业余侠客
帖　子：413
专家分：233
回复 2楼 九转星河
实质就是简单的运用广度搜索原理求局部最优解集合
这个是什么 我们还没学。。。。
来　自：长长久久
等　级：贵宾
威　望：22
帖　子：3848
专家分：10955
回复 4楼 花脸
其实这个可以是深入浅出~
第一次求所有第一步的最大值~
第二次求所有第二步的最大值~
第n次求所有第n步的最大值~
由于一个确定的位置最多只能由两个上一步的位置推出来~所以位置解就是求左斜上方和斜右斜上方的位置(如果有的话)的较大值~
[此贴子已经被作者于 16:54编辑过]
[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~更~*/[/code]
等　级：业余侠客
帖　子：413
专家分：233
回复 5楼 九转星河
&&必须用这代码。？？这代码&&不太认识。。。。
附件: 您没有浏览附件的权限，请
等　级：版主
威　望：23
帖　子：1542
专家分：2868
我怎么算出来等于40呢？5+7+8+8+7+5＝40
来　自：长长久久
等　级：贵宾
威　望：22
帖　子：3848
专家分：10955
回复 7楼 ehszt
第一行的5是指行数而不是内容~按你这样的算法这题就非常简单了~
[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~更~*/[/code]
等　级：业余侠客
帖　子：413
专家分：233
回复 8楼 九转星河
能否&&把你所想的代码写下。。。。
等　级：业余侠客
帖　子：413
专家分：233
回复 7楼 ehszt
&&这个我也不清楚。。
版权所有，并保留所有权利。
Powered by , Processed in 0.076330 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights Reserved}