求高手解决约瑟夫环问题

Question

我自己用循环单链表实现了个约瑟夫环，结果到后面错误百出，链表实现的也不是很好～我的代码就不好意思贴了，好有就是我这里几乎无法找到一台电脑把我的垃圾代码贴上来，只能手机求助高人了～期待高人用循环链表解决～谢谢大家了～好的话有加分，虽然本人分不多哈～

Answer 1

http://space.itpub.net/7435839/viewspace-263015

Answer 2

以前写过的一个简单的约瑟夫，用集合实现的： public static void print(int number, int count) {
ArrayList list = new ArrayList();
for (int i = 1; i <= number; i++) {
list.add(i);
}
int no = 1;
for (int i = 1; list.size() > 1; i++) {
if (i % count == 0) {
System.out.println("第" + no++ + "位：" + list.remove(0));
} else {
list.add(list.remove(0));
}
}
System.out.println("最后一位：" + list.get(0));
} public static void main(String[] args) {
print(50, 3);
}

Answer 3

希望这个对楼主有所帮助public class Josephus {
  /**
   * 自己的编号
   */
  private final int number;   /**
   * 链表指针
   */
  private Josephus previous;   /**
   * 链表指针
   */
  private Josephus next;   /**
   * 创建一个新的<code>Josephus</code>对象。
   * 
   * @param number
   *          自己的编号
   */
  public Josephus(int number) {
    this.number = number;
  }   
  /**
   * 返回 <code>number</code> 的当前值。
   *
   * @return <code>number</code> 的当前值
   */
  public int getNumber() {
    return number;
  }   /**
   * 返回 <code>previous</code> 的当前值。
   * 
   * @return <code>previous</code> 的当前值
   */
  public Josephus getPrevious() {
    return previous;
  }   /**
   * 设置 <code>previous</code> 的当前值。
   * 
   * @param previous
   *          <code>previous</code> 的当前值
   */
  public void setPrevious(Josephus previous) {
    this.previous = previous;
  }   /**
   * 返回 <code>next</code> 的当前值。
   * 
   * @return <code>next</code> 的当前值
   */
  public Josephus getNext() {
    return next;
  }   /**
   * 设置 <code>next</code> 的当前值。
   * 
   * @param next
   *          <code>next</code> 的当前值
   */
  public void setNext(Josephus next) {
    this.next = next;
  }   /**
   * 从自己开始报数，报到的人被踢走。
   * 
   * @param n
   *          报的数字
   * @return 被踢走的人
   */
  public Josephus startCountingOut(int n) {
    Josephus current = this;
    for (int i = 1; i < n; i++) {
      current = current.getNext();
    }
    return current.countOut();
  }   /**
   * 从自己开始报3个数，报到的人被踢走。
   * 
   * @return 被踢走的人
   */
  public Josephus startCountingOut() {
    return startCountingOut(3);
  }   /**
   * 被报到，而被踢走
   * 
   * @return 被踢走的人
   */
  private Josephus countOut() {
    previous.setNext(next);
    next.setPrevious(previous);
    return this;
  }
  
  @Override
  public String toString() {
    StringBuilder buff = new StringBuilder(64);
    buff.append("Josephus");
    buff.append("\nNum:  ").append(number);
    buff.append("\nPrev: ").append(previous.getNumber());
    buff.append("\nNext: ").append(next.getNumber());
    return buff.toString();
  }
     public static Josephus init(int n) {
    Josephus[] arrays = new Josephus[n];
    for (int i = 0; i < arrays.length; i++) {
      arrays[i] = new Josephus(i);
    }
    for (int i = 0; i < arrays.length; i++) {
      arrays[i].setNext(arrays[(i + 1) % n]);
      arrays[i].setPrevious(arrays[(i + n - 1) % n]);
    }
    return arrays[0];
  }   public static void main(String[] args) {
    Josephus j = init(50);
    do {
      System.out.println("报数的人:");
      System.out.println(j);
      j = j.startCountingOut();
      System.out.println("被踢走的人:");
      System.out.println(j);
      // 移交给下一个人
      j = j.getNext();
    } while ((j.getNext()) != j); // 就他一个了
    System.out.println("最后的幸存者:");
    System.out.println(j);
  }
}

