java編程約瑟夫問(wèn)題實(shí)例分析

2024-07-13 10:15:30

字體：大中小

供稿：網(wǎng)友

一、簡(jiǎn)介

約瑟夫問(wèn)題（有時(shí)也稱為約瑟夫斯置換，是一個(gè)出現(xiàn)在計(jì)算機(jī)科學(xué)和數(shù)學(xué)中的問(wèn)題。在計(jì)算機(jī)編程的算法中，類似問(wèn)題又稱為約瑟夫環(huán)。又稱“丟手絹問(wèn)題”.）

例子：

len個(gè)人圍成一個(gè)圈，玩丟手絹游戲。從第k個(gè)人開(kāi)始，從1開(kāi)始數(shù)數(shù)，當(dāng)數(shù)到m時(shí)，數(shù)m的人就退出圈子，當(dāng)圈子只剩下一個(gè)人為止。

問(wèn)題分析與算法設(shè)計(jì)

約瑟夫問(wèn)題并不難，但求解的方法很多；題目的變化形式也很多。這里給出一種實(shí)現(xiàn)方法。

題目中l(wèi)en個(gè)人圍成一圈，因而啟發(fā)我們用一個(gè)循環(huán)的鏈來(lái)表示，可以使用結(jié)構(gòu)數(shù)組來(lái)構(gòu)成一個(gè)循環(huán)鏈。結(jié)構(gòu)中有兩個(gè)成員，其一為指向第一個(gè)孩子的頭節(jié)點(diǎn)，另一個(gè)為作為判斷的節(jié)點(diǎn)temp（負(fù)責(zé)跑龍?zhí)祝?/p>

具體代碼如下：

package demo11;/**      * 約瑟夫問(wèn)題， 化為丟手絹      *       * @author tianq 思路：建立一個(gè)Child類 一個(gè)循環(huán)列表類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();	}}// 先建立一個(gè)孩子類class Child {	// 孩子的標(biāo)識(shí)	int no;	Child nextChild;	// 指向下一個(gè)孩子	public Child(int no) {		// 構(gòu)造函數(shù)給孩子一個(gè)id		this.no = no;	}}class CyclLink {	// 先定義一個(gè)指向鏈表第一個(gè)小孩的引用	// 指向第一個(gè)小孩的引用，不能動(dòng)	Child firstChild = null;	Child temp = null;	int len = 0;	// 表示共有幾個(gè)小孩	int k = 0;	//開(kāi)始的孩子	int m = 0;	//數(shù)到幾推出	// 設(shè)置m	public void setM(int m) {		this.m = m;	}	// 設(shè)置鏈表的大小	public void setLen(int len)	  {		this.len = len;	}	// 設(shè)置從第幾個(gè)人開(kāi)始數(shù)數(shù)	public void setK(int k) {		this.k = k;	}	// 開(kāi)始play	public void play() {		Child temp = this.firstChild;		// 1.先找到開(kāi)始數(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;			}			// 找到要出圈的前一個(gè)小孩			Child temp2 = temp;			while (temp2.nextChild != temp) {				temp2 = temp2.nextChild;			}			// 3.將數(shù)到m的小孩，退出			temp2.nextChild = temp.nextChild;			// 讓temp指向下一個(gè)數(shù)數(shù)的小孩			temp = temp.nextChild;			// this.show();			this.len--;		}		// 最后一個(gè)小孩		System.out.println("最后出圈" + temp.no);	}	// 初始化環(huán)形鏈表	public void createLink() {		for (int i = 1; i <= len; i++) {			if (i == 1) {				// 創(chuàng)建第一個(gè)小孩				Child ch = new Child(i);				this.firstChild = ch;				this.temp = ch;			} else {				if (i == len) {					// 創(chuàng)建第一個(gè)小孩					Child ch = new Child(i);					temp.nextChild = ch;					temp = ch;					temp.nextChild = this.firstChild;				} else {					// 繼續(xù)創(chuàng)建小孩					Child ch = new Child(i);					temp.nextChild = ch;					temp = ch;				}			}		}	}	// 打印該環(huán)形鏈表	public void show() {		Child temp = this.firstChild;		do {			System.out.print(temp.no + " ");			temp = temp.nextChild;		}		while (temp != this.firstChild);	}}

結(jié)果：

約瑟夫問(wèn)題,java編程