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

发布时间：2010-07-25 19:17:37

Josephus 约瑟夫 问题

假设n个竞赛者排成一个环形，依次顺序编号1，2，…，n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到所有的人都出列为止。最后出列者为优胜者。

无论是用链表实现还是用数组实现来解约瑟夫问题都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较麻烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。注意到原问题仅仅是要求出最后的胜利者的序号，而不是要模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-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 --> 0

k+1 --> 1

k+2 --> 2

...

...

k-2 --> n-2

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？变回去的公式很简单：x'=(x+k)%n

如何知道(n-1)个人报数的问题的解？显然，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！

递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式

f[1]=0;

f[i]=(f[i-1]+m)%i; (i>1)

有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f[i]，程序也是很简单：

#include

main()

{

int 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 %d\n", s+1);

}

这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。

PKU Joseph相关问题:

1012 Joseph

一半好人一半坏人。模拟打表。

#include

using namespace std;

int a[14];

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(s

   return false;

 }

 return true;

}

int main()

{

 int i,j;

 for(i=1;i<=13;++i)

 {

  j=i+1;

  while(!fun(i,j))

   ++j;

  a[i]=j;

 }

    int k;

 while(cin>>k && k)

  cout<

 return 0;

}

2359 Questions

标准约瑟夫问题+字符串

#include

using namespace std;

char s[30002];

int main()

{

 char ch;

 

 int len=0;

 while((ch=getchar())!=EOF)

 {

  if(ch!='\n')

  {

   ++len;

   s[len]=ch;

  }

 }

 int t=0;

 

 for(int i=2;i<=len;++i)

         t=(t+1999)%i;

 if(s[t+1]==' ')

  cout<<"No"<

 else if(s[t+1]=='?')

  cout<<"Yes"<

 else

        cout<<"No comments"<

 

 return 0;

}

1781 In Danger

只考虑M为2的情况，将十进制转换为二进制，循环左移一位，再转换为十进制即为解，解法证明见具体数学1.3。

#include

#include

using namespace std;

int main()

{

    string s;

 while(cin>>s)

 {

  if(s=="00e0")

   break;

  string str=s.substr(0,2);

  int i,j;

  int t=s[3]-'0';

  for(i=0;i

   str+='0';

  int len=str.length();

     int sum=str[0]-'0';

  for(i=1;i

   sum=sum*10+(str[i]-'0');

  int a[100];

  j=0;

  while(sum)

  {

   a[j]=sum%2;

   ++j;

   sum/=2;

  }

  

  for(i=0;i

  {

   t=a[i];

   a[i]=a[j-1-i];

   a[j-1-i]=t;

  }

  t=a[0];

  for(i=1;i

   a[i-1]=a[i];

  a[j-1]=t;

  t=a[0];

  for(i=1;i

   t=t*2+a[i];

  cout<

 

 }

 return 0;

}

2244 Eeny Meeny Moo

N个城市轮流断电，求最小的M使胜者为城市2。从城市1开始断，相当于循环N-1次。

#include

using namespace std;

int fun(int m,int n)

{

 int s=0,i;

 for(i=2;i

  s=(s+n)%i;

 return s+1;

}

int main()

{

 int m;

 int j;

 while(cin>>m && m)

 { 

  j=2;

  while(fun(m,j)!=1)

   ++j;

  cout<

 }     

 

 return 0;

}

3517 And Then There Was One

有初始值的约瑟夫问题，和2244一样，结果加上初始值就可以。

#include

using namespace std;

int main()

{

int i,j,k,m,n,s;

while(1)

{

cin>>n>>k>>m;

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+1<结果加初始值

}

return 0;

}

2939 Flavius Josephus Reloaded

#include

#include

using namespace std;

typedef long long ll;

#define HASHLEN 1987039

struct hashtype

{

    int v;   //value，查找的值

    int cnt; //count,查找的次数

}hash[HASHLEN];

int addorfind(int v,int cnt)

{

    int t=v%HASHLEN;

    while(hash[t].v!=-1 && hash[t].v!=v)

 {

        t++;

        if(t>=HASHLEN)

            t=0;

    }

    if(hash[t].v!=-1)

        return hash[t].cnt;

 else

 {

        hash[t].cnt=cnt;

        hash[t].v=v;

        return -1;

    }

}

int main()

{

    int n,a,b;

    while(scanf("%d",&n) && n)

 {

        scanf("%d%d",&a,&b);

        memset(hash,-1,sizeof(hash)); 

        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("%d\n",n-cnt+t);

                break;

            }

            ++cnt;

        }

    }

 return 0;

}

PKU 2800

#include

#include

using namespace std;

int main()

{

 long long  N,K;

        while(cin>>N>>K)

  {

   long long sk,ssk,i,s,e,tmp,ans;

   

   sk = sqrt((double)K);

      ssk = K / sk;

   

   for (i = 1, ans = 0; i <= N && i <= ssk; i++)

   {

    ans += K % i;

   }

  

   if (N > K)

   {

    ans += (N - K) * K;

   }

          

  

   for (i = sk; i > 1; i--)

   {

   

    s = K / i;

   

    e = K / (i - 1);

   

    if (N < s)

    {

     break;

    }

    if (N < e)

    {

     e = N;

    }

    tmp = (K % e + K % (s + 1)); //K%e为首项，K%(S+1)为尾项

    tmp *= (e - s); //(e-s)为总项数

    tmp /= 2;

    ans += tmp;

    

   }

   cout<

  }

  return 0;

}

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

推荐内容

相关推荐