取火柴游戲

時(shí)間限制: 1 Sec內(nèi)存限制: 128 MB

題目描述

輸入k及k個(gè)整數(shù)n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根數(shù)為ni；接著便是你和計(jì)算機(jī)取火柴棒的對(duì)弈游戲。取的規(guī)則如下：每次可以從一堆中取走若干根火柴，也可以一堆全部取走，但不允許跨堆取，也不允許不取。

誰取走最后一根火柴為勝利者。

例如：k＝2，n₁＝n₂＝2，A代表你，P代表計(jì)算機(jī)，若決定A先取：

A：(2,2)→(1,2) {從一堆中取一根}

P：(1,2)→(1,1) {從另一堆中取一根}

A：(1,1)→(1,0)

P：(1,0)→ (0,0) {P勝利}

如果決定A后取：

P：(2,2)→(2,0)

A：(2,0)→ 0,0) {A勝利}

又如k＝3，n1=1，n2＝2，n3＝3，A決定后取：

P：(1,2,3)→(0,2,3)

A：(0,2,3)→(0,2,2)

A已將游戲歸結(jié)為(2,2)的情況，不管P如何取A都必勝。

編一個(gè)程序，在給出初始狀態(tài)之后，判斷是先取必勝還是先取必?cái)。绻窍热”貏伲?qǐng)輸

出第一次該如何取。如果是先取必?cái)。瑒t輸出“l(fā)ose”。

輸入

輸入k及k個(gè)整數(shù)n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根數(shù)為ni；

輸出

判斷是先取必勝還是先取必?cái)。绻窍热”貏伲?qǐng)輸出第一次該如何取。如果是先取必?cái)。瑒t輸出“l(fā)ose”。

樣例輸入

3
3 6 9

樣例輸出

4 3
3 6 5 

輸出確實(shí)很坑人。。。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int n;
 6 int a[1111];
 7 int s,k,maxx;
 8 
 9 int main()
10 {
11     cin>>n;
12     s=k=maxx=0;
13     for(int i=0;i<n;i++)
14     {
15         cin>>a[i];
16         s=s^a[i];
17         if(i<n-1)
18             k=k^a[i];
19         if(a[maxx]<a[i])
20             maxx=i;
21     }
22     if(s==0)
23         cout<<"lose"<<endl;
24     else
25     {
26         cout<<a[maxx]-k<<" "<<maxx+1<<endl;
27         a[maxx]=k;
28         for(int i=0;i<n-1;i++)
29             cout<<a[i]<<" ";
30         cout<<a[n-1];
31     }
32     return 0;
33 }

總結(jié)

以上是生活随笔為你收集整理的【博弈论】取火柴游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。