甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法？
成都创新互联公司专业为企业提供平陆网站建设、平陆做网站、平陆网站设计、平陆网站制作等企业网站建设、网页设计与制作、平陆企业网站模板建站服务，10多年平陆做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
【参考解答（递归法）】
基础：楼梯有一个台阶，只有一种走法（一步登上去）；两个台阶，有2种走法（一步上去，或分两次上去）；
递推：有n个台阶时，设有count(n)种走法，最后一步走1个台阶，有count(n-1)种走法；最后一步走2个台阶，有count(n-2)种走法。于是count(n)=count(n-1)+count(n-2)。
可见，此问题的数学模型竟然是斐波那契数。
#includestdio.hint main()
{ unsigned long count(int n); int n; unsigned long m; printf("请输入楼梯的阶数:"); scanf("%d",n);
m=count(n); printf("有%lu种爬楼梯的方法\n",m); return 0;
}unsigned long count (int n)
{ unsigned long f; if(n==1)
f=1; else if(n==2)
f=2; else
f=count(n-1)+count(n-2); return(f);
}1234567891011121314151617181920212223
（1）首先我们建立一个函数，判断函数的合法性
[cpp] view plaincopy
void jump_ladder(int layer, int* stack, int* top)
{
if(layer = 0)
return;
return;
}
（2）判断当前的层数是为1或者是否为2
[cpp] view plaincopy
void jump_ladder(int layer, int* stack, int* top)
{
if(layer = 0)
return;
if(layer == 1){
printf_layer_one(layer, stack, top);
return;
}
if(layer == 2){
printf_layer_two(layer, stack, top);
return;
}
return;
}
（3）对于2中提及的打印函数进行设计，代码补全
[cpp] view plaincopy
#define GENERAL_PRINT_MESSAGE(x)\
do {\
printf(#x);\
for(index = (*top) - 1 ; index = 0; index --)\
printf("%d", stack[index]);\
printf("\n");\
}while(0)
void printf_layer_one(int layer, int* stack, int* top)
{
int index ;
GENERAL_PRINT_MESSAGE(1);
}
void printf_layer_two(int layer, int* stack, int* top)
{
int index;
GENERAL_PRINT_MESSAGE(11);
GENERAL_PRINT_MESSAGE(2);
}
注： a）代码中我们使用了宏，注意这是一个do{}while(0)的结构，同时我们对x进行了字符串强转
b）当剩下台阶为2的时候，此时有两种情形，要么一次跳完；要么分两次
（4）当阶梯不为1或者2的时候，此时需要递归处理
[cpp] view plaincopy
void _jump_ladder(int layer, int* stack, int* top, int decrease)
{
stack[(*top)++] = decrease;
jump_ladder(layer, stack, top);
stack[--(*top)] = 0;
}
void jump_ladder(int layer, int* stack, int* top)
{
if(layer = 0)
return;
if(layer == 1){
printf_layer_one(layer, stack, top);
return;
}
if(layer == 2){
printf_layer_two(layer, stack, top);
return;
}
_jump_ladder(layer- 1, stack, top, 1);
_jump_ladder(layer- 2, stack, top, 2);
}
这里在函数的结尾添加了一个函数，主要是递归的时候需要向堆栈中保存一些数据，为了代码简练，我们重新定义了一个函数。
总结：
1）这道题目和斐波那契数列十分类似，是一道地地道道的递归题目
2）递归的函数也需要好好测试，使用不当，极容易堆栈溢出或者死循环。对此，我们可以按照参数从小到大的顺序依次测试，比如说，可以测试楼梯为1、2、3的时候应该怎么运行，同时手算和程序相结合，不断修正代码，完善代码。
这个要用递归做。到某一阶n有两种可能，从第n-1上1阶，从第n-2上2阶，因此到达第n阶的的函数f（n）的走法等于f（n-1）+f（n-2），即到达f（n-1）阶的走法与f(n-2）阶的走法之和！
代码如下：
int f( int n )
{
if ( n == 1 )
{
return 1;
}
else if ( n == 2 )
{
return 2;
}
else
{
return f(n-1) + f(n-2);
}
}
int main()
{
int num = f( 10 );
return 0;
}
打印出 num 的值得话，可以看到 10 阶共有 89 种走法。
int count = 0;
void a( void )
{
�0�2 count++;
�0�2 if ( count 100 )
�0�2 a(); // 如果count100, 调用自己。一直到100就停止！不过递归多了耗尽堆栈会崩溃！
}
递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法的特点
递归过程一般通过函数或子过程来实现。
递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
例子如下：
描述：把一个整数按n(2=n=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。
参数说明：s: 保存转换后得到的结果。
n: 待转换的整数。
b: n进制（2=n=20）
void
numbconv(char *s, int n, int b)
{
int len;
if(n == 0) {
strcpy(s, "");
return;
}
/* figure out first n-1 digits */
numbconv(s, n/b, b);
/* add last digit */
len = strlen(s);
s[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];
s[len+1] = '\0';
}
void
main(void)
{
char s[20];
int i, base;
FILE *fin, *fout;
fin = fopen("palsquare.in", "r");
fout = fopen("palsquare.out", "w");
assert(fin != NULL fout != NULL);
fscanf(fin, "%d", base);
/*PLS set START and END*/
for(i=START; i = END; i++) {
numbconv(s, i*i, base);
fprintf(fout, "%s\n", s);
}
exit(0);
}
递归算法简析（PASCAL语言）
递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写
程序能是程序变得简洁和清晰.
一 递归的概念
1.概念
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).
如:
procedure a;
begin
.
.
.
a;
.
.
.
end;
这种方式是直接调用.
又如:
procedure b; procedure c;
begin begin�0�2
. .
. .
. .
c; b;
. .
. .
. .
end; end;
这种方式是间接调用.
例1计算n!可用递归公式如下:
1 当 n=0 时�0�2
fac(n)={n*fac(n-1) 当n0时
可编写程序如下:
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
设n阶台阶的走法数为f(n)
显然有
1 n=1�0�2
f(n)={
f(n-1)+f(n-2) n2
可编程序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
二，如何设计递归算法
1.确定递归公式
2.确定边界(终了)条件
三，典型例题
例3 梵塔问题
如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子
从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上
不能出现大盘压小盘.找出移动次数最小的方案.
程序如下:
program fanta;
var
n:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'---',c)
else begin
move(n-1,a,c,b);
writeln(a,'---',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b;
repeat
while (b[j]=x) and (ji) do j:=j-1;
if ji then begin t1:=b; b:=b[j];b[j]:=t1;end;
while (b=x) and (ij) do i:=i+1;
if ij then begin t1:=b[j];b[j]:=b;b:=t1; end
until i=j;
b:=x;
i:=i+1;j:=j-1;
if sj then quicksort(b,s,j);
if it then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a:6);
writeln;
end.
#include stdio.h
int fuck(int n, int m)
{
if(n == 1 || n == 0) return 1;
if(n 0) return 0;
int total = 0;
int i = 1;
for(; i m; ++i)
{
total += fuck(n - i, m);
}
return total;
}
int main()
{
int a;
scanf("%d", a);
int n[a];
int i;
for(i = 0; i a; ++i)
{
scanf("%d", n[i]);
}
int b;
scanf("%d", b);
int m[b];
for(i = 0; i a; ++i)
{
scanf("%d", n[i]);
}
for(i = 0; i a i b; ++i)
{
printf("%d", fuck(n[i], m[i]));
}
return 0;
}
没编译器，你先编译试试，应该没错
望采纳~