• 首页

  • 文章归档

  • 友链

  • 关于页面
D u e l s , I S h e e p !
D u e l s , I S h e e p !

ISheep

Code for fun, Make world better

02月
08
大学课程

DS-汉诺塔

发表于 2020-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')
分享到:
DS-八皇后问题
DS-线性表
  • 文章目录
  • 站点概览
ISheep

🐏 ISheep

放羊么?

Github Twitter Email Telegram RSS
看爆 Top5
  • 2020年终总结 538次看爆
  • 【转载】 2010年的房地产调控,我们收获了什么?写在房价暴涨前 423次看爆
  • 正则表达式入门 415次看爆
  • 搬家 408次看爆
  • 二〇二一 · 迷茫 、恐慌 368次看爆

站点已萌萌哒运行 00 天 00 小时 00 分 00 秒(●'◡'●)ノ♥

Copyright © 2022 ISheep 浙ICP备19046944号

由 Halo 强力驱动 · Theme by Sagiri · 站点地图