當前位置:編程學習大全網 - 編程語言 - java編程17人編號為0-16圍成壹圈,0號人開始從1報數,凡是報數為3倍數的人離開圈子,繼續到壹個,問他編號

java編程17人編號為0-16圍成壹圈,0號人開始從1報數,凡是報數為3倍數的人離開圈子,繼續到壹個,問他編號

這是壹個約瑟夫環的問題

解答如下:

依據提議,可以將題目等價變換為:“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;

}

}

  • 上一篇:與世界上的編程角色壹起玩。
  • 下一篇:紅外線報警器原理 紅外線報警器安裝
  • copyright 2024編程學習大全網