Josephus環(huán)的四種解法(約瑟夫環(huán))基于java詳解
約瑟夫環(huán)
約瑟夫環(huán)(約瑟夫問(wèn)題)是一個(gè)數(shù)學(xué)的應(yīng)用問(wèn)題:已知n個(gè)人(以編號(hào)1,2,3…n分別表示)圍坐在一張圓桌周圍。從編號(hào)為k的人開(kāi)始報(bào)數(shù),數(shù)到m的那個(gè)人出列;他的下一個(gè)人又從1開(kāi)始報(bào)數(shù),數(shù)到m的那個(gè)人又出列;依此規(guī)律重復(fù)下去,直到圓桌周圍的人全部出列。
通常解決這類問(wèn)題時(shí)我們把編號(hào)從0~n-1,最后結(jié)果+1即為原問(wèn)題的解
引用別人的一個(gè)圖:直觀說(shuō)明問(wèn)題
分析:
- 第一步:從1開(kāi)始報(bào)數(shù)為3的時(shí)候就刪除3號(hào)結(jié)點(diǎn)
- 第二步:從4號(hào)結(jié)點(diǎn)開(kāi)始報(bào)數(shù),當(dāng)為3的時(shí)候刪除6號(hào)結(jié)點(diǎn);
- 第三步:從7號(hào)結(jié)點(diǎn)開(kāi)始報(bào)數(shù),當(dāng)為3的時(shí)候刪除1號(hào)結(jié)點(diǎn);
- 第四步:從2號(hào)結(jié)點(diǎn)開(kāi)始報(bào)數(shù),當(dāng)為3的時(shí)候刪除5號(hào)結(jié)點(diǎn);
- 第五步:從7號(hào)結(jié)點(diǎn)開(kāi)始報(bào)數(shù),當(dāng)為3的時(shí)候刪除2號(hào)結(jié)點(diǎn);
- 第六步:從4號(hào)元素開(kāi)始報(bào)數(shù),當(dāng)為3的時(shí)候刪除8號(hào)結(jié)點(diǎn);
- 第七步:又從4號(hào)開(kāi)始報(bào)數(shù),當(dāng)為3的時(shí)候刪除4號(hào)結(jié)點(diǎn),此時(shí)鏈表中只有一個(gè)7號(hào)結(jié)點(diǎn),所以最后的結(jié)點(diǎn)就是7號(hào)結(jié)點(diǎn);
1.模擬解法
public class 模擬 { public static void main(String[] args) { Scanner in=new Scanner(System.in); //總?cè)藬?shù) int n=in.nextInt(); // 數(shù)到m的那個(gè)人出列 int m=in.nextInt(); // 初始化為0 都沒(méi)有出去 int [] arr=new int[n]; //剩下的人數(shù) int peopleLeft=n; //初始化下標(biāo) int index=0; // 下標(biāo)計(jì)算器 int count=0; // >0 出循環(huán)為負(fù) while (peopleLeft>1){ if(arr[index]==0){ // count為計(jì)步器 不是下標(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; 第一個(gè)位置永遠(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); } //逆推驗(yàn)證代碼 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é)點(diǎn)類 */ 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; // 臨時(shí)節(jié)點(diǎn) 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()); }
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
springboot2.6.7集成springfox3.0.0的示例代碼
這篇文章主要介紹了springboot2.6.7集成springfox3.0.0的示例代碼,本文通過(guò)示例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-04-04Mybatis 自動(dòng)映射(使用需謹(jǐn)慎)
這篇文章主要介紹了Mybatis 自動(dòng)映射(使用需謹(jǐn)慎),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10Java實(shí)現(xiàn)自動(dòng)生成縮略圖片
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)自動(dòng)生成縮略圖片,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-04-04Jmeter參數(shù)化獲取序列數(shù)據(jù)實(shí)現(xiàn)過(guò)程
這篇文章主要介紹了Jmeter參數(shù)化獲取序列數(shù)據(jù)實(shí)現(xiàn)過(guò)程,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07使用springboot aop來(lái)實(shí)現(xiàn)讀寫分離和事物配置
這篇文章主要介紹了使用springboot aop來(lái)實(shí)現(xiàn)讀寫分離和事物配置,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-04-04Spring解決循環(huán)依賴的方法(三級(jí)緩存)
今天,我們要說(shuō)的是spring是如何解決循環(huán)依賴的。對(duì)于一個(gè)問(wèn)題說(shuō)解決之前,我們首先要先明確形成問(wèn)題的本因。那么循環(huán)依賴,何為循環(huán)依賴呢?感興趣的朋友跟隨小編一起看看吧2021-11-11IntelliJ IDEA中使用mybatis-generator的示例
這篇文章主要介紹了IntelliJ IDEA中使用mybatis-generator,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-04-04淺談Spring如何解決循環(huán)依賴的問(wèn)題
這篇文章主要介紹了淺談Spring如何解決循環(huán)依賴的問(wèn)題,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09Java實(shí)現(xiàn)畫圖的詳細(xì)步驟(完整代碼)
今天給大家?guī)?lái)的是關(guān)于Java的相關(guān)知識(shí),文章圍繞著Java實(shí)現(xiàn)畫圖的詳細(xì)步驟展開(kāi),文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下2021-06-06