Hanoi

Code
, ,

汉诺塔

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

程序实现

python

1
2
3
4
5
6
7
8
9
10
11
12
13
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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);
}

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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');
    }
}