FC2ブログ

スポンサーサイト

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

アルゴリズム勉強記⑤~石とりゲーム&四捨五入編~

今回のテーマは石取りゲームと四捨五入です。


石取りゲームのルールは、
・先攻後攻が交互に石をとっていく
・一度に取れる石は1個からn個まで
・最後に石をとった方が負け

という簡単なものです。
一見普通のゲームに見えますが、実はこれゲームになってません。何故かというと、先攻が必ず勝ってしまうからです。

次のようなアルゴリズムで勝利できます。
まず、相手がi個取ったなら、自分はn + 1 - i個取るようにします。
すると石は、自分のターンごとにi + (n + 1 - i) = n + 1個ずつ減っていくことになります。

つまり、相手のターンに石が(n + 1)k + 1個(kは0以上の整数)になるように石をとれば、自分のターンでは(n + 1)個減るので、必ず相手に1残るようにもっていけるということになります。

というわけで、結局先攻が最初に石を(n + 1)k + 1個にしてしまうと、後攻はどう足掻いても勝てないのです。

マジで? と思うのなら実行ファイルで用意したので、下からダウンロードして試してみてください。
後攻を選べば絶対勝てませんので。(先攻を選んでも、初手で↑のようにしなければ負けます)

ダウンロード

うーん、一見普通のゲームに見えても、必勝法があったりするもんなんですね。
事典にはもう一つ別バージョンの石取りゲームをフィボナッチ数列で必勝するアルゴリズムがあるので、後日そちらもやってみたいと思います。



「2整数a, bで、a / bを小数第2位で四捨五入する」
ということを実現するために、整数型変数rを使って

r = (10^2 * ((double)a / (double)b) + 0.5) / 1

とすると、結果の小数 x.yzが r = x * 100 + y * 10 + zの形で代入される。


というのが事典に載ってたんですが、式の意味がわけわかめだったので教えて!gooで質問したところ、非常にわかりやすい回答をいただきまして理解できました。

まず (double)a / (double)b は、四捨五入前の結果です。これをfとします。
次に、fに10^2をかけていますが、これの目的は「fを2回左シフトする」(10進)です。
すると、小数第1位に四捨五入すべき数字がずれこんできます。これに0.5を足すと、切り上げならくり上がりで1の位が増え、切り捨てならそのままになります。
これで、残った小数部は不要なので1で割って捨てることで、最終的な結果が出ます。
もちろん、10^2の部分を10^3に変えれば、小数第3位までの四捨五入ができます。


ううん、なるほど。よく考えられてるなあ。
標準の四捨五入だと、 3.145→3.14になってしまうので、これもどこかで使うかも。


とまあ今日は比較的ライトな感じで終わりました。
次は何やろうかな~。
スポンサーサイト

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

コメント

Secret

プロフィール

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。