专栏首页开心的学习之路算法训练 Hanoi问题

算法训练 Hanoi问题

问题描述

  如果将课本上的Hanoi塔问题稍做修改:仍然是给定N只盘子,3根柱子,但是允许每次最多移动相邻的M只盘子(当然移动盘子的数目也可以小于M),最少需要多少次?   例如N=5,M=2时,可以分别将最小的2个盘子、中间的2个盘子以及最大的一个盘子分别看作一个整体,这样可以转变为N=3,M=1的情况,共需要移动7次。

输入格式

  输入数据仅有一行,包括两个数N和M(0<=M<=N<=8)

输出格式

  仅输出一个数,表示需要移动的最少次数

样例输入

5 2

样例输出

7 思路:        解题需要两步:1、转换成传统Hanoi问题    2、输出转换后的步数。        1、此Hanoi塔与传统Hanoi塔的关系为:把n个盘中的每m个想成一个整体,就变成了传统的只能一次移动一个盘的Hanoi问题,n / m (如果有余数则+1)的结果就成了传统Hanoi塔的盘子数;        2、分析传统Hanoi塔,假设初始状态盘子都在柱子A上,B为目标柱子,C为临时柱子,移动两个盘,需要3步(小盘--->C,大盘--->B,小盘---->B),移动三个盘,需要把前两个盘移动到柱子C,再将最大盘移到目标柱子,再把前两个盘移动到目标柱子,所以需要的步数为3(移两个盘)+ 1(移动最大盘) + 3(移两个盘) = 7步,移动四个盘,需要把前三个盘移动到柱子C,再把最大盘移动到目标柱子,再把前三个盘子移动到目标柱子,所以需要的步数为7 + 1 + 7 = 15步,依此类推。

#include <cstdio>

int Conver(int n, int m)
{
	if(n % m != 0)
		return n / m + 1;	
	else
		return n / m;
} 

int Hanoi(int n)
{
	if(n == 2)
		return 3;
	else
		return 2 * Hanoi(n - 1) + 1;
}

int main()
{
	int n, m, con, ans;
	scanf("%d%d", &n, &m);
	con = Conver(n, m);
	ans = Hanoi(con);
	printf("%d\n", ans);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法训练 Anagrams问题

    问题描述   Anagrams指的是具有如下特性的两个单词:在这两个单词当中,每一个英文字母(不区分大小写)所出现的次数都是相同的。例如,“Unclear”...

    AI那点小事
  • 小朋友学C语言(31):递归解决汉诺塔

    (一)汉诺塔介绍 汉诺塔(Hanoi Tower)问题是源于印度一个古老传说: 在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主...

    海天一树
  • 汉诺塔——各种编程范式的解决

      理解递归,汉诺塔(Tower of Hanoi)是个很适合的工具,不大不小,作为最开始递归的理解正合适。从而学习各种计算机语言乃至各种编程范式的时候,汉诺塔...

    窗户
  • Data Structures and Algorithms Basics(002): Recursion

    2,子集:包含重复元素的集合,求所有可能的子集组合。注意:子集个数比不重复的集合要少;

    用户5473628
  • 汉诺塔问题详解

       相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个...

    RAIN7
  • 奇技淫巧”话递归

    “To Iterate is Human, to Recurs,Divine.” --- L. Peter Deutsch “迭代是人,递归是神” 第一次见有人...

    itclanCoder
  • 入门任意一种编程语言所必须的几道习题

      每当学习一门计算机语言,我们也要做一些练习以便逐步熟悉。随着我们对这种编程语言本身支持的抽象手段理解的过程,以下这些问题,基本可以在几乎每门编程语言学习的过...

    窗户
  • 算法回顾--如何写递归?

    总之递归就是”装傻”的把原始的思路表现出来,不需要关心具体过程,只需要不停的缩小问题规模,然后答案自然就会被计算出来.

    屈定
  • [算法题] 汉诺塔问题

    问题描述 三个柱子,起初有若干个按大小关系顺序安放的盘子,需要全部移动到另外一个柱子上。移动规则:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 ...

    静默虚空
  • 学习笔记-小甲鱼Python3学习第二十

    ----------------------------分割线,哈哈哈----------------------------------

    py3study
  • 递归

    若尘_
  • 汉诺塔(问题以及扩展)

    汉诺塔问题(三柱及四柱)详解 汉诺塔问题-步数 关于步数 是个很简单的问题 高中大家都学过 可能也做过类似的题

    杨鹏伟
  • 蓝桥杯 试题 算法训练 加法运算

    你的表妹正在学习整数的加法,请编写一个程序来帮助她学习。该程序调用了一个函数GetTwoInts,由它来返回两个从键盘读入的100以内的整数,然后计算这两个整数...

    杨鹏伟
  • 递归与数学归纳法

    递归与数学归纳法(RMI):Recursion and mathematical induction

    LeviMaster
  • Day5、Python

    题目 汉诺塔 1、程序分析     Hanoi塔问题,算法分析如下,设A上有n个盘子(编号由上到下:1、2、3……、n)。A:初始塔,B:中转塔,...

    Jack_Cui
  • 《剑指offer》专题—算法训练 day02

    https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423?

    RAIN7
  • 《剑指offer》专题—算法训练 day01

      从今天起,博主开始了 《 剑指offer 》 系列 算法专题的学习,希望大家 跟随着博主一起,开始这段美妙的算法之旅…

    RAIN7
  • 关于面试总结5-python笔试题(递归)

    本篇继续收集一些常见的python笔试题,以基础知识为主,递归是面试最喜欢考的一个问题,不管是做开发还是测试,都无法避免考递归。本篇结合实际案例,讲下几种关于递...

    上海-悠悠
  • 人工智能导论 (二) - Methodologies of Knowledge Representation 知识表示方法

    ![](https://upload-images.jianshu.io/upload_images/4685968-478a076781ace9ce.png?...

    JavaEdge

扫码关注云+社区

领取腾讯云代金券