C语言:青蛙跳台与汉诺塔问题

简介: 原理:一只青蛙跳n个台阶,青蛙可以一次性跳1个台阶,也可以跳2个台阶,问,有多少种跳法,可以跳过n个台阶。分析:青蛙跳台本质上是递归问题,那它为什么是递归问题呢?

 青蛙跳台

jgnu0vkn.png

原理:一只青蛙跳n个台阶,青蛙可以一次性跳1个台阶,也可以跳2个台阶,问,有多少种跳法,可以跳过n个台阶。

分析:青蛙跳台本质上是递归问题,那它为什么是递归问题呢?

①假如有一个台阶,那青蛙只有一种跳法。

②假如有两个台阶,青蛙有两种跳法,1.一个一个台阶跳。2.跳两个台阶

③假如有三个台阶,青蛙有三种跳法,1.一个一个台阶跳。2.一次跳两个台阶再跳一个台阶。3.一次跳一个台阶再跳两台阶。

④假如有四个台阶,青蛙有五种跳法(这里就不再推啦,有兴趣的小伙伴可以推一推)

⑤假如有五个台阶,青蛙有九种跳法(这里就不再推啦,有兴趣的小伙伴可以推一推)


666ba2d04b9c4257afa3cd5e85f7fb4a.png


#include<stdio.h>
int frog_diving_tower(int n)
{
  if (n == 1)
  {
    return 1;
  }
  if (n == 2)
  {
    return 2;
  }
  return frog_diving_tower(n - 1) + frog_diving_tower(n - 2);
}
int main()
{
  int n = 0;
  printf("请输入台阶个数:");
  scanf("%d", &n);
  int ret = frog_diving_tower(n);
  printf("一共有%d种跳法",ret);
  return 0;
}


升华:一只青蛙跳n个台阶,青蛙可以一次性跳1个台阶,也可以跳2个台阶,也可以跳3个台阶,问,有多少种跳法,可以跳过n个台阶。


#include<stdio.h>
int frog_diving_tower(int n)
{
  if (n == 1)
  {
    return 1;
  }
  if (n == 2)
  {
    return 2;
  }
  if (n == 3)
  {
    return 3;
  }
  return frog_diving_tower(n - 1) + frog_diving_tower(n - 2) + frog_diving_tower(n - 3);
}
int main()
{
  int n = 0;
  printf("请输入台阶个数:");
  scanf("%d", &n);
  int ret = frog_diving_tower(n);
  printf("一共有%d种跳法",ret);
  return 0;
}


注释:不难看出其中的规律,只要改动int frog_diving_tower(int n)这个函数就行。


屏幕截图 2023-06-19 145130.png


原理:有三个柱子A,B,C,而A柱上有n个圆盘,要求把A柱的圆盘放在C盘上,并且要求小的圆盘放在大的圆盘上,问:A柱上的n个圆盘放在C盘上,需要移动多少次,求最小次数。

分析:汉诺塔问题本质上还是递归问题,那它为什么是递归问题呢?

①假如有一个圆盘:需要移动1次。A-C。

②假如有两个圆盘:需要移动3次。A-B,A-C,B-C

③假如有三个圆盘:需要移动7次。A ->C,A->B,C->B,A->C,B->A,B->C,A->C


屏幕截图 2023-06-19 145924.png

1683443499141


2d6d4437ed8e43f692641037e5940bd6.png


注意:

f3c7095dbe814eba9b112d0dabfe787c.png


代码实现

//这里one是A柱
//这里two是B柱
//这里there是C柱
#include<stdio.h>
void move(char x, char y)
{
  printf("%c->%c ", x, y);//这里模拟圆盘移动过程 
}
void hanoi(int n, char one, char two, char three) 
{
  if (n == 1)
    move(one, three);
  else
  {
    hanoi(n - 1, one, three, two); //将A柱上n-1个盘子移到B柱上(借助 C)
    move(one, three);              //将A柱上剩下的1个盘子移到C柱上
    hanoi(n - 1, two, one, three); //将B柱上n-1个盘子移到C柱上(借助 A)
  }
}
int main()
{
  int n = 0;
  printf("请输入圆盘个数:");
  scanf("%d", &n);
  hanoi(n, 'A', 'B', 'C');  
  return 0;
}


不知不觉就到了尾声啦,作为小白的我,可能写的不是很好,不对的地方还请各位小伙伴留言给我谢谢啦。


目录
相关文章
|
C语言
c语言汉诺塔
c语言汉诺塔
108 0
|
3月前
|
机器学习/深度学习 C语言
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
要保持最小的步数,每一次汉诺塔问题(无论是最初还是递归过程中的),如果此时初始柱盘子数为偶数,我们第一步是把最上面的盘子移动到中转柱,如果为奇数,我们第一步则是将其移动到目标柱。
78 0
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
|
6月前
|
C语言
C语言递归问题【青蛙跳台阶】和【汉诺塔】
C语言递归问题【青蛙跳台阶】和【汉诺塔】
|
5月前
|
C语言
【c语言】汉诺塔问题详解(c语言递归函数)
【c语言】汉诺塔问题详解(c语言递归函数)
61 0
|
6月前
|
C语言
汉诺塔————经典递归问题(C语言实现)
汉诺塔————经典递归问题(C语言实现)
134 0
|
6月前
|
C语言
【C语言】汉诺塔 —— 详解
【C语言】汉诺塔 —— 详解
|
C语言
C语言经典题目之 汉诺塔问题
C语言经典题目之 汉诺塔问题
79 0
|
6月前
|
C语言
C语言解决汉诺塔问题
C语言解决汉诺塔问题
62 0
|
6月前
|
算法 C语言
C语言汉诺塔数列(循环版,递归版)
C语言汉诺塔数列(循环版,递归版)
70 0
|
C语言
【C语言刷题】汉诺塔问题
【C语言刷题】汉诺塔问题
58 1