【约瑟夫环的问题】
有17个人（编号从0到16），按编号依次排列成一个圆环（编号16的接着编号为0 的人），从编号为0 的人开始报数，数到3的人退出圆环，如此循环，最后留下的那个人的编号是什么？
0，1，2，3，4，5，6，7，8，，9，10，11，12，13，14，15，16
要求：请用面向对象的思想来处理这个问题并在下面写出具体的代码（可以选择你熟悉的语言，如java/C++/C#等）
代码如下：
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[17];
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(17);
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);
}
}
该贴被root编辑于2013-2-25 11:07:02
当前位置：
论坛首页 »
自由讨论区 »
Android, Python及开发编程讨论区
»
发起投票
技术讨论
加好友
发消息
2013-2-25 11:00:02 |
赞(
操作
