约瑟夫问题

有n个人围成一圈，顺序编号。从第一个人开始报数，凡报到m的人退出圈子，问最后一个圈中的人的编号。

import java.util.LinkedList;

/**
* author Akalius Kung 2008-2-10
**/
public class Josephus {

private static int removeNM(int n, int m) {  
  LinkedList<Integer> list = new LinkedList<Integer>();  
  for(int i = 0; i < n; i++){
  list.add(new Integer(i));  
  }
  int removed = 0; 
  while(list.size() > 1) {  
  removed = (removed + m - 1) % list.size();  
      list.remove(removed);  
  }  
  return list.get(0).intValue();  
}

public static void main(String[] args) throws Exception {  
  System.out.println(removeNM(3,1));  
    } 
 
}  

最简单原始的算法，用数组记录谁被out了。  
  int removed = 0;  // location which will be removed
  int leftLen=list.size(); // num of which value is not -1
  while(leftLen > 1) { // if still have elem not removed
for(int i=0;i<list.size();i++){
if(a[i]==-1){ // if elem has been removed, skip it
removed ++;
}
if(i==(removed + m - 1)% list.size){ // finding the elem to be removed
a[i]=-1;
removed =i;
leftLen--;
}
}      

  }  
  return a[0];

评论

3 楼 Android_gqs 2011-11-24  

应该数报到m或m的倍数的人出圈

2 楼 loveofgod 2008-02-13  

没必要再实现一个循环链表，循环链表的性质其实可以通过链表或数组的模拟，下标取余即可

1 楼 ggggqqqqihc 2008-02-13  

我认为最好的办法是先实现一个循环链表的类，然后直接模拟。