在我心中有一個夢

一、題目

   Josephus Problem

There are people standing in a circle waiting to be executed. After the first person is executed, certain number of people is skipped and one person is executed. Then again, people are skipped and a person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

 

The task is to choose the place in the initial circle so that you (and your friends) are the last person(s) remaining and so survive.

 

Input: The number of total persons and the number of persons in your group hoping to survive. The maximum number of persons is 100.

 

Output: The positions you and your friends should stand (in ascending order).

 

   

Sample Input:

41  2

 

Sample Output

16 31

 二、我的程式碼

import java.util.*;
public class Josephus
{
    public static int [] FindKillPlace(int n)
    {
        int KillCounter=0;
        int KillPlace=0;
        int array[]=new int[n];
        for (int i=0;i<array.length;i++)
            array[i]=0;   
        for (int i=0;;i++)
        {
            i%=array.length;
            if (array[i]!=0)
                continue;
            KillCounter++;
            if (KillCounter==3)
            {
                array[i]=++KillPlace;
                KillCounter=0;
            }
            if(KillPlace==n)
                break;
        }   
            return array ;
    }
   
    public static void main(String [] args)
    {
       
        Scanner scanner=new Scanner(System.in);
        int PersonTotal,PersonNumber,inNum;
        int PersonKillPlace[];
        while(scanner.hasNext())
        {
            inNum=scanner.nextInt();
            if(inNum==0) break;
            PersonTotal=inNum;
            inNum=scanner.nextInt();
            if(inNum==0) break;
            PersonNumber=inNum;
            PersonKillPlace=FindKillPlace(PersonTotal);
            for(int i=0;i<PersonTotal;i++)
            {
                    if ((PersonTotal-PersonKillPlace[i])<PersonNumber)
                        System.out.print((i+1)+" ");
            }
            System.out.println("");
           
        }       
    }
   
   
}

三、執行結果