Hanoi

Hanoi

汉诺塔

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。它是一个非常著名的智力趣题,在很多算法书籍📕和智力竞赛中都有涉及。有A,B,C三根柱子,在A柱子上有n个大小不等的盘子,大盘在下,小盘在上。要求将所有盘子由A柱搬动到C柱上,每次只能搬动一个盘子,搬动过程可以借助任何一根柱子,但是必须满足大盘在上,小盘在下。

程序实现

python

#source代表源柱子,temp代表中间柱,target代表模板柱子,n为 盘子个数
def move(source,target):
    print(source,"==>",target)
def hanoi(n,source,temp,target):
    if(n==1):
        move(source,target)
    else:
        hanoi(n-1,source,target,temp)
        move(source,target)
        hanoi(n-1,temp,source,target)
n=int(input("输入盘子数:"))
print("移动",n,"个盘子的步骤是:")
hanoi(n,'A','B','C')

C

#include <stdio.h>
#include <windows.h>
void Hanoi(int n, char a,char b,char c);
void Move(int n, char a, char b);
int count;
int main()
{
    int n=8;
    printf("汉诺塔的层数:\n");
    scanf(" %d",&n);
    Hanoi(n, 'A', 'B', 'C');
    return 0;
}
void Hanoi(int n, char a, char b, char c)
{
    if (n == 1)
    {
        Move(n, a, c);
    }
    else
    {
        Hanoi(n - 1, a, c, b);
        Move(n, a, c);
        Hanoi(n - 1, b, a, c);
    }
}
void Move(int n, char a, char b)
{
    count++;
    printf("第%d次移动 Move %d: Move from %c to %c !\n",count,n,a,b);
}

非递归实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
//第0位置是柱子上的塔盘数目
int zhua[100] = { 0 }, zhub[100] = { 0 }, zhuc[100] = { 0 };
char charis(char x, int n)
//左右字符出现顺序固定,且根据n值奇偶尔不同
{
    switch (x)
    {
    case'A':
        return(n % 2 == 0) ? 'C' : 'B';
    case'B':
        return(n % 2 == 0) ? 'A' : 'C';
    case'C':
        return(n % 2 == 0) ? 'B' : 'A';
    default:
        return'0';
    }
}
void print(char lch, char rch)
//打印字符
{
    if (lch == 'A')
    {
        switch (rch)
        {
        case'B':
            zhub[0]++;
            zhub[zhub[0]] = zhua[zhua[0]];
            zhua[zhua[0]] = 0;
            zhua[0]--;
            break;
        case'C':
            zhuc[0]++;
            zhuc[zhuc[0]] = zhua[zhua[0]];
            zhua[zhua[0]] = 0;
            zhua[0]--;
            break;
        default:
            break;
        }
    }
    if (lch == 'B')
    {
        switch (rch)
        {
        case'A':
            zhua[0]++;
            zhua[zhua[0]] = zhub[zhub[0]];
            zhub[zhub[0]] = 0;
            zhub[0]--;
            break;
        case'C':
            zhuc[0]++;
            zhuc[zhuc[0]] = zhub[zhub[0]];
            zhub[zhub[0]] = 0;
            zhub[0]--;
            break;
        default:
            break;
        }
    }
    if (lch == 'C')
    {
        switch (rch)
        {
        case'A':
            zhua[0]++;
            zhua[zhua[0]] = zhuc[zhuc[0]];
            zhuc[zhuc[0]] = 0;
            zhuc[0]--;
            break;
        case'B':
            zhub[0]++;
            zhub[zhub[0]] = zhuc[zhuc[0]];
            zhuc[zhuc[0]] = 0;
            zhuc[0]--;
            break;
        default:
            break;
        }
    }
    printf("\t");
    int i;
    printf("(");
    for (i = 1; i <= zhua[0]; i++)
        printf("%d", zhua[i]);
    printf(")");
    printf("(");
    for (i = 1; i <= zhub[0]; i++)
        printf("%d", zhub[i]);
    printf(")");
    printf("(");
    for (i = 1; i <= zhuc[0]; i++)
        printf("%d", zhuc[i]);
    printf(")");
    printf("\n");
}
void Hanoi(int n)
{
    //分配2^n个空间
    bool * isrev;
    isrev = (bool*)malloc(sizeof(bool)*(int)pow(2, n));
    for (int i = 1; i < pow(2, n); i++)
        isrev[i] = false;
    //循环计算是否逆序
    for (int ci = 2; ci <= n; ci++)
    {
        for (int zixh = (int)pow(2, ci - 1); zixh < pow(2, ci); zixh += 4)
            //初始值重复一次,自增值可加4,减少循环次数。
            isrev[zixh] = isrev[(int)pow(2, ci) - zixh];
        //该位置为中间位置,且奇次幂逆序,偶数幂不逆序
        isrev[(int)pow(2, ci)] = ((ci - 1) % 2 == 0) ? false : true;
    }
    char lch = 'A', rch;
    rch = (n % 2 == 0 ? 'B' : 'C');
    printf("%d\t", 1);
    printf("%c->%c", lch, rch);
    print(lch, rch);
    for (int k = 2; k < pow(2, n); k++)
    {
        if (k % 2 == 0)
            rch = charis(lch,n);
        else
            lch = charis(rch,n);
        printf("%d\t", k);
        if (isrev[k])
        {
            printf("%c->%c", rch, lch);
            print(rch, lch);
        }
        else
        {
            printf("%c->%c", lch, rch);
            print(lch, rch);
        }
    }
}
    int main()
    {
        int n;
        printf("请输入盘子个数:");
        scanf("%d", &n);
        zhua[0] = n;
        for (int i = 1; i <= n; i++)
            zhua[i] = n - i + 1;
        Hanoi(n);
        system("pause");
        return 0;
    }

Java

public class Hanoi {
    /**
    * 
    * @param n 盘子的数目
    * @param origin 源座
    * @param assist 辅助座
    * @param destination 目的座
    */
    public void hanoi(int n, char origin, char assist, char destination) {
        if (n == 1) {
            move(origin, destination);
        } else {
            hanoi(n - 1, origin, destination, assist);
            move(origin, destination);
            hanoi(n - 1, assist, origin, destination);
        }
    }

    // Print the route of the movement
    private void move(char origin, char destination) {
        System.out.println("Direction:" + origin + "--->" + destination);
    }

    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        hanoi.hanoi(3, 'A', 'B', 'C');
    }
}

  转载请注明: Hanoi

 上一篇
Matlab遗传算法工具箱 Matlab遗传算法工具箱
近期在学习Matlab遗传算法,就接触到了谢菲尔德大学的Matlab遗传算法工具箱。下面将对其进行简单的介绍以及安装。 工具箱简介​ 谢菲尔德(Sheffield)遗传算法工具箱是由英国谢菲尔德大学开发的遗传算法工具箱。由MATLAB
2019-03-23
下一篇 
...... ......
多希望有一天突然惊醒,发现自己在课上睡着了,一切都是一场梦。你告诉同桌,说做了个好长的梦,同桌骂你白痴,叫你好好听课,你回头望着窗外的球场,一切都那么熟悉,一切还充满希望…”那时还喜欢炙热的夏天,蝉鸣、单车和下课铃声。怀念那时的一切的一切
2019-03-04 Long
  目录