UC知道Pascal 加法链
来源：百度知道 编辑：UC知道 时间：2024/06/24 12:35:40
一个加法链满足一下5点：
1.它是一个列数记为A
2.数列严格递增
3.第一项是1
4.最后一项是N
5.对于第K项（K>1）存在i,j（1<=i,j<k[i,j可相同]）使得A[K]=A[i]+A[j]
现在已知N，求最短的加法链长度，给出个方案。
输入：
5（数N）
0（输入数据以一行一个数0结束）
输出：
4（L，为最短的加法链长度）
1245（一行L个数所得的加法链）
ps:1<=n<=200
1.它是一个列数记为A
2.数列严格递增
3.第一项是1
4.最后一项是N
5.对于第K项（K>1）存在i,j（1<=i,j<k[i,j可相同]）使得A[K]=A[i]+A[j]
现在已知N，求最短的加法链长度，给出个方案。
输入：
5（数N）
0（输入数据以一行一个数0结束）
输出：
4（L，为最短的加法链长度）
1245（一行L个数所得的加法链）
ps:1<=n<=200
好像是SDTSC一道题吧
var ans,a:array [1..200] of longint;
nans,n:longint;
procedure dfs(y:longint);
var i:longint;
begin
if a[y]=n then begin
if y<nans then begin
nans:=y;
move(a,ans,y<<2);
end;
exit;
end;
if (a[y]>n) or (y>=nans) then exit;
if (nans<>maxlongint) and (a[y]<<(nans-y)<n) then exit;
for i:=y downto 1 do begin
a[y+1]:=a[y]+a[i];
dfs(y+1);
end;
end;
procedure work;
var i:longint;
begin
readln(n);
if n=0 then halt;
nans:=maxlongint;
a[1]:=1;
dfs(1);
writeln(nans);
for i:=1 to nans do begin
write(ans[i]);
if i=nans then writeln else write(' ');
end;
end;
begin
repeat work until false;
end.