Skip to main content

汉诺塔问题

December 6, 2018   

题面

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

自己汉诺塔问题晕了很久,但搜索写多了至少也有一些通悟


不妨假设:

  • 当只有

    1个盘子
    

    1. 把盘子从A直接移到C
  • 当只有

    2个盘子
    

    1. 将上面的盘子从A移动到B
    2. 将下面的盘子从A移动到C
    3. 将B上的盘子从B移动到C
  • 当有

    3个盘子
    

    1. 将上面的盘子从A移动到C
    2. 将中间的盘子从A移动到B
    3. 将C上的盘子从C移动到B
    4. 将下面的盘子从A移动到C
    5. 将B上面的盘子从B移到A
    6. 将B上的盘子从B移到C
    7. 将A上的盘子从A移到C

可以发现当有3个盘子时,中间就会转化成2个盘子的情况,2个盘子最后就会转化成1个盘子的情况,显然可采用递归的方法

思路

n-1个盘子移到B,再把最下面的盘子移到C,再把B上的n-1个盘子移到C

#include <iostream>
#include <cstdio>
using namespace std;

int ans,n;

void dfs(int x,int a,int b,int c)// num from  trans   end
{
    if(x==1)
    {
        printf("move from %d to %d\n",a,c);
        ans++;
     	return;   
    }
    dfs(x-1,a,c,b);
    printf("move from %d to %d\n",a,c);
    ans++;
    dfs(x-1,b,a,c);
}

int main()
{
    scanf("%d",&n);
    dfs(n,1,2,3);
    printf("need %d steps\n",ans);
	return 0;
}

自己遇到的坑

  • a,b,c三个柱子没有搞清楚,递归函数里到底四个参数分别代表什么要搞清楚

其他一些……

  • f[n]=f[n-1]*2+1

    本次的次数就等于把n-1个盘子移动了两回,加上剩下的最大的盘子移动的一次