/**

?*?作者：徐守威

?*?功能：約瑟夫問題(丟手帕問題)

?*?具體問題：設(shè)編號(hào)為1,2,3....n的n個(gè)人圍坐一圈，約定編號(hào)為k（1<=k<=n）的人從1開始

?*?報(bào)數(shù)，數(shù)到m的那個(gè)人出列，它的下一位從一開始報(bào)數(shù)，報(bào)到m的那個(gè)人又出列，以此類推，

?*?直到所有人出列為止，如此產(chǎn)生一個(gè)出列編號(hào)的序列...

?*?解決方案：鏈表

?*/

package?com.jasxu;

import?java.io.*;

public?class?T4?{

?

/**

?*?@param?args

?*/

public?static?void?main(String[]?args){

//?TODO?Auto-generated?method?stub

try

{

InputStreamReader?isr=new?InputStreamReader(System.in);

BufferedReader?br=new?BufferedReader(isr);

System.out.println("請(qǐng)輸入?yún)⒓釉撚螒蛐『⒌膫€(gè)數(shù)：");

String?joinNmu=br.readLine();

System.out.println("請(qǐng)輸入您想從編號(hào)為幾的小孩開始報(bào)數(shù)？");

String?n1=br.readLine();

System.out.println("請(qǐng)輸入您想數(shù)到幾的小孩出列？");

String?n2=br.readLine();

int?num1=Integer.parseInt(n1);

int?num2=Integer.parseInt(n2);

int?joinLen=Integer.parseInt(joinNmu);

CycLink?cyclink=new?CycLink();

cyclink.setLen(joinLen);

cyclink.createLink();

cyclink.setK(num2);

cyclink.setM(2);

cyclink.show();

cyclink.play();

}

catch(Exception?e)

{

e.printStackTrace();

}

?

}

}

?

//構(gòu)建各個(gè)孩子

class?Child

{

//定義child的編號(hào)

int?no;

//定義可以指向下一個(gè)的指針

?

Child?nextChild=null;

//創(chuàng)建構(gòu)造函數(shù)

public?Child(int?no)

{

//賦編號(hào)

this.no=no;

}

}

//構(gòu)建一個(gè)環(huán)形鏈表

class?CycLink

{

//先定義一個(gè)指向鏈表第一個(gè)小孩的引用

//指向第一個(gè)小孩的引用，不能動(dòng)

Child?firstChild=null;

//定義一個(gè)游標(biāo)，相當(dāng)于跑龍?zhí)?/span>

Child?temp=null;

//定義一個(gè)表示大小的的len，表示共有幾個(gè)小孩

int?len=0;

int?k=0;

int?m=0;

//構(gòu)造函數(shù)，用來設(shè)置環(huán)形鏈表的大小

public?void?setLen(int?len)

{

this.len=len;

}

//設(shè)置m的值

public?void?setM(int?m)

{

this.m=m;

}

//設(shè)置從第幾個(gè)人開始數(shù)數(shù)

public?void?setK(int?k)

{

this.k=k;

}

//游戲?qū)崿F(xiàn)

public?void?play()

{

//設(shè)置跑龍?zhí)椎男『?/span>

Child?temp=this.firstChild;

//1.找到開始數(shù)數(shù)的人

for(int?i=1;i<k;i++)

{

temp=temp.nextChild;

}

while(this.len!=1)

{

//2.數(shù)m下

for(int?j=1;j<m;j++)

{

temp=temp.nextChild;

}

//3.找到要出圈的前一個(gè)小孩

//定義一個(gè)2號(hào)跑龍?zhí)椎娜?/span>

Child?temp2=temp;

while(temp2.nextChild!=temp)

{

temp2=temp2.nextChild;

}

//4.數(shù)完了過后將數(shù)到m的小孩退出圈

temp2.nextChild=temp.nextChild;

//讓temp指向下一個(gè)數(shù)數(shù)的小孩

temp=temp.nextChild;

this.len--;

}

//輸出最后一個(gè)小孩

System.out.println("最后出圈的小孩是："+temp.no+"號(hào)小孩！");

}

?

//初始化環(huán)形鏈表

public?void?createLink()

{

//統(tǒng)計(jì)有多少個(gè)孩子

for(int?i=1;i<=len;i++)

{

if(i==1)

{

//首先創(chuàng)建第一個(gè)小孩

Child?ch=new?Child(i);

//將第一個(gè)孩子的應(yīng)用交給firstChild

this.firstChild=ch;

//同時(shí)也要將引用交給跑龍?zhí)子?/span>

this.temp=ch;

}

else

{

//判斷是否是創(chuàng)建最后一個(gè)小孩

if(i==len)

{

//繼續(xù)創(chuàng)建小孩

Child?ch=new?Child(i);

//將temp的指針指向下一條地址的引用

temp.nextChild=ch;//這條線相當(dāng)于搭橋的線

//橋答完后還要讓temp指向剛剛創(chuàng)建的那個(gè)孩子

temp=ch;

//最后一個(gè)小孩的指針應(yīng)指向頭一個(gè)地址的引用

temp.nextChild=this.firstChild;

}

else

{

//繼續(xù)創(chuàng)建小孩

Child?ch=new?Child(i);

//將temp的指針指向下一條地址的引用

temp.nextChild=ch;//這條線相當(dāng)于搭橋的線

//橋答完后還要讓temp指向剛剛創(chuàng)建的那個(gè)孩子

temp=ch;

}

?

}

}

}

//打印該環(huán)形鏈表

public?void?show()

{

//定義一個(gè)跑龍?zhí)?/span>

Child?temp=this.firstChild;

do

{

System.out.print(temp.no+"?");

temp=temp.nextChild;

}while(temp!=this.firstChild);

}

}

?

轉(zhuǎn)載于:https://www.cnblogs.com/Jasxu/p/3529753.html

總結(jié)

以上是生活随笔為你收集整理的约瑟夫问题(丢手帕问题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。