首页 > 代码库 > poj 2484 A Funny Game

poj 2484 A Funny Game

题目:http://poj.org/problem?

id=2484

一,题意:

n个硬币围成一个圈,Alice与Bob轮流从圈中取硬币。每次能够取一枚或者连续的两枚。

硬币取走后留下的空位不用填补,空位相隔的两个硬币视为不相邻。Alice第一个開始取。

取走最后一个硬币的人为胜利者。

二,解析:

该题为一道简单的博弈。是一道榜样对手动作的博弈。

先看看该博弈的神秘态 : 当该圈被取掉的硬币分成两部分,两部分硬币分别全然同样的时候

是个神秘态,这是先手必败,由于仅仅要后手榜样先手在相应的边取同样的硬币则必能取到最后一个硬币。

所以,在Alice取了硬币后仅仅要Bob,在圈中取相应的硬币将硬币分成全然同样的部分则BOb必胜。

可是当硬币数小于等于2是等时Alice能够一次性取完则Alice必胜。

三。代码:

#include <iostream>
#include <stdio.h>
using namespace std;
int N;
int main()
{
    while(scanf("%d",&N)!=EOF && N)
    {
        if(N<=2)
            printf("Alice\n");
        else
            printf("Bob\n");
    }
    return 0;
}

 


poj 2484 A Funny Game