有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];
分享到:
相关推荐
用循环单向链表解决约瑟夫问题 原题: 设有n个人站成一圈,每个人持有一个密码(正整数)。现从第t个人开始,按顺时针方向“1,2,3,4,…”循环报数,数到m1(第t个人所持密码)的人出列,然后从出列者的下一个人重新...
已知n个人(不妨分别以编号1,2,3,…,n 代表 )围坐在一张圆桌周围,首先从编号为 k 的人从1开始顺时针报数,1, 2, 3, ...,记下顺时针数到 m 的那个人,同时从编号为 k ...数据结构中经典的双向约瑟夫问题c语言代码
约瑟夫问题代码,约瑟夫问题代码
约瑟夫问题,通过类实现的链表,并加以改进,做成双向链表
约瑟夫问题的两种求解方法,顺序存储和链表
约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的人的序号为5,4,6,2,3。最后剩下1号。 假定在圈子里前K个为好人,后K...
约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。 分析: (1)由于对于每个人只有死和活两种...
用链表与循环完成约瑟夫问题 while (cin>>x>>y) { node *p, *q; //建立循环链表 for (i = 1; i ; i++) { if (i == 1) { list->head = new node; list->head->data = i; q = list->head; ...
Josephus 约瑟夫问题(POJ)相关习题的源代码(1012,2359,1781,2244,3517,2939,2800)
C++_循环链表实现约瑟夫问题 vc2008 课堂作业!
该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n个人围坐一圈,用链表中的每一个结点代表一个人和他所代表的序号。在输入初始序号m后,对该链表进行遍历,直到第m个结点,令该结点的序号值作为新的序号值,...
利用循环链表实现约瑟夫问题的求解。 约瑟夫问题如下:已知n个人(n>=1)围坐一圆桌周围,从1开始顺序编号。从序号为1的人开始报数,顺时针数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依...
约瑟夫问题C语言
解决约瑟夫问题,数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构...
利用STL解决约瑟夫问题,可以接受数据的不同存储方式,比如vector ,list 等。
约瑟夫问题循环链表实现代码
约瑟夫问题的来历 约瑟夫问题的一般形式: 约瑟夫问题的另外一个有名的例子: 猴子选大王 笔算解决约瑟夫问题
算法实现源程序java代码实现约瑟夫问题