java編程約瑟夫問題實例分析

2024-07-13 10:15:30

字體：大中小

來源：轉載

供稿：網友

一、簡介

約瑟夫問題（有時也稱為約瑟夫斯置換，是一個出現在計算機科學和數學中的問題。在計算機編程的算法中，類似問題又稱為約瑟夫環。又稱“丟手絹問題”.）

例子：

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) {		// 構造函數給孩子一個id		this.no = no;	}}class CyclLink {	// 先定義一個指向鏈表第一個小孩的引用	// 指向第一個小孩的引用，不能動	Child firstChild = null;	Child temp = null;	int len = 0;	// 表示共有幾個小孩	int k = 0;	//開始的孩子	int m = 0;	//數到幾推出	// 設置m	public void setM(int m) {		this.m = m;	}	// 設置鏈表的大小	public void setLen(int len)	  {		this.len = len;	}	// 設置從第幾個人開始數數	public void setK(int k) {		this.k = k;	}	// 開始play	public 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編程