Answer 4

小小的修改了下
public class Josephus {
  /**
   * 自己的编号
   */
  private final int id;   /**
   * 链表指针
   */
  private Josephus previous;   /**
   * 链表指针
   */
  private Josephus next;   /**
   * 创建一个新的<code>Josephus</code>对象。
   * 
   * @param number
   *          自己的编号
   */
  public Josephus(int id) {
    this.id = id;
  }   
  /**
   * 返回 <code>number</code> 的当前值。
   *
   * @return <code>number</code> 的当前值
   */
  public int getNumber() {
    return id;
  }   /**
   * 返回 <code>previous</code> 的当前值。
   * 
   * @return <code>previous</code> 的当前值
   */
  public Josephus getPrevious() {
    return previous;
  }   /**
   * 设置 <code>previous</code> 的当前值。
   * 
   * @param previous
   *          <code>previous</code> 的当前值
   */
  public void setPrevious(Josephus previous) {
    this.previous = previous;
  }   /**
   * 返回 <code>next</code> 的当前值。
   * 
   * @return <code>next</code> 的当前值
   */
  public Josephus getNext() {
    return next;
  }   /**
   * 设置 <code>next</code> 的当前值。
   * 
   * @param next
   *          <code>next</code> 的当前值
   */
  public void setNext(Josephus next) {
    this.next = next;
  }   /**
   * 从自己开始报数，报到的人被踢走。
   * 
   * @param n
   *          报的数字
   * @return 被踢走的人
   */
  public Josephus startCountingOut(int n) {
    Josephus current = this;
    for (int i = 1; i < n; i++) {
      current = current.getNext();
    }
    return current.countOut();
  }   /**
   * 从自己开始报3个数，报到的人被踢走。
   * 
   * @return 被踢走的人
   */
  public Josephus startCountingOut() {
    return startCountingOut(3);
  }   /**
   * 被报到，而被踢走
   * 
   * @return 被踢走的人
   */
  private Josephus countOut() {
    previous.setNext(next);
    next.setPrevious(previous);
    return this;
  }
  
  @Override
  public String toString() {
    return "Josephus" + this.id + "\tID: " + this.id + "\t" +
           "Pre: " + this.previous.id + "\t" + "Next: " + this.next.id ;
  }
     public static Josephus init(int n) {
    Josephus[] arrays = new Josephus[n];
    for (int i = 0; i < arrays.length; i++) {
      arrays[i] = new Josephus(i);
    }
    for (int i = 0; i < arrays.length; i++) {
      arrays[i].setNext(arrays[(i + 1) % n]);
      arrays[i].setPrevious(arrays[(i + n - 1) % n]);
    }
    return arrays[0];
  }   public static void main(String[] args) {
    Josephus j = init(50);
    do {
      j = j.startCountingOut();
      System.out.println("被踢走的人:");
      System.out.println(j);
      // 移交给下一个人
      j = j.getNext();
    } while ((j.getNext()) != j); // 就他一个了
    System.out.println("最后的幸存者:");
    System.out.println(j);
  }
}

Answer 5

public class JosephusTest {    public static void main(String[] args) {
        System.out.println(josephus2(5));
    }    /**
     * 计算约瑟夫问题，间隔 1 个的值，这个有数学解法，即：将最高位的 1 取出，将数值左移一位，
     * 再将最高位的那个 1 添至最低位即可<br />
     * 例如 1010 的约瑟夫间隔为 1 的值为 0101（5）。Concrete Mathematics 书中并未加 1，
     * 那是由于其第一个从 0 开始的，如果从 1 开始时需要加 1<br />
     * 算法参考：Concrete Mathematics 一书第一章最后部分
     *
     * @param count
     * @return
     */
    public static int josephus2(int count) {
        int n = (count ^ leftOneBit(count)) << 1;
        return (n | 1) + 1;
    }    /**
     * 获得一个数最高位为 1 的值，比如 1111（15）的最高位值为 1000<br />
     * 算法参考：Hacker's Delight 一书第三章
     *
     * @param num
     * @return
     */
    public static int leftOneBit(int num) {
        for(int i = 0; i < 5; i++) {
            num |= (num >> (1 << i));
        }
        return num - (num >>> 1);
    }
}

