2012-10-03 22:44:50Morris
[2013/10更新][資料結構] 誰說非遞迴河內塔不好寫的 ?
Background.
上資料結構光是一個 ADT 定義就可以講了很久, 定義相信是很重要的一環, 不過我聽了一節課的陣列定義也是有點累了, 隔了一個禮拜過後, 換了個遞迴講, 光是費氏+階乘的遞迴展開就一節課多了, 之後講了遞迴必須的堆疊定義, Oh, my god, 一講到非遞迴河內塔不好寫, 我整個賭氣了
#include <stdio.h>
void hanoi(int n, char A, char B, char C) {
if(n == 1)
printf("Move %d from %c to %c\n", n, A, C);
else{
hanoi(n - 1, A, C, B);
printf("Move %d from %c to %c\n", n, A, C);
hanoi(n - 1, B, A, C);
}
}
int main() {
int n;
while(scanf("%d", &n) == 1)
hanoi(n, 'A', 'B', 'C');
return 0;
}
數學解 AB, AC, BA, BC, CA, CB 0~5
「經過何錦文教授的指導，我大致上可以說一說這個解法怎麼來的，首先很明顯的數字移動部分來自於遞迴，接著狀態轉移的部分，可以從n的奇偶數下手發現，上部份轉換成下部份的狀態可以從遞迴中察覺。如果要證明的話可以從數學歸納法下手證明與原始遞迴一樣」－2012/10/18
「更有一個不用遞迴，不用堆疊的方法，一個決定移動最大或者是最小的計數器，然後一直迭代即可。」－和教授 2012/10/18
#include <stdio.h>
#define N 1048576
int ni[N], ac[N];
int main() {
int n, i, j, k;
while(scanf("%d", &n) == 1) {
ni[0] = 1, ac[0] = 1;
int len = 1;
int g[6] = {1,0,4,5,2,3};
int v[6] = {3,2,5,4,0,1};
for(i = 2; i <= n; i++) {
ni[len] = i, ac[len] = 1;
for(j = 0; j < len; j++)
ni[j+len+1] = ni[j], ac[j] = g[ac[j]];
len = len*2+1;
for(k = 0, j++; j < len; j++, k++)
ac[j] = v[ac[k]];
}
for(i = 0; i < len; i++) {
int A, C;
if(ac[i] == 0) A = 0, C = 1;
else if(ac[i] == 1) A = 0, C = 2;
else if(ac[i] == 2) A = 1, C = 0;
else if(ac[i] == 3) A = 1, C = 2;
else if(ac[i] == 4) A = 2, C = 0;
else if(ac[i] == 5) A = 2, C = 1;
printf("Move %d from %c to %c\n", ni[i], A+'A', C+'A');
}
}
return 0;
}
部落格專用相簿
[資料結構] 誰說非遞迴河內塔不好寫的 ?
#include <stdio.h>
#include <stack>
using namespace std;
int main() {
int n;
int i, j, k;
while(scanf("%d", &n) == 1) {
stack<int> stk[3];
for(i = n; i >= 1; i--)
stk[0].push(i);
char peg[] = {'A','B','C'};
if(n&1) swap(peg[1], peg[2]);
while(true) {
int disk[3];
for(i = 0; i < 3; i++)
disk[i] = stk[i].size() ? stk[i].top() : 0xfffffff;
int mnIdx = 0;
for(i = 1; i < 3; i++)
if(disk[i] < disk[mnIdx])
mnIdx = i;
printf("Move disk %d from %c to %c\n", disk[mnIdx], peg[mnIdx], peg[(mnIdx+1)%3]);
stk[mnIdx].pop();
stk[(mnIdx+1)%3].push(disk[mnIdx]);
if(stk[1].size() == n || stk[2].size() == n)
break;
for(i = 0; i < 3; i++)
disk[i] = stk[i].size() ? stk[i].top() : 0xfffffff;
if(disk[0] > min(disk[1], disk[2]) && disk[0] < max(disk[1], disk[2])) {
if(disk[1] < disk[2]) {
printf("Move disk %d from %c to %c\n", disk[0], peg[0], peg[2]);
stk[0].pop(), stk[2].push(disk[0]);
} else {
printf("Move disk %d from %c to %c\n", disk[0], peg[0], peg[1]);
stk[0].pop(), stk[1].push(disk[0]);
}
} else if(disk[1] > min(disk[0], disk[2]) && disk[1] < max(disk[0], disk[2])) {
if(disk[0] < disk[2]) {
printf("Move disk %d from %c to %c\n", disk[1], peg[1], peg[2]);
stk[1].pop(), stk[2].push(disk[1]);
} else {
printf("Move disk %d from %c to %c\n", disk[1], peg[1], peg[0]);
stk[1].pop(), stk[0].push(disk[1]);
}
} else {
if(disk[0] < disk[1]) {
printf("Move disk %d from %c to %c\n", disk[2], peg[2], peg[1]);
stk[2].pop(), stk[1].push(disk[2]);
} else {
printf("Move disk %d from %c to %c\n", disk[2], peg[2], peg[0]);
stk[2].pop(), stk[0].push(disk[2]);
}
}
}
}
return 0;
}
上資料結構光是一個 ADT 定義就可以講了很久, 定義相信是很重要的一環, 不過我聽了一節課的陣列定義也是有點累了, 隔了一個禮拜過後, 換了個遞迴講, 光是費氏+階乘的遞迴展開就一節課多了, 之後講了遞迴必須的堆疊定義, Oh, my god, 一講到非遞迴河內塔不好寫, 我整個賭氣了
#include <stdio.h>
void hanoi(int n, char A, char B, char C) {
if(n == 1)
printf("Move %d from %c to %c\n", n, A, C);
else{
hanoi(n - 1, A, C, B);
printf("Move %d from %c to %c\n", n, A, C);
hanoi(n - 1, B, A, C);
}
}
int main() {
int n;
while(scanf("%d", &n) == 1)
hanoi(n, 'A', 'B', 'C');
return 0;
}
數學解 AB, AC, BA, BC, CA, CB 0~5
「經過何錦文教授的指導，我大致上可以說一說這個解法怎麼來的，首先很明顯的數字移動部分來自於遞迴，接著狀態轉移的部分，可以從n的奇偶數下手發現，上部份轉換成下部份的狀態可以從遞迴中察覺。如果要證明的話可以從數學歸納法下手證明與原始遞迴一樣」－2012/10/18
「更有一個不用遞迴，不用堆疊的方法，一個決定移動最大或者是最小的計數器，然後一直迭代即可。」－和教授 2012/10/18
#include <stdio.h>
#define N 1048576
int ni[N], ac[N];
int main() {
int n, i, j, k;
while(scanf("%d", &n) == 1) {
ni[0] = 1, ac[0] = 1;
int len = 1;
int g[6] = {1,0,4,5,2,3};
int v[6] = {3,2,5,4,0,1};
for(i = 2; i <= n; i++) {
ni[len] = i, ac[len] = 1;
for(j = 0; j < len; j++)
ni[j+len+1] = ni[j], ac[j] = g[ac[j]];
len = len*2+1;
for(k = 0, j++; j < len; j++, k++)
ac[j] = v[ac[k]];
}
for(i = 0; i < len; i++) {
int A, C;
if(ac[i] == 0) A = 0, C = 1;
else if(ac[i] == 1) A = 0, C = 2;
else if(ac[i] == 2) A = 1, C = 0;
else if(ac[i] == 3) A = 1, C = 2;
else if(ac[i] == 4) A = 2, C = 0;
else if(ac[i] == 5) A = 2, C = 1;
printf("Move %d from %c to %c\n", ni[i], A+'A', C+'A');
}
}
return 0;
}
部落格專用相簿
[資料結構] 誰說非遞迴河內塔不好寫的 ?
#include <stdio.h>
#include <stack>
using namespace std;
int main() {
int n;
int i, j, k;
while(scanf("%d", &n) == 1) {
stack<int> stk[3];
for(i = n; i >= 1; i--)
stk[0].push(i);
char peg[] = {'A','B','C'};
if(n&1) swap(peg[1], peg[2]);
while(true) {
int disk[3];
for(i = 0; i < 3; i++)
disk[i] = stk[i].size() ? stk[i].top() : 0xfffffff;
int mnIdx = 0;
for(i = 1; i < 3; i++)
if(disk[i] < disk[mnIdx])
mnIdx = i;
printf("Move disk %d from %c to %c\n", disk[mnIdx], peg[mnIdx], peg[(mnIdx+1)%3]);
stk[mnIdx].pop();
stk[(mnIdx+1)%3].push(disk[mnIdx]);
if(stk[1].size() == n || stk[2].size() == n)
break;
for(i = 0; i < 3; i++)
disk[i] = stk[i].size() ? stk[i].top() : 0xfffffff;
if(disk[0] > min(disk[1], disk[2]) && disk[0] < max(disk[1], disk[2])) {
if(disk[1] < disk[2]) {
printf("Move disk %d from %c to %c\n", disk[0], peg[0], peg[2]);
stk[0].pop(), stk[2].push(disk[0]);
} else {
printf("Move disk %d from %c to %c\n", disk[0], peg[0], peg[1]);
stk[0].pop(), stk[1].push(disk[0]);
}
} else if(disk[1] > min(disk[0], disk[2]) && disk[1] < max(disk[0], disk[2])) {
if(disk[0] < disk[2]) {
printf("Move disk %d from %c to %c\n", disk[1], peg[1], peg[2]);
stk[1].pop(), stk[2].push(disk[1]);
} else {
printf("Move disk %d from %c to %c\n", disk[1], peg[1], peg[0]);
stk[1].pop(), stk[0].push(disk[1]);
}
} else {
if(disk[0] < disk[1]) {
printf("Move disk %d from %c to %c\n", disk[2], peg[2], peg[1]);
stk[2].pop(), stk[1].push(disk[2]);
} else {
printf("Move disk %d from %c to %c\n", disk[2], peg[2], peg[0]);
stk[2].pop(), stk[0].push(disk[2]);
}
}
}
}
return 0;
}
(悄悄話)
2013-05-05 13:58:46
(悄悄話)
2013-05-03 08:07:01