IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> 【C语言】递归汉诺塔 -> 正文阅读

[C++知识库]【C语言】递归汉诺塔

在这里插入图片描述

一、预备知识

问题一:什么是递归?

程序调用自身的编程技巧称为递归( recursion)。

问题二:递归有什么用?

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,是一种把大事化小的思想,递归思想只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

简单来说,递归就是把一件大事情中重复的小事情看成是一种事情,然后我们只需要重复完成这个小事情就可以了。

举个例子:
生活中洋葱,俄罗斯套娃都算是一种递归现象

二、汉诺塔

汉诺塔相信大家没听过也玩过:
在这里插入图片描述
在这个图中,把第一个柱子上的三个圆盘都移动到另一个柱子上
而且有如下规则:

  1. 每一次只能移动一个圆盘。
  2. 每一根柱子上放置的圆盘从上往下看都是由小到大的,即不能把比自己大的圆盘放在小圆盘上面。

这是一个简单的益智游戏,你也可以在网站上玩到这个游戏。

这样一看似乎不难,但随着圆盘数量的增加往往会导致很多人都无法快速的完成这个游戏。而各个不同的圆盘数量,移动最少次数完成就是一个2的n次方减一(2^n-1)。

而这个诀窍,可以简单介绍为:

这里为了方便说明给3个圆盘标上abc,假设起始圆盘都在a。

1.当圆盘数量是奇数时,第一个圆盘直接放去c,当圆盘数量是偶数时,第 一层要先放b。

2.整体的思路就是
先把n-1(n为总圆盘数)个圆盘借助c由a放到b上。
然后把最后一个圆盘套到c上。
最后把n-1个圆盘借助a由b转到c上。

会上面两个要点,即使不是最少步数过关,也可以很快。

三、c语言实现

那C语言中如何实现这种递归呢?

我们可以参考我们上面汉诺塔的思路

//首先定义一个move函数,设n为我们需要移动的圆盘数

void move(int n, char a, char b, char c)
{
	if (n == 1)
	{
		printf("%c->%c\n", a, c);//第一层的移法
	}
	else
	{
		move(n - 1, a, c, b);//把前面n-1层由a移动到b
		printf("%c->%c\n", a, c);//把最底面一层由a移动到c
		move(n - 1, b, a, c);//把前面n-1层由b移动到c

      //像这里,在move函数里面调用move函数就是递归。
	}
}

当移动块数是1的时候,就直接由a到c就可以了,然后当n>1的时候,就要先把n-1由a全移动到b,再把最后一个铺底的放在c上,然后再把b的全部移动到c上。

设计完递归函数不要忘了主函数:

//设一个主函数
int main()
{
    int n;//圆盘数
	printf("请输入圆盘块数:>");
	scanf("%d", &n);
	printf("移动方法为:\n");
	move(n, 'a', 'b', 'c');//调用move函数

    return 0;

}

四、完整代码

以下就是这个汉诺塔问题的完整代码:

//abc是三根柱子

#include <stdio.h>

void move(int n, char a, char b, char c)
{
	if (n == 1)
	{
		printf("%c->%c\n", a, c);//第一层的移法
	}
	else
	{
		move(n - 1, a, c, b);//把前面n-1层由a移动到b
		printf("%c->%c\n", a, c);//把最底面一层由a移动到c
		move(n - 1, b, a, c);//把前面n-1层由b移动到c
	}
}

int main()
{
    int n;
	printf("请输入圆盘块数:>");
	scanf("%d", &n);
	printf("移动方法为:\n");
	move(n, 'a', 'b', 'c');
    
    return 0;
}

  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现(C语言)
C++PrimerPlus 第七章 函数-C++的编程模块(
Problem C: 算法9-9~9-12:平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇(六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2021-07-26 11:53:50  更:2021-07-26 11:56:03 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/25 15:51:23-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计