一、簡介
約瑟夫問題（有時也稱為約瑟夫斯置換，是一個出現在計算機科學和數學中的問題。在計算機編程的算法中，類似問題又稱為約瑟夫環。又稱“丟手絹問題”.）
例子：
len個人圍成一個圈，玩丟手絹遊戲。從第k個人開始，從1開始數數，當數到m時，數m的人就退出圈子，當圈子只剩下一個人為止。
問題分析與算法設計
約瑟夫問題並不難，但求解的方法很多；題目的變化形式也很多。這裡給出一種實現方法。
題目中len個人圍成一圈，因而啟發我們用一個循環的鏈來表示，可以使用結構數組來構成一個循環鏈。結構中有兩個成員，其一為指向第一個孩子的頭節點，另一個為作為判斷的節點temp（負責跑龍套）。
具體代碼如下：
package demo11;/** * 約瑟夫問題， 化為丟手絹* * @author tianq 思路：建立一個Child類一個循環列表類CyclLink */public class demo11 {public static void main(String[] args) {CyclLink cyclink = new CyclLink();cyclink.setLen(15);cyclink.createLink();cyclink.setK(2);cyclink.setM(2);cyclink.show();cyclink.play();}}// 先建立一個孩子類class Child {// 孩子的標識int no;Child nextChild;// 指向下一個孩子public Child(int no) {// 構造函數給孩子一個idthis.no = no;}}class CyclLink {// 先定義一個指向鍊錶第一個小孩的引用// 指向第一個小孩的引用，不能動Child firstChild = null;Child temp = null;int len = 0;// 表示共有幾個小孩int k = 0;//開始的孩子int m = 0;//數到幾推出// 設置mpublic void setM(int m) {this.m = m;}// 設置鍊錶的大小public void setLen(int len) {this.len = len;}// 設置從第幾個人開始數數public void setK(int k) {this.k = k;}// 開始playpublic void play() {Child temp = this.firstChild;// 1.先找到開始數數的人for (int i = 1; i < k; i++) {temp = temp.nextChild;}while (this.len != 1) {// 2.數m下for (int j = 1; j < m; j++) {temp = temp.nextChild;}// 找到要出圈的前一個小孩Child temp2 = temp;while (temp2.nextChild != temp) {temp2 = temp2.nextChild;}// 3.將數到m的小孩，退出temp2.nextChild = temp.nextChild;// 讓temp指向下一個數數的小孩temp = temp.nextChild;// this.show();this.len--;}// 最後一個小孩System.out.println("最後出圈" + temp.no);}// 初始化環形鍊錶public void createLink() {for (int i = 1; i <= len; i++) {if (i == 1) {// 創建第一個小孩Child ch = new Child(i);this.firstChild = ch;this.temp = ch;} else {if (i == len) {// 創建第一個小孩Child ch = new Child(i);temp.nextChild = ch;temp = ch;temp.nextChild = this.firstChild;} else {// 繼續創建小孩Child ch = new Child(i);temp.nextChild = ch;temp = ch;}}}}// 打印該環形鍊錶public void show() {Child temp = this.firstChild;do {System.out.print(temp.no + " ");temp = temp.nextChild;}while (temp != this.firstChild);}}結果：
總結
以上就是本文關於java編程約瑟夫問題實例分析的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！