josephus.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 150 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//12 Mar 2008
package cn.edu.whu.iss.algorithm.unit14.test;

import java.util.ArrayList;
import java.util.List;

public class Josephus implements JosephusPermutationTestData{

	private static String res;
	private static int m,n;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		int captiveNumber = 7;
//		int startFrom = 1;
//		int runStep = 4;
//
//		CaptiveList list = new CaptiveList(startFrom, captiveNumber, runStep);
//		Link lastOne = list.runGame();
//		System.out.println("The survival: " + lastOne);
		for(int i=0;i<ANS.length;i++){
			System.out.println(getRes(M[i],N[i]));
		}
		
	}
	
	public static String getRes(int m,int n){
		Josephus.m = m;
		Josephus.n = n;
		res="<";
		return getRes();
	}
	
	public static String getRes(){
		CaptiveList list = new CaptiveList(1, n, m);
		Link lastOne = list.runGame();
		res+=lastOne+">";
		return res;
	}

	/**
	 * Singly-circularly-linked list to solve Josephus problem
	 */
	private static class CaptiveList {
		private Link dynamicHead;
		private int runStep;

		/**
		 * @param startFrom
		 *            the start position
		 * @param captiveNumber
		 *            total number
		 * @param runStep
		 *            move runStep forward
		 */
		public CaptiveList(int startFrom, int captiveNumber, int runStep) {
			this.runStep = runStep;
			Link previous = null;
			Link head = null;
			for (int i = 1; i <= captiveNumber; i++) {
				Link tmpLink = new Link(i);
				if (previous == null) {
					head = tmpLink;
				} else {
					previous.next = tmpLink;
				}
				previous = tmpLink;

				if (i == startFrom) {
					dynamicHead = tmpLink;
				}
			}
			previous.next = head; // circle the list
		}

		/**
		 * @return the one who got himself suicided
		 */
		private Link suicide() {
			Link current = dynamicHead;
			Link previous = null;
			int testPos = runStep;
			while (--testPos >= 1) {
				previous = current;
				current = current.next;
			}
			if (previous == current.next) {
				previous.next = null;
			} else {
				previous.next = current.next;
			}
			dynamicHead = current.next; // reset first link
			return current;
		}

		/**
		 * Let captives suicide
		 * 
		 * @return the survival
		 */
		public Link runGame() {
			List<Link> killed = new ArrayList<Link>();
			while (dynamicHead != null && dynamicHead.next != null) {
				killed.add(suicide());
			}
			for (int i = 0; i < killed.size(); i++) {
				Link kill = (Link) killed.get(i);
				res+=kill+",";
				//System.out.println("Killing: " + kill);
			}
			return dynamicHead;
		}
	}

	/**
	 * Simple link class
	 * 
	 * @author Lisan
	 */
	private static class Link {
		private int number;
		public Link next;

		/**
		 * @param number
		 */
		public Link(int number) {
			this.number = number;
		}

		/*
		 * (non-Javadoc)
		 * 
		 * @see java.lang.Object#toString()
		 */
		public String toString() {
			return String.valueOf(number);
		}
	}
}