一共十六個盤子,盤子必須從小到大排列,只能在abc三個塔自由移動,一次只能移動一個!求源碼
這個要遞推,假設開始的時候全部在a塔上,目標是全部移到c塔上。
從一個盤子開始:
1. 一個盤子,從a移到c塔顯然只需要一步,所以答案是1
2.兩個盤子,那麼我們需要先將上面的一個盤子移到b塔,需要1步;再將a最下面的移到c塔上,需要1步;然後再將b塔的移到c塔上,需要1步;所以總計是3
3.三個盤子,那麼我們需要先將上面兩個移到b塔,按照2中給出的方法來,移動兩個需要的步數是3;再將最下面的移到c塔,需要1步;再將b塔的兩個移到c塔,需要3步;所以總計7步。
4.四個盤子,那麼我們需要先將上面三個移到b塔,按照3中給出的方法來,移動兩個需要的步數是7;再將最下面的移到c塔,需要1步;再將b塔的三個移到c塔,需要7步;所以需要15
。。。
所以我們可以推出一個公式:
a(n) = a(n-1)*2 + 1
其中 a(1) = 1