您好,登錄后才能下訂單哦!
小編給大家分享一下Josephus環(huán)的解法有哪些,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
約瑟夫環(huán)
約瑟夫環(huán)(約瑟夫問題)是一個數(shù)學(xué)的應(yīng)用問題:已知n個人(以編號1,2,3…n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數(shù),數(shù)到m的那個人出列;他的下一個人又從1開始報數(shù),數(shù)到m的那個人又出列;依此規(guī)律重復(fù)下去,直到圓桌周圍的人全部出列。
通常解決這類問題時我們把編號從0~n-1,最后結(jié)果+1即為原問題的解
引用別人的一個圖:直觀說明問題
分析:
第一步:從1開始報數(shù)為3的時候就刪除3號結(jié)點
第二步:從4號結(jié)點開始報數(shù),當(dāng)為3的時候刪除6號結(jié)點;
第三步:從7號結(jié)點開始報數(shù),當(dāng)為3的時候刪除1號結(jié)點;
第四步:從2號結(jié)點開始報數(shù),當(dāng)為3的時候刪除5號結(jié)點;
第五步:從7號結(jié)點開始報數(shù),當(dāng)為3的時候刪除2號結(jié)點;
第六步:從4號元素開始報數(shù),當(dāng)為3的時候刪除8號結(jié)點;
第七步:又從4號開始報數(shù),當(dāng)為3的時候刪除4號結(jié)點,此時鏈表中只有一個7號結(jié)點,所以最后的結(jié)點就是7號結(jié)點;
1.模擬解法
public class 模擬 { public static void main(String[] args) { Scanner in=new Scanner(System.in); //總?cè)藬?shù) int n=in.nextInt(); // 數(shù)到m的那個人出列 int m=in.nextInt(); // 初始化為0 都沒有出去 int [] arr=new int[n]; //剩下的人數(shù) int peopleLeft=n; //初始化下標(biāo) int index=0; // 下標(biāo)計算器 int count=0; // >0 出循環(huán)為負(fù) while (peopleLeft>1){ if(arr[index]==0){ // count為計步器 不是下標(biāo)指向 count++; if(count==m){ arr[index]=1; count=0; peopleLeft--; } } index++; if(index==arr.length){ index=0; } } for (int i = 0; i < arr.length; i++) { if(arr[i]==0){ System.out.println(i+1); } } } }
2.遞歸解法
/** * 遞歸式: * f(1)=0; 第一個位置永遠(yuǎn)為0 * f(i)=f(i)+m%n; */ public static int yuesefu(int n,int m){ if(n==1){ return 0; }else { return (yuesefu(n-1,m) + m) % n; } } public static void main(String[] args) { System.out.println(yuesefu(41,3)+1); vailCode(41,3); } //逆推驗證代碼 public static void vailCode(int a,int b){ System.out.print(b); int reslut; for (int i = a; i >=2 ; i--) { reslut=2; for (int j = i; j <=a ; j++) { reslut=(reslut+b)%j; } System.out.printf("->%d",reslut+1); } }
3.循環(huán)鏈表解法
public class CircularLinkedList { public static void main(String[] args) { /** * 節(jié)點類 */ class Node{ private int data=1; private Node next; Node(){ next=null; } } Node head,temp; head=new Node(); head.data=1; int a=41; int b=3; // 臨時節(jié)點 temp=head; for (int i = 0; i < a; i++) { Node new_node=new Node(); new_node.data=i+1; temp.next=new_node; temp=new_node; } temp.next=head.next; while (head.next!=head){ for (int i = 0; i < b-1; i++) { head=head.next; } System.out.print("->"+(head.data+1)); head.next=head.next.next; } System.out.println(head.data); } }
4.Collection解法
public static void main(String[] args) { int a=41; int b=3; LinkedList<Integer> list = new LinkedList<>(); for (int i = 0; i < a; i++) { list.add(i+1); } while (list.size()>1){ for (int i = 0; i < b-1; i++) { list.add(list.remove()); } System.out.print("->"+list.getFirst()); list.remove();//remve head } System.out.println(list.getFirst()); }
以上是“Josephus環(huán)的解法有哪些”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對大家有所幫助,如果還想學(xué)習(xí)更多知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。