专栏文章

约瑟夫问题

ssun_and_moon
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min4yg5n
此快照首次捕获于
2025/12/01 20:38
3 个月前
此快照最后确认于
2025/12/01 20:38
3 个月前
查看原文
约瑟夫问题解释
nn 个人的编号是 1∼n1 \sim n，如果他们依编号按顺时针排成一个圆圈，从编号是 11 的人开始顺时针报数。
（报数是从 11 报起）当报到 kk 的时候，这个人就退出游戏圈。下一个人重新从 11 开始报数。
求最后剩下的人的编号或依次出圈人的编号。这就是著名的约瑟夫环问题。

方法一：暴力——O(nk)O(nk)

AC代码：
CPP
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671 
#define maxn 1000005
using namespace std;
int a[maxn];
int f,t,s;
int ans;
int n,k;
int main()
{
    cin>>n>>k;
    while(f<n)
    {
    	t++;//现在报数报到的位置 
    	if(t>n)
    		t=1;
    	if(a[t]==0)
    	{
    		s++;//这人还在，报数！ 
    		if(s==k)//这人该出圈了 
    		{
	    		a[t]=1;
    			f++;//又出圈了一个 
	    		s=0;//重新报数 
	    		if(lx==0)
					cout<<t<<' ';
				else
					ans=t;
			}
		}
	}
	if(lx==1)
		cout<<ans;
	return 0;
}

方法二：链表——O(nk)O(nk)

AC代码：
CPP
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671 
#define maxn 1000005
using namespace std;
int a[maxn];//链表指针数组~ 
int f,t,s;
int ans;
int n,k;
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
		a[i]=i+1;
	a[n]=1;
    while(f<n)
    {
    	t=a[t];//下一个位置 ~
		s++;//报数 ——
		if(s==k-1)//场外贵宾一位！（出圈） 
		{
			if(lx==1)
				ans=a[t];
			else
				cout<<a[t]<<' ';
			a[t]=a[a[t]];
			s=0;
			f++;
		}
    }
	if(lx==1)
		cout<<ans;
	return 0;
}

方法三：模拟——O(nk)O(nk)

AC代码：
CPP
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671 
#define maxn 1000005
using namespace std;
int a[maxn];//现在坐在i位置的人是谁呢？当然是a[i]咯~ 
int f,t,s;
int ans;
int n,k;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    	a[i]=i;
    for(s=1,f=n;f>=1;f--)//每轮循环都能有“场外贵宾一位！”（出圈大吉） 
    {
    	s=(s+k-2)%f+1;//下一位场外贵宾！ 
    	if(lx==0)
			cout<<a[s]<<' ';
		else
			ans=a[s];
		for(int j=s;j<f;j++)//后面的，都给我往左移一位！  
			a[j]=a[j+1];
    }
	if(lx==1)
		cout<<ans;
	return 0;
}

方法四：分块——O(nn)O(n\sqrt{n})

AC代码：
CPP
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671 
#define maxn 1000005
using namespace std;
bool a[maxn];//现在编号为 i 人还好吗？a[i] 为 1 就还好 
int b[maxn];//现在 i 组还有几个人？b[i]个人~ 
int c;//初始一组几个人？这个变量告诉你~ 
int f,t,s;
int ans;
int n,k;
int main()
{
    cin>>n>>k;
    k=(k-1)%n+1;
    c=sqrt(n);
    s=1;
    for(int i=1;i<=n;i++)
	{
		a[i]=true;
		b[i/c]++;
	}
	for(f=n;f>=1;f--)//每轮循环，贵宾一位！ 
	{
		s=(s+k-2)%f+1;
		int x=s,l=0;
		while(b[l]<x)
			x-=b[l++];
		t=l*c-1;
		while(x)
			x-=a[++t];
		if(lx==0)
			cout<<t<<' ';
		else
			ans=t;
		a[t]=false;//贵宾走了，但他的位置还在…… 
		b[t/c]--;//小组人数-- 
	}
	if(lx==1)
		cout<<ans;
	return 0;
}

方法五：线段树——O(nlog⁡n)O(n \log n)

