2021-03-26：给定一个正整数N，表示有N份青草统一堆放在仓库里。有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草。不管是牛

2021-03-26：给定一个正整数N，表示有N份青草统一堆放在仓库里。有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草。不管是牛还是羊，每一轮能吃的草量必须是：1，4，16，64…(4的某次方)。谁最先把草吃完，谁获胜。假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定。根据唯一的参数N，返回谁会赢。

福大大 答案2021-03-26：

1.自然智慧即可。
递归。

2.根据结果反推，找规律。
N被5整除，余0或者余2，后手赢。

代码用golang编写，代码如下：

package main

import "fmt"

func main() {
    for i := 0; i <= 50; i++ {
        fmt.Println(i, " : ", winner1(i), winner2(i))
    }
}

// 如果n份草，最终先手赢，返回"先手"
// 如果n份草，最终后手赢，返回"后手"
func winner1(n int) string {
    if n < 5 {
        if n == 0 || n == 2 {
            return "后手"
        } else {
            return "先手"
        }
    }
    base := 1
    for base <= n {
        if winner1(n-base) == "后手" {
            return "先手"
        }
        if base > n/4 { // 防止base*4之后溢出
            break
        }
        base *= 4
    }
    return "后手"
}
func winner2(n int) string {
    if n%5 == 0 || n%5 == 2 {
        return "后手"
    } else {
        return "先手"
    }
}

执行结果如下：

左神java代码
评论