【C 语言基础】青蛙跳台阶和汉诺塔问题

迈不过友情╰ 2021-09-13 18:50 273阅读 0赞

### 文章目录 ###

*   *  青蛙跳台阶
     *   *  题目
         *  思路
         *  分析
         *  1. 从跳法次数分析
         *   *  代码1（递归）
         *  2. 从过程分析
         *   *  代码2（非递归）
     *  青蛙跳台阶变式1
     *   *  题目
         *  分析
         *   *  代码3（递归）
     *  青蛙跳台阶变式2
     *   *  题目
         *  分析
         *   *  代码4（递归）
     *  汉诺塔问题（求步数）
     *   *  题目
         *  思路
         *  分析
         *   *  代码5（非递归）
             *  代码6（递归）
     *  汉诺塔问题（求移动过程）
     *   *  题目
         *  思路
         *  分析
         *   *  代码7（递归）
     *  结语

## 青蛙跳台阶 ##

### 题目 ###

> 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法

### 思路 ###

> 遇见题目我们可以在纸上先动手画画，把最简单的几种方式列出来，作比较，找规律。

### 分析 ###

> 按照上面表格可以从跳法次数，过程，或者两者结合找规律

### 1. 从跳法次数分析 ###

>  *  观察表格，可以知道从n>=3时，第n个数就是前两个数的和（与斐波那契数列一样）
>  *  我们自己推论，当台阶数为n时，设跳法有f(n)次，如果青蛙先跳1阶，则剩下的台阶数为n-1，即剩余跳法有f(n-1)次；如果青蛙先跳2阶，则剩下的台阶数为n-2，即剩余跳法有f(n-2)次。
>  *  故跳法次数f(n)=f(n-1)+f(n-2)，因为等号右边有两个值，故当n=1，n=2时为最后的特殊限制条件
>  *  下面代码为递归求法，如果想用非递归，可以将递归通项改成循环

#### 代码1（递归） ####

#include <stdio.h>
    int jump(int n)
    { 
    	if (n == 1)
    		return 1;
    	if (n == 2)
    		return 2;
    	return jump(n - 1) + jump(n - 2);
    }
    int main()
    { 
    	int n;
    	scanf("%d", &n);
    	int ret = jump(n);
    	printf("%d", ret);
    	return 0;
    }

### 2. 从过程分析 ###

>  *  观察表格，可以知道，跳n阶台阶，跳两阶台阶次数可以为0到n/2次，而每一次跳两阶台阶的顺序也是不定的。可以通过计数原理的组合数C(n，m)，表示从n个数中选m个数排列。n表示每次需要跳的次数，m表示一次跳两阶的次数
>  *  组合数C(n，m)，可以由n！/(m！\*(n-m)！)求得
>  *  下面代码为非递归求法，如果想要写成递归，可以根据循环修改

#### 代码2（非递归） ####

#include <stdio.h>
    int fac(int m)
    { 
    	int i = 0;
    	int count = 1;
    	for (i = 1; i <= m; i++)
    	{ 
    		count *= i;
    	}
    	return count;
    }
    int jump(int n)
    { 
    	int i = 0;						//i为跳两阶台阶的次数
    	int sum = 0;					//sum为计算跳法
    	for (i = 0; i <= n / 2; i++)
    	{ 
    		int a = 0;
    		a = n - i * 2 + i;			//a为跳到n阶台阶跳的次数 
    		sum += fac(a) / (fac(i)*fac(a - i));
    	}
    	return sum;
    }
    int main()
    { 
    	int n;
    	scanf("%d", &n);
    	int ret = jump(n);
    	printf("%d", ret);
    	return 0;
    }

## 青蛙跳台阶变式1 ##

### 题目 ###

> 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶…也可以跳n级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法

### 分析 ###

