文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-04-02 19:55

关注

一、青蛙跳台阶

题目

一只青蛙一次可以跳上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 语言实现青蛙跳台阶和汉诺塔内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