Question

どんちっちｱｼﾞ('-' 鯵)зIB生@⚡︎な病民

ハノイの塔について調べてるのですが、漸化式習ってないのでよくわかりません...
P=1が得られるのでのところから解説お願いします🙇‍♀️

滞化式をつくろう

 

還のEd ごのごとから、

  

gz 王2g。十1

となることがわかります。この式は、【基本】滋化式 (特殊解型) で出てきていま   '
ず。特性方程式                                 :

ヵー2p十1
を解いて ヵ= 1 が得られるので、
gzr1 十1 = 2(g。十1)
本85まま。ごこれより、

g。十1 274(g」填1)        な

 

が得ちれます。 円板が1枚のときは1回なので gi 三 1 だからら

 

 

 

ーーの2

となります。

 

つまり、 z 枚の円板があるときは、最小移動回数は (27 1) 回になることがねわかり 議
ます。 10枚のときは、1023回ですね。                        5

ハノイの塔