スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

アルゴリズム勉強記⑥~石取りゲーム2とフィボナッチ数編~

今回は、前回の石取りゲームのルールがちょっと複雑(?)バージョンの必勝法です。

今回の石取りゲームは、
・一度にとれる石の数は「1個以上、相手が前に取った数の2倍個以下」
・最後に石を取った方の勝ち

というものです。
例を挙げると、

石の初期値:20個
Aがとれる数:1~19個→3個とる
Bのとれる数:1~3*2個→4個とる
Aのとれる数:1~4*2個……

という具合です。
多く取ろうとすると相手も多くとれるし、相手の手を少なくしようとすれば自分が取るのも少なくなるという、まあ一見ゲームらしい感じです。

がしかしこれにも必勝法が!
事典でこのアルゴリズム見て目からウロコでした。なんでこんなこと思いつくんだろう? 数列眺めてたら閃いたりするものなのか?

その必勝法とは、

現在の石の数以下の最大のフィボナッチ数を、現在の石から引く

その結果以下の最大のフィボナッチ数を、結果から引く

その結果以下の……

と繰り返していって、結果がフィボナッチ数になった時点でそれをとる数とする、というものです。


とりあえず34以下のフィボナッチ数を挙げると、

1, 1, 2, 3, 5, 8, 13, 21, 34

となります。
ここで、石の数を32個として手順を追っていきます。
32以下の最大のフィボナッチ数→21
32 - 21 = 11

11以下の最大のフィボナッチ数→8
11 - 8 = 3
3はフィボナッチ数なので、取る数は3

以上から、現在の石の数は 32 = 21 + 8 + 3と表せます。
ここで、21と8、8と3が、フィボナッチ数列上で2個離れていることに着目します。
なぜなら、ある和nは、(その数以下の最大のフィボナッチ数 + そのフィボナッチ数の前のフィボナッチ数以下のm)で成り立っているからです。
よって、フィボナッチ数列において、第n項 * 2 < 第n+2項が成り立つ(第n+1項はnより第n項より大きいので当然です)ことから、

21 > 8 * 2
8 > 3 * 2
となります。

よって、ここで3個とれば、相手は6個までしか取れないので、21 + 8個には到達できないことになります。
つまり、これで「相手に勝たせない」手となります。


要するに、現在の石の数を「フィボナッチ数の和」と考え、「その中で最も小さいフィボナッチ数」個とれば、「その次に相手が取れる数が、2番目に小さいフィボナッチ数に到達しない」ため相手は勝てないということです。(結論)

フィボナッチ数列は最近やったばっかりなんですが、こんな性質があったとは。
n - (n以下の最大のフィボナッチ数) < (そのフィボナッチ数の前のフィボナッチ数) 、なりますね。よく考えてみると。
ただ、この必勝法一つ弱点があって、それは「最初の石の数がフィボナッチ数だったとき」です。このとき、数をフィボナッチ数の和に分解することができないので、どうしようもありません。こういうときは1個取るしかないですね。で、相手がこの戦法を使ってしまえば負ける……と。

いやあ、なんつーか、感服しました。
数列面白いですね。今は数Ⅱやってて、数Bの教科書買ってないんでやるにやれないんですが。早くやりたい。
けどその間にああ、数ⅠAもやらないと……くそ、通常の3倍のスピードでやれればいいのに。

続きを読む

スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

プロフィール

PON4416

Author:PON4416
職業: 高校生

プログラミング歴: 2年弱

絵描き歴: '09年11月ごろから

趣味: プログラミング(C, C++)、お絵かき、漫画、アニメ、ゲーム

好きなもの: ジョジョ(2=3>1=4=7>5=6)、東方、うみねこ、ガンダム00、イカ娘

妖夢
嫁です(キリッ


Wilesの趣味的な人格。
最近PHPを始めたらしい。→やめたらしい

メール: yoshihiro[dot]hozumi[at]gmail[dot]com
skype: wiles4416

主にpixivで活動しています。
マイピクとか常に大募集してますw
プロフィールはこちらから



にほんブログ村 イラストブログ イラスト練習へ

最新記事
ひとりごと
最新コメント
月別アーカイブ
カテゴリ
ブロとも一覧

Weak's Smaller
割れ厨撲滅
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。