笔试题-牛羊吃草问题

2022-6-22 diaba 笔试题 

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));
        }
    }
}

« scp拷贝文件 | 笔试题-最少的袋子数装苹果»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022