0

ゲーム:
5 つのセクションに分割されたボックスがあります。ボックスの中にマウスが座っています。ボックスの近くに座っている猫。
毎ターン、猫は足をセクションに置きます。
1) ねずみがいる部分に猫が前足を置いたらゲームオーバー
2) そうでなければ、ねずみは猫の手の下の部分を含めて隣の部分に移動
する最小手数 (平均) で勝ちます。
チェーン - 猫の一連の動きを周期的に繰り返します。
次の関数は、特定のチェーンで勝つまでの平均移動回数を返します。 

public static double computePerformanceForChain(String chain)
{
    final int iterationsCount = 10000;
    int catPos, mousePos,steps=0;
    Random random = new Random(System.currentTimeMillis());
    for(int i=0; i<iterationsCount; i++)
    {
        mousePos=random.nextInt(5);
        for(int j=0;;j++)
        {
            catPos=Integer.parseInt(String.valueOf(chain.charAt(j%chain.length())));
            steps++;
            if(catPos==mousePos)  break;
            if(mousePos==0) mousePos=1;
            else if(mousePos==4) mousePos=3;
            else mousePos+=random.nextInt(2)*2-1;
        }
    }
    return (double)steps/iterationsCount;
}

たとえば、computePerformanceForChain("1133")約 3 を返します。
ただし、チェーン"23"関数ループの場合。
なぜこうなった？ありがとう。

4

2 に答える 2

2

Simple answer: there is no guarantee that execution will get out of inner loop
Check out inner loop: 

    for(int j=0;;j++) {
        catPos=Integer.parseInt(String.valueOf(chain.charAt(j%chain.length())));
        steps++;
        if(catPos==mousePos)  break;
        if(mousePos==0) mousePos=1;
        else if(mousePos==4) mousePos=3;
        else mousePos+=random.nextInt(2)*2-1;
    }

So, on each iteration mousePos's parity is changed. So if:

  • mousePos get initially assigned to odd number
  • chain is even-odd sequence such as "23"

then catPos will never be equal to mousePos and loop never finishes.

Simply put: if mouse is initially in odd-number section (section 3 for example), then cat is not able to catch it with 2-3 chain and will infinitely repeat this sequence.

于 2013-02-27T07:01:14.407 に答える
1

猫のシーケンスでは、猫が偶数の正方形から奇数の正方形に移動し、これを繰り返し、常に偶数、奇数、偶数、奇数にします。マウスは、常に隣接するマスに移動するため、常に偶数から奇数、偶数、奇数に移動します。したがって、50/50 の確率で、マウスが右の正方形から開始されます。猫が偶数のマスに移動するときにマウスが奇数のマスにある場合、猫が奇数のマスに移動しようとすると、マウスは偶数のマスに移動します。

この状況では、猫は決してネズミを捕まえません。

これは、猫が常に奇数から偶数、奇数から偶数になる偶数のソリューションに当てはまります。

于 2013-02-27T07:09:51.567 に答える