递归及非递归汉诺塔
程序代码：#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void move(char, char);
void hanoi1(int, char, char, char);
void hanoi2(int, char, char, char);
int get_dis_size(int);
int * calc_dis_value(int, int *, int);
void even_next(char *, char *, char, char, char, int);
void odd_next(char *, char *, char, char, char, int);
int main(void)
{
int n;
scanf("%d", &n);
hanoi2(n, 'A', 'B', 'C');
return 0;
}
void move(char from, char to)
{
printf("%c -> %c\n", from, to);
}
void hanoi1(int n, char a, char b, char c)
{
if(n == 1)
move(a, c);
else if(n > 1) {
hanoi1(n - 1, a, c, b);
move(a, c);
hanoi1(n - 1, b, a, c);
}
}
void hanoi2(int n, char a, char b, char c)
{
int size = get_dis_size(n);
int * dis_arr = (int *)calloc(size, sizeof(int));
int i, j = 0;
int p = (int)pow(2, n);
char prev[2];
if(size || n > 0) {
calc_dis_value(n, dis_arr, size);
if(n % 2)
move(a, c);
else
move(a, b);
prev[0] = a;
for(i = 2; i < p; i++) {
if(i % 2)
odd_next(prev + 0, prev + 1, a, b, c, n);
else
even_next(prev + 0, prev + 1, a, b, c, n);
if(i == dis_arr[j]) {
move(prev[1], prev[0]);
j++;
} else {
move(prev[0], prev[1]);
}
}
}
free(dis_arr);
}
int get_dis_size(int n)
{
int dis_size = 1;
int i;
if(n < 3)
return 0;
else if(n > 3)
for(i = 4; i <= n; i++)
dis_size = i % 2 ? dis_size * 2 + 1 : dis_size * 2;
return dis_size;
}
int * calc_dis_value(int n, int * dis_arr, int size)
{
int i, j, k, p, tmp;
if(n > 2) {
for(i = 0, j = 3; i < size; j++) {
p = (int)pow(2, j);
if(j % 2) {
tmp = i;
dis_arr[i++] = p / 2;
for(k = tmp - 1; k >= 0; k--)
dis_arr[i++] = p - dis_arr[k];
} else {
for(k = i - 1; k >= 0; k--)
dis_arr[i++] = p - dis_arr[k];
}
}
}
return dis_arr;
}
void odd_next(char * prev1, char * prev2, char a, char b, char c, int n)
{
if(n % 2) {
if(*prev2 == a)
*prev1 = b;
else if(*prev2 == b)
*prev1 = c;
else
*prev1 = a;
} else {
if(*prev2 == a)
*prev1 = c;
else if(*prev2 == b)
*prev1 = a;
else
*prev1 = b;
}
}
void even_next(char * prev1, char * prev2, char a, char b, char c, int n)
{
if(n % 2) {
if(*prev1 == a)
*prev2 = b;
else if(*prev1 == b)
*prev2 = c;
else
*prev2 = a;
} else {
if(*prev1 == a)
*prev2 = c;
else if(*prev1 == b)
*prev2 = a;
else
*prev2 = b;
}
}
/*
n = 1 n = 2 n = 3 n = 4 n = 5 n = 6 n = 7
1 A -> C A -> B A -> C A -> B A -> C A -> B A -> C
2 A -> C A -> B A -> C A -> B A -> C A -> B
3 B -> C C -> B B -> C C -> B B -> C C -> B
4 C -> A (A -> C) B -> A (A -> B) C -> A (A -> C) B -> A (A -> B) C -> A (A -> C)
5 B -> A C -> A B -> A C -> A B -> A
6 B -> C C -> B B -> C C -> B B -> C
7 A -> C A -> B A -> C A -> B A -> C
8 A -> C A -> B A -> C A -> B
9 B -> C C -> B B -> C C -> B
10 B -> A C -> A B -> A C -> A
11 C -> A B -> A C -> A B -> A
12 C -> B (B -> C) B -> C (C -> B) C -> B (B -> C) B -> C (C -> B)
13 A -> B A -> C A -> B A -> C
14 A -> C A -> B A -> C A -> B
15 B -> C C -> B B -> C C -> B
16 C -> A (A -> C) B -> A (A -> B) C -> A (A -> C)
17 B -> A C -> A B -> A
18 B -> C C -> B B -> C
19 A -> C A -> B A -> C
20 A -> B (B -> A) A -> C (C -> A) A -> B (B -> A)
21 C -> B B -> C C -> B
22 C -> A B -> A C -> A
23 B -> A C -> A B -> A
24 B -> C C -> B B -> C
25 A -> C A -> B A -> C
26 A -> B A -> C A -> B
27 C -> B B -> C C -> B
28 C -> A (A -> C) B -> A (A -> B) C -> A (A -> C)
29 B -> A C -> A B -> A
30 B -> C C -> B B -> C
31 A -> C A -> B A -> C
32 A -> C A -> B
33 B -> C C -> B
34 B -> A C -> A
35 C -> A B -> A
36 C -> B (B -> C) B -> C (C -> B)
37 A -> B A -> C
38 A -> C A -> B
39 B -> C C -> B
40 B -> A C -> A
41 C -> A B -> A
42 C -> B B -> C
43 A -> B A -> C
44 A -> C (C -> A) A -> B (B -> A)
45 B -> C C -> B
46 B -> A C -> A
47 C -> A B -> A
48 C -> B (B -> C) B -> C (C -> B)
49 A -> B A -> C
50 A -> C A -> B
51 B -> C C -> B
52 B -> A (A -> B) C -> A (A -> C)
53 C -> A B -> A
54 C -> B B -> C
55 A -> B A -> C
56 A -> C A -> B
57 B -> C C -> B
58 B -> A C -> A
59 C -> A B -> A
60 C -> B (B -> C) B -> C (C -> B)
61 A -> B A -> C
62 A -> C A -> B
63 B -> C C -> B
64 C -> A (A -> C)
65 B -> A
66 B -> C
67 A -> C
68 A -> B (B -> A)
69 C -> B
70 C -> A
71 B -> A
72 B -> C
73 A -> C
74 A -> B
75 C -> B
76 C -> A (A -> C)
77 B -> A
78 B -> C
79 A -> C
80 A -> B (B -> A)
81 C -> B
82 C -> A
83 B -> A
84 B -> C (C -> B)
85 A -> C
86 A -> B
87 C -> B
88 C -> A
89 B -> A
90 B -> C
91 A -> C
92 A -> B (B -> A)
93 C -> B
94 C -> A
95 B -> A
96 B -> C
97 A -> C
98 A -> B
99 C -> B
100 C -> A (A -> C)
101 B -> A
102 B -> C
103 A -> C
104 A -> B
105 C -> B
106 C -> A
107 B -> A
108 B -> C (C -> B)
109 A -> C
110 A -> B
111 C -> B
112 C -> A (A -> C)
113 B -> A
114 B -> C
115 A -> C
116 A -> B (B -> A)
117 C -> B
118 C -> A
119 B -> A
120 B -> C
121 A -> C
122 A -> B
123 C -> B
124 C -> A (A -> C)
125 B -> A
126 B -> C
127 A -> C
可以看出移动的过程是一个交叉顺序链，可是在有些位置会被断开：
n = 1: 无
n = 2: 无
n = 3: 4
n = 4: 4 12
n = 5: 4 12 16 20 28
n = 6: 4 12 16 20 28 36 44 48 52 60
n = 7: 4 12 16 20 28 36 44 48 52 60 64 68 76 80 84 92 100 108 112 116 124
（括号中是正确的顺序），我们只需要在断开的时候把过程反过来就行了，可以看出这些断开点有规律可寻，如当n = 7时，4 + 124 = 2 ^ 7，12 + 116 = 2 ^ 7，16 + 112 = 2 ^ 7...
64 + 64 = 2 ^ 7，这是一些以2 ^ (n - 1)对称的数。但这里有一个问题，就是如果n是奇数，那么 2 ^ (n - 1)存在，而n是偶数2 ^ (n - 1)不存在，需要在一个循环里判断。
*/
hanoi1是汉诺塔递归移动函数。
hanoi2是汉诺塔迭代移动函数。
[ 本帖最后由 lz1091914999 于 2011-8-23 17:18 编辑 ]
