编程挑战高校俱乐部数字游戏答案

题目详情

两个人玩一个数字游戏，给定两个正整数A,B，两个人轮流从一个数中减去另外一个数的正数倍，要保证结果非负，首先得到0的人获胜。例如：30 8经过一步操作可以变为22 8 或者14 8 或者 6 8。两个人都足够聪明。

输入格式：
多组数据，每组数据占一行是两个空格分隔的正整数（在32位整书范围内）
输出格式：
每组数据一行，输出是第一个人赢，还是第二个人赢。

答题说明
输入样例
3 5
4 5
输出样例：

1

2

代码如下

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Mathematics {
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        
        int min = 0;//较小数
        int max = 0;//较大数
        while (cin.hasNext()) {
            min = cin.nextInt();
            max = cin.nextInt();
            if (min > max) {
                int temp = min;
                min = max;
                max = temp;
            }
            
            if (max % min == 0) {
                System.out.println(1);//第一个人赢
                continue;
            }
            
            List<Integer> queue = new ArrayList<Integer>();
            while (true) {
                int shang = max / min;
                int mod = max % min;
                if (mod == 0)
                    break;
                queue.add(shang);
                
                if (min > mod) {
                    int temp = min;
                    min = mod;
                    mod = temp;
                }
                max = mod;
            }
            
            int size = queue.size();
            if (size == 1) {
                if (queue.get(0) == 1) {
                    System.out.println(2);//第二个人赢
                }
                else {
                    System.out.println(1);//第一个人赢
                }
                continue;
            }
            
            int win = -1;
            for (int i = size - 1; i >= 0; i--) {
                if (i == size - 1) {
                    if (queue.get(i) == 1) {
                        win = 1;
                    }
                    else {
                        win = 2;
                    }
                }
                else if (i == 0) {
                    if (win == 2 && queue.get(0) > 1) {
                        win = 1;
                    }
                }
                else {
                    if (queue.get(i) == 1) {
                        win = win == 1 ? 2 : 1;
                    }
                    else {
                        win = 2;
                    }
                }
            }
            System.out.println(win);
        }
        cin.close();
    }
    
}

版权声明：本文为博主原创文章，未经博主允许不得转载。