問題描述
Josephu(約瑟夫、約瑟夫環) 問題 Josephu 問題為：設編號為1，2，… n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數，數到m 的那個人出列，它的下一位又從1開始報數，數到m的那個人又出列，依次類
推，直到所有人出列為止，由此產生一個出隊編號的序列，
舉個例子
n = 5 , 即有5個人
k = 1, 從第一個人開始報數
m = 2, 數2下
經過一次出圈后
第二次出圈
第三次出圈
第四次出圈
所以最終的出圈順序 2->4->1->5->3
以上方法是使用單向回圈鏈表來完成的，下面看代碼展示
創建一個孩子類，每個孩子物件表示一個節點
class Boy{
//小孩編號
private int no;
//下一個小孩
private Boy next;
//構造器
public Boy(int no){
this.no = no;
}
public int getNo() {
return no;
}
public Boy getNext() {
return next;
}
public void setNo(int no) {
this.no = no;
}
public void setNext(Boy next) {
this.next = next;
}
}
創建單向回圈鏈表
并且創建添加孩子和顯示的方法
class CircleSingleLinkedList{
private Boy first = null;
public CircleSingleLinkedList(){}
/**
* 添加指定的節點
* @param nums
*/
public void add(int nums){
if(nums < 1){
System.out.println("輸入的資料不合法~~");
return;
}
Boy curBoy = null;
for (int i = 1; i < nums + 1; i++) {
Boy boy = new Boy(i);
if(i == 1){
first = boy;
curBoy = first;
boy.setNext(first);
}else{
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
public void showBoy(){
if (first == null){
System.out.println("鏈表為空~~");
return;
}
//因為first不能動，所以創建一個輔助指標
Boy curBoy = first;
while(true){
System.out.println("小孩的編號是" + curBoy.getNo());
if (curBoy.getNext() == first)
break;
curBoy = curBoy.getNext();
}
}
}重點：出圈
/**
* 根據用戶輸入，計算小孩出圈的順序
* @param startNo 開始小孩的編號
* @param countNum 一次數幾下
* @param nums 總共小孩數
*/
public void countBoy(int startNo,int countNum,int nums){
if(first == null || startNo < 1 || startNo > nums){
System.out.println("輸入的資料有誤~~~");
return;
}
//創建輔助指標，指向first指標的前一位
Boy helper = first;
while(helper.getNext() != first ){
helper = helper.getNext();
}
//根據開始小孩的編號，是first指標指向開始小孩
for (int i = 0; i < startNo - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//開始報數出隊
while(first.getNext() != first){
//報數
for (int i = 0; i < countNum - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//出隊
System.out.println("小孩" + first.getNo() + "出圈~~");
helper.setNext(first.getNext());
first = first.getNext();
}
System.out.println("最后出圈的小孩編號" + first.getNo());
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/226200.html
標籤：java