UC知道信息竞赛 编程
来源：百度知道 编辑：UC知道 时间：2024/06/10 17:11:02
问题描述：共有n级台阶。一个人一步可走1、2、3 级台阶。
输入：n：integer
输出：走完n级台阶的走法总数、以及所有走法。
样例：输入：3;
输出：1、2
3
1、1、1
2、1
sum=4
我是用递归做的：
program ztj;
var sum:longint;
n:integer;
procedure ztj(m:integer);
var i:integer;
begin
if m=0 then begin
sum:=sum+1;
end;
if m<0 then exit;
if m>0 then begin
for i:=1 to 3 do
ztj(m-i);
end;
end;
begin
read(n);
sum:=0;
ztj(n);
writeln(sum);
end.
我只用局部变量递归模拟“走的步子”，只能输出总共的走法数量，
但不能实现走法的输出。请各位帮忙想一想用局部变量解决走法的依次输出。
若有程序请用pascal给出。多谢了！
输入：n：integer
输出：走完n级台阶的走法总数、以及所有走法。
样例：输入：3;
输出：1、2
3
1、1、1
2、1
sum=4
我是用递归做的：
program ztj;
var sum:longint;
n:integer;
procedure ztj(m:integer);
var i:integer;
begin
if m=0 then begin
sum:=sum+1;
end;
if m<0 then exit;
if m>0 then begin
for i:=1 to 3 do
ztj(m-i);
end;
end;
begin
read(n);
sum:=0;
ztj(n);
writeln(sum);
end.
我只用局部变量递归模拟“走的步子”，只能输出总共的走法数量，
但不能实现走法的输出。请各位帮忙想一想用局部变量解决走法的依次输出。
若有程序请用pascal给出。多谢了！
用一个数组来记录走法，搜索时多设一个参数(k)来表示下标.
k表示步数（数组的下标），t表示走的台阶数，z是方法数
这是回溯搜索（可以说是递归）方法
var z,n:integer;
a:array[1..1000] of integer;
procedure f(k,t:integer);
var i:integer;
begin
if t>n then exit
else if t=n then
begin
inc(z);
for i:=1 to k-2 do write(a[i],' ');
writeln(a[k-1]);
end
else
for i:=1 to 3 do
begin
a[k]:=i;
f(k+1,t+i);
end;
end;
begin
readln(n);
f(1,0);
writeln(z);
end.