解答如下:
依據提議,可以將題目等價變換為:“n(n=17)人編號為0到(n-1)圍成壹圈,0號人開始從0報數,凡是報數為m-1 (m=3)倍數的人離開圈子,繼續到壹個,問他編號”
壹開始的狀態
0,1,2,3,4,5 ..... (n-2), (n-1) n個人
第壹個人被踢之後 設第壹個被踢的人的編號為k, 則 k = m%n-1 當n=17,m=3時,k=2。也就是說編號為2的人離開了圈子
這時候的狀態
0, .... (k-1), (k+1) ,(k+2)...(n-2),(n-1) (n-1)個人,當n=17,m=3時: 0,1,3,4,5,6,7,8,9,10,11,12,13,14,15,16
將這時候的編號做轉換. 因為是圍城壹個圈子,下壹個開始數的是(k+1).所以也可以表示為
(k+1),(k+2) ... (n-2),(n-1),0....(k-1) (n-1)個人,當n=17,m=3時: 3,4,5,6,7,8,9,10,11,12,13,14,15,16,0,1
重新編號。得到:
0,1,2,3,4...(n-3),(n-2)(n-1)個人 這個時候 ,這裏重新構成了壹個約瑟夫環。也就是說,這是壹個遞推的關系。
這裏我們進行了重新編號。那麽 (n-1)個人和 n個人之間的編號不壹樣的。但是兩者之間有壹定的關系,可以沖新編號推導出老的
公式如下: i' = (i+k)%(n-1) 比如,當n=17,m=3時 . 新的環編號是 (n-2),我要求他在老的環中的編號,那麽編號是 i' = ( (n-2) + k ) % (n-1) = 17%16 = 1,就是老的換種編號為1的那壹個
反過來有 :i = (i'+m)%n
有了上面的推斷,可以代碼如下:
int ysf(int n,int m){
if(n==1){
return 0; //當環內只有壹個人的時候,就是他自己
}
return (ysf(n-1,m) + m ) % n ;
}
------------------完整代碼---------------------
public class Test{
public static void main(String[] args){
int a = 17;
int b = 3;
System.out.println(ysf(a,b));
}
static int ysf(int n,int m){
if(n==1){
return 0;
}
return (ysf(n-1,m) +m) % n;
}
}