在一個U形的鐵棒上套著九個圓環,要將九個圓環從鐵棒中解出.
解法:
若要將九連環的九個圓環完全從鐵棒中分離需要幾個步驟呢?其實這個問題可以用遞迴關係來思考:
(1) 假設要將前 k 個圓環解出至少需要 ak 個步驟
(2) a1 = 1, a2 = 2
(3) ak = ak-1 + 2 ak-2 +1:因為要解 k 個環,要先把前 k-2 個環解出( ak-2 步),然後解下第 k 個環(加上 1 步),再把前 k-2 個環還原( ak-2 步),最後再解下前 k-1 個環 ( ak-1 步)。
(4) 綜合上列三點,可得 a9 = 341