C 語言洗牌算法：模擬還原初始順序的循環次數計算

給定 2n 張牌，每次洗牌按「取後半段第一張、前半段第一張、後半段第二張、前半段第二張...」的規則重新排序。求需要多少次洗牌才能回到初始順序？本文提供完整 C 語言實現與邏輯解析。

問題建模

• 初始陣列：a[i] = i + 1 (i = 0 ~ 2n-1)
• 單次洗牌映射：新位置 j 對應舊位置 f(j)
  
  • j 為偶數：f(j) = n + j/2（取後半段）
  • j 為奇數：f(j) = j/2（取前半段）
• 重複應用映射直到陣列還原，計數器即為答案。

核心代碼實現

#include <stdio.h>
#include <stdlib.h>

void shuffle_once(int *src, int *dst, int n) {
    for (int i = 0; i < 2 * n; i++) {
        if (i % 2 == 0)
            dst[i] = src[n + i / 2];
        else
            dst[i] = src[i / 2];
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int total = 2 * n;
    int *a = malloc(total * sizeof(int));
    int *b = malloc(total * sizeof(int));

    for (int i = 0; i < total; i++) a[i] = i + 1;

    int count = 0;
    while (1) {
        shuffle_once(a, b, n);
        count++;
        int same = 1;
        for (int i = 0; i < total; i++) {
            if (a[i] != b[i]) { same = 0; break; }
        }
        if (same) break;
        // 複製 b 回 a 供下一輪
        for (int i = 0; i < total; i++) a[i] = b[i];
    }

    printf("經%d次洗牌回到初始位置\n", count);
    free(a);
    free(b);
    return 0;
}

關鍵點解析

1. 雙緩衝陣列：用 a、b 交替存放當前/下一狀態，避免覆蓋數據。
2. 映射公式推導：觀察規律得出偶奇位置對應的來源索引，O(1) 計算無需嵌套循環。
3. 終止條件：逐元素比較兩陣列是否完全相同，相同則結束。

複雜度分析

• 時間：O(k × n)，k 為洗牌次數（通常遠小於 n）。
• 空間：O(n)，兩個長度 2n 的整型陣列。

進階思考

此問題本質是尋找排列的階。可用數學方法（置換群的循環分解）在 O(n log n) 甚至 O(n) 內求解，適合極大 n 場景。代碼實現可參考「順序統計樹」或「並查集」優化。