-
Problem Description
兩個足夠聰明的人玩輪流取石頭的游戲，誰取到最后一個石頭誰就贏了，他們一次只能取1個、3個、7個或8個石頭，寫一程式判斷n個石頭時先取的人是輸還是贏，
輸入格式:
一個整數n，其值不超過10000000，
輸出格式：
如果先取的人贏，請以單獨一行輸出1，否則輸出0，
輸入樣例：
這里是3組輸入，
1
10
300
輸出樣例：
上面3組資料對應的輸出分別如下：
1
1
0
-
問題解讀
首先這兩個人都足夠聰明，假使第一個人先取，他會想盡辦法贏，但第二個人也不是吃素的，他會不遺余力的阻擊第一個人贏，由于石頭數不確定，我們不妨先用較小數目的石頭試試水，看看能否找到規律，
-
列舉分析
我們假設 P 1 P_1 P1?、 P 2 P_2 P2?分別代表第一個人和第二個人，且第一個人先取，現在來列舉幾種情況，看看第一個人什么情況下去會贏，
一個石頭：
注：第一個人贏，
兩個石頭：
注：第一個人輸，
三個石頭：
第一種情況:
注：第一個人贏，
第二種情況:
注：第一個人贏，
四個石頭：
第一種情況:
注：第一個人贏，
第二種情況:
注：第一個人贏，
五個石頭：
第一種情況:
注：第一個人贏，
第二種情況:
注：第一個人贏，
第三種情況:
注：第一個人贏，
繼續列舉，發現當石頭數為：2 4 6 15 17 19 30 32 34 36 45 47 49 51……時，第二個人贏，觀察這些資料可以發現：當n%15==0或2或4或6時，第二個人贏，其余情況第一個人贏，這樣，我們就找到了規律，
-
代碼實作
#include<iostream>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
if(n%15==0)
cout<<0;
else if(n%15==2)
cout<<0;
else if(n%15==4)
cout<<0;
else if(n%15==6)
cout<<0;
else
cout<<1;
}
return 0;
}
-
運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/238629.html
標籤：其他
下一篇：鏈表的中間結點20201221