6
  • 2 人のプレイヤー A と B が数字nを含むゲームをプレイしています
  • プレイヤー A が最初の動きを行い、両方のプレイヤーが交互にプレイします。
  • 各手番で、プレーヤーは数字 n を取り、2^i < nとなる数字iを選択し、 kの 2 進数表現の 1 の数が次の値以上である場合、 nをk = n - 2^iに置き換えます。 nのバイナリ表現における 1 の数
  • どのプレーヤーも手を出せなくなったとき、つまりそのようなiが存在しなくなったとき、ゲームは終了します。

例えば：

n = 13 = b1101

可能な i=1 のみ

k = n - 2^i = 11 = b1011

繰り返しますが、可能なのは i = 2 だけです

k = n - 2^i = 7 = b111

プレイヤー A はそれ以上手が出せないので、プレイヤー B が勝ちます。

どのステップでも、n のバイナリ表現の対応する位置に 0 が存在するように、i のみを選択できると推測しました。

例: n=1010010 の場合、i は {0,2,3,5} のみです。

しかし、私はこれ以上先に進むことはできません.ミニマックスアルゴリズムは私を正確に打っていません.助けていただければ幸いです.よろしくお願いします.

4

1 に答える 1

3

nが大きすぎないと仮定すると、動的計画法を使用してこの問題を解決できます。配列A[1：n]を定義します。ここで、A [i]は、プレーヤーiが入力iで勝つかどうかを表します。解釈を使用してみましょう：

   A[i] = 1, if A wins on input i,
   A[i] = 0, if A loses on input i.

これで、Aは次のようにボトムアップで計算できます。

A[1] = 0, A[2] = 1.
For j=3:n { 
      Assign A[j] = 1 if there exists a number i such that (A[j-2^i] = 0) AND 
                              (number of 1's in i >=  number of 1's in j)
      Otherwise  Assign A[j] = 0 
}
于 2012-09-25T00:07:02.910 に答える