约瑟夫问题（约瑟夫环）

小甲鱼

题目：用循环链表模拟约瑟夫问题，把41个人自杀的顺序编号输出。

故事情节：

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

视频讲解：http://blog.fishc.com/1959.html


源代码参考：http://bbs.fishc.com/thread-25337-1-1.html

兢兢

[人数] = 100
[数数] = 3
Dim b()
ReDim b([人数])
For i=1 to [人数]
   b(i) = 1
Next
i=1
n = [人数]
m=1
While (n > 1)
    While (i<=[人数])
    If b(i) =1 Then
        If m mod [数数] = 0 Then
            b(i)=0
           n = n - 1
          s=s & "→" & i
         End If
        m = m + 1
    End If
    i = i + 1
Wend
i = 1
Wend
msgbox s,vbokonly,"排除顺序"
For i = 1 To [人数]  '查找最后一个数字
        If b(i) = 1 Then
                msgBox  "最后剩下的数是" & i,vbokonly,"约瑟夫环"
        End If
Next

青春@无限

强烈支持楼主ing……

Mr.

谢谢楼主分享

Dokgo.小浪_

强烈支持楼主ing……我真的很感悟……

Dokgo.小浪_

真是难得给力的帖子啊。我只说两句……

じO-联合

强烈支持楼主ing……

じO-联合

强烈支持楼主ing……

安静的渴

支持楼主

1205191816

强烈支持楼主ing……

被忧伤腐蚀

强烈支持楼主ing……

everest

强烈支持楼主ing……

安吉

1. /*编号为1~N的N个人按顺时针方向坐一圈，每个人持有一个密码（正整数，可以自由输入），
   
2. 开始人选一个正整数作为报数上限值M，从第一个人按顺时针方向自1开始顺序报数，报到M时
   
3. 停止报数。报M的人出列，将他的密码作为新的M值，从他顺时针方向上的下一个人开始从1报数，
   
4. 如此下去，直至所有人出列*/
   
5. #include<stdio.h>
   
6. #include<stdlib.h>
   
7. 
   
8. typedef struct circular_linked_list{
   
9.         int password;
   
10.         int index;
    
11.         struct  circular_linked_list *next;
    
12. } Node;
    
13. 
    
14. Node * Creat (int n);
    
15. 
    
16. int main()
    
17. {
    
18.         int i,n,m;
    
19.         Node *p, *temp;
    
20.         printf("输入一个正整数n，代表有n个人围成一个圈。\n");
    
21.         scanf("%d",&n);
    
22.         p=Creat(n);
    
23.         printf("输入一个正整数M，代表第一个人报数的上限值。\n");
    
24.         scanf("%d",&m);
    
25. 
    
26.     m=m>n?m%n:m;
    
27.         while(p->next!=p)
    
28.         {
    
29.                 for(i=1;i<m-1;i++)
    
30.                         p=p->next;
    
31.                 printf("%d->",p->next->index);
    
32.                 m=p->next->password;
    
33.         m=m>n?m%n:m;
    
34.                 temp=p->next;
    
35.                 p->next=temp->next;
    
36.                 free(temp);
    
37.                 p=p->next;
    
38.         }
    
39.         return 0;
    
40. }
    
41. Node *Creat(int n)
    
42. {
    
43.         int i;
    
44.         Node *head, *p, *s;
    
45.         head = (Node *)malloc(sizeof(Node));
    
46.         p=head;
    
47.         printf("输入N个正整数，代表每个人手中的密码\n");
    
48.         for(i=0;i<n;i++)
    
49.         {
    
50.                 s=(Node *)malloc(sizeof(Node));
    
51.                 scanf("%d",&s->password);
    
52.                 s->index=i+1;
    
53.                 p->next=s;
    
54.                 p=s;
    
55.         }
    
56.         s->next=head->next;
    
57.         free(head);
    
58.         return s->next;
    
59. }
    

复制代码

yinjia哈哈

感谢楼主

yinjia哈哈

感谢楼主啊

铭记太阳

每人持有密码的高级约瑟夫环代码用循环链表实现：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #define NUM 10
   
4. #define START 2
   
5. struct Date
   
6. {
   
7.     int number;
   
8.     int password;
   
9.     struct Date *next;
   
10. };
    
11. 
    
12. void ListInsert(struct Date **pt,int num,int pass)
    
