精华内容
下载资源
问答
  • Josephus

    2020-03-31 13:41:45
    标答(队列,可以显示过程) public class Josephus { public static void main(String[] args) { int m = Integer.parseInt(args[0]); int n = Integer.parseInt(args[1]); // initialize the queu...

    标答(队列,可以显示过程)

    public class Josephus {
        public static void main(String[] args) {
            int m = Integer.parseInt(args[0]);
            int n = Integer.parseInt(args[1]);
    
            // initialize the queue
            Queue<Integer> queue = new Queue<Integer>();
            for (int i = 0; i < n; i++)
                queue.enqueue(i);
    
            while (!queue.isEmpty()) {
                for (int i = 0; i < m-1; i++)
                    queue.enqueue(queue.dequeue());
                StdOut.print(queue.dequeue() + " ");
            } 
            StdOut.println();
        }
    }
    

    递推(只能求出结果)

    int Josephus(int n,int k){
    	int re=0;
    	for(int i=2;i<=n;i++){
    		re=(re+k)%i;
    	}
    	return re;
    }
    
    展开全文
  • josephus

    2020-05-14 19:50:09
  • Josephus
  • Josephus排序

    2014-10-14 16:30:13
    时间复杂度为O(n),空间复杂度为O(1),为算法导论思考题Josephus排序问题1答案
  • Josephus问题

    2013-04-03 14:58:56
    用顺序表处理Josephus问题 c语言
  • Josephus算法

    2013-05-28 20:25:08
    这是我自己写的一个josephus算法,使用顺序表做的
  • Josephus

    2020-11-30 20:28:06
    Josephus环题目描述代码变题代码 题目描述 有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。 据说著名犹太历史学家 Josephus有过以下的故事...

    题目描述

    有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。

    据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。

    在这里插入图片描述

    代码

    #include<iostream>
    #define nmax 50
    using namespace std;
    int main()
    {
    	int i, k, m, n, num[nmax], * p;
    	cout << "please input the total of numbers: ";
    	cin >> n;
    	p = num;
    	for (i = 0; i < n; i++)
    		*(p + i) = i + 1;
    	i = 0;  //累计参与游戏的人员位置
    	k = 0;  //累计报数值
    	m = 0;  //累计退出的人数
    	while(m<n-1)
    	{
    		if(*(p+i)!=0) k++;
    		if(k==3)
    		{ 
    			     *(p+i)=0;
    			      k=0;        //报数值回归0
    			      m++;      //累加退出的人数
    		}
    		i++;
    		if(i==n) i=0;  //当到达最后一个人时,赋值回到0,保证形成环状
    	}
    	while(*p==0) p++;
    	cout<<*p<<" is left"<<endl;
    	return 0; 
    }
    

    变题

    题目描述
    有 12 人围坐成一圈玩报数游戏,从1号人员开始顺时针报数,报到k的人员被淘汰出局;接着仍沿顺时针方向从被淘汰出局者的下一人员又重新从 1 开始报数,报到 k的人被淘汰;如此继续,直到最后只剩下一个人时停止。请编写程序输出最后所剩那个人的编号。
    注意:
    (1)假设参加游戏的人的编号沿顺时针方向依次为 1 到 12,可以使用数组来存放各数据;
    (2)k>1,由用户通过 cin 输入指定。

    输入 :
    输入一个整数,代表报数值;
    输出 :
    输出一个整数,即最后剩下的人的编号;
    样例输入 Copy
    3
    样例输出 Copy
    10

    代码

    #include<iostream>
    using namespace std;
    int main()
    {
    	int i, j = 0, k, out = 0, c[12] = { 0 };
    	int* p;
    	cin >> k;
    	p = c;
    	for (i = 0; i < 12; i++)
    		*(p + i) = i + 1;
    	i = 0;
    	while (out < 11)
    	{
    		if (*(p + i) != 0)j++;
    		if (j == k)
    		{
    			*(p + i) = 0;
    			j = 0;
    			out++;
    		}
    		i++;
    		if (i == 12)i = 0;
    	}
    	while (*p == 0)p++;
    	cout << *p;
        return 0;
    }
    
    展开全文
  • JosePhus 问题

    2020-12-29 17:58:00
    JosePhus 问题 Josephus问题是下面的游戏:N个人编号1~N,围坐成一个圆圈。从一号人开始传递一个热土豆。经过M次传递后拿着热土豆的人被清除离座,围坐的圆圈缩紧,由坐在被清除人后面的人拿起热土豆继续进行游戏。...

    JosePhus 问题

    Josephus问题是下面的游戏:N个人编号1~N,围坐成一个圆圈。从一号人开始传递一个热土豆。经过M次传递后拿着热土豆的人被清除离座,围坐的圆圈缩紧,由坐在被清除人后面的人拿起热土豆继续进行游戏。最后整下的人获胜。因此,如果M=0和N=5,则游戏人依次被清除,5号游戏人获胜。如果M=1和N=5,那么被清除的人的顺序是2,4,1,5。
    a.编写一个程序解决在M和N为一般值下的Josephus问题,应使所编程序尽可能地高效率,要确保每个单元都能被清除。
    b.这个程序的运行时间是多少?

    #include <iostream>
    #include <list>
    #include <chrono>  
    using namespace std;
    using namespace chrono;
    int main()
     {
    	int i, j, n, m, mPrime, numLeft;
    	list <int > L;
    	list<int>::iterator iter; 
    	//Initialization
    	cout<<"enter N (# of people) & M (# of passes before elimination):";
    	cin>>n>>m;
    	numLeft = n;
    	mPrime = m % n;
    	auto start = system_clock::now();
    	for (i =1 ; i <= n; i++)
    		L.push_back(i);
    		iter = L.begin();
    		// Pass the potato
    	for (i = 0; i < n; i++)
    	{
    		mPrime = mPrime % numLeft;
    		if (mPrime <= numLeft/2) // pass forward
    		for (j = 0; j < mPrime; j++)
    		{
    			iter++;
    		if (iter == L.end())
    			iter = L.begin();
    		}
    		else // pass backward
    		for (j = 0; j < mPrime; j++)
    		{
    			if (iter == L.begin())
    			iter = --L.end();
    			else
    			iter--;
    		}
    		cout<<*iter<<" ";
    		iter= L.erase(iter);
    		if (iter == L.end())
    			iter = L.begin();
    	}
    	cout<<endl;
    	auto end = system_clock::now();
    	auto duration = duration_cast<microseconds>(end - start);
    	cout << " Consume:  " << double(duration.count())*microseconds::period::num / microseconds::period::den << " s(秒)" << endl;
    	return 0;
    }
    
    展开全文
  • Josephus C++

    2011-05-22 13:20:57
    转载来的,是没问题的,用C++实现的josephus 算法
  • josephus 环问题

    2017-10-26 10:43:35
    Josephus环的问题看起来很简单,假设有n个人排成一个圈。从第一个人开始报数,数到第m个人的时候这个人从队列里出列。然后继续在环里数后面第m个人,让其出列直到所有人都出列。求所有这些人出列的排列顺序。
  • Josephus 排列

    2017-07-24 16:59:23
    《算法导论第三版》14-2 P.202 Josephus 排列 n个人排成环,并从1到n编号,给定正整数m,从第一个人开始报数,每次报到m的那个人出列,求人员出列的排列,称为(n,m)-Josephus 排列1、假定m的常数,找出O(n)的算法...
  • Josephus Permutation

    2019-03-22 09:21:41
    This problem takes its name by arguably the most important event in the life of the ancient historian Josephus: according to his tale, he and ...
  • josephus问题

    2019-10-08 23:43:18
    josephus问题其实就是一个游戏,一群小孩围成一个圈,设置一个数,这个数是个小于小孩总数大于0的一个整数,从第一个小孩开始报数,当其中一个小孩报到你设置的那个数的时候离开那个圈,这样一来反复报下去,直到只...
  • Josephus Again

    2017-07-21 16:05:08
    But now, we think about another Josephus problem. At the first, the circle includes n person. From the first one to start to call the number until call the m, we add a person beside the person who ...
  • josephus_survivor(7,3) => means 7 people in a circle; one every 3 is eliminated until one remains [1,2,3,4,5,6,7] - initial sequence [1,2,4,5,6,7] => 3 is counted out [1,2,4,5,7] => 6 is counted out ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,264
精华内容 1,705
关键字:

josephus