目录

                      一、青蛙跳台阶

                      题目

                      一只青蛙一次可以跳上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个盘子,和最下面一个盘子。移动步骤如下:
                      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 语言基础实现青蛙跳台阶和汉诺塔问题的文章就介绍到这了,更多相关c 语言实现青蛙跳台阶和汉诺塔内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com!