递归求汉诺塔问题 递归求青蛙跳台问题

递归求汉诺塔问题 递归求青蛙跳台问题"/>

递归求汉诺塔问题 递归求青蛙跳台问题

1.递归求汉诺塔问题
在汉诺塔问题中，假设有A、B、C三根柱子，A柱子上由上到下从小到大摆放了n个圆盘，要借助B柱子将A柱子上的圆盘由移动到C柱子上，还是按由上到下从小到大摆放。
设想A上有一个圆盘，直接移到C上(a->c),只需要一次 2^1-1；
设想A上有两个圆盘，通过（A->B,A->C,B->C),需要三次 2^2-1；
设想A上有三个盘子，通过（A->C A->B C->B A->C B->A B->C A->C ),
需要七次 2^3-1；
如果有n个盘子，则可把问题归结于把（n-1）个放在B上，再将A上最大的放到C上，现在在B上的（n-1)个盘子，可归结于把（n-2)个放到A上，再将B上最大的放到C上，以此类推，用递归实现。代码如下

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
void Move(char pos1, char pos2)
{printf("%c->%c ", pos1, pos2);
}
//pos1开始位置
//pos2中间位置
//pos3结束位置
void Hanota(int n, char pos1, char pos2, char pos3)
{if (n == 1){Move(pos1,pos3);}else{Hanota(n - 1, pos1, pos3, pos2);Move(pos1, pos3);Hanota(n - 1, pos2, pos1, pos3);}
}
int main()
{int n;printf("请输入盘子的数量\n");scanf("%d", &n);Hanota(n, 'A', 'B', 'C');system("pause");return 0;
}

2.一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，问这个青蛙跳上n级台阶一共有多少种跳法。
跳一级台阶一种方法；
跳两级台阶两种方法；1 1 或 2
跳三级台阶三种方法；1 1 1或1 2 或2 1；
跳四级台阶五种方法；1 1 1 1或1 2 1 或1 1 2或2 1 1或 2 2
跳n级台阶，可想为最后一次跳一阶或最后一次跳两阶，则可归结于跳（n-1）级台阶和跳（n-2)级台阶的跳法相加，以此类推，递归实现。代码如下

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int JumpFloor(n)
{if (n == 0){return 0;}else if (n <= 2){return n;}else{return JumpFloor(n - 1) + JumpFloor(n - 2);}
}
int main()
{int n=0;int ret = 0;printf("请输入台阶数\n", n);scanf("%d", &n);ret=JumpFloor(n);printf("%d\n", ret);system("pause");return 0;
}