02月
08

发表于 • 字数统计 1167 • 被 131 人看爆

题目说明

汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

分析

典型的递归问题，就很绕的感觉。当有n个圆盘是，把问题转化为把上面n-1个圆盘移到第二根柱子，再把最大的圆盘移到第三根柱子。最后将n-1个圆盘移动到第三根柱子上。

  1. 目标：把A柱子上的N个盘子移动到C柱子
  2. 递归的思想就是把这个目标分解成三个子目标
  3. 子目标1：将前n-1个盘子从a移动到b上（借助c）
  4. 子目标2：将最底下的最后一个盘子从a移动到c上（直接移动）
  5. 子目标3：将b上的n-1个盘子移动到c上（借助a）
  6. 然后每个子目标又是一次独立的汉诺塔游戏，也就可以继续分解目标直到N为1

递归的理解

递归就是函数中调用函数本身的情况，比如

//阶乘
int factorial(int n)
{
    if(n <= 1)
        return 1;
    else
    {
        return (n * factorial(n-1));
    }
}

题解

c solution

可直接运行代码

#include <iostream>
using namespace std;
//目标是A->C
void hanoi(int N ,char A , char B ,char C)
{
    if(N == 1)
        cout << A << "-->" << C << endl ;
    else
    {
        hanoi(N-1 , A , C , B) ;
        cout << A << "-->" << C << endl ; //==hanoi(1,a,b,c)
        hanoi(N-1 , B , A , C) ;
    }
}
int main()
{
    int n;
    cout << "输入盘子的个数:";
    cin >> n;
    cout << "移动过程如下" << endl;
    cout << "-----------" << endl;
    hanoi(n, 'A' , 'B' , 'C') ;
    return 0;
}

python solution

def move(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        move(n-1, a, c, b)  # 子目标1
        move(1, a, b, c)    # 子目标2
        move(n-1, b, a, c)  # 子目标3
n = input('enter the number:')
move(int(n), 'A', 'B', 'C')
分享到：