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

更新時間：2017年12月25日 16:16:39 作者：Mu_TQ

這篇文章主要介紹了java編程約瑟夫問題實例分析，具有一定借鑒價值，需要的朋友可以參考下。

一、簡介

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

例子：

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

問題分析與算法設計

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

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

具體代碼如下：

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

結果：