首页 > 代码库 > 约瑟夫问题例题小结
约瑟夫问题例题小结
类型1：约瑟夫问题原题：（http://acm.hdu.edu.cn/showproblem.php?pid=2925）
大体就是一圈人，数到m的退出，询问最后留下来的人。
这样的题是约瑟夫系列问题的基础，普通暴力做法O(n*m)，不够优秀，可以通过数学方法优化至O(n)，其所用的思路是将一个规模n的问题转移成规模n-1的问题。
公式形式推导都很简单:f(i)表示规模i的约瑟夫问题最后留下人的编号，f(i)=(f(i-1)+m)%i
类型2：规模变态版：(http://poj.org/problem?id=1781)
类型1限制只数1,2，即每次去掉偶数项，易推导f(i)=(f(i-1)+2)%i
然而数据时限卡O(n)，通过《具体数学》上一种及其奇葩的推导，有一个O(log)解法，即f(i)=i循环右移（把二进制最高为的1放在最右面）
类型3：类型1变式：（http://poj.org/problem?id=1012）
2×n个人，通过约瑟夫方式间隔m杀人，使后n个坏人在前n个好人之前被杀的最小m。
引入Joseph递推公式，设有n个人，(0～n-1)，间隔m， f(i) 表示当前子序列中第i轮要退出的那个人
则 f(0)=0;
f(i)=(f(i-1)+m-1)%(n-i+1);
这个公式我真不知道是咋来的。。。
反正假设我们知道这个公式，那么就可以从小大到枚举m，O(n)枚举。
类型4：模型转变
假设不再是圈，而是一个链，每次从没有死的第一个开始计数。
这道题我确实是结合标程与打表找规律做出来的。
打表每一轮死亡的人，设f(i,j)表示第i轮第j个死的人，我们可以将f(i,j)按照不同j值分类，这些都比较好想，
这道题难点在于第a个人所表示的f(i,j)=a，则f(i-1,j)=a-a/k-1，人从0计数。
上面做完就随便怎么都能做了。
现在暂时总结这么多，总之约瑟夫问题足够神奇，也足够恶心。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 1000000int f[MAXN];int main(){// freopen("input.txt","r",stdin); int n,m; while (scanf("%d%d",&n,&m),n+m) { f[1]=0; int t,x; for (int i=2;i<=n;i++) { f[i]=(f[i-1]+m%i)%i; } printf("%d %d %d\n",n,m,f[n]+1); }}
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 99000000const int ten[7]={1,10,100,1000,10000,100000,1000000};struct aaa{ int val,id,ans;}al[10000];bool cmp_val(aaa a1,aaa a2){ return a1.val<a2.val;}bool cmp_id(aaa a1,aaa a2){ return a1.id<a2.id;}int main(){ // freopen("input.txt","r",stdin); char str[5]; int n=0; while (scanf("%s",str),str[0]+str[1]+str[3]-‘0‘*3) { int i,x; x=((str[0]-‘0‘)*10+str[1]-‘0‘)*ten[str[3]-‘0‘]; al[n++].val=x; al[n-1].id=n-1; } sort(al,al+n,cmp_val); int now=0; int x,y,z; int i; x=0; while (now<n && al[now].val==1) al[now].ans=x+1; for (i=2;i<=MAXN;++i) { x=(x+2)>=i?(x+2-i):(x+2); while (now<n && al[now].val==i) al[now++].ans=x+1; } sort(al,al+n,cmp_id); for (i=0;i<n;i++) { printf("%d\n",al[i].ans); }}
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 99000000const int ten[7]={1,10,100,1000,10000,100000,1000000};int main(){ freopen("input.txt","r",stdin); char str[5]; int n=0; int x; while (scanf("%s",str),str[0]+str[1]+str[3]-‘0‘*3) { x=((str[0]-‘0‘)*10+str[1]-‘0‘)*ten[str[3]-‘0‘]; for (int i=30;i>=0;i--) { if (x&(1<<i)) { printf("%d\n",(((x^(1<<i))<<1)+1)); break; } } }}
约瑟夫问题例题小结