「康威序列」C語言實現：Look-and-say 數列生成邏輯與代碼詳解

康威序列簡介

「康威序列」，又稱「Look-and-say 序列」，是一個經典的整數序列：1, 11, 21, 1211, 111221, 312211... 其生成規則極具趣味性——每一項都是對前一項的「讀法」描述。例如：

• 第 1 項：「1」→ 讀作「一個 1」→ 記作 11
• 第 2 項：「11」→ 讀作「兩個 1」→ 記作 21
• 第 3 項：「21」→ 讀作「一個 2、一個 1」→ 記作 1211
• 第 4 項：「1211」→ 讀作「一個 1、一個 2、兩個 1」→ 記作 111221

本題要求輸入 n (1 ≤ n ≤ 30)，輸出第 n 項序列。由於數字增長迅速，必須以字符串形式存儲與處理。

核心算法思路

採用迭代法：從初始字符串 "1" 開始，重複執行 n-1 次「讀取並生成下一項」的操作。每次迭代掃描當前字符串，統計連續相同字符的個數，按「個數 + 字符」格式拼接生成新字符串。

C語言完整實現

#include <stdio.h>
#include <string.h>

void generate_next(char *s, int n);

int main() {
    int n;
    char str[10000];  // 足夠大的緩衝區，n=30 時長度約 446 萬，但題目通常測試較小 n
    while (scanf("%d", &n) != EOF) {
        strcpy(str, "1");
        generate_next(str, n);
        printf("%s\n", str);
    }
    return 0;
}

void generate_next(char *s, int n) {
    int i, j, count, len;
    char current_char, tmp[10000];

    for (j = 1; j < n; ++j) {          // 需要迭代 n-1 次
        len = 0;
        for (i = 0; s[i] != '\0'; ++i) { // 掃描當前字符串
            if (i == 0) {
                current_char = s[i];
                count = 1;
            } else {
                if (current_char == s[i]) {
                    ++count;            // 同字符計數+1
                } else {
                    // 寫入「個數+字符」
                    len += sprintf(tmp + len, "%d%c", count, current_char);
                    current_char = s[i]; // 切換到新字符
                    count = 1;
                }
            }
        }
        // 處理最後一組字符
        sprintf(tmp + len, "%d%c", count, current_char);
        strcpy(s, tmp);                // 更新為新字符串
    }
}

關鍵點解析

1. 雙緩衝區：使用 tmp 暫存生成的新字符串，避免原地修改導致掃描錯亂。
2. sprintf 格式化：%d%c 直接將計數與字符拼接，簡潔高效。
3. 邊界處理：循環結束後須額外寫入最後一組字符統計結果。
4. 複雜度：每項長度約為前一項的 1.3 倍（康威常數），n=30 時長度達百萬級，char[10000] 僅適用於較小 n；實際工程中應動態分配內存。

測試樣例

這道題是字符串處理與模擬算法的優秀練習，亦展示了數學規律在編程中的直接應用。