//***************************
//**    Josephus問題解法1  **
//**    jose1.cpp          **
//***************************

#include <iostream.h>

void main()
{
  //建立小孩數組
  const int num=10;    //小孩數
  int interval;        //每次數interval個小孩，便讓該小孩離開
  int a[num];          //小孩數組
  //給小孩編號
  for(int i=0; i<num; i++)   //小孩的編號只與小孩數有關
    a[i]=i+1;
  //輸入數小孩間隔
  cout <<"please input the interval: ";    //輸入一個數小孩個數
  cin >>interval;
  //將全體參加的小孩輸出
  for(int i=0; i<num; i++)    //順序輸出開始時的小孩編號
    cout <<a[i] <<",";
  cout <<endl;

  int k=1;      //標識處理第k個離開的小孩
  int i=-1;     //數組下標(下一個值0就是第一個小孩的下標)
  //處理獲勝前的小孩
  while(1){
    //在圈中數interval個小孩
    for(int j=0; j<interval; ){
      i=(i+1)%num;       //對下標加1求模
      if(a[i]!=0)        //如果該元素的小孩在圈中，則承認數數有效
        j++;
    }
    if(k==num) break;    //該小孩是最后一個(勝利者)嗎？
    cout <<a[i] <<",";   //輸出離開的小孩之編號
    a[i]=0;              //標識該小孩已離開
    k++;                 //準備處理下一個圈中小孩
  }
  //break語句跳轉到此
  cout <<"\nNo." <<a[i] <<" boy've won.\n";    //輸出勝利者
}