递归经典问题--汉诺塔问题.青蛙跳台阶问题

第一个就是古老的汉诺塔问题：问题是这样的，现在有A,B,C三座塔，然后A上面有n个盘子，盘子是由小到大从上到下依次排列的，我们现在想要把A座上面的盘子全部移到C座上面去，要求是每次只能移动一个盘子，并且在移动的过程中大盘始终要在下，问需要移动的步骤是什么？

下面直接看代码吧：

#include<stdio.h>
void move(char a,char b){
printf("%c->%c
",a,b);}

void hanoi(int n,char a,char b,char c){

if(n==1)
move(a,c);
else{
hanoi(n-1,a,c,b);
move(a,c);
hanoi(n-1,b,a,c);}}




int main(){
int n;
scanf("%d",&n);
hanoi(n,A,B,C);
return 0;}

第二个问题就是青蛙跳台阶问题：有一个青蛙跳台阶，一次可以跳一格，也可以跳两个，问这只青蛙跳n阶可以有多少种可能。台阶数 可能

1 1

2 2

3 3

4 5

5 8.....

是不是和前面介绍过的斐波那契数有点像，1 1 2 3 5 8 13

循环法：

#include<stdio.h>
int jump(int n)
{
int a=1;
int b=2;
int c=n;
while(n<2){
c=a+b;
a=b;
b=c;
n--;
}
return c;
}


int main()
{
int n;
scanf("%d",&n);
int c=jump(n);
printf("%d",c);
return 0;
}

递归法：

#include<stdio.h>
int jump(int n){
	if (n <= 2)
		return n;
	else
		return jump(n - 1) + jump(n - 2);
}

int main(){
	int n;
	scanf("%d", &n);
	int c = jump(n);
	printf("%d", c);
	return 0;
}