>  *  根据原题推论，当台阶数为n时，设跳法有f(n)次，如果青蛙先跳1阶，则剩下的台阶数为n-1，即剩余跳法有f(n-1)次；如果青蛙先跳2阶，则剩下的台阶数为n-2，即剩余跳法有f(n-2)次。
>  *  那么当青蛙跳3阶台阶，则剩下的台阶数为n-3，即剩余跳法有f(n-3)次…当青蛙跳n阶台阶，则剩下的台阶数为n-n，即剩余跳法有f(n-n)次
>  *  故跳法次数f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-n)
>  *  由推论可得f(n-1)=f(n-2)+f(n-3)…+f(n-n)，将其代入上面式子
>  *  故跳法次数为f(n)=2\*f(n-1)，因为等号右边只有一个值，故n=1为最后的特殊限制条件

#### 代码3（递归） ####

#include <stdio.h>
    int jump(int n)
    { 
    	if (n == 1)
    		return 1;
    	return 2*jump(n - 1);
    }
    int main()
    { 
    	int n;
    	scanf("%d", &n);
    	int ret = jump(n);
    	printf("%d", ret);
    	return 0;
    }

## 青蛙跳台阶变式2 ##

### 题目 ###

> 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶…也可以跳m级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(m<=n)

### 分析 ###

>  *  根据变式1推论得f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-n)
>  *  而这里最多一次只能跳m阶，故f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-m)
>  *  由推论得f(n-1)=f(n-2)+f(n-3)…+f(n-m)+f(n-m-1)，代入上面式子
>  *  故跳法次数为f(n)=2\*f(n-1)-f(n-m-1)
>  *  因为通过递归n的值在减少，当n<m时，其实最多就只能跳n阶，与变式1就是一样的问题了

#### 代码4（递归） ####

#include <stdio.h>
    int jump(int n,int m)
    { 
    	if (n > m)
    		return 2 * jump(n - 1, m) - jump(n - 1 - m, m);
    	else
    	{ 
    		if (n == 1)
    			return 1;
    		return 2 * jump(n - 1, n);
    	}
    }
    int main()
    { 
    	int n, m;
    	scanf("%d%d", &n, &m);
    	int ret = jump(n,m);
    	printf("%d", ret);
    	return 0;
    }

## 汉诺塔问题（求步数） ##

### 题目 ###

> 有A，B，C三个柱子，A柱子上从上到下，从小到大排列着n个圆盘。现要求将A柱子上的n个圆盘全部移动到C柱子上，依然按照从上到下，从小到大的顺序排列。且对移动过程要求如下：
> 
> a）一次只能移动一个盘子。
> 
> b）移动过程中大盘子不允许出现在小盘子上方。
> 
> 问：总共需要移动的步数是多少？

### 思路 ###

> 因为求的是步数，我们可以通过找前面几组数据，观察是否有什么规律

### 分析 ###

>  *  通过表格观察，可以知道盘子数为n时，步数为20\+21\+…+2n-1，即2n\-1
>  *  我们可以通过下面这张图片来推论：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTM2Nzg0NQ_size_16_color_FFFFFF_t_70]
>  *  假设盘子数量为n，通过化繁为简思想，我们可以把盘子分成两个部分。上面n-1个盘子，和最下面一个盘子。移动步骤如下：
>     
>     1.  将最上面的n-1个盘子移动到B柱上
>     2.  将最下面的盘子移动到C柱上
>     3.  再将B柱上的n-1个盘子移动到C柱上
>  *  问题转化成如何移动最上面n-1个盘子。按照上面的思路解决n-1个盘子移动的问题。
>  *  假设移动n个盘子需要的步数为f(n)，则移动n-1个盘子需要f(n-1)步。
>  *  故移动步数为f(n)=f(n-1)+1+f(n-1)，即**f(n)=2\*f(n-1)+1**
>  *  通过等比数列变形又可以得到f(n)=2n\-1

#### 代码5（非递归） ####

