Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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;
}