C 语言基础实现青蛙跳台阶和汉诺塔问题
一、青蛙跳台阶
题目
一只青蛙一次可以跳上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
- 我们可以通过下面这张图片来推论:
- 假设盘子数量为n,通过化繁为简思想,我们可以把盘子分成两个部分。上面n-1个盘子,和最下面一个盘子。移动步骤如下:
- 将最上面的n-1个盘子移动到B柱上
- 将最下面的盘子移动到C柱上
- 再将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 语言基础实现青蛙跳台阶和汉诺塔问题的文章就介绍到这了,更多相关C 语言实现青蛙跳台阶和汉诺塔内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了R语言作图:坐标轴的设置方式,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了R语言删除指定变量或对象的操作方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- 这篇文章主要介绍了c++中system("pause")的作用和含义,非常不错,具有参考借鉴价值,需要的朋友参考下吧...2020-04-25
- 这篇文章主要介绍了Go语言压缩和解压缩tar.gz文件的方法,实例分析了使用Go语言压缩文件与解压文件的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-05-03
基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍 的相关资料,需要的朋友可以参考下...2016-05-14- 这篇文章主要介绍了R语言基本画图函数与多图多线的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
InterlliJ IDEA2020新建java web项目找不到Static Web的解决
这篇文章主要介绍了InterlliJ IDEA2020新建java web项目找不到Static Web的解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-09-02- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C#判断一个字符串是否是数字或者含有某个数字的方法,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 这篇文章主要介绍了C#类中static变量用法,实例分析了static变量使用技巧与相关注意事项,需要的朋友可以参考下...2020-06-25
- 这篇文章主要给大家介绍C# winform快捷键设置技巧,涉及到C winform快捷键相关知识,对C winform知识感兴趣的朋友可以参考下本篇文章...2020-06-25
- 这篇文章主要介绍了基于Ionic3实现选项卡切换并重新加载echarts,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-09-24
- 最近项目不多忙,于是抽点时间巩固下切换窗口问题,感兴趣的朋友跟着小编一起学习吧...2020-06-25