[過去ﾛｸﾞ] C言語なら俺に聞け 160 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
827(1): デフォルトの名無しさん (ｽｯﾌﾟﾌﾟ Sd8f-Yz/h) [sage] 2023/04/02(日) 09:45:46.28 ID:NRuCP2qfd(1/2) AAS
>>786
2^64回ではなくて64!回じゃないのか？
828: デフォルトの名無しさん (ﾗｸｯﾍﾟﾍﾟ MM4f-+zBY) [sage] 2023/04/02(日) 10:09:18.45 ID:tfS01X/KM(1) AAS
>>827
正確には、最短で(2^64-1)回
1枚 1回
2枚 3回
3枚 7回
4枚 15回
･･･
n枚 (2^n-1)回
考え方としては、1回前までの円盤を一時的に順に積み上げて最後の1枚を目標に移動し
その後その円盤の上に全く同じ手順で直前までの手順を復元する
要するに、n枚の時の回数をA(n)回とすると、(n+1)枚の時の回数はA(n+1)=A(n)*2+1
この漸化式の一般解を求めると上の回数になる
その結果、繰返し回数の見積りは
O(n)=2^n
となる
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.039s