【C】青蛙跳台阶和汉诺塔问题(递归)

简介: 【C】青蛙跳台阶和汉诺塔问题(递归)

前言

这篇博客总结递归当中俩个经典的问题,青蛙跳台阶和汉诺塔,用C语言实现!

一.青蛙跳台阶

题目:

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

解题思路:

n=1,跳一个台阶,只有一种跳法;


n = 2,先跳一个台阶,再跳一个台阶,或者直接跳俩个台阶,有俩种跳法;


n>2,青蛙跳第一次时,有俩种可能,即跳一个台阶或者跳俩个台阶,只需要将这俩种情况下的跳法加起来即可,用一个函数fib()实现求青蛙跳上一个 n 级的台阶总共有多少种跳法,那么结果为Fib(n - 1) + Fib(n - 2)。


用递归实现,

代码:

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

运行结果:

73d8c9be8b2a4960a39693770de0ac9a.png

二.汉诺塔

汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说。

大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照从大到小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移动一个圆盘。问应该如何操作?

题目:

这里我们实现这样一个过程,有A、B、C三个柱子,A柱上有n个盘子,将这n个盘子移动到C柱上,用代码实现移动过程并计算要进行多少次移动!

解题思路:

假如n=3,那么这三个盘子的移动过程如下:

8db972b3b76053252a74323344ec3c52.gif

首先将A上面的俩个盘子通过C移动到B;

73d8c9be8b2a4960a39693770de0ac9a.png

再将A上的盘子移动到C;

73d8c9be8b2a4960a39693770de0ac9a.png

再将B上的俩个盘子通过A移动到C;

73d8c9be8b2a4960a39693770de0ac9a.png

对于n个盘子,要将其通过B放到C上;

我们首先要实现A最下面的盘子放到C上,那么我们就先实现将A上面的n-1个盘子通过C放到B上,然后再将A上的最后一个盘子放到C上;

73d8c9be8b2a4960a39693770de0ac9a.png

再将A上的盘子移动到C;

73d8c9be8b2a4960a39693770de0ac9a.png

然后要实现将B上的盘子通过A放到C上,实现过程和上面类似,这个过程封装一个函数进行递归。


对于计算移动的次数,也可以用递归实现,思路如下:


当n = 1时,次数为1;


当n > 1时,


计算将n-1个盘子从A通过B移动到C的次数

将A上的最后一个盘子移动到C为一次

将B上的盘子(n-1个)通过A移动到C

还可以按如下规律去求次数:


次数为2 ^ n - 1;

代码实现:

#include<stdio.h>
#include<math.h>
void Hannoi(int n, char A, char B, char C)
{
  if (1 == n)
  {
    printf("%c->%c ", A, C);
  }
  if (n > 1)
  {
    Hannoi(n - 1, A, C, B);
    printf("%c->%c ", A, C);
    Hannoi(n - 1, B, A, C);
  }
}
int Count_hannoi(int n)
{
  if (1 == n)
    return 1;
  if(n > 1)
      return 2 * Count_hannoi(n - 1) + 1;
}
int main()
{
  printf("输入有几个盘子n = ");
  int n = 0;
  scanf("%d", &n);
  Hannoi(n, 'A', 'B', 'C');//打印移动过程
  /*printf("\n需要进行%d次移动\n", (int)pow(2,n) - 1);*/  //规律法
  printf("\n需要进行%d次移动\n", Count_hannoi(n));//递归法
  return 0;
}

运行结果:73d8c9be8b2a4960a39693770de0ac9a.png


目录
打赏
0
0
0
0
5
分享
相关文章
汉诺塔 递归问题
汉诺塔 递归问题
108 0
递归问题的实际运用:汉诺塔问题
递归问题的实际运用:汉诺塔问题
134 0
递归问题的实际运用:汉诺塔问题
汉诺塔?爬楼梯?斐波那契?知道递归就够了
汉诺塔?爬楼梯?斐波那契?知道递归就够了
115 0
【递归问题】——汉诺塔
【递归问题】——汉诺塔
238 0
【递归】青蛙跳台阶的变式题你还会吗?
【递归】青蛙跳台阶的变式题你还会吗?
145 0
【递归】青蛙跳台阶的变式题你还会吗?
【递归与回溯算法】汉诺塔与八皇后问题详解
文章目录 1 汉诺塔问题 1.1 汉诺塔问题概述 1.2 思路分析 1.3 代码实现(Java) 1.4 结果验证 2 八皇后问题 2.1 八皇后问题概述 2.2 思路分析 2.2.1 问题划分与分析 2.2.2 涉及到的数据结构分析 2.2.3 上下对角线与行列的关系 2.3 代码实现(Java) 2.4 结果验证
【递归与回溯算法】汉诺塔与八皇后问题详解
C#中汉诺塔问题的递归解法
百度测试部2015年10月份的面试题之——汉诺塔。 汉诺塔就是将一摞盘子从一个塔转移到另一个塔的游戏,中间有一个用来过度盘子的辅助塔。 百度百科在此。 游戏试玩在此。 用递归的思想解决汉诺塔问题就是分为两种情况: 第一种情况是只有一个盘子的情况,也就是最基本的情况,这种情况下,直接将该盘子从原始塔转移到目标塔即可胜利; 第二种情况是右n个盘子的情况,也就是普遍情况,这种情况下,要将除了最底下的那个盘子以外的(n-1)个盘子从原始塔转移到辅助塔,再把最底下的那个盘子(第n个盘子)从原始塔转移到目标塔,最后将辅助塔的(n-1)个盘子从辅助塔转移到目标塔。
1855 0