Answer 6

public class JosephLoop { private int total;
private int number;

/**
 * @param total 一共有total个人参加
 * @param number 数到number时，退出。
 */
public JosephLoop(int total, int number) {
super();
this.total = total;
this.number = number;
} static class Entry{
int index;
int speak;
Entry next;
/**
 * @param index 生成约瑟夫环时，人员的顺序。
 * @param speak 人员的当前报数。
 * @param next 下一个人员的引用。
 */
public Entry(int index, int speak, Entry next) {
super();
this.index = index;
this.speak = speak;
this.next = next;
}

}

public int getTheLast(){
Entry header = new Entry(0,0,null);
createLoop(header,total);
Entry e = header;
for(int speak = 0;e!=e.next;e=e.next,speak++){
e.speak=speak;
if(speak>=number-1){
speak = 0;
removeNextEntry(e);
}
}
return e.index;
}
/**删除元素e的下一个元素。
 * @param e 链表元素。
 */
private static void removeNextEntry(Entry e) {
e.next = e.next.next;
}
/**
 * @param header 循环链表的表头。
 * @param size 参与人员的数量；约瑟夫环的大小。
 * @return 返回循环链表的表头。
 */
private static Entry createLoop(Entry header, int size) {
Entry tmp = header;
for(int i=1;i<=size;i++){
tmp.next = new Entry(i,i,null);
tmp = tmp.next;
}
tmp.next = header.next;
return header;
}

/**
 * @param args
 */
public static void main(String[] args) {
System.out.println(new JosephLoop(3,2).getTheLast());
}}

Answer 7

上面贴的那个图是 Concrete Mathematics 一书第二版的影印版。中文版只有第一版，是由西安电子科技大学出版社于 1992 年出版，封面我在网上找不到。

Answer 8

too good to come here.

Answer 9

约瑟夫环 在JAVASE中有什么地方应用得到吗？

Answer 10

使用LinkedListpublic static void getLastPerson(int count,int step){
List<String> persons=new LinkedList<String>();
for(int i=1;i<=count;i++){
persons.add(""+i);
}
int tmp=-1;
while(count>1){
tmp=(tmp==-1)?(tmp+step)%count:(tmp+step-1)%count;
persons.remove(tmp);
count=count-1;
}
System.out.println(persons.get(0));
}

Answer 11

谢谢大家哦~我调试通过了我的循环单链表，呵呵，我也贴上我的吧~
package circleLink;public class Node {
public String data;
public Node next;
public Node(String data){
this.data=data;
}
public void print(){
System.out.println(data);
}}
package circleLink;public class CircleLink {
 Node first;
 Node last;
private int size;

public CircleLink(){

}
public void addLast(Node node){
if(first==null){
first=node;
last=node;
first.next=last;
last.next=first;
size++;
}else{
last.next=node;
last=node;
last.next=first;
size++;
}

}
public Node remove(Node node){
Node pre=first;
Node tem=first;
Node rear=null;

for(int i=0;i<size;i++){
if(tem==node){
if(node==first){
rear=first.next;
first=rear;
last.next=first;
size--;
return rear;
}
if(node==last){
last=pre;
last.next=first;
size--;
return first;
}
rear=tem.next;
pre.next=tem.next;
size--;
return rear;
}
pre=tem;
tem=tem.next;
}
return rear;
}
public void print(){
Node tem=first;
if(tem!=null)
for(int i=0;i<size;i++){
tem.print();
tem=tem.next;
}

}
public int size(){
return size;
}

}
package circleLink;public class CircleGame { public void start(int number,int count){
CircleLink c=new CircleLink();
for(int i=1;i<=number;i++){
c.addLast(new Node("gamer:"+i));
}
int startNum=1;
Node tem=c.first;
while(c.size()>1){
if(startNum%count==0){
System.out.println("出去的人是:"+tem.data);
tem=c.remove(tem);

}else{
tem=tem.next;
}
startNum++;
}
System.out.println("获胜的是"+c.first.data);
}
public static void main(String[] args) {
new CircleGame().start(3, 3);
}}