写点什么

2022-12-02:有 a 块草莓蛋糕,有 b 块芝士蛋糕,两人轮流拿蛋糕, 每次不管是谁只能选择在草莓蛋糕和芝士蛋糕中拿一种, 拿的数量在 1~m 之间随意, 谁先拿完最后的蛋糕谁赢。 返回先手赢还是后手赢。

  • 2022-12-02
    北京
  • 本文字数:1887 字

    阅读完需:约 6 分钟

2022-12-02:有a块草莓蛋糕,有b块芝士蛋糕,两人轮流拿蛋糕, 每次不管是谁只能选择在草莓蛋糕和芝士蛋糕中拿一种, 拿的数量在1~m之间随意, 谁先拿完最后的蛋糕谁赢。 返回先手赢还是后手赢。

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 编写。代码如下:


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代码

发布于: 刚刚阅读数: 4
用户头像

还未添加个人签名 2021-02-15 加入

还未添加个人简介

评论

发布
暂无评论
2022-12-02:有a块草莓蛋糕,有b块芝士蛋糕,两人轮流拿蛋糕, 每次不管是谁只能选择在草莓蛋糕和芝士蛋糕中拿一种, 拿的数量在1~m之间随意, 谁先拿完最后的蛋糕谁赢。 返回先手赢还是后手赢。_算法_福大大架构师每日一题_InfoQ写作社区