算法經典：二叉樹小球下落問題（兩種解法）

算法經典：二叉樹小球下落問題（兩種解法）

《算法競賽入門經典》6.3.1 例題：深度 D 的滿二叉樹，節點編號 1~2^D-1（根為 1，左子 2k，右子 2k+1）。每節點有開關，初始關閉。小球從根落下，遇開關關閉向左、打開向右，經過即翻轉開關。I 個小球依次落下，求第 I 顆小球落在哪個葉子（編號）。D ≤ 20，I 不超過葉子數，最多 1000 組測試。

解法一：直接模擬（會超時）

模擬每顆小球逐層下落，維護開關狀態陣列 s[]。

#include <stdio.h>
#include <string.h>
#define MAXD 20
int s[1< n) break;             // 落出樹外（到達葉子下一層）
            }
            printf("%d\n", k/2);              // 父節點即葉子編號
        }
    }
    return 0;
}

缺點：I 可達 2^(D-1) ≈ 50萬，每球落 D 層，總操作 ~10^7，1000 組測試極其緩慢。

解法二：數學規律 O(D) 秒解

觀察規律：第 I 顆球的路徑完全由 I 的二進制特徵決定，無需模擬前 I-1 顆球。

• 根節點：所有球必經。第 1 球去左，第 2 球去右，第 3 球去左……奇數球去左，偶數球去右。
• 進入左/右子樹後，問題遞歸：該子樹內球的相對序號為 (I+1)/2（左）或 I/2（右）。
• 重複 D-1 次即到達葉子。

#include <stdio.h>
#include <string.h>
#define MAXD 20
int s[1<

輸入:
5
53
輸出:
(對應葉子編號，具體數值視樹深度而定)