一开始有21个球，甲和乙轮流拿球，甲先、乙后，
每个人在自己的回合，一定要拿不超过3个球，不能不拿。
最终谁的总球数为偶数，谁赢。
请问谁有必胜策略。
21球，是甲赢。如果把21变成其他正整数，误以为甲也一定赢，但实际上是不一定。可能甲赢，乙赢，打平。
通过递归可以发现规律。1甲 3乙 5乙 7乙，9甲 11乙 13乙 15乙。
代码用rust编写。代码如下：
fn main() {
let mut i = 1;
while i < 500 {
//let ans = win1(i,0,0,0);
let ans = win(i);
println!("i = {},ans = {}", i, ans);
i += 2;
}
}
// balls = 21
// ball是奇数
fn win(balls: i32) -> String {
return process(0, balls, 0, 0);
}
// 憋递归！
// turn 谁的回合！
// turn == 0 甲回合
// turn == 1 乙回合
// rest剩余球的数量
// 之前，jiaBalls、yiBalls告诉你！
// 当前，根据turn，知道是谁的回合！
// 当前，还剩多少球，rest
// 返回：谁会赢！
fn process(turn: i32, rest: i32, jia: i32, yi: i32) -> String {
if rest == 0 {
return if (jia & 1) == 0 {
String::from("甲")
} else {
String::from("乙")
};
}
// rest > 0, 还剩下球！
if turn == 0 {
// 甲的回合！
// 甲，自己赢！甲赢！
for pick in 1..=get_min(rest, 3) {
// pick 甲当前做的选择
if process(1, rest - pick, jia + pick, yi) == "甲" {
return String::from("甲");
}
}
return String::from("乙");
} else {
for pick in 1..=get_min(rest, 3) {
// pick 甲当前做的选择
if process(0, rest - pick, jia, yi + pick) == ("乙") {
return String::from("乙");
}
}
return String::from("甲");
}
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
// 我们补充一下设定，假设一开始的球数量不是21，是任意的正数
// 如果最终两个人拿的都是偶数，认为无人获胜，平局
// 如果最终两个人拿的都是奇数，认为无人获胜，平局
// rest代表目前剩下多少球
// cur == 0 代表目前是甲行动
// cur == 1 代表目前是乙行动
// first == 0 代表目前甲所选的球数，加起来是偶数
// first == 1 代表目前甲所选的球数，加起来是奇数
// second == 0 代表目前乙所选的球数，加起来是偶数
// second == 1 代表目前乙所选的球数，加起来是奇数
// 返回选完了rest个球，谁会赢，只会返回"甲"、"乙"、"平"
// win1方法，就是彻底暴力的做所有尝试，并且返回最终的胜利者
// 在甲的回合，甲会尝试所有的可能，以保证自己会赢，如果自己怎么都不会赢，那也要尽量平局，如果这个也不行，只能对方赢
// 在乙的回合，乙会尝试所有的可能，以保证自己会赢，如果自己怎么都不会赢，那也要尽量平局，如果这个也不行，只能对方赢
// 算法和数据结构体系学习班，视频39章节，牛羊吃草问题，就是类似这种递归
fn win1(rest: i32, cur: i32, first: i32, second: i32) -> String {
if rest == 0 {
if first == 0 && second == 1 {
return String::from("甲");
}
if first == 1 && second == 0 {
return String::from("乙");
}
return String::from("平");
}
if cur == 0 {
// 甲行动
let mut best_ans = String::from("乙");
for pick in 1..=get_min(3, rest) {
let mut cur_ans = win1(rest - pick, 1, first ^ (pick & 1), second);
if cur_ans == "甲" {
best_ans = String::from("甲");
break;
}
if cur_ans == "平" {
best_ans = String::from("平");
}
}
return best_ans;
} else {
// 乙行动
let mut best_ans = String::from("甲");
for pick in 1..=get_min(3, rest) {
let mut cur_ans = win1(rest - pick, 0, first, second ^ (pick & 1));
if cur_ans == "乙" {
best_ans = String::from("乙");
break;
}
if cur_ans == "平" {
best_ans = String::from("平");
}
}
return best_ans;
}
}执行结果如下：
