※ 引述《smart0eddie (smart0eddie)》之铭言：
: 2024-07-08
: 1823. Find the Winner of the Circular Game
: https://en.wikipedia.org/wiki/Josephus_problem
思路：
先写公式
J(1,k) = 0
代表只有一个人的时候第0个位置的人获胜(0-based)
而当多个人的时候 每次踢掉一个人的下一轮都是等于是n-1的新游戏
所以 J(n,k) = (J(n-1,k) + k) % n
说明 +k代表每次数人头的位置移动
%n代表圆形的余数 数人头超过一个圈要取余数 回到0开始计算位置
Code:
impl Solution {
pub fn find_the_winner(n: i32, k: i32) -> i32 {
let mut winner = 0;
for i in 1..=n {
winner = (winner + k) % i;
}
winner + 1
}
}