#include <stdio.h>
    #include <math.h>
    int main()
    { 
    	int n;
    	scanf("%d", &n);
    	int count =0;
        count=(int)pow(2,n)-1;
    	printf("%d", count);
    	return 0;
    }

#### 代码6（递归） ####

#include <stdio.h>
    int tower(int n)
    { 
    	if (n == 1)
    		return 1;
    	else
    		return 2 * tower(n - 1) + 1;
    }
    int main()
    { 
    	int n;
    	scanf("%d", &n);
    	int ret=tower(n);
    	printf("%d", ret);
    	return 0;
    }

## 汉诺塔问题（求移动过程） ##

### 题目 ###

> 有A，B，C三个柱子，A柱子上从上到下，从小到大排列着n个圆盘。现要求将A柱子上的n个圆盘全部移动到C柱子上，依然按照从上到下，从小到大的顺序排列。且对移动过程要求如下：
> 
> a）一次只能移动一个盘子。
> 
> b）移动过程中大盘子不允许出现在小盘子上方。
> 
> 问：打印移动的方案 (例如, 移动A柱最上面的圆盘到C柱, 则输出"A -> C")

### 思路 ###

> 因为求的是移动方案，所以我们可以将前几组数据列出来，结合递归化简为繁的思想找共性和非共性

### 分析 ###

>  *  通过观察得到：除了n=1，n>1时，都是先将A柱上面n-1个盘子拿到B柱（粗字体为其过程），再将A柱最下面盘子拿到C柱。此时A柱变成辅助柱，再将B柱上的盘子放到C柱
>  *  故将A柱最下面盘子移到C柱为**中间过程**
>  *  **上一步**为将初始柱（A柱）上面n-1个盘子借助辅助柱（C柱）移到目标柱（B柱）【其实可以这里看作单独一个n-1的汉诺塔，将A柱上的盘子移动到B柱】
>  *  **下一步**为将初始柱（B柱）上面n-1个盘子借助辅助柱（A柱）移到目标柱（C柱）【其实可以这里看作单独一个n-1的汉诺塔，将B柱上的盘子移动到C柱】
>  *  而上一步，中间过程，下一布就是递归的**核心思想**
>  *  而当n=1时，盘子数只有一个，我们将其直接放到目标柱即可（其为最**终的限制条件**）
>  *  初始柱，辅助柱，目标柱，其实就是把该步骤的移动过程当作一个单独的汉诺塔问题，需要移动盘子现在所在的位置为初始柱，要将其放到的位置就是目标柱

#### 代码7（递归） ####

#include <stdio.h>
    void hanio(int n, char x, char y, char z)
    { 
    	if (n == 1)
    		printf("%c->%c\n",x,z);		//当盘子只剩一个时，直接打印初始柱移动到目标柱的过程
    	else
    	{ 
    		hanio(n - 1, x, z, y);		//将n-1个盘子从起始柱放到目标柱(第一次A->B，第二次B->A，后面往复)
            
    		printf("%c->%c\n", x, z);	//打印初始柱移动到目标柱的过程
            
    		hanio(n - 1, y, x, z);		//将n-1个盘子从起始柱放到目标柱(第一次B->C，第二次C->B，后面往复)
    	}
    }
    int main()
    { 
    	int n;
    	scanf("%d", &n);
    	hanio(n,'A','B','C');
    	return 0;
    }

## 结语 ##

>  *  以上青蛙跳台阶和汉诺塔问题主要是围绕讲解**递归思想**，如果不太理解递归，可以浏览上一章[第六章 C世界函数的故事（2）][C_2]进行查阅。
>  *  本次讲解，不乏其中有很多漏洞和不足，如果大家觉得哪里不好，可以评论给我指正，希望和大家一起进步。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTM2Nzg0NQ_size_16_color_FFFFFF_t_70]: /images/20210913/fdf65fda7b594013b70be4bac1a82db9.png
[C_2]: https://blog.csdn.net/weixin_51367845/article/details/115975440?spm=1001.2014.3001.5501