約瑟夫問題詳解(CC++)

1、Josephus 約瑟夫 問題n 個(gè)競賽者排成一個(gè)環(huán)形，依次挨次編號1，2，n。從某個(gè)指定的第1 號開頭，沿環(huán)計(jì)數(shù)，每數(shù)到第 m 個(gè)人就讓其出列，且從下一個(gè)人開頭重計(jì)數(shù)，連續(xù)進(jìn)展下去。這個(gè)過程始終進(jìn)展到全部的人都出列為止。最終出列者為優(yōu)勝者。無論是用鏈表實(shí)現(xiàn)還是用數(shù)組實(shí)現(xiàn)來解約瑟夫問題都有一個(gè)共同點(diǎn)：要模擬整個(gè)玩耍過程， 不僅程序?qū)懫饋肀容^麻煩，而且時(shí)間簡單度高達(dá)O(nm)，當(dāng)n，m 格外大(例如上百萬，上千萬)的時(shí)候，幾乎是沒有方法在短時(shí)間內(nèi)出結(jié)果的。留意到原問題僅僅是要求出最終的成功 者。為了爭辯便利，先把問題略微轉(zhuǎn)變一下，并不影響原意：問題描述：n 個(gè)人0(n-1)0 開頭報(bào)數(shù)，報(bào)到(m

2、-1)0 開頭報(bào)數(shù)。求成功者的編號。我們知道第一個(gè)人(編號肯定是 m%n-1) 出列之后，剩下的 n-1 個(gè)人組成了一個(gè)的約瑟夫環(huán)k=m%n的人開頭: k k+1 k+2 . n-2, n-1, 0, 1, 2, . k-2并且從k 開頭0?，F(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：k- 0k+1- 1k+2- 2.k-2- n-2變換后就完完全全成為了(n-1)個(gè)人報(bào)數(shù)的子問題，假設(shè)我們知道這個(gè)子問題的解：例如 xx 變回去不剛好就是n 個(gè)人狀況的解嗎？變回去的公式很簡潔：x”=(x+k)%n如何知道(n-1)個(gè)人報(bào)數(shù)的問題的解？明顯，只要知道(n-2)個(gè)人的解就行了。(n-2)個(gè)人的解呢？固然是先求

3、(n-3)的狀況這明顯就是一個(gè)倒推問題！遞推公式：fii 個(gè)人玩玩耍報(bào)m 退出最終成功者的編號，最終的結(jié)果自然是fn遞推公式f1=0;fi=(fi-1+m)%i;(i1)1-n 挨次算出 fi的數(shù)值，最終結(jié)果是 fn。由于實(shí)際生1 開頭，我們輸出fn+1 由于是逐級遞推，不需要保存每個(gè)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);這個(gè)算法的時(shí)間簡單度為O

4、(n)n，m 等于一百萬， 往會成倍地提高算法執(zhí)行效率。PKUJoseph 相關(guān)問題:1012Joseph一半好人一半壞人。模擬打表。#include using namespace std;int a14;bool fun(int k,int m)/s 表示第I(1,2,.,k)次刪除數(shù)組中的數(shù)的下標(biāo)，留意：隨著刪除，數(shù)組的大小在漸漸減小。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標(biāo)準(zhǔn)約瑟夫問題+字符串#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 個(gè)城市輪番斷電，求最小的M 21 開頭斷，相當(dāng)于循環(huán)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 一樣，結(jié)果加上初始值就可以。#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 次循環(huán)s=(s+k)%i;cout(s+m)%n+1endl;/結(jié)果加初始值return 0;2939Flavius Josephus Reloaded#include #include using namespace std;typedef long long ll;#define HASHLEN 1987039struct

9、hashtypeint v;/value，查找的值int cnt; /count,查找的次數(shù)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 個(gè)位置查找到x int t=addorfind(int)x,cnt);/t，cnt:t 個(gè)數(shù)和第cnt 個(gè)數(shù)相等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