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

目录
  • 一、青蛙跳台阶
    • 题目
    • 思路
    • 分析
      • 1. 从跳法次数分析
      • 2. 从过程分析
  • 二、青蛙跳台阶变式1
    • 题目
    • 分析
  • 三、青蛙跳台阶变式2
    • 题目
    • 分析
  • 四、汉诺塔问题(求步数)
    • 题目
    • 思路
    • 分析
  • 五、汉诺塔问题(求移动过程)
    • 题目
    • 思路
    • 分析

一、青蛙跳台阶

题目

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

时间: 2021-09-14

C语言递归之汉诺塔和青蛙跳台阶问题

递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题.汉诺塔问题等,在研究递归问题时我们要注意三点: 1.递归的结束条件 2.递归在每次进行过程中,都得离条件越来越近 3.相邻两次递归调用之间的关联关系 汉诺塔问题: 有三根杆子A, B, C.A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆: 1.每次只能移动一个圆盘: 2.大盘不能叠在小盘上面,可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆,

C 语言基础之C语言的常见关键字

目录 ​1.auto 2.register 3.signed和unsigned 4.typedef 5.extern 6.拓展 首先我们简单的和这些关键字见见面(被高亮的关键字是今天要介绍的) 这其中有大家熟知的数据类型:int,char,float,double- 也有控制语句用到的:if,for,do- 还有一些就是今天主要介绍的关键字. 至于还有一些新增的关键字,以上表格未曾提到,大家如果想去了解,可自行查找. 个别术语介绍(可先跳过,后文如若遇到不懂,可回来了解) 自动变量:指的是局部作

C语言位运算符的具体使用

目录 布尔位运算符 移位运算符 对于更多紧凑的数据,C 程序可以用独立的位或多个组合在一起的位来存储信息.文件访问许可就是一个常见的应用案例.位运算符允许对一个字节或更大的数据单位中独立的位做处理:可以清除.设定,或者倒置任何位或多个位.也可以将一个整数的位模式(bit pattern)向右或向左移动. 整数类型的位模式由一队按位置从右到左编号的位组成,位置编号从 0 开始,这是最低有效位(least significant bit).例如,考虑字符值'*',它的 ASCII 编码为 42,相当

C语言指针笔试题全面解析

目录 前言 一.指针笔试题 1.题目如图: 2.题目如图: 3.题目如图: 4.题目如图: 5.题目如图: 6.题目如图: 7.题目如图: 8.题目如图: 总结 前言 通过8道指针笔试题的解析,可以充分的复习到指针的相关知识,并且题目中会结合许多之前的相关知识,希望通过本篇文章,对大家所学的知识进行一个复习. 提示:以下是本篇文章正文内容,下面案例可供参考 一.指针笔试题 1.题目如图: 逐条语句分析: ①.定义了一个大小为5的整型数组,并进行了初始化 ②.定义了一个整型指针变量ptr用来存放地

C语言 函数缺省参数详情

目录 一.函数简介 1.函数声明 2.函数定义 3.函数调用 4.函数形参和实参 二.函数缺省参数 1.函数全缺省参数 2.函数半缺省参数 三.注意事项 一.函数简介 1.函数声明 函数声明只是一个空壳,不会有具体的函数实现,而定义要实现函数的实现,例如: int sub(int x,int y); //只需要声明即可,不需要实现这个函数的功能 2.函数定义 函数的定义需要实现这个函数的功能,例如: int sub(int x,int y) ////需要实现这个函数的功能 { return (x

C语言中的常量详解

目录 C语言中的常量 字面常量 #define定义的标识符常量 枚举常量 C语言中的常量 C编程中的常量是一些固定的值,它在整个程序运行过程中无法被改变. 字面常量 字面常量是直接写出的固定值,它包含C语言中可用的数据类型,可分为整型常量,字符常量等.如:9.9,"hello"等就属于这一类常量. ##const修饰的常变量 有的时候我们希望定义这么一种变量:值不能被修改,在整个作用域中都维持原值.为了满足用户需求,C语言标准提供了const关键字.在定义变量的同时,在变量名之前加上c

C语言:陷阱与缺陷详解

