主题：有道题我不会做，各位大虾救命！！
zhaoren
[专家分：420] 发布于 2005-07-11 16:28:00
有一个数字三角形如下：从顶层走到底层，每次往下走，只能选向左或向右两个方向走，找出数字之和为30的所有路径。
7
/ \
4 6
/ \/ \
6 9 3
/ \ / \/ \
6 3 7 1
/ \ / \ / \/ \
2 5 3 2 8
/ \ / \ / \ / \/ \
5 9 4 7 3 2
如答出来，在下感激不尽 QQ523614832 [em1][em2]
回复列表 （共19个回复）
11 楼
sd5774188 [专家分：260] 发布于 2005-07-25 21:29:00
广搜……
12 楼
zhaoren [专家分：420] 发布于 2005-08-20 12:17:00
[em24][em1][em7][em18][em28][em19]
13 楼
mo19880630 [专家分：420] 发布于 2005-08-20 13:19:00
深搜与广搜都可以做，并且用树图也可以做
14 楼
火狼 [专家分：80] 发布于 2005-08-22 18:13:00
把所有的情况都找出来，和为30的不就出来了。
15 楼
lzl1403 [专家分：1670] 发布于 2005-08-24 00:45:00
好像可以用动态规划做，问题是记录路径有点难度……
16 楼
shefuchenko [专家分：60] 发布于 2005-08-24 10:04:00
我正在查询，可是却没有，自己做的低归超时啊！！！
17 楼
阿Ben [专家分：2200] 发布于 2005-08-26 21:38:00
这题好像不能用动态规划……
如果问题改为“找出数字之和最大的路径”，就是最典型的动态规划题。
这题我认为应该用深度优先搜索。
18 楼
zhaoren [专家分：420] 发布于 2005-09-25 19:15:00
没会写程序的人吗？
19 楼
zhaoren [专家分：420] 发布于 2005-09-25 19:37:00
我已打了一个程序，不知是否还有更简便的：
var a:array[1..6,1..6]of integer;
c,d,f,b,e,s,i,j:integer;
begin
for i:=1 to 6 do
for j:=1 to i do
read(a[i,j]);
for b:=1 to 2 do
for c:=1 to 3 do
for d:=1 to 4 do
for e:=1 to 5 do
for f:=1 to 6 do begin
s:=7+a[2,b]+a[3,c]+a[4,d]+a[5,e]+a[6,f];
if (s=30)and((b-1=1)or(b-1=0))and((c-b=0)or(c-b=1))
and((d-c=0)or(d-c=1))and((e-d=0)or(e-d=1))and
((f-e=0)or(f-e=1))
then
writeln('7',' ',a[2,b],' ',a[3,c],' ',a[4,d],' ',
a[5,e],' ',a[6,f]);
end;
end.
用的是穷举
我来回复
您所在位置：