package com.jiucaiyuan.net.question;



/**

 * 牛羊吃草问题：有先吃和有后吃，看谁刚好吃完所有草

 * 吃草规则， 吃的时候只能吃4^m次幂份，看谁会胜利

 *

 * @Author jiucaiyuan  2022/6/22 23:11

 * @mail services@jiucaiyuan.net

 */



public class EatGrass {



    /**

     * 思路1：先手先吃，尝试所有情况，如果能胜利，就先手胜利，否则后手胜利，暴力尝试

     *

     * @param n

     * @return

     */

    public static String winner1(int n) {

        //0   1    2    3     4

        //后  先   后    先    先

        if (n < 5) {

            return (n == 0 || n == 2) ? "后手" : "先手";

        }

        //n>=5

        int base = 1; //先手决定吃的草份数

        //有问题

        while (base <= n) {

            //当一共有n份草，先手吃了base份，留给后手n-base份草

            //父过程是先手，子过程称为后收手

            if (winner1(n - base).equals("后手")) {

                return "先手";

            }

            if (base > n / 4) {  //防止base*4后溢出

                break;

            }

            base *= 4;

        }

        return "后手";

    }



    /**

     * 打表法：通过打印0-100份草的胜利情况：后先后先先后先后先先后先后先先后先后先先后先后先先

     * 分析规律写代码

     *

     * @param n

     * @return

     */

    public static String winner2(int n) {

        if (n % 5 == 0 || n % 5 == 2) {

            return "后手";

        }

        return "先手";

    }



    public static void main(String[] args) {

        for (int i = 0; i < 100; i++) {

            System.out.println(i + "\t" + winner1(i));

        }

    }

}