目录 一.前言 二.字符指针 三.边界计算与不对称边界 1.经典错误① 2.经典错误② 3.小结 四.求值顺序 五.运算符&& ||和! 总结 一.前言 二.字符指针 结论一:复制指针并不会复制指针所指向的内容.两个指针所指向位置相同,实际为同一个指针. 结论而:开辟两个数组,即使两个数组内容相同,地址也绝不相同. 三.边界计算与不对称边界 1.经典错误① int main() { int i = 0; int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,

C语言字符串的模式匹配之BF与KMP

目录 BF算法(Brute-Force算法) KMP算法(快速的) KMP-yxc模板 总结 确定一个子串(模式串)在主串中第一次出现的位置. BF算法(Brute-Force算法) BF算法即朴素的简单匹配法,采用的是穷举的思路.从主串的每一个字符开始依次与模式串的字符进行比较. int index_BF(SeqString S, SeqString T, int begin)//从S的第begin位(下标)开始进行匹配判断 { int i = begin, j = 0; while (i <

C 语言基础之初识 C 语言常量

目录 1.字面常量 2.const修饰的常变量 3.#define定义的标识符常量(也叫预处理) 4.枚举常量 C语言中的常量分为以下几种: 字面常量 const修饰的常变量 #define定义的标识符常量 枚举常量 1.字面常量 即字面意思不能改变的量.如1就是1,你不能说让1等于2:如人的血型有固定的几种(A,B,O,AB):如人的性别也只分为男性,女性,以及更深奥的一种形态. 在C语言中:1,3.14,'a',"hello"-这些都叫做常量. 2.const修饰的常变量 可以通过

C 语言基础之C 语言三大语句注意事项

目录 1.分支语句 2.if语句 3.switch语句 3.1语句结构 4.循环语句 4.1 while循环(do while类似) 4.2 do while循环 4.3 for循环 5.goto语句 在今天的内容介绍之前我们要知道:C语言中,由一个分号( ; )隔开的就是一条语句. 很好理解,如: int a=3;//语句1 printf("请大家多多指教!");//语句2 ;//语句3----空语句 今天讲解的内容,则是自己对于这三种语句一些细节的介绍.(并不是具体讲解这些语句)

关于C语言 const 和 define 区别

目录 一.const 使用 1.const 修饰变量 2.const 修饰指针 3.const 修饰在函数名前面当 4.const 修饰在函数名后面 5.const 修饰函数参数 二.define 使用 1.define 定义常量 2.define 定义函数 3.define 定义多行函数 4.define 防止头文件重复包含 三.const 和 define 区别 四.const 优点 一.const 使用 const 是 constant 的缩写,"恒定不变"的意思.被 const

解析php中static,const与define的使用区别

define部分:宏不仅可以用来代替常数值,还可以用来代替表达式,甚至是代码段.(宏的功能很强大,但也容易出错,所以其利弊大小颇有争议.)宏的语法为:#define 宏名称 宏值作为一种建议和一种广大程序员共同的习惯,宏名称经常使用全部大写的字母.利用宏的优点:1)让代码更简洁明了当然,这有赖于你为宏取一个适当的名字.一般来说,宏的名字更要注重有明确直观的意义,有时宁可让它长点.2)方便代码维护对宏的处理,在编译过程中称为"预处理".也就是说在正式编译前,编译器必须先将代码出现的宏,用

C语言 strcpy和memcpy区别详细介绍

C语言 strcpy和memcpy区别详细介绍 PS:初学算法,开始刷leetcode,Rotate array的预备知识(写的代码Time Limit Exceed难过)于是百度高效算法,本篇作为预备知识. 1.strcpy和strncpy函数 这个不陌生,大一学C语言讲过,其一般形式为strcpy(字符数组1,字符串2)作用是将字符串2复制到字符数组1中去. EX: char str1[10]='',str2[]={"China"}; strcpy(str1,str2); strn

C++中const与#define的利弊分析

C++中const与#define的区别如下: 用#define MAX 255定义的常量是没有类型的,所给出的是一个立即数,编译器只是把所定义的常量值与所定义的常量的名字联系起来,define所定义的宏变量在预处理的时候进行替换,在程序中使用到该常量的地方都要进行拷贝替换: 用const float MAX = 255; 定义的常量有类型名字,存放在内存的静态区域中,在程序运行过程中const变量只有一个拷贝,而#define 所定义的宏变量却有多个拷贝,所以宏定义在程序运行过程中所消耗的内存

详解微信小程序中var、let、const用法与区别

微信小程序可以使用Javascript的最新ES6标准来开发所以微信小程序中var.let.const用法与区别可以视为Javascript ES6标准中var.let.const用法与区别 let命令 基本用法 ES6 新增了let命令,用来声明变量.它的用法类似于var,但是所声明的变量,只在let命令所在的代码块内有效. { let a = 10; var b = 1; } a // ReferenceError: a is not defined. b // 1 上面代码在代码块之中,分

从go语言中找&和*区别详解

*和&的区别 :& 是取地址符号 , 即取得某个变量的地址 , 如 ; &a*是指针运算符 , 可以表示一个变量是指针类型 , 也可以表示一个指针变量所指向的存储单元 , 也就是这个地址所存储的值 . 从代码中验证 : 先构建一个Rect类型 : 1. &是取地址符号, 取到Rect类型对象的地址 2. *可以表示一个变量是指针类型(r是一个指针变量): 3.*也可以表示指针类型变量所指向的存储单元 ,也就是这个地址所指向的值 4.查看这个指针变量的地址 , 基本数据类型直

C语言编程技巧 关于const和#define的区别心得

#define ASPECT_RATIO 1.653 编译器会永远也看不到ASPECT_RATIO这个符号名,因为在源码进入编译器之前,它会被预处理程序去掉,于是ASPECT_RATIO不会加入到符号列表中.如果涉及到这个常量的代码在编译时报错,就会很令人费解,因为报错信息指的是1.653,而不是ASPECT_RATIO.如果ASPECT_RATIO不是在你自己写的头文件中定义的,你就会奇怪1.653是从哪里来的,甚至会花时间跟踪下去.这个问题也会出现在符号调试器中,因为同样地,你所写的符号名不

解析php中const与define的应用区别

1.const用于类成员变量定义,一旦定义且不能改变其值.define定义全局常量,在任何地方都可以访问.2.define不能在类中定义而const可以.3.const不能在条件语句中定义常量 复制代码 代码如下: if (...) {     const FOO = 'BAR';    // invalid } but if (...) {     define('FOO', 'BAR'); // valid } 4.const采用一个普通的常量名称,define可以采用表达式作为名称. 复制

C语言中auto,register,static,const,volatile的区别详细解析

1)auto这个关键字用于声明变量的生存期为自动,即将不在任何类.结构.枚举.联合和函数中定义的变量视为全局变量,而在函数中定义的变量视为局部变量.这个关键字不怎么多写,因为所有的变量默认就是auto的. (2)register这个关键字命令编译器尽可能的将变量存在CPU内部寄存器中而不是通过内存寻址访问以提高效率. (3)static常见的两种用途:1>统计函数被调用的次数; 2>减少局部数组建立和赋值的开销.变量的建立和赋值是需要一定的处理器开销的,特别是数组等含有较多元素的存储类型.在一

理解PHP5中static和const关键字的区别

PHP5中加入了很多面向对象的思想,PHP5的面向对象比较接近Java的面向对象思想.我们这里对PHP5中的static和const关键字作用进行一下描述,希望对学习PHP5的朋友有帮助. (1) static static关键字在类中是,描述一个成员是静态的,static能够限制外部的访问,因为static后的成员是属于类的,是不属于任何对象实例,其他类是无法访问的,只对类的实例共享,能一定程序对该成员尽心保护.类的静态变量,非常类似全局变量,能够被所有类的实例共享,类的静态方法也是一样的,类

详解C语言中的#define宏定义命令用法

#define 命令#define定义了一个标识符及一个串.在源程序中每次遇到该标识符时,均以定义的串代换它.ANSI标准将标识符定义为宏名,将替换过程称为宏替换.命令的一般形式为: #define identifier string 注意: 1.该语句没有分号.在标识符和串之间可以有任意个空格,串一旦开始,仅由一新行结束. 2.宏名定义后,即可成为其它宏名定义中的一部分. 3.宏替换仅仅是以文本串代替宏标识符,前提是宏标识符必须独立的识别出来,否则不进行替换.例如: #define XYZ t