Josephus算法的JAVA语言实现

　2008-01-05 19:15:31　来源：WEB开发网　闂傚倸鍊风欢姘缚瑜嶈灋闁圭虎鍠栫粻顖炴煥閻曞倹瀚�

闂傚倸鍊风粈渚€骞夐敓鐘插瀭闁汇垹鐏氬畷鏌ユ煙閹殿喖顣奸柛搴＄У閵囧嫰骞掗幋婵冨亾閻㈢ǹ纾婚柟鐐灱濡插牊绻涢崱妤冃℃繛宀婁簽缁辨捇宕掑鎵佹瀸闂佺懓鍤栭幏锟�

濠电姷鏁告慨顓㈠箯閸愵喖宸濇い鎾寸箘閹规洟姊绘笟鈧ḿ褍煤閵堝悿娲Ω閳轰胶鍔﹀銈嗗笂閼冲爼鍩婇弴銏＄厪闁搞儮鏅涙禒褏绱掓潏鈺佷槐闁轰焦鎹囬弫鎾绘晸閿燂拷闂傚倸鍊风欢姘缚瑜嶈灋闁圭虎鍠栫粻顖炴煥閻曞倹瀚�　　闂傚倸鍊烽懗鑸电仚缂備胶绮〃鍛村煝瀹ュ鍗抽柕蹇曞У閻庮剟姊虹紒妯哄闁圭⒈鍋嗛惀顏囶樄闁哄本娲樼换婵婄疀閺囩姷鐛ラ梻浣哄帶婢瑰﹥绂嶅⿰鍫氣偓鏃堝礃椤忎礁浜鹃柨婵嗛婢ь喖霉閻樻瑥瀚粻楣冩煕椤愩倕鏋庨柣蹇嬪劜閵囧嫰寮村Ο鍝勫Е濡炪們鍨洪悷鈺呭箖閳╁啯鍎熼柕鍥у簻閹凤拷

核心提示：Josephus算法：比如一群小孩围成一圈，任意假定一个数字m，Josephus算法的JAVA语言实现，从第一个小孩起，顺时针方向数，该算法用数组循环实现，但数组是线性排列的，每数到第m个小孩时，该小孩便出局；随小孩不断离开圈子不断缩小

　　Josephus算法：比如一群小孩围成一圈，任意假定一个数字m，从第一个小孩起，顺时针方向数，每数到第m个小孩时，该小孩便出局；随小孩不断离开圈子不断缩小，最后剩下一个小孩便是胜利者。该算法用数组循环实现，但数组是线性排列的，而小孩是围成圈的，使用"加1求模"的方法解决循环！

程序如下：
import java.io.*;
class Josephus
{
public static void main(String[] args)
{
int num=10;
int interval=2;
int[] a=new int[num];
for(int i=0;i<num;i++)
a[i]=i+1;
System.out.PRintln("please input the interval: ");
try
{InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
String s=br.readLine();
interval=Integer.parseInt(s);
}
catch(Exception e)
{System.out.println(e);
}

for(int i=0;i<num;i++)
System.out.print(a[i]+" ");
System.out.print(" ");

int k=1;
int i=-1;

while(true)
{
for(int j=0;j<interval;)
{i=(i+1)%num;
if(a[i]!=0)
j++;
}

if(k==num) break;
System.out.print(a[i]+" ");
a[i]=0;
k++;
}

System.out.print(" No. "+a[i]+" boy´ve won. ");
}

}