名前だけ聞いても分からないかもですが、やったことのある方もたくさんいると思います。
私も授業中とかによくやりました。
最後の1つを取ったら勝ち的なゲームです。
このゲームには必勝法があるので、今回はそれを紹介します。
ルール
- いくつかの石を3つの山に分けます。
- 2人のプレイヤーは交互に1つの山から1つ以上の好きな数の石をとる。
- 最後の1つを取った方の勝ちヽ(´∀`。)ノ゚イェイ
必勝法
説明がちょっと難しいのですが、
それぞれの山の石の数を2進法展開して同じ基底の係数の和が全て偶数になるように石をとります。
文章で書かれてもよく分からないと思うので、PHPのコードにしてみました。
1function saikyou($input) {
2$order = ceil(log(max($input), 2)) + 1;
3arsort($input);
4foreach ($input as $k => $v) {
5$binary[$k] = str_split(str_pad(decbin($v), $order, "0", STR_PAD_LEFT));
6}
7$key = null;
8for ($i = 0; $i < $order; $i++) {
9$sum = 0;
10foreach ($binary as $v) {
11$sum += (int)$v[$i];
12}
13if ($sum % 2 == 1) {
14if ($key === null) {
15foreach ($binary as $k => $v) {
16if ($v[$i] === "1") {
17$key = $k;
18$binary[$key][$i] = "0";
19break;
20}
21}
22} else {
23$binary[$key][$i] = (string)(1 - (int)$binary[$key][$i]);
24}
25}
26}
27ksort($binary);
28foreach ($binary as $k => $v) {
29$output[$k] = bindec(implode("", $v));
30}
31return $output;
32}
33
$inputには配列でそれぞれの山の石の数を入れます。
↓こんな感じになります。
1$input = array(9, 2, 5);
2$output = saikyou($input); // array(7, 2, 5)
3
$outputは最強の石の取り方でできたそれぞれの山の石の数です。
上の例では(7,2,5)なので、9の山から石を2つ取るのが最強です。
ちゃんと2進法展開の同じ基底の係数の和が全て偶数になっているのが分かります。
山の数は3つでなくても同じですし、石の数もいくつあっても考え方は一緒です。
便利な関数がたくさんあって短いコードでスッキリ書けました。
説明の難しいこともコードにするとスッキリですね。
◯参考