a683.
01363 - Joseph's Problem
內容
約瑟夫很喜歡參加程式比賽。他最喜歡的題目理所當然就是約瑟夫問題。
題目敘述如下:
有n個人編號從0到n-1圍成一圈。從第0個人數到第k個人將會被處決。
在那之後剩下來的人中編號為第k個人會接著被處決，一直到只剩下一個人為止。
這個人變是存活下來的唯一一個人。在這個問題裡將會給定n跟k並求最後生還者一開始的編號。
聰明如你當然知道這個問題的解法。解法相當的短，事實上只需要一個迴圈便可求得。
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r;
其中 x mod y 表示x除以y後的餘數。
但約瑟夫不是相當的聰明。他懂得這個演算法，卻不懂背後的原理。因此他是實上只記得演算法的一部分，
而誤解了其中的一部分，且告訴他的朋友安卓這著名的問題解法如下:
r := 0;
for i from 1 to n do
r := r + (k mod i);
return r;
安卓當場指證出了約瑟夫的錯誤，但卻也計算出了約瑟夫提供的演算法的錯誤答案結果，作為對照。
給你n和k請找出
輸入說明
輸入包含多組測試資料，每組測試資料包含整數n跟k (1n, k
109).
輸出說明
對於每組輸入請輸出其對應的和
範例輸入
#1
5 3
範例輸出
#1
7
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (100%): 3.0s , <1M
公開 測資點#0 (100%): 3.0s , <1M
提示 ：
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||