13. {
    
14.     struct Date *tmp=NULL,*middle=NULL;
    
15.     tmp=(struct Date *)malloc(sizeof(struct Date));
    
16.     if(tmp==NULL)   exit(1);
    
17.     tmp->number = num;
    
18.     tmp->password = pass;
    
19.     if((*pt)!=NULL)
    
20.     {       
    
21.         middle = *pt;
    
22.         *pt = tmp;
    
23.         tmp->next = middle;
    
24.     }
    
25.     else
    
26.     {
    
27.         tmp->next=NULL;
    
28.         (*pt)=tmp;
    
29.     }
    
30. //    printf("插入成功！\n");
    
31. }
    
32. 
    
33. void ListPrint(struct Date *pt)
    
34. {
    
35.     while(pt!=NULL)
    
36.     {
    
37.             printf("%d--%d\n",pt->number,pt->password);
    
38.         pt = pt->next;
    
39.     }
    
40.     putchar('\n');
    
41. }
    
42. void ListCircle(struct Date **pt)
    
43. {
    
44.     struct Date *rear=*pt;
    
45.     while(rear->next!=NULL)
    
46.         rear=rear->next;
    
47.     rear->next=*pt;
    
48. }
    
49. 
    
50. void JosephusHard(struct Date *pt)
    
51. {
    
52.     struct Date *kill,*previous;
    
53.     unsigned code=START;
    
54.     int i=0,FLAG=0;
    
55.     printf("kill game start!\n");
    
56.     printf("start code is: %d\n\n",START);   
    
57. 
    
58.     while((pt->next)!=pt)
    
59.     {
    
60.         if(code<1)
    
61.         {
    
62.             printf("the code is error\n");
    
63.             exit(1);
    
64.         }
    
65.         else if(code==1)
    
66.         {
    
67.             FLAG=1;
    
68.             goto specialsec;
    
69.         }
    
70.         else if(code==2)
    
71.         {
    
72.              ;   
    
73.         }
    
74.         else
    
75.         {
    
76.                 for(i=code-2;i>0;--i)
    
77.                     pt=pt->next;
    
78.         }
    
79.         kill=pt->next;
    
80.         code=kill->password;
    
81.         pt->next=kill->next;
    
82.         printf("kill No.%d\t",kill->number);
    
83.         printf("next code is %d\n\n",code);
    
84.         free(kill);
    
85.         pt=pt->next;
    
86. 
    
87. specialsec:
    
88.         if(FLAG)
    
89.         {
    
90.             FLAG=0;        //重置FLAG
    
91.             previous=pt;
    
92.             while(previous->next!=pt)
    
93.             {
    
94.                 previous=previous->next;       
    
95.             }
    
96.             kill=pt;            
    
97.             pt=previous;
    
98.             code=kill->password;
    
99.             pt->next=kill->next;
    
100.             printf("kill No.%d\n",kill->number);
     
101.             printf("next code is %d\n",code);
     
102.             free(kill);
     
103.             pt=pt->next;
     
104.         }
     
105. 
     
106. 
     
107.    
     
108.     }
     
109.     printf("kill game over, No.%d survive!\n",pt->number);
     
110. 
     
111. }
     
112. 
     
113. int main()
     
114. {
     
115.     struct Date *pt=NULL;
     
116.     for(int i=NUM ;i>0;i--)
     
117.         ListInsert(&pt,i, NUM+1-i);
     
118.     ListPrint(pt);
     
119.     ListCircle(&pt);
     
120. 
     
121.     JosephusHard(pt);
     
122.     return 0;
     
123. }
     

复制代码

Theen

1. # Python 3
   
2. number = int(input("Game number:"))
   
3. people = []
   
4. for i in range(number):
   
5.     people += [[i - 1, i + 1, i + 1]]
   
6. people[0][0], people[number - 1][2] = number - 1, 0
   
7. 
   
8. flag = 0
   
9. for deadnumber in range(number - 2):
   
10.     for j in range(2):
    
11.         flag = people[flag][2]
    
12.     temp = people[flag]
    
13.     temp2 = temp[2]
    
14.     people[temp[0]][2] = temp[2]
    
15.     people[temp[2]][0] = temp[0]
    
16.     people[flag] = [0, 0, 0]
    
17.     flag = temp2
    
18. 
    
19. print(people[flag][1], people[people[flag][2]][1])
    

复制代码

圣狄雅哥

学习了

lils76