约瑟夫问题（循环链表）

问题描述：

约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。一群人表决说要死，所以用一种策略来先后杀死所有人。于是约瑟夫建议：每次由其他两人一起杀死一个人，而被杀的人的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后一签，在杀了除了他和剩余那个人之外的最后一人，他劝服了另外一个没死的人投降了罗马。

 1 //利用循环链表模拟约瑟夫问题，把41个人自杀的顺序编号输出
 2 #include<iostream>
 3 #include<malloc.h>
 4 #include<string.h>
 5 #include<stdlib.h>
 6 #include<stdio.h>
 7 using namespace std;
 8 
 9 typedef struct Node{
10     int data;
11     struct Node *next;
12 }Node,*LinkList;
13 
14 void InitList(LinkList &L){
15     L = (LinkList)malloc(sizeof(Node));
16     if(!L)
17         exit(0);
18     L->next = NULL;
19 }
20 
21 LinkList CreatList(LinkList &L, int n){//尾插法创建单链表 
22     LinkList r,p;
23     r = L;
24     for(int i = 1; i <= n; i++){
25         p = (LinkList)malloc(sizeof(Node));
26         p->data = i;
27         r->next = p;
28         r = p;
29     }
30     r->next = NULL;
31     p->next = L->next;//尾部指向头部，循环链表 
32     return p->next;//返回头结点的头指针（构成循环） 
33 }
34 
35 int main(){
36     int n = 41;
37     int m = 3;
38     LinkList L,p;
39     InitList(L);
40     p = CreatList(L,n);
41     LinkList temp;
42     m %= n;
43     while(p != p->next){
44         for(int i = 1;i < m-1; i++){
45             p = p->next;
46         }
47         printf("%d->",p->next->data);
48         //删除结点 
49         //p->next->next;
50         temp = p->next;
51         p->next = temp->next; 
52         free(temp);
53         p = p->next;
54     }
55     cout<<p->data;
56     return 0;
57 }

运行结果：

关于约瑟夫问题的题目：

n个人围成一个圈，每个人分别标注为1、2、...、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。给定n个人，请你编程计算出最后胜利者标号数。（要求用单循环链表完成。）

第一行为人数n;
第二行为报数k

链表实现：

 1 #include<stdio.h>
 2 #include<malloc.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 
 6 typedef struct Node{
 7     int data;
 8     struct Node *next;
 9 }Node,*LinkList;
10 
11 int main(){
12     LinkList L,p,r;
13     L = (LinkList)malloc(sizeof(Node));
14     r = L;
15     int n,k;
16     scanf("%d%d",&n,&k);
17     for(int i = 1; i <= n; i++){///尾插法建立循环链表
18         p = (LinkList)malloc(sizeof(Node));
19         p->data = i;
20         r->next = p;
21         r = p;
22     }
23     p->next = L->next;//让最后一个链表的下一个节点指向开头
24     LinkList s;
25     s = L->next;
26     while(s != s->next){
27         for(int i = 1; i < k-1; i++){
28             s = s->next;
29         }
30         s->next = s->next->next;//删除结点 
31         s = s->next;
32     }
33     printf("%d",s->data);
34     return 0;
35 }

数组实现：

 1 #include<stdio.h>
 2 int main(){
 3     int n,k;
 4     scanf("%d%d",&n,&k);
 5     int a[1001];
 6     int dead = 0;//记录已经死了多少人 
 7     int num = 0;//没有被杀的人喊数
 8     for(int i = 1; i <= n; i++)
 9         a[i] = i;
10     for(int i = 1; ;i++){
11         if(i > n)
12             i %= n;//如果大于总人数，则从头开始 
13         if(a[i] > 0)
14             num++;
15         if(k == num && dead != n-1){//如果当前这个人报的数等于k 并且没有已经死亡n-1个人
16             num = 0;
17             a[i] = 0;
18             dead++;
19         }
20         if(k == num && dead == n-1){ //如果这个人报数等于k，并且已经死了n-1个人，说明当前这个人就是最后的一个活着的了
21             printf("%d",a[i]);
22             break;
23         }
24     }
25     return 0; 
26 }

运行结果：

公式法：

#include<stdio.h>
int main()
{
    int n, m,i,s=0;
    scanf("%d%d",&n,&m);
    /*
    首先从2开始，因为1个人的时候报的数字的人为0号，结果已经确定了。不需要从i=0开始，要注意的是序列从0开始编号的，所以最后的输出结果也要加1.
    s表示的是上一轮的结果，m代表是每多少个人出列一次，i代表当前已经出列了多少个人。
    整个式子就是根据上一个的出列数和已经出列的人数来算的。
    */
    for(i=2;i<=n;i++)
        s=(s+m)%i;
    printf("%d", s+1);
    return 0;
}

约瑟夫问题（循环链表）

推荐阅读