josephuslist.java

用链表实现Josephus问题的源码

package Josephus;

import java.io.*;
public class JosephusList
{
	public static void main(String[] args)
	{
		/**
		 * Initialization.
		 */
		LinkedList theList = new LinkedList();
		
		String s = "";
		int n = 0;//the number of people
		int m = 0;//the time to pass
		
		/**
		 * Print the prompt and get Input.
		 */
		System.out.print("Enter the number of people n : ");
		try
		{
			BufferedReader in = new BufferedReader(new
				InputStreamReader(System.in));
			s = in.readLine();
			n = Integer.parseInt(s);
		}catch(IOException e){}
		
		System.out.print("Enter the time to be passed m : ");
		try
		{
			BufferedReader in = new BufferedReader(new 
				InputStreamReader(System.in));
			s = in.readLine();
			m = Integer.parseInt(s);
		}catch(IOException e){}

		/**
		 * Initialize the list.
		 */
		for(int i = n; i >= 1; i--)
			theList.insert(i);
		
		LinkedListItr itr = theList.first();
		/**
		 * count and kick the people
		 */
		while(!theList.isEmpty())
		{
			//count
			for(int j = m; j > 1; j--)
			{
				itr.advance();
				
				if(itr.isPastEnd())
					itr = theList.first();
			}
			
			//print the people to kick.
			System.out.println("The " + itr.current.element
				+ " person is kicked");
			
			theList.remove(itr.current.element);
			
			n--;
			
			itr.advance();
			if(itr.isPastEnd())
				itr = theList.first();
				
			if(n == 1)
				break;
		}
		
		System.out.println("Only the " + itr.current.element + " person left.");
		System.out.println();
	}
	/**
	 * Method to print the list.
	 */
	 
	public static void printList(LinkedList theList)
	{
		if(theList.isEmpty())
			System.out.println("Empty list.");
			
		else
		{
			LinkedListItr itr = theList.first();
			
			for(; !itr.isPastEnd(); itr.advance())
				System.out.print(itr.retrieve() + " ");
		}
		
		System.out.println();
	}
}