藍橋杯 FJ 字符串問題：遞歸與迭代優化方案

題目規律

字串序列定義：

A1 = "A"
A2 = "ABA"
A3 = "ABACABA"
A4 = "ABACABADABACABA"
...
An = A(n-1) + char('A'+n-1) + A(n-1)

輸入 N (≤26)，輸出 AN。N=20 時長度約 100 萬，N=26 時長度達 6700 萬，記憶體與時間壓力極大。

原始遞歸代碼缺陷

• 使用巨大靜態陣列 char ch[1500000]，棧溢位風險。
• 遞歸深度 N=26 導致棧幀過多，效率低。
• 字串拼接重複複製，時間複雜度 O(2^N)。

優化方案一：迭代構建（自底向上）

string s = "A";
for (int i = 2; i <= n; ++i) {
    s = s + char('A' + i - 1) + s;
}
cout << s << endl;

• 使用 std::string 自動管理記憶體，避免手動陣列。
• 但 N=26 時字串長度 67M，拼接仍會產生大量臨時物件，需預留容量：s.reserve((1<。

void printA(int n) {
    if (n == 1) { cout << 'A'; return; }
    printA(n-1);
    cout << char('A' + n - 1);
    printA(n-1);
}