约瑟夫环问题

果子

[bgcolor=#ffffff]        据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。[/bgcolor]
[bgcolor=#ffffff]       现假设有N个人，从第一个人开始数，数到M的人退出，请编程实现最后一个留下来的人是谁？[/bgcolor]
[bgcolor=#ffffff]       如输入：4  2[/bgcolor]
[bgcolor=#ffffff]       [/bgcolor]第1个出局的人的序号是:2
       第2个出局的人的序号是:4
       第3个出局的人的序号是:3
       最后留下来的人的序号是： 1

      如输入：3 5

      第1个出局的人的序号是:2
      第2个出局的人的序号是:3
      最后留下来的人的序号是： 1

果子

下面是以循环链表的方式解答：

1. #include <stdio.h>
2. #include <string.h>
3. #include <malloc.h>
4. typedef struct josefu *list;
6. struct josefu{
7.         int num;
8.         list next;
9. };
10. int main(int argc,char *argv[])
11. {
12.         list head = NULL,s = NULL,p = NULL;
13.         int i,totall_pepole,count;
14.         int set;
16.         if(argc != 3)
17.         {
18.                 fprintf(stderr,"Please input 3 param.\n");
19.                 printf("Param followed as [program name] [pepole num] [count]:\n");
20.                 printf("%s 3 2\n ",argv[0]);
21.                 return 0;
22.         }
24.         totall_pepole = atoi(argv[1]);
25.         count = atoi(argv[2]);
27.         /*Create a circular queue.*/
28.         s = malloc(sizeof *s);
29.         head = s;
30.         s->num = 1;
31.         s->next = head;
32.         /*End circular queue*/
34.         p = head;
36.         /*All the people stand in a circle.*/
37.         for(i = 2;i<=totall_pepole;i++)
38.         {
39.                 p->next = malloc(sizeof(*p));
40.                 p = p->next;
41.                 p->num = i;
42.                 p->next = head;
43.         }
44.         set = totall_pepole;
45.         /*Game begin. */
46.         while(p != p->next)
47.         {
48.                 list t;
49.                 for(i=1;i<count;i++)
50.                 {
51.                         p = p->next;
52.                 }
53.                 printf("第%d个出局的人的序号是:%d\n",set - (--totall_pepole),p->next->num);
54.                 t = p->next;
55.                 p->next = p->next->next;
56.                 free(t);
57.         }
60.         printf("最后留下来的人的序号是： %d\n",p->num);
61.         /*Destroy*/
63.         free(p);
65.         return 0;
66. }

复制代码

boyfaceone

游戏蛮刺激的！上面的方法很不错，思路清晰。
试着用数组做了下。

果子

boyfaceone:游戏蛮刺激的！上面的方法很不错，思路清晰。
试着用数组做了下。 (2013-06-16 21:55)

恩，之前我是做了两种方法，一种是数组，一种是循环链表。
下面是数组的方法，比较暴力，呵呵。百度上有更精妙的解法。

1. #include <stdio.h>
2. int is_empty(char a[], int N)
3. {
4.     int i,flag = 0;
5.     for(i=0; i<N; i++)
6.     {   
7.         if( a == &#39;1&#39; )
8.         {      
9.             flag = 1;   
10.             break;      
11.         }      
12.         else   
13.             flag = 0;   
14.     }   
15.     return flag;
16. }
18. int josef_num(char a[],int N,int M)
19. {
20.     int i = 0,count = 0;
22.     while(i<N)
23.     {   
24.         if ( a == &#39;1&#39; )
25.             count++;   
26.         if(count == M)
27.         {      
28.             a[i++] = 0;
29.             count = 0;  
30.             if( ! is_empty(a,N) )
31.                 break;         
32.             if( i == N)
33.                 i = 0;         
34.             continue;
35.         }
36.         i++;
37.         if(i == N)
38.             i = 0;
39.     }
41.     return i;
42. }
45. int main()
46. {
47.     int N,M;
48.     char a[256] = {0};
49.     int i;
51.     printf("Please input the number of pepole[1-256]:");
52.     scanf("%d",&N);
53.     printf("Input a number again:");
54.     scanf("%d",&M);
56.     /*Initialize array a*/
57.     for(i=0; i<N; i++)
58.     {
59.         a = &#39;1&#39;;
60.     }
61.     printf("The last pepole number is:%d\n",josef_num(a,N,M));
63. }

复制代码

果子

还可以用数学归纳法：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到m-1的退出
　　，剩下的人继续从0开始报数。求胜利者的编号。
　　我们知道第一个人(编号一定是(m-1)%n) 出列之后，剩下的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-3 --> n-3
　　k-2 --> n-2
　　序列1： 0, 1, 2, 3 … n-2, n-1
　　序列2： 0, 1, 2, 3 … k-1, k+1, …, n-2, n-1
　　序列3： k, k+1, k+2, k+3, …, n-2, n-1, 1, 2, 3,…, k-2,
　　序列4：0, 1, 2, 3 …, 5, 6, 7, 8, …, n-3, n-2
　　变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解               吗？！！变回去的公式很简单，相信大家都可以推出来：
　　∵ k=m%n;
　　∴ x&#39; = x+k = x+ m%n ; 而 x+ m%n 可能大于n
　　∴x&#39;= (x+ m%n)%n = (x+m)%n
　　得到 x‘=(x+m)%n
　　如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下           面写递推公式：
　　令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n].
　　递推公式:
　　f[1]=0;
　　f=(f[i-1]+m)%i; (i>1)
　　有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。我们输出f[n]由于是逐级递推，不需要保存每个，程序也是异常简单：(注意编号是0 -- n-1)
　　

1. #include <stdio.h>
2. 　　int main(void)
3. 　　{
4. 　　int n, m, i, s=0;
5. 　　printf ("N M = ");
6. 　　scanf("%d%d", &n, &m);
7. 　　for (i=2; i<=n; i++)
8. 　　s=(s+m)%i;
9. 　　printf ("The winner is %d\n", s);
10. 　　return 0 ;
11. 　　}

复制代码

　　时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且           往往会成倍地提高算法执行效率。
　　参照上面提供的思路，我认为可以类似的得到一个更易于明白的方法，设有（1,2,3，……，k-1，k，k+1，……，n）n个数，当k出列时，那么有
　　k+1 -->1
　　k+2 -->2
　　...
　　...
　　n -->n-k
　　1 -->n-k+1
　　...
　　...
　　k-1 -->n-1
　　由上面一组式子可以推出，若知道新产生的n-1个数中某个数x，那么很显然可以推出x在原数列里的位置，即x‘=（x+k）%n,由此，我们可以得到一个递推公式
　　f[1]=1
　　f[n]=(f[n-1]+k)%n （n>1）
　　如果你认为上式可以推出约瑟夫环问题的解，很不幸，你错了，上面的递推公式中，在某种情况下，f[n-1]+k会整除n，如n=2，k=3，这时我们修要对上式进行修正，
　　f[n]=(f[n-1]+k)%n;if(f[n]==0)f[n]=n;
　　问题得解。 程序代码如下：
　　

1. #include<stdio.h>
2. 　　int main()
3. 　　{
4. 　　int n,k,s=1;
5. 　　scanf("%d%d",&n,&k);
6. 　　for(int i=2;i<=n;i+=1)
7. 　　{
8. 　　s=(s+k)%i;
9. 　　if(s==0)s=i;
10. 　　}
11. 　　printf("ans=%d\n",s);
12. 　　return 0;
13. 　　}

复制代码

　　当然，我们还可以用递归方法解决此问题：
　　

1. #include<stdio.h>
2. 　　int main()
3. 　　{
4. 　　int jos(int n,int k);
5. 　　int n,k,s;
6. 　　scanf("%d%d",&n,&k);
7. 　　s=jos(n,k);
8. 　　printf("ans=%d\n",s);
9. 　　return 0;
10. 　　}
11. 　　int jos(int n,int k)
12. 　　{
13. 　　int x;
14. 　　if(n==1)x=1;
15. 　　else {x=(jos(n-1,k)+k)%n;if(x==0)x=n;}
16. 　　return x;
17. 　　}

复制代码