第７５章 石取りゲーム　その２

石の山の数がn個、一度に取れる最大の石の個数がm個の場合を考えてみます。

もし自分が石を取って石山の数がk(m+1)+1個となったらどうでしょうか。

次に相手がp個取ったら、自分は(m+1-p)個とります。

石山の数は(k-1)(m+1)+1個となります。つまり、１回のターンでm+1個ずつ 石山の数が減るように石を取ることが出来るのです。ついには１個のみが残ることになります。

では、どのように石をとれば石山の数がk(m+1)+1個となるのでしょうか。

n-x=k(m+1)+1

x=-k(m+1)+(n-1)・・・(*)

x=(n-1)%(m+1)

最後の変形はわかったでしょうか。

a%b=c

これは、

c=-kb+a

と同義です。これは、(*)と同じ形になっていますね。

では、プログラムを見てみましょう。前章とほとんど同じでよいはずです。

コンピュータが取る時に乱数ではなく、(n-1)%(m+1)個取ります。 これで、残りの石はk(m+1)+1個となります。あとは、相手の取る石(p)に合わせて (m+1-p)個取っていけばよいです。

しかし、最初に取る石の個数が０個((n-1)%(m+1)=0)となってしまう場合もあります。 この時は、１個だけ取って相手の出方を待ちます。

// game2_02.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int takestone(int *, int, int, int);
int think(int, int);

int main()
{
    // nStone:石の数 nGet:取れる石の数 nSente:１なら人が先手
    // nOrder:１なら先手、-1なら後手の番

    int nStone, nGet, nSente, nOrder, nResult;
    char answer[8];

    printf("石を交互に取り、最後の１個を取った人が負けです\n");
    while (1) {
        nOrder = 1;
        printf("石の数は(5以上100以下)==");
        gets(answer);
        nStone = atoi(answer);
        if (nStone < 5 || nStone > 100) {
            printf("石の数が不正です\n");
            continue;
        }
        while (1) {
            printf("一度に取れる石の数は(2以上)==");
            gets(answer);
            nGet = atoi(answer);
            if (nGet >= nStone) {
                printf("一度に取れる石の数が多すぎます\n");
                continue;
            }
            if (nGet < 2) {
                printf("一度に取れる石の数が少なすぎます\n");
                continue;
            }
            break;
        }
        printf("あなたが先手になりますか(Y/N)--");
        gets(answer);
        if (strcmp(answer, "y") == 0 || strcmp(answer, "Y") == 0) {
            nSente = 1;
        } else {
            nSente = 0;
        }
        while (1) {
            nResult = takestone(&nStone, nGet, nSente, nOrder);
            if (nResult == -1)
                break;
            nOrder *= -1;
        }
        printf("続けますか(Y/N)--");
        gets(answer);
        if (strcmp(answer, "n") == 0 || strcmp(answer, "N") == 0)
            break;
        printf("======================\n\n");
    }
    return 0;
}

int takestone(int *pstone, int nGet, int nSente, int nOrder)
{
    char answer[8];
    int n;

    srand((unsigned)time(NULL));

    if ((nOrder == 1 && nSente == 1) || (nOrder == -1 && nSente == 0)) { //人が先手で現在先手の番
        while (1) {
            printf("取る石の数は--");
            gets(answer);
            n = atoi(answer);
            if (n > nGet) {
                printf("一度に取れる石の数は%d個までです\n", nGet);
                continue;
            }
            if (n <= 0) {
                printf("１個以上を指定してください\n");
                continue;
            }
            if (n >= *pstone) {
                printf("そのような取り方は出来ません\n");
                continue;
            }
            *pstone -= n;
            if (*pstone == 1) {
                printf("あなたの勝ちです\n");
                return -1;
            }
            break;
        }
    } else {
        if (*pstone <= nGet + 1) {
            n = *pstone - 1;
        } else {
            n = think(*pstone, nGet);
        }
        printf("コンピュータは%d個取りました\n", n);
        *pstone -= n;
        if (*pstone == 1) {
            printf("コンピュータの勝ちです\n");
            return -1;
        }
    }
    printf("残りの石は%d個です\n", *pstone);
    return 0;
}

int think(int nStone, int nGet)
{
    int x;

    x = (nStone - 1) % (nGet + 1);
    if (x == 0)
        return 1;
    else
        return x;
}

また、石の個数を「○」などで表示しておくとゲームの臨場感(?)が高まります。 挑戦してみてください。