2022-12-02：有a块草莓蛋糕，有b块芝士蛋糕，两人轮流拿蛋糕，
每次不管是谁只能选择在草莓蛋糕和芝士蛋糕中拿一种，
拿的数量在1~m之间随意，
谁先拿完最后的蛋糕谁赢。
返回先手赢还是后手赢。
nim博弈。
答案2022-12-02：
找规律法。
1.a==b
蛋糕一样多
先手必输，因为先手不管拿什么，拿多少
后手都在另一堆上，拿同样多的蛋糕
继续让两堆蛋糕一样多
最终先手必输，后手必赢
2.a!=b
如果 a != b
关注a和b的差值，
谁最先遇到差值为0，谁输
那么这就是巴什博奕
差值蛋糕数量共rest个。
每次从最少取1个，最多取m个，最后取光的人取胜。
如果rest=(m 1)*k s (s!=0) 那么先手一定必胜
因为第一次取走s个，
接下来无论对手怎么取，
先手都能保证取到所有(m 1)倍数的点，
那么循环下去一定能取到差值最后一个。
时间复杂度：O(1)。
空间复杂度：O(1)。
代码用rust编写。代码如下：
代码语言：rust复制use std::iter::repeat;
fn main() {
let vv = 100;
println!("测试开始");
for a in 0..=vv {
for b in 0..vv {
for m in 0..vv {
let ans1 = who_win1(a, b, m);
let ans2 = who_win2(a, b, m);
if ans1 != ans2 {
println!("出错了！");
println!("a : {}", a);
println!("b : {}", b);
println!("m : {}", m);
println!("ans1 : {}", ans1);
println!("ans2 : {}", ans2);
}
}
}
}
println!("测试结束");
}
// 草莓蛋糕a块
// 巧克力蛋糕b块
// 每次可以在任意一种上拿1~m块
// 返回谁会赢，"先手" or "后手"
static mut dp: [[[&str; 101]; 101]; 101] = [[[""; 101]; 101]; 101];
fn get_max<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn get_min<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
// 暴力方法
// 为了验证
fn who_win1(a: i32, b: i32, m: i32) -> &'static str {
if m >= get_max(a, b) {
// nim博弈
return if a != b { "先手" } else { "后手" };
}
if a == b {
// 蛋糕一样多
// 先手必输，因为先手不管拿什么，拿多少
// 后手都在另一堆上，拿同样多的蛋糕
// 继续让两堆蛋糕一样多
// 最终先手必输，后手必赢
return "后手";
}
if unsafe { dp[a as usize][b as usize][m as usize] } != "" {
return unsafe { dp[a as usize][b as usize][m as usize] };
}
let mut ans = "后手";
for pick in 1..=get_min(a, m) {
if who_win1(a - pick, b, m) == "后手" {
ans = "先手";
}
if ans == "先手" {
break;
}
}
for pick in 1..=get_min(b, m) {
if who_win1(a, b - pick, m) == "后手" {
ans = "先手";
}
if ans == "先手" {
break;
}
}
unsafe {
dp[a as usize][b as usize][m as usize] = ans;
}
return ans;
}
// 正式解法
// 时间复杂度O(1)
// 先看nim博弈
fn who_win2(a: i32, b: i32, m: i32) -> &'static str {
// if m >= get_max(a, b) {
// // nim博弈
// return if a != b { "先手" } else { "后手" };
// }
// m < max(a,b)
if a == b {
// 蛋糕一样多
// 先手必输，因为先手不管拿什么，拿多少
// 后手都在另一堆上，拿同样多的蛋糕
// 继续让两堆蛋糕一样多
// 最终先手必输，后手必赢
return "后手";
}
// 如果 a != b
// 关注a和b的差值，
// 谁最先遇到差值为0，谁输
// 那么这就是巴什博奕
// 差值蛋糕数量共rest个。
// 每次从最少取1个，最多取m个，最后取光的人取胜。
// 如果rest=(m 1)*k s (s!=0) 那么先手一定必胜
// 因为第一次取走s个，
// 接下来无论对手怎么取，
// 先手都能保证取到所有(m 1)倍数的点，
// 那么循环下去一定能取到差值最后一个。
let rest = get_max(a, b) - get_min(a, b);
return if rest % (m 1) != 0 {
"先手"
} else {
"后手"
};
}执行结果如下：
在这里插入图片描述左神java代码
