黑马程序员技术交流社区
标题:
Josephus问题求解
[打印本页]
作者:
兰海忠
时间:
2011-7-26 23:35
标题:
Josephus问题求解
还上学的时候老师讲了这个问题但没有注意，去年面试的时候就出了这道题上机写代码，通过了再笔试，结果自己弄了半天没有弄出来，自己灰溜溜的走了。现在敢问各位大侠这题是什么解的。问题是这样的：说一群小孩子围成一圈，任意假定一个数M，从第一个孩子开始器，顺时针方向数，每数到M的小孩时，该小孩子离开。从下一个孩子开始又开始重新数，也是到M时孩子离开。孩子不断离开，圈子变小。请问最后离开的孩子是第几个孩子。 希望大家能解决一下详细点的，本人比较愚钝希望说具体点。谢谢！
作者:
匿名
时间:
2011-7-27 08:59
约瑟夫环问题，可以用递归和链表实现。人为的构造个循环链表，递归到只剩一个孩子就行了
作者:
匿名
时间:
2011-7-27 09:15
首先，建立一个数组array，长度为孩子的数量。 数组的每个元素的值，就是孩子的位置编号，从1开始编号。
第二，建立一个统计变量count，计算当前数组中还剩余的孩子的数量。
第三，若剩余人数大于1，则孩子们，开始报数。
第四，若某个孩子，报出了关键数字，则将count-1，然后将array[该孩子的下标] = 0，即报出关键数字的孩子，将离开，咱们把他的号码，置为0，就意味着他离开了。
第五，只有号码不为0的孩子，才可以参与报数。
第六，建立一个报数时需要使用的变量temp，用于保存当前孩子需要报的数字。
第七，最后，数组中，元素值不为0的那个元素，就是剩下的那个孩子的，编号。
废话少说，看代码：[code=java]package org.cxy.demo;
public class Children {
private int[] child;
private int count;
public Children(int max){
this.child = new int[max];
for(int i=0;i<this.child.length;i++){
this.child[i] = i+1;
this.count++;
}
}
public int quitByNumber(int number){
int temp = 1;
// 若剩余的孩子数大于1,则游戏继续。
while(this.count>1){
for(int i=0;i<this.child.length;i++){
if(this.child[i]!=0){
System.out.printf("第 %d 个孩子,报数为：%d\n",this.child[i],(temp%number == 0 ?number:temp%number));
if(temp%number == 0){
System.out.printf("哦啊,第 %d 个孩子,离开了!\n",this.child[i]);
this.child[i] = 0;
this.count--;
}
temp++;
}
}
}
for(int i=0;i<this.child.length;i++){
if(this.child[i]!=0){
return this.child[i];
}
}
return -1;
}
public static void main(String[] args) {
Children c = new Children(13);
System.out.printf("最终留下来的是第 %d 个孩子!\n",c.quitByNumber(3));
}
}[/code]程序执行结果：[code=java]第 1 个孩子,报数为：1
第 2 个孩子,报数为：2
第 3 个孩子,报数为：3
哦啊,第 3 个孩子,离开了!
第 4 个孩子,报数为：1
第 5 个孩子,报数为：2
第 6 个孩子,报数为：3
哦啊,第 6 个孩子,离开了!
第 7 个孩子,报数为：1
第 8 个孩子,报数为：2
第 9 个孩子,报数为：3
哦啊,第 9 个孩子,离开了!
第 10 个孩子,报数为：1
第 11 个孩子,报数为：2
第 12 个孩子,报数为：3
哦啊,第 12 个孩子,离开了!
第 13 个孩子,报数为：1
第 1 个孩子,报数为：2
第 2 个孩子,报数为：3
哦啊,第 2 个孩子,离开了!
第 4 个孩子,报数为：1
第 5 个孩子,报数为：2
第 7 个孩子,报数为：3
哦啊,第 7 个孩子,离开了!
第 8 个孩子,报数为：1
第 10 个孩子,报数为：2
第 11 个孩子,报数为：3
哦啊,第 11 个孩子,离开了!
第 13 个孩子,报数为：1
第 1 个孩子,报数为：2
第 4 个孩子,报数为：3
哦啊,第 4 个孩子,离开了!
第 5 个孩子,报数为：1
第 8 个孩子,报数为：2
第 10 个孩子,报数为：3
哦啊,第 10 个孩子,离开了!
第 13 个孩子,报数为：1
第 1 个孩子,报数为：2
第 5 个孩子,报数为：3
哦啊,第 5 个孩子,离开了!
第 8 个孩子,报数为：1
第 13 个孩子,报数为：2
第 1 个孩子,报数为：3
哦啊,第 1 个孩子,离开了!
第 8 个孩子,报数为：1
第 13 个孩子,报数为：2
第 8 个孩子,报数为：3
哦啊,第 8 个孩子,离开了!
第 13 个孩子,报数为：1
最终留下来的是第 13 个孩子![/code]
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2