约瑟夫环问题

问题描述

设编号为1，2，3 ……，n（n > 0）个人按顺时针方向围坐一圈，没人持有一个正整数密码。开始时任意给出一个报数上限值m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止报数，报 m 的人出列，并将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 开始顺序报数；如此下去，直到所有人全部出列为止。

基本要求：设计程序模拟该过程，给出出列人的编号序列。

测试数据：n=7，密码依次为：3，1，7，2，4，8，4，m= 20。

问题分析：

1. 要求输出编号序列，所以得保存每个人的编号；
2. 在出列过程中，要用到该出列人的密码，所以得保存密码。
3. 顺时针方向围坐一圈。

基于以上三点，可以设采用不带头结点单向循环链表。如下：

代码实现：

结点类：

public class Node {
	private int no;
	private int mima;
	private Node next;

	public Node(int no, int mima) {
		this.no = no;
		this.mima = mima;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public int getMima() {
		return mima;
	}

	public void setMima(int mima) {
		this.mima = mima;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
}
           

不带头结点的单向循环链表类：

//不带头结点的单向循环链表
public class NoHeadOneWayLoopList {
	private Node head;
	private int currentSize;

	public NoHeadOneWayLoopList() {
		head = null;
		currentSize = 0;
	}

	// 返回下标为 i 的那个结点的指针，结点编号从0开始；
	public Node index(int i) {
		if (i >= 0 && i < currentSize) {
			Node temp = head;
			for (int j = 0; j < i; j++) {
				temp = temp.getNext();
			}
			return temp;
		} else {
			System.out.println("下标超界！");
			return null;
		}
	}

	// 插入结点，使其成为第 i 个结点。
	public void insertNode(Node node, int i) {
		if (head == null) {
			head = node;
			head.setNext(head);
		} else {
			Node temp = index(i - 1);
			node.setNext(temp.getNext());
			temp.setNext(node);
		}
		currentSize++;
	}

	public void deleteNode(int i) {
		if (i == 0) {
			if (currentSize == 1) {
				head = null;
			} else {
				Node preNode = index(currentSize - 1);
				Node deletedNode = preNode.getNext();
				head = deletedNode.getNext();
				preNode.setNext(head);
				deletedNode.setNext(null);
			}
		} else {
			Node preNode = index(i - 1);
			Node deletedNode = preNode.getNext();
			head = deletedNode.getNext();
			preNode.setNext(head);
			deletedNode.setNext(null);
		}
		currentSize--;
	}

	public Node getHead() {
		return head;
	}

	public void setHead(Node head) {
		this.head = head;
	}

	public int getCurrentSize() {
		return currentSize;
	}

	public void setCurrentSize(int currentSize) {
		this.currentSize = currentSize;
	}
}           

测试类：

public class TestClass {
	private static NoHeadOneWayLoopList list;

	public static void main(String[] args) {
		list = new NoHeadOneWayLoopList();
		list.insertNode(new Node(1, 3), 0);
		list.insertNode(new Node(2, 1), 1);
		list.insertNode(new Node(3, 7), 2);
		list.insertNode(new Node(4, 2), 3);
		list.insertNode(new Node(5, 4), 4);
		list.insertNode(new Node(6, 8), 5);
		list.insertNode(new Node(7, 4), 6);
		f(list.index(list.getCurrentSize() - 1), 20);
	}

	public static void f(Node first, int m) {
		if (first.getNext() != first) {
			for (int i = 0; i < m - 1; i++) {
				first = first.getNext();
			}
			Node deletedNode = first.getNext();
			int mima = deletedNode.getMima();
			System.out.print(deletedNode.getNo() + "   ");
			first.setNext(deletedNode.getNext());
			deletedNode.setNext(null);
			list.setCurrentSize(list.getCurrentSize() - 1);
			f(first, mima);
		} else {
			System.out.print(first.getNo() + "   ");
		}
	}
}           

输出结果：