个人笔记|c语言初阶（2-函数—实战收尾篇-青蛙跳台阶-汉诺塔问题）实战|c语言|开发语言|后端|新人

因为这段时间比较忙，所以频率比较低，那么我们话不多说，直接进入正题：

目录
1.青蛙跳台阶
1.1问题描述：
1.2问题分析：
1.3算法实现
2.汉诺塔问题：
2.1问题描述
2.2问题分析
2.3算法实现

1.青蛙跳台阶 1.1问题描述：题目：一只青蛙一次可以跳1阶台阶，也可以跳2阶。求该青蛙跳上一个n 级的台阶总共有多少种跳法?
1.2问题分析：

由题意可简单分析：
到第1阶：1
到第2阶：1
到第3阶：2
到第4阶：3
到第5阶：5
......
到第n阶：（n-1）阶的跳法总数+（n-2）阶的跳法总数
如要跳到第三阶的话，要么从第一台阶跳两阶，要么从第二台阶跳一阶，因此到第三台阶的跳法总数就是到第一台阶的加上到第二台阶的。
我们发现1 1 2 3 5 8 13.....就是我们上篇讲过的裴波那契数列，因此思路一下子就清晰了。

1.3算法实现

#include //类比于斐波那契数列1 1 2 38 13 21 34 55 //递归方式速度慢求的过大时可能存在栈溢出--stack overflow//函数递归实现青蛙跳台阶问题的解决 int Jump1(int n) { if (n <= 2) { return n; } else { return Jump1(n - 1) + Jump1(n - 2); } } //使用循环解决问题 int Jump2(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 = 0; int ret = 0; printf("请输入台阶数:"); scanf_s("%d", &n); ret = Jump1(n); //递归函数 printf("递归法:有%d种跳法\n", ret); ret = Jump2(n); //循环函数 printf("循环法:有%d种跳法\n", ret); return 0; }

因为我们在上篇已经对斐波那契数列进行了分析，此处不再赘述

2.汉诺塔问题： 2.1问题描述
有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n）。

文章图片

可以去浏览器搜一下汉诺塔小游戏，尝试自己玩一下哦

2.2问题分析

如果n=1，则只需要把A柱的一个盘子放到c柱上
如果n=2，需要先把A柱的第一个盘子放到B柱，然后把A的第二个盘子放到c柱，最后把B的盘子移到c
当n>=3时，就把所有盘子分成两份，第一份是除最后一个盘子的所有盘子，第二份是最后一个盘子，如此，要把A全部挪到C时，首先把第一份挪到B上，然后把第二份挪到C上，最后把B上的第一份盘子挪到c上就行了
但实际上我们每次只能移动一个圆盘，因此我们对第一份圆盘的挪用作为问题，将它进行分解，子问题就是对每一个圆盘的移动，当圆盘个数为1时，直接将A上的原盘移动到C，以此作为递归出口，同次类似，然后使用递归将B上的所有盘子依次移动到C柱上即可。
问题的解决三步走战略：n-1->b; 1->c; n-1->c
递归出口——n==1,直接移动即可，无需进入递归

2.3算法实现

//汉诺塔递归问题： #pragma warning(disable:4996) #includevoid Move(char m, char n) { printf("移动%c -> %c\n", m, n); return; }void Hanoi(int n, char x, char y, char z) { //设置递归条件，当n=1时，只需将x上的最后一个盘子移动到z上即可 if (1 == n) { Move(x, z); } else { //第一步，把n-1个盘子从x移动到y Hanoi(n - 1, x, z, y); //第二步，把最后一个盘子从x柱移到z柱 Move(x, z); //第三步，把n-1个盘子从y柱移到z柱 Hanoi(n - 1, y, x, z); } }int main() { //汉诺塔问题的递归 //首先要有三个圆柱 char a = 'a', b = 'b', c = 'c'; //然后要有对应的盘子 int n; scanf("%d", &n); //调用函数实现递归 Hanoi(n, a, b, c); return 0; }