ishikado https://blog.hatena.ne.jp/ishikado/ ishikadoのアルゴリズム勉強録 https://ishikado.hatenadiary.org/ Daveのハノイの計算量はたかだかO(2^N)でありmax(N)=19なので、愚直にK手後のハノイの状態を求めることができる。 一方Earlの方法はO(3^N)なため、愚直なシミュレーションでは状態を求められない。 そこで、どのようにしてEarlのシミュレーションを行うかが問題となる。 ここで、一番下のdiskにのみ着目すると、通常のハノイのように手数を再帰的に計算していくことができることがわかる。 このため、先に3の累乗を前計算しておくことにより、たかだかO(N)でEarlのシミュレーションを実行することができる。最初に基底に向かうタイプの再帰苦手です。 #include <iostream… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fishikado.hatenadiary.org%2Fentry%2F20120330%2F1333119670" title="SRM 482 div1 Medium - ishikadoのアルゴリズム勉強録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-03-30 00:01:10 rich https://ishikado.hatenadiary.org/entry/20120330/1333119670 1.0 100%