主題
題目連結：
題目意譯：
現在，我們將建立出一個有 n 列（索引值從 1 開始數）的列表。我們從第 1 列寫下一個 0 開始。對於接下來的每一列，根據前一列的結果把每一個「0」替換成「01」以及每一個「1」替換成「10」便可以得到本列的內容。
例如說，對於 n = 3，第 1 列為 0、第二列為 01、第三列為 0110。
給定兩整數 n 和 k，回傳上述表格中第 n 列中的第 k 個（索引值從 1 開始數）符號為何。
限制：
1 ≦ n ≦ 30
1 ≦ k ≦ 2 ^ n - 1
範例測資：
範例 1：
輸入： n = 1, k = 1
輸出： 0
解釋： 第 1 列： 0
範例 2：
輸入： n = 2, k = 1
輸出： 0
解釋：
第 1 列： 0
第 2 列： 01
範例 3：
輸入： n = 2, k = 2
輸出： 1
解釋：
第 1 列： 0
第 2 列： 01
解題思維：
觀察題目生成的表格之後可以看到：
令第 i 列的內容為 Si，且從中對半切會得到 Li 、 Ri，則第 i + 1 列的內容為 Li+1 + Ri+1，其中 Li+1 = (Li + Ri) 、 Ri+1 = (Ri + Li)（對於 i ≧ 2）。
（此可由數學歸納法證明，在此省略。）
因此給定 n 和 k 之後，我們可以先看第 k 個符號座落於 Sn 中的何處：
如果 k 座落於 Ln 中，則我們可以將 n 減去 1；
（因為 Si 與 Si+1 的前半部（即 Li+1）相同）
如果 k 座落於 Rn 中的「前半部份」，則我們可以將 n 減去 1 並將 k 減去 2 ^ (n - 3)；
（因為這個「前半」根據上面的觀察可變成 Rn-1，且索引值的位移量恰好為 2 ^ (n - 3)）
如果 k 座落於 Rn 中的「後半部份」，則我們可以將 n 減去 1 並將 k 減去 (2 ^ (n - 2) + 2 ^ (n - 3))。
（類似上面關於「前半」的緣故）
最後一路將 n 遞減到 2 為止，便可以直接得到答案了——即如果此時的 k 值為 1，則回傳 0；反之，k 值為 2，則回傳 1。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
