Question

【題目】漢諾塔(又稱河內(nèi)塔)問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤大梵天命令婆羅門把圓盤從下面開(kāi)始按大小順序重新擺放在另一根柱子上.并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤.如下圖所示，從左到右有ABC三根柱子，其中A柱子上面有從小疊到大的n個(gè)圓盤，現(xiàn)要求將A柱子上的圓盤移到C柱子上去，期間只有一個(gè)原則:一次只能移動(dòng)一個(gè)盤子且大盤子不能在小盤子上面，則移動(dòng)的次數(shù)為_______(用表示)

ABC

Answer 1

【答案】

【解析】

設(shè)n個(gè)圓盤移動(dòng)次數(shù)為，，得到遞推公式，計(jì)算得到答案.

設(shè)n個(gè)圓盤移動(dòng)次數(shù)為，當(dāng)時(shí)，易知.

當(dāng)有個(gè)圓盤時(shí)，需要把上面的個(gè)圓盤移出來(lái)，把最下面的圓盤放在最下面，再把上面的個(gè)圓盤移上去，故.

即，數(shù)列是首項(xiàng)為，公比為的等比數(shù)列，故，.

故答案為：.