约瑟夫环问题

jerrychoi

浏览: 3425 次
性别:
来自: 福州

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2009-08 ( 2)
更多存档...

博客分类：

数据结构

游戏 F#D语言生活 J#

问题描述：n个人（编号从1到n），从1开始报数，报到m的退出，剩下的人继续从1开始报数。求胜利者的编号。

C语言指针版本

 1:  #include <stdio.h>

 2:  #include <stdlib.h>

3:

 4:  int main()

 5:  {

 6:      int n,m;

 7:      printf("请输入n和m的值:");

 8:      scanf("%d %d",&n,&m);

9:

10:      int *number = (int *)malloc(sizeof(int)*n);

11:      int temp;

12:      for(temp=0 ; temp<n ; ++temp)

13:      {

14:          *(number+temp) = 0;    //0代表没没出列,1代表出列

15:      }

16:

17:      printf("依次出列的号码为：");

18:      int count;

19:      for(count=0,temp=0 ; count<n ; ++count,temp = (temp+1)%n)

20:      {

21:          for(int i=0 ; i<m ;temp = (temp+1)%n)

22:          {

23:              if(*(number+temp) == 1)

24:              {

25:                  continue;

26:              }

27:              if( (i+1)== m )

28:              {

29:                  *(number+temp) = 1;

30:                  break;

31:              }

32:              ++i;

33:          }

34:          printf("%d\t",temp+1);

35:          if(count == n-1)

36:          {

37:              printf("\n胜利者的编号为：%d\n",temp+1);

38:          }

39:      }

40:

41:      return 0;

42:  }

43:

C++的循环链表版本

（注：CircList.h头文件事先已经写好，是循环链表）

 1:  #include "CircList.h"

2:

 3:  template<class T>

 4:  void Josephus(CircList<T> &Js,int n,int m)    //n---总数，m---目标数

 5:  {

 6:      CircLinkNode<T> *p = Js.GetHead()->link,*pre = NULL;

 7:      for (int i = 0;i < n-1;++i)    //执行n-1次

 8:      {

 9:          for (int j = 1;j < m;++j)    //数m个人

10:          {

11:              pre = p;

12:              p = p->link;

13:              if(p == Js.GetHead())

14:              {

15:                  p = p->link;

16:                  pre = pre->link;

17:              }

18:          }

19:          cout<<"出列的人是:"<<p->data<<endl;

20:          pre->link = p->link;

21:          delete p;

22:          p = pre->link;

23:          if(p == Js.GetHead())

24:          {

25:              p = p->link;

26:              pre = pre->link;

27:          }

28:      }

29:  }

30:

31:  void main()

32:  {

33:      CircList<int> clist;

34:      int n,m;

35:      cout<<"输入游戏者人数和报数间隔：";

36:      cin>>n>>m;

37:      for(int i = 1;i <= n;++i)

38:          clist.Insert(i-1,i);

39:      Josephus(clist,n,m);

40:  }

41:

约瑟夫问题的数学方法（以下内容为网上转载）

      无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达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
      k-1   --> n-1

      变换后就完完全全成为了(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]，程序也是异常简单：
 1:  #include <stdio.h>
 2:  
 3:  int main() 
 4:  { 
 5:      int n, m, i, s=0; 
 6:      printf ("请输入n和m的值：");
 7:      scanf("%d %d", &n, &m); 
 8:      for (i=2; i<=n; i++) 
 9:          s=(s+m)%i; 
10:      printf ("The winner is %d\n", s+1); 
11:      return 0;
12:  }