killcriminal.java

古罗马有一个残酷的杀死犯人的游戏。若干个犯人站成一圈

import java.io.*;
import java.text.DecimalFormat;

class Data{
	public int data;   //save the data
	
	Data next;      
	
	public Data(int input){
		data=input;
		next=null;
		}
	}
//链表构造队列	
class SeQueue{
	private int length;     //save the number of Data
	private Data head,tail;
	
	public SeQueue(){
		length=0;
		head=null;
		tail=null;
		}
	
	//往队列中加入元素
	public void addElement(int input){
		Data temp=new Data(input);
		if(tail==null){
			head=tail=temp;
			}
		else{
			tail.next=temp;
			tail=temp;
			}
		length++;
		}
	public int remove(){
		Data temp=new Data(-1);
		if(length>0){
			temp=head;
			
			if(head==tail)  head=tail=null;
	  	        else           head=head.next;
                        length--;
			}
			
                temp.next=null;
		return temp.data;
		}
	public int gethead(){
		if(length>0)
		  return head.data;
		else return -1;
		}
	public int length(){
		return length;
		}
	}
	
public class KillCriminal{
	public static void main(String []args)throws IOException{
           BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
           
           SeQueue survivor=new SeQueue();
           String s=new String();
           String getarry[]=new String[3];
           int amount=0;
           int potion=0;
           int step=0;
           
           DecimalFormat form=new DecimalFormat("0.000");
           double beginingtime=0;
           double endingtime=0;

           while(true){
              System.out.println("Please input: 总数 初始位置 步长");
              try{
                  s=br.readLine();
                  if(s.equals("finish")){
                      break;
                     }
                  getarry=s.split(" ");
                  amount=Integer.parseInt(getarry[0]);
                  potion=Integer.parseInt(getarry[1]);
                  step=Integer.parseInt(getarry[2]);
                 }catch(IOException e){break;}

               beginingtime=System.currentTimeMillis();
               for(int i=0;i<amount;i++)
                   survivor.addElement(i+1);
               //get the potion
               for(int i=0;i<potion-1;i++)
                   survivor.addElement(survivor.remove());

               //kill the unlucky criminal
               while(survivor.length()>1){
                    for(int i=0;i<step%survivor.length();i++)
                       survivor.addElement(survivor.remove());
                    step=step+survivor.remove();           //kill the unlucy criminal and add the step
                    }
              endingtime=System.currentTimeMillis();
              System.out.println("Survivor is:"+survivor.remove());
              System.out.println("It takes :"+form.format((endingtime-beginingtime)/1000)+"ms");
              System.gc();
              }
           
           
	  }
       }