3

私は次のように減らした問題を与えられました：あなたはすべてのものを持つ2進数（例えば11111）と同じ長さの2進数のセット（00101、10000、01100、00100、11100）を与えられます。2人のプレーヤーAとBがいます。各ターンで、プレーヤーはメインの2進数（11111）から、2の2進数のANDが小さい数字になるように、小さい数字のいずれかを引くことができます。次に、次のプレーヤーは結果から減算することができます。もう引き算できないプレイヤーは負けます。例えば。

   A         B       
 11111     11010   // Now A cannot subtract 
-00101    -10000   // anymore in the next turn. 
-------   ------   // So B wins the game.
 11010     01010
-------   ------

両方のプレーヤーが最適にプレーする場合（彼らの勝利のために最良の選択をする）、私はどちらのプレーヤーが与えられた2進数の組み合わせで勝つかを見つけなければなりません。

O（n ^ 2）アプローチを試しましたが、もっと速い方法はありますか？

編集：O（n ^ 2）：ここで、nは状態の数です。長さ6（111111）の2進数の場合、2^6の状態が可能です。だから私の複雑さはO（（2 ^ 6）^ 2）です。

編集：すべての可能な状態を生成するマイコード：

void makeAllStates() /* Bottom Up Approach. Starting from 00000 and going to 11111 */
{
    // bool states[i] : True if state[i] is a winning position.
    // bool isWord[i] : True if the given state matches a smaller number. (eg. If the main number has been reduced to 10110 and there is a smaller number 10110, then isWord[i] is true.
    // bool visited[i] : True If the given state has been visited  
    // int statecount : Total number of states
    int temp;
    for(int xx=1;xx<stateCount;xx++)
    {
        for(int yy=1;yy<stateCount;yy++)
        {
            if(xx&yy)
                continue;
            if(!(isWord[xx] || isWord[yy]))
                continue;
            if(!visited[yy])
                continue;
            temp = xx^yy;
            if(isWord[temp])
                continue;
            if(states[temp])
                continue;
            if(isWord[xx] && isWord[yy])
                states[temp] = false;
            else
            {
                if(isWord[xx])
                    states[temp] = !states[yy];
                else
                    states[temp] = !states[xx];
            }
            visited[temp] = true;
            if(temp == stateCount-1 && states[temp])
            {
                return;
            }

        }
    }
}
4

2 に答える 2

3

それがあなたに役立つかどうかはわかりません（あなたはO（n ^ 2）アプローチについて話しましたが、Nが何を意味するのかは言いませんでした）。不偏ゲームの一般的なアプローチを試してください（スプレイグ・グランディ理論）。

  • ゲーム内の位置はあなたのメインナンバーです
  • すべての「負けている」位置（もう何も減算できないような位置）を見つけます
  • すべての「失われた」位置に対してx：Grundy関数g（x）= 0;
  • 次に、位置yの汚れた関数を計算する場合は、位置yから位置x_iに曲がることができるように、すべての位置x_1...x_kを見つけます。g（y）= mex（g（x_1）、...、g（x_k））。「mex」は「最小の除外」です。g（x_1）、...、g（x_k）を除くすべての中で最小の非負の整数です。たとえば、mex（2、3、4）= 0、mex（0、1、2、5）= 3、mex（0、1）=2などです。

すべてのゲーム位置を再帰的に考慮することができ、位置xを1回（g（x）の計算中に）考慮するため、このアルゴリズムは可能な位置の数によって線形であることに注意してください。位置間の可能なターン数によって線形になります。つまり、O（N * K）です。ここで、Nは状態の数であり、Kは小さい数のセットのサイズです（ゲームでターンを行うことができます）。

g（START_POSITION）= 0の場合、開始位置は負け位置であり、最初のプレーヤーが負けます（ターンごとに勝ち位置になります）。g（START_POSITION）> 0の場合、開始位置が勝ち位置（g（x）= 0となるように位置xへのターンが存在する）であるため、最初のプレーヤーが勝ちます。

英語が下手でごめんなさい、そしてそれがお役に立てば幸いです

于 2013-02-08T20:43:38.443 に答える
0

K.Bulatovの入力に基づいて、これが最悪の場合の時間計算量O（n ^ 2）の最終的なコードです。剪定後、呼び出しの数は大幅に削減されました。主な機能は次のとおりです。

//state : The state for which grundy number is being queried.
//visited[i] : If the grundy number of the state has already been calculated.
//wordStates[] : an array with all the smaller numbers stored.
//mex() : "minimal excludant" - the smallest non-negative integer not in array
int grundyNum(int state)
{
    if(visited[state])
        return grundy[state];
    int grundArr[wordStates.size()];
    int loc =0;
    visited[state] = true;
    for(int xx =0;xx<wordStates.size();xx++)
    {
        if((state&wordStates[xx]) == wordStates[xx])
        {
            grundArr[loc] = grundyNum(state^wordStates[xx]);
            loc++;
        }
    }
    grundy[state] =  mex(grundArr,loc);
    return grundy[state];
}

次のように関数を呼び出すだけで、勝者が得られます。

result = grundy(1111111);
winner = result==0?"B":"A";
于 2013-02-09T10:03:48.110 に答える