Josephus環(huán)的四種解法(約瑟夫環(huán))基于java詳解
約瑟夫環(huán)
約瑟夫環(huán)(約瑟夫問題)是一個(gè)數(shù)學(xué)的應(yīng)用問題:已知n個(gè)人(以編號(hào)1,2,3…n分別表示)圍坐在一張圓桌周圍。從編號(hào)為k的人開始報(bào)數(shù),數(shù)到m的那個(gè)人出列;他的下一個(gè)人又從1開始報(bào)數(shù),數(shù)到m的那個(gè)人又出列;依此規(guī)律重復(fù)下去,直到圓桌周圍的人全部出列。
通常解決這類問題時(shí)我們把編號(hào)從0~n-1,最后結(jié)果+1即為原問題的解
引用別人的一個(gè)圖:直觀說明問題
分析:
- 第一步:從1開始報(bào)數(shù)為3的時(shí)候就刪除3號(hào)結(jié)點(diǎn)
- 第二步:從4號(hào)結(jié)點(diǎn)開始報(bào)數(shù),當(dāng)為3的時(shí)候刪除6號(hào)結(jié)點(diǎn);
- 第三步:從7號(hào)結(jié)點(diǎn)開始報(bào)數(shù),當(dāng)為3的時(shí)候刪除1號(hào)結(jié)點(diǎn);
- 第四步:從2號(hào)結(jié)點(diǎn)開始報(bào)數(shù),當(dāng)為3的時(shí)候刪除5號(hào)結(jié)點(diǎn);
- 第五步:從7號(hào)結(jié)點(diǎn)開始報(bào)數(shù),當(dāng)為3的時(shí)候刪除2號(hào)結(jié)點(diǎn);
- 第六步:從4號(hào)元素開始報(bào)數(shù),當(dāng)為3的時(shí)候刪除8號(hào)結(jié)點(diǎn);
- 第七步:又從4號(hào)開始報(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 都沒有出去
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的示例代碼,本文通過示例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-04-04
Mybatis 自動(dòng)映射(使用需謹(jǐn)慎)
這篇文章主要介紹了Mybatis 自動(dòng)映射(使用需謹(jǐn)慎),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
Java實(shí)現(xiàn)自動(dòng)生成縮略圖片
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)自動(dòng)生成縮略圖片,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-04-04
Jmeter參數(shù)化獲取序列數(shù)據(jù)實(shí)現(xiàn)過程
這篇文章主要介紹了Jmeter參數(shù)化獲取序列數(shù)據(jù)實(shí)現(xiàn)過程,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
使用springboot aop來實(shí)現(xiàn)讀寫分離和事物配置
這篇文章主要介紹了使用springboot aop來實(shí)現(xiàn)讀寫分離和事物配置,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-04-04
Spring解決循環(huán)依賴的方法(三級(jí)緩存)
今天,我們要說的是spring是如何解決循環(huán)依賴的。對(duì)于一個(gè)問題說解決之前,我們首先要先明確形成問題的本因。那么循環(huán)依賴,何為循環(huán)依賴呢?感興趣的朋友跟隨小編一起看看吧2021-11-11
IntelliJ IDEA中使用mybatis-generator的示例
這篇文章主要介紹了IntelliJ IDEA中使用mybatis-generator,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-04-04
Java實(shí)現(xiàn)畫圖的詳細(xì)步驟(完整代碼)
今天給大家?guī)淼氖顷P(guān)于Java的相關(guān)知識(shí),文章圍繞著Java實(shí)現(xiàn)畫圖的詳細(xì)步驟展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下2021-06-06

