SicilyFunny Game

一、題目描述

Two players, Singa and Suny, play, starting with two natural numbers. Singa, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Suny, the second player, does the same with the two resulting numbers, then Singa, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7):

     25 711 74 74 31 31 0

an Singa wins.

二、輸入

The input consists of a number of lines. Each line contains two positive integers (<2^31) giving the starting two numbers of the game. Singa always starts first. The input ends with two zeros.

三、輸出

For each line of input, output one line saying either Singa wins or Suny wins assuming that both of them play perfectly. The last line of input contains two zeroes and should not be processed.

四、解題思路

一開始，看完題目完全沒頭緒，不知道從何下手。后來想想，這是一個博弈游戲，按照游戲規則，如果其中一個數不比另外一個數大一倍或一倍以上時，游戲將進行簡單地相減。

if(nultipleNum2 > nultipleNum1)nultipleNum2 -= nultipleNum1;

如果，出現一個數是另外一個數的n倍，游戲結束。
當其中一個數是另外一個數的二倍以上(n倍)時，這時玩家可以根據逆推的方法選擇減去n倍或者n-1倍，以達到讓自己贏的情況。

五、代碼

#include<iostream>using namespace std;int main()
{int num1, num2;cin >> num1 >> num2;while(num1 || num2){int nultipleNum1, nultipleNum2;nultipleNum1 = num1;nultipleNum2 = num2;int result = 0;    //記錄輪到誰，1：Singa，0：Sunywhile(nultipleNum1 && nultipleNum2) //如果兩個數都大于0，游戲繼續{result++;result %= 2;if(nultipleNum1 > nultipleNum2){if(nultipleNum1 / nultipleNum2 >= 2) break;     //當遇到一個數是另外一個數的兩倍或兩倍以上時，即能贏得游戲else nultipleNum1 -= nultipleNum2;}else{if(nultipleNum2 / nultipleNum1 >= 2) break;else nultipleNum2 -= nultipleNum1;}}if(result == 1) cout << "Singa wins" << endl;else cout << "Suny wins" << endl;cin >> num1 >> num2;}return 0;
}