[數學方法]OI練習題：硬幣遊戲 coins 解題報告

 硬幣遊戲  coins.cpp/c/pas

【問題描述】

Alice 和 Bob 決定要玩一個有趣的硬幣遊戲。遊戲的一開始他們把 n (1<=n<=10^6 ) 個硬幣放成一個圓圈，如下圖所示。一次操作是指拿走一個硬幣或者拿走兩個相鄰的硬幣，而其他的硬幣留在原來的位置不動。每次操作至少要拿走一個硬幣。從 Alice 開始，遊戲雙方輪流進行操作。拿到最後一個硬幣的人獲勝。

注意：當 n>3 時，我們沿順時針方向用 C1 ， C2 ， ….. Cn 來表示這 n 個硬幣。如果 Alice 拿走了 C2 ，那麼 C1 和 C3 就不相鄰了！（因為它們中間有一個空位置）

假設 Alice 和 Bob 都很聰明，並且兩個人都用最好的策略來比賽。現在請你來寫一個程序判斷誰將會贏得這個比賽？

 

【輸入格式】

* 第一行一個整數 k, 表示有 k 組測試資料。 (1<=k<=10000)

* 以下 k 行每行一個整數 n (1<=n<=10^6 ) ，表示遊戲開始時硬幣的個數。

【輸出格式】

* 對於每一個 n ，如果 Alice 能獲勝，輸出“ Alice ”，否則輸出“ Bob ”。

【輸入輸出樣例】

輸入：

3

1

2

3

輸出：

Alice

Alice

Bob

 。

【分析】

這是一道經典的博弈問題。這個遊戲大家都玩過吧，也都知道怎麼玩吧。

如果不知道，可以去看看『名探偵コナン』電視劇版『工藤新一への挑戦状』第六集。

犯人（和代小姐）利用這個數學知識，成功殺死了受害者（久美）。在工藤新一偵探的過程中，工藤新一和那個數學家都提到了這個遊戲。以下是電視劇截圖。

電視劇中也提到了，數學家說『不后攻的話就沒辦法贏的』，高木刑事說『總之 第一個出手是沒法贏的不是嗎』。
 因為Alice、Bob兩人都很聰明，兩人都是最好的策略，所以只要Alice一出手拿不到最後一個，那麼他已經輸了這局遊戲。
因此，程序也出來了，如果N>=3則Bob贏，如果N<3則Alice贏，就這麼簡單！

【我的代碼】

這麼簡單的程序就不用參考我的代碼了吧～所以不給出裸代碼了。

C++语言: 高亮代码由发芽网提供

01 #include <cstdio>
02 #include <cstdlib>
03 using namespace std;
04 int main()
05 {
06     freopen("coins.in","r",stdin);
07     freopen("coins.out","w",stdout);
08     int N;
09     int X;
10     scanf("%d\n",&N);
11     for(int i=1;i<=N;i++)
12     {
13         scanf("%d\n",&X);
14         if(X>=3)
15             printf("Bob\n");
16         else
17             printf("Alice\n");
18     }
19     return 0;
20 }