原神wiki
雑談/ファルザン / 845
2030
コメント
views
7
フォロー
845
ちゃんと考えるとこんな感じ（以下白字）：n+1段のハノイの塔を動かすには①上の1～n段目までを完全にどかして別の列に積み上げる。②n+1段目を①とは別の列の一番下に移動させる。③最初にどかした1～n段をn+1段目の上にのせる。の3stepを踏めばOK。いまn段のハノイの塔を別の列へ移すのに必要な手数をA[n]とすると、①は定義からA[n]手、②は1手、③はA[n]手（※n+1段目は1～n段までのすべてを乗せられる段なので①のときと同じ手順を踏める）なので、A[n+1]=2A[n]+1が成立する（初項は明らかにA[1]=1）。あとは素直に漸化式を解くなり数学的帰納法を使うなりすれば一般解A[n]=2^n - 1にたどり着けるぞ（たかだか第7項の具体値が分かればいいのでA[1],A[2],…って順に計算してもOK）。"n+1段目を追加するとn段目までのセットを待避&乗せるで合計2回移動させないといけないから手数が倍くらいになる"ってところに気づけたら、細かく計算しなくても手数が2^nオーダーって見積れますね。
通報 ...