C语言函数递归经典例题:汉诺塔和小青蛙跳台阶

汉诺塔

问题描述

将塔A的柱子移动到塔C
要求:

大的柱子只能在小的柱子下面
一次只能移动一个柱子

思路

想把A上的n个柱子移动到C 核心思路是:
S1:先把A上面n-1个柱子移动到B
S2:再把A剩下的1个柱子移动到C
S3:最后把B上的n-1个柱子移动到C

本题显然可以分裂出子问题 移动n个柱子从A到C和移动n-1个柱子从B到C是类似的问题

假设 void Hanoi(int n, char source, char auxiliary, char target)的功能是:
把在source(源头塔)上的n个柱子利用auxiliary(辅助塔) 移动到target(目标塔)
看下面代码的时候不要受参数名影响(B有时候作为目标塔有时候作为辅助塔这取决于传参的顺序)
就这么理解:Hanoi()的功能是把第二个参数上的n个柱子利用第三个参数移动到第四个参数上去
递归的出口:只有一个柱子的时候结束递开始"归" 一个柱子直接移动就行了
每次调用都是一层一层往上越来越接近1个柱子的情况
move函数只是模拟了移动这个行为 move(‘A’,‘C’)就表示把A塔上第一个柱子移动到C塔上去

代码实现

当假设出函数的功能 同时有了子问题如何分裂的思路之后
直接顺着这个思路写下去那就对了!!

void move(char ch1, char ch2)
{printf("%c----->%c\n", ch1, ch2);
}void Hanoi(int n, char source, char auxiliary, char target)
{//如果只有1个柱子 直接移动到目标塔就行if (n == 1){move(source, target);}//不止1个柱子 接收到的参数是A B Celse//n>=2{//S1:先把A上面n-1个柱子移动到BHanoi(n - 1, source, target, auxiliary);//S2:再把A剩下的1个柱子移动到Cmove(source, target);//S3:最后把B上的n-1个柱子移动到CHanoi(n - 1, auxiliary, source, target);}
}int main()
{Hanoi(3, 'A', 'B', 'C');return 0;
}

思考:怎么判断一共要移动几次?(时间复杂度?)

根据子问题的递推规则发现:
n个柱子移动次数是1+2*(n-1个柱子的移动次数)
进一步找规律发现:
n个柱子需要移动2^n-1次
也就是说时间复杂度是O(2^n) 其中n是盘子的数量
这个复杂度已经相当高了在2.00GHz的处理器下 64个柱子要跑270多年

小青蛙跳台阶

BC117 小乐乐走台阶

在牛客网上有一道类似的题目可以先尝试做一做
题目链接

问题描述

一只青蛙
他可以一次跳一级台阶
或者一次跳两级台阶
假设青蛙要跳上n级台阶
请问一共有多少种跳法?
在这里插入图片描述

递归

这道题和斐波那契数列十分类似只不过斐波那契数列我们直接知道第三个数开始每个数就是前两个数之和
而这道题 青蛙跳上一级台阶只有1种跳法 ;跳上二级台阶有2种跳法
思考:跳上第n级(n>=3)呢?
假设我给定一个函数 frogJumps(int steps) 假设它的功能就是:可以计算出青蛙跳到steps级台阶有多少种跳法
假设青蛙第一次跳了1级那么剩下的跳法就是frogJumps(n-1)
假设青蛙第一次跳了2级那么剩下的跳法就是frogJumps(n-2)
所以所有的跳法就是frogJumps(n-1) + frogJumps(n-2) 当n>=3
只要有了递推公式递归的代码其实很容易写出来

int frogJumps(int steps)
{if (steps <= 2)return steps;elsereturn frogJumps(steps - 1) + frogJumps(steps - 2);
}int main()
{printf("%d ", frogJumps(1));printf("%d ", frogJumps(2));printf("%d ", frogJumps(3));printf("%d ", frogJumps(4));printf("%d ", frogJumps(5));return 0;
}

动态规划

不管是用递归计算n! 还是递归求第n个斐波那契数量
递归代码虽十分简洁但是有一个很严重的问题:递归很容易产生大量的重复计算
但是实际上:

在计算10!的时候就已经产生9! 8! 7!..了
在计算第40个斐波那契数的时候前面的斐波那契数其实也都已经计算过了
那么该怎么把这些已经计算过的子问题给利用起来帮助计算下一个子问题呢?

这就引出了动态规划的一个典型的思想:利用上一步的计算结果快速计算出下一步的结果
下面可以看看动态规划会怎么计算这道题:

台阶的级数n和几种跳法其实是一一对应的 --> 数组

#define N 10
int main()
{int arr[N] = { 0 };arr[0] = 1;arr[1] = 2;//前两个子问题的解直接给出//从第三个子问题开始(i=2) 计算得出for (int i = 2; i < N; i++)arr[i] = arr[i - 1] + arr[i - 2];//当循环结束 其实数组里已经放好了1~N级台阶对应的跳法for (int i = 0; i < N; i++)printf("青蛙跳上%d级台阶有%d种跳法\n", i + 1, arr[i]);return 0;
}

迭代

● 尝试用while改写(和斐波那契一样的) 因为n很大的时候递归效率太差
● 求n个台阶有几种跳法其实就相当于求第n个"斐波那契数"
● 核心在于while的循环条件是什么

int Fib(int index)
{//如果index 1 2 直接返回即可if (index <= 2)return index;//如果能走到这里 就说明index>=3了 那就计算求出第index个数(也就是index级台阶有几种跳法)int a = 1;int b = 2;int tmp = 0;while (index >= 3)//3级 循环1次 把tmp返回;4级 循环2次 把tmp返回....{tmp = a + b;a = b;b = tmp;index--;}return tmp;
}int main()
{printf("%d\n", Fib(1));printf("%d\n", Fib(2));printf("%d\n", Fib(3));printf("%d\n", Fib(4));printf("%d\n", Fib(5));printf("%d\n", Fib(6));printf("%d\n", Fib(7));printf("%d\n", Fib(8));printf("%d\n", Fib(9));printf("%d\n", Fib(10));return 0;
}