※ 引述《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
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720410231.A.D6A.html