經典演算法題目詳解：漢諾塔、約瑟夫環、費波那契數列與位運算技巧

編輯：關於C語言

前言

在計算機科學與程式設計面試中，幾個經典的演算法問題反覆出現，它們不僅考驗邏輯思維，更涵蓋了遞歸、位運算、陣列操作等核心技能。本文將系統講解六大高頻題目：漢諾塔、約瑟夫環、費波那契數列（遞歸與非遞歸）、判斷 2 的冪次、計算二進制中 1 的個數、以及 O(n) 時間複雜度調整陣列奇偶順序。每個問題均附帶 C++ 實作碼與核心思路解析，助你快速掌握精髓。

1. 漢諾塔問題

問題描述

有三根柱子 X、Y、Z，X 柱上套著 n 個大小不一的圓盤（大在下、小在上）。要求將所有圓盤移至 Z 柱，過程中只能借助 Y 柱，且每次只能移動一個圓盤，大盤不能壓在小盤上方。

核心思路：分治遞歸

將 n 個盤的移動分解為三步：

將 X 上的 n-1 個盤借助 Z 移動到 Y；
將 X 上剩下的最大盤直接移至 Z；
將 Y 上的 n-1 個盤借助 X 移動到 Z。

遞歸終止條件為 n==1 時直接移動。

C++ 實作

void moveNext(char pre, char next) {
    cout << pre << "-->" << next << endl;
}

void hanio(int n, char XBlock, char YBlock, char ZBlock) {
    if (n == 1) {
        moveNext(XBlock, ZBlock);
    } else {
        hanio(n - 1, XBlock, ZBlock, YBlock);
        moveNext(XBlock, ZBlock);
        hanio(n - 1, YBlock, XBlock, ZBlock);
    }
}

2. 約瑟夫環

問題描述

n 個人圍成一圈，從第 1 人開始報數，報到 m 的人出列，下一人繼續從 1 報告數，循環直到剩下最後一人。

核心思路：循環鏈表模擬

建立首尾相連的循環鏈表，用指針遍歷計數，刪除第 m 個節點，直到只剩一個節點。

C++ 實作

typedef struct node {
    int num;
    struct node *next;
} LinkNode;

LinkNode* create_link(int num) {
    LinkNode *p, *current, *head;
    p = (LinkNode*)malloc(sizeof(LinkNode));
    p->num = 1; p->next = NULL;
    head = current = p;
    for (int i = 2; i <= num; i++) {
        p = (LinkNode*)malloc(sizeof(LinkNode));
        p->num = i; p->next = NULL;
        current->next = p;
        current = p;
    }
    current->next = head; // 首尾相連
    return head;
}

void make_play(LinkNode* link, int mcode) {
    assert(link != NULL && mcode != 0);
    LinkNode *pLink = link, *pPre = NULL, *pDel;
    cout << "遊戲開始！" << endl;
    while (pLink != pPre) {
        for (int n = 1; n < mcode; n++) {
            pPre = pLink;
            pLink = pLink->next;
        }
        pDel = pLink;
        cout << "出列的是 " << pDel->num << endl;
        pPre->next = pLink->next;
        pLink = pPre->next;
        free(pDel);
    }
    cout << "最後出列的是：" << pLink->num << endl;
}

3. 費波那契數列：遞歸與非遞歸

問題描述

求數列 1, 1, 2, 3, 5, 8, 13, 21... 的第 n 項。

遞歸版（指數級複雜度，教學用）

int fib_rec(int n) {
    if (n <= 2) return 1;
    return fib_rec(n - 1) + fib_rec(n - 2);
}

非遞歸版（線性複雜度，工程用）

利用滾動變量保存前兩項，迭代累加。

int fib_iter(int n) {
    if (n <= 2) return 1;
    int valN1 = 1, valN2 = 1, sumN;
    for (int i = 1; i <= n - 2; i++) {
        sumN = valN1 + valN2;
        valN2 = valN1;
        valN1 = sumN;
    }
    return sumN;
}

4. 判斷一個數是否為 2 的冪次方

位運算技巧

2 的冪次方在二進制中只有一個 1（如 1=1, 2=10, 4=100, 8=1000）。性質：x & (x - 1) == 0 當且僅當 x 是 2 的冪次方（x>0）。

int find2power(int a[], int len) {
    int count = 0;
    for (int i = 0; i < len; i++) {
        if (a[i] > 0 && (a[i] & (a[i] - 1)) == 0) count++;
    }
    cout << count << endl;
    return count;
}

5. 計算整數二進制中 1 的個數

逐位檢查法

每次取最低位 num & 1，然後右移 num >>= 1，直到 num 為 0。

int num1OfBinery(int num) {
    int count = 0;
    while (num) {
        if (num & 1) count++;
        num >>= 1;
    }
    return count;
}

進階：num &= (num - 1) 可直接消除最低位的 1，循環次數等於 1 的個數，更高效。

6. 陣列奇偶分離（O(n) 時間、O(1) 空間）

雙指針交換法

維護 mark 指向下一個奇數應放置的位置，i 遍歷陣列。遇到奇數則與 mark 位置交換，mark++。一次遍歷完成分離。

void swapElement(int arr[], int i, int mark) {
    int tmp = arr[i];
    arr[i] = arr[mark];
    arr[mark] = tmp;
}

void partition(int arr[], int num) {
    int i = 0, mark = 0;
    // 找第一個奇數
    while (i < num && (arr[i] & 1) == 0) i++;
    if (i == num) return; // 全偶數
    swapElement(arr, i, mark);
    i++; mark++;
    while (i < num) {
        if ((arr[i] & 1) == 1) {
            swapElement(arr, i, mark);
            mark++;
        }
        i++;
    }
}

測試主程式

int main() {
    // 測試漢諾塔
    // hanio(3, 'X', 'Y', 'Z');
    // 測試費波那契
    // cout << fib_iter(7) << endl;
    // 測試約瑟夫環
    LinkNode* head = create_link(7);
    make_play(head, 5);
    // 測試 2 的冪次方
    int arr[] = {1,2,3,4,5,6,7,8,16,50};
    find2power(arr, 10);
    // 測試二進制 1 的個數
    // cout << num1OfBinery(7) << endl;
    // 測試奇偶分離
    // int arr2[] = {1,2,4,6,7,5,8,9};
    // partition(arr2, 8);
    return 0;
}