约瑟夫问题详解(CC++)

1、Josephus 约瑟夫 问题n 个竞赛者排成一个环形，依次挨次编号1，2，n。从某个指定的第1 号开头，沿环计数，每数到第 m 个人就让其出列，且从下一个人开头重计数，连续进展下去。这个过程始终进展到全部的人都出列为止。最终出列者为优胜者。无论是用链表实现还是用数组实现来解约瑟夫问题都有一个共同点：要模拟整个玩耍过程， 不仅程序写起来比较麻烦，而且时间简单度高达O(nm)，当n，m 格外大(例如上百万，上千万)的时候，几乎是没有方法在短时间内出结果的。留意到原问题仅仅是要求出最终的成功 者。为了争辩便利，先把问题略微转变一下，并不影响原意：问题描述：n 个人0(n-1)0 开头报数，报到(m

2、-1)0 开头报数。求成功者的编号。我们知道第一个人(编号肯定是 m%n-1) 出列之后，剩下的 n-1 个人组成了一个的约瑟夫环k=m%n的人开头: k k+1 k+2 . n-2, n-1, 0, 1, 2, . k-2并且从k 开头0。现在我们把他们的编号做一下转换：k- 0k+1- 1k+2- 2.k-2- n-2变换后就完完全全成为了(n-1)个人报数的子问题，假设我们知道这个子问题的解：例如 xx 变回去不刚好就是n 个人状况的解吗？变回去的公式很简洁：x”=(x+k)%n如何知道(n-1)个人报数的问题的解？明显，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？固然是先求

3、(n-3)的状况这明显就是一个倒推问题！递推公式：fii 个人玩玩耍报m 退出最终成功者的编号，最终的结果自然是fn递推公式f1=0;fi=(fi-1+m)%i;(i1)1-n 挨次算出 fi的数值，最终结果是 fn。由于实际生1 开头，我们输出fn+1 由于是逐级递推，不需要保存每个fi，程序也是很简洁：#include mainint n, m, i, s=0;printf (“N M = “);scanf(“%d%d“, &n, &m);for (i=2; i=n; i+) s=(s+m)%i; printf (“The winner is %dn“, s+1);这个算法的时间简单度为O

4、(n)n，m 等于一百万， 往会成倍地提高算法执行效率。PKUJoseph 相关问题:1012Joseph一半好人一半坏人。模拟打表。#include using namespace std;int a14;bool fun(int k,int m)/s 表示第I(1,2,.,k)次删除数组中的数的下标，留意：随着删除，数组的大小在渐渐减小。int s=0,t=2*k; for(int i=1;i=k;+i)s=(s-1+m)%t;-t;if(sk)return false;return true;int mainint i,j; for(i=1;ik & k)coutakendl; retu

5、rn 0;2359Questions标准约瑟夫问题+字符串#include using namespace std;char s30002;int mainchar ch;int len=0; while(ch=getchar)!=EOF)if(ch!=”n”)+len; slen=ch;int t=0;for(int i=2;i=len;+i)t=(t+2022)%i;if(st+1=” ”)cout“No“endl; else if(st+1=”?”)cout“Yes“endl; elsecout“No comments“endl;return 0;1781In Danger只考虑M 2

6、1.3。#include #include using namespace std;int mainstring s; while(cins)if(s=“00e0“)break;string str=s.substr(0,2);int i,j;int t=s3-”0”; for(i=0;it;+i)str+=”0”;int len=str.length; int sum=str0-”0”;for(i=1;ilen;+i) sum=sum*10+(stri-”0”); int a100;j=0;while(sum)aj=sum%2;+j;sum/=2;for(i=0;ij/2;+i)t=ai;

7、ai=aj-1-i;aj-1-i=t;t=a0;for(i=1;ij;+i)ai-1=ai;aj-1=t;t=a0;for(i=1;ij;+i)t=t*2+ai; couttendl;return 0;2244Eeny Meeny MooN 个城市轮番断电，求最小的M 21 开头断，相当于循环N-1 次。#include using namespace std;int fun(int m,int n)int s=0,i; for(i=2;im & m)j=2;while(fun(m,j)!=1)+j;coutjendl;return 0;3517And Then There Was One22

8、44 一样，结果加上初始值就可以。#includeusing namespace std;int mainint i,j,k,m,n,s;while(1)cinnkm;if(n=0 & k=0 & m=0)break;s=0;for(i=2;i=n-1;i+)/N-1 次循环s=(s+k)%i;cout(s+m)%n+1endl;/结果加初始值return 0;2939Flavius Josephus Reloaded#include #include using namespace std;typedef long long ll;#define HASHLEN 1987039struct

9、hashtypeint v;/value，查找的值int cnt; /count,查找的次数hashHASHLEN;int addorfind(int v,int cnt)int t=v%HASHLEN; while(hasht.v!=-1 & hasht.v!=v)t+; if(t=HASHLEN)t=0;if(hasht.v!=-1) return t;t=cnt;hasht.v=v; return -1;int mainint n,a,b; while(scanf(“%d“,&n) & n)scanf(“%d%d“,&a,&b); memset(hash,-1,sizeof(hash);

10、 ll x=0;int cnt=1; addorfind(0,0);while(1)x=x*x%n;x=(x*a+b)%n;/在HASH 中第t 个位置查找到x int t=addorfind(int)x,cnt);/t，cnt:t 个数和第cnt 个数相等if(t!=-1)printf(“%dn“,n-cnt+t);break;+cnt;return 0;PKU 2800#include #include using namespace std;int mainlong long N,K;while(cinNK)long long sk,ssk,i,s,e,tmp,ans;sk = sqrt(double)K);ssk = K / sk;for (i = 1, ans = 0; i = N & i K)ans += (N - K) * K;for (i = sk; i 1; i-)s