AC代码：
CPP
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671 
#define maxn 1000005
using namespace std;
int tree[maxn*4]; //线段树要吃四倍空间？！太吓人啦！ 
int f,s=1,t; 
int ans;
int n,k;
void build(int i,int l,int r)//建树！（要致富，先撸树） 
{
	if(l==r)
	{
		tree[i]=1; 
		return;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i]=tree[i*2]+tree[i*2+1];
}
void update(int i,int l,int r,int u,int v)//修改其中一点的数值！（小心树木倒塌） 
{
	if(l==r)
	{
		tree[i]=v;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid)
		update(i*2,l,mid,u,v);
	else
		update(i*2+1,mid+1,r,u,v);
	tree[i]=tree[i*2]+tree[i*2+1];
	return;
}
int query(int i,int l,int r,int k)//查询其中一点的数值！（树木不好查） 
{
	if(l==r)
		return l;
	int mid=(l+r)/2;
	if(k<=tree[i*2])
		return query(i*2,l,mid,k);
	else
		return query(i*2+1,mid+1,r,k-tree[i*2]);
} 
int main()
{
	cin>>n>>k;
	build(1,1,n);
	for(f=n;f>=1;f--)//这次邀请贵宾，咱要用线段树！ 
	{
		s=(s+k-2)%f+1;
		t=query(1,1,n,s);
		if(lx==0)
			cout<<t<<' ';
		else
			ans=t;
		update(1,1,n,t,0);
	}
	if(lx==1)
		cout<<ans;
	return 0;
}

方法六：树状数组——O(nlog⁡nlog⁡n)O(n \log n \log n)

AC代码：
CPP
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671 
#define maxn 1000005
using namespace std;
int tree[maxn]; //树状数组比线段树要好多啦 ~不多吃空间 ~ 
int f,s=1,t; 
int ans;
int n,k;
void update(int i,int r,int v)//增加其中一点的数值！（小心树木倒塌） 
{
	for(int x=i;x<=r;x+=x&-x)
		tree[x]+=v;
	return;
}
bool check(int mid)//二分判断条件 
{
	int sum=0;
	for(int x=mid;x>0;x-=x&-x)
		sum+=tree[x];
	return sum>=s;
}
int ef(int l,int r)//咱要节省时间……O(n)~O(log n) 
{
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	return r;
}
void build(int i,int r)//建树！（要致富，先撸树） 
{
	for(int j=i;j<=r;j++)
		update(j,r,1);
}
int main()
{
	cin>>n>>k;
	build(1,n);
	for(f=n;f>=1;f--)//这次邀请贵宾，咱要用……树状数组！ 
	{
		s=(s+k-2)%f+1;
		ans=ef(1,n);
		if(lx==0)
			cout<<ans<<' ';
		update(ans,n,-1);
	}
	if(lx==1)
		cout<<ans;
	return 0;
}

方法七：块状链表——O(nn)O(n\sqrt{n})

AC代码：
CPP
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671 
#define maxn 1000005
using namespace std;
bool a[maxn];//现在编号为 i 人还好吗？a[i] 为 1 就还好 
struct lb
{
    int next;
    vector<int>v;
}b[maxn];//现在 i 组还有几个人？b[i].v.size()个人~ 
int c;//初始一组几个人？这个变量告诉你~ 
int f,t,s;
int ans;
int n,k;
int main()
{
    cin>>n>>k;
    k=(k-1)%n+1;
    c=sqrt(n);
    s=1;
    for(int i=1;i<=n;i++)
	{
		a[i]=true;
		b[i/c].v.push_back(i);
	}
    for(int i=0;i<n;i++)
		b[i].next=i+1;
	for(f=n;f>=1;f--)//每轮循环，贵宾一位！ 
	{
		s=(s+k-2)%f+1;
		int x=s,l=0;
		while(b[l].v.size()<x)
        {
			x-=b[l].v.size();
            l=b[l].next;
        }
		t=l*c-1;
		if(lx==0)
			cout<<b[l].v[x-1]<<' ';
		else
			ans=b[l].v[x-1];
		a[t]=false;//贵宾走了，但他的位置还在…… 
		b[l].v.erase(b[l].v.begin()+x-1);//不好！他在vector里的位置没了！！！ 
	}
	if(lx==1)
		cout<<ans;
	return 0;
}

方法八：递归——O(n)O(n)

注：此代码仅限P8671
AC代码：
CPP
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,k;
int f(int n)
{
  if(n==1)
    return 1;
  return (f(n-1)+k-1)%n+1;
}
int main()
{
  cin>>n>>k;
  cout<<f(n);
  return 0;
}

方法九：递推——O(n)O(n)

注：此代码仅限P8671
AC代码：
CPP
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int ans=1;
int n,k;
int main()
{
  cin>>n>>k;
  for(int i=1;i<=n;i++)
    ans=(ans+k-1)%i+1;
  cout<<ans;
  return 0;
}

方法十：递归优化——O(k)O(k)

注：此代码仅限P8671
AC代码：
CPP
//方法十 
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int k;
int f(int n)
{
    if(n==1)
        return 1;
    return (f(n-1)+k-1)%n+1;
}
int fk(int n)
{
    if(n<k)
        return f(n);
    int l=fk(n-n/k),y=n%k;
    if(l<=y)
    	return l+n/k*k;
    l-=y;
    return (l-1)/(k-1)+l;
}
int n;
int main()
{
	cin>>n>>k;
	cout<<fk(n);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...