Problem 400
の編集
https://www.odz.sakura.ne.jp/projecteuler/index.php?Problem+400
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[Problem 400:http://projecteuler.net/problem=400]] 「フィボナッチ木ゲーム」 [#g01dd795] ''フィボナッチ木''とは以下のように再帰的に定義された二分木のことである: -T(0) はノード(節点)を持たない木(空木)である. -T(1) はノードを一つだけ持つ二分木である. -T(&tex{k};) は T(&tex{k};-1) と T(&tex{k};-2) を子ノードとして持つルートノード(最上位にあるノード)からなる. このような木構造上で二人の対局者がゲームをする. それぞれの局面で対局者はあるノードを選択し, そのノードをルートとする部分木全体を削除する.~ 木全体のルートノードを強制的に取らされた対局者が敗者となる. &tex{k};=1 から &tex{k};=6 までの T(&tex{k};) に対し最初の局面で先手必勝となる手は以下のようになる. (訳注:赤いノードで示されている) #ref("https://projecteuler.net/resources/images/0400_winning.png",center,nolink) T(&tex{k};) の木構造上でゲームをした時, 最初の局面で先手必勝となる(すなわち, 後手が勝てる戦略がない)手の数を &tex{f(k)}; としよう. 例として &tex{f(5)}; = 1, &tex{f(10)}; = 17 となる. &tex{f(10000)}; を求めよ. 末尾18桁を回答として答えよ.
タイムスタンプを変更しない
*[[Problem 400:http://projecteuler.net/problem=400]] 「フィボナッチ木ゲーム」 [#g01dd795] ''フィボナッチ木''とは以下のように再帰的に定義された二分木のことである: -T(0) はノード(節点)を持たない木(空木)である. -T(1) はノードを一つだけ持つ二分木である. -T(&tex{k};) は T(&tex{k};-1) と T(&tex{k};-2) を子ノードとして持つルートノード(最上位にあるノード)からなる. このような木構造上で二人の対局者がゲームをする. それぞれの局面で対局者はあるノードを選択し, そのノードをルートとする部分木全体を削除する.~ 木全体のルートノードを強制的に取らされた対局者が敗者となる. &tex{k};=1 から &tex{k};=6 までの T(&tex{k};) に対し最初の局面で先手必勝となる手は以下のようになる. (訳注:赤いノードで示されている) #ref("https://projecteuler.net/resources/images/0400_winning.png",center,nolink) T(&tex{k};) の木構造上でゲームをした時, 最初の局面で先手必勝となる(すなわち, 後手が勝てる戦略がない)手の数を &tex{f(k)}; としよう. 例として &tex{f(5)}; = 1, &tex{f(10)}; = 17 となる. &tex{f(10000)}; を求めよ. 末尾18桁を回答として答えよ.
テキスト整形のルールを表示する