问题描述：k个好人和k个坏人站成一圈，前k个是好人，后k个是坏人，m是隔的人数，求最小的m，可以将所有的k个坏人杀死，而好人留下。
这是一个典型的约瑟夫问题的简单变形，
在做这道题的时候，我对约瑟夫问题有所了解，但是对具体的算法步骤却不是很通，我的第一想法就是用循环链表来做。
这是我的程序：
1
#include<stdio.h>
2
3
struct node{
4
int x;
5 int flag;
6 struct node* next;
7
};
8typedef struct node NODE;
9int a[14]={0};
10
11
12void main()
13{
14 int k;
15 NODE *p;
16 NODE *q;
17 int i;
18 while(scanf("%d",&k)==1)
19
{
20 if(k==0)
21 break;
22 if(a[k]==0){
23 int tem=0;
24 int m=k+1;
25 NODE *con=NULL;
26 NODE *con1=NULL;
27 NODE *head=(NODE *)malloc(sizeof(NODE));
28 head->x=1;
29 head->flag=0;
30 q=head;
31 for(i=2;i<=k;i++)
32 {
33 p=(NODE *)malloc(sizeof(NODE)); //分配指针
34 if(p==NULL)
35 return;
36 p->x=i;
37 p->flag=0;
38 q->next=p;
39 q=p;
40
}
41 con=q;
42 con1=q;
43 for(i=k+1;i<=2*k;i++)
44 {
45 p=(NODE *)malloc(sizeof(NODE)); //分配指针
46 if(p==NULL)
47 return;
48 p->x=i;
49 p->flag=1;
50 q->next=p;
51 q=p;
52 }
53
54 q->next=head;
55 q=con->next;
56 while(m)
57 {
58 while(q->flag==1)//是坏人
59 {
60 q->flag=2;
61 tem++;
62
63 for(i=1;i<=m;i++)
64 {
65 q=q->next;
66 if(q->flag==2)
67 {
68 while(q->flag==2)
69 { q=q->next;}
70 }
71 }
72
73 }
74 if(tem==k)
75 break;
76 m++;
77 tem=0;
78 con=con->next;
79 q=con->next;
80 NODE *con2=con1->next;
81 for(i=k+1;i<=2*k;i++)
82 {
83 if(con2->flag==2)
84 con2->flag=1;
85 con2=con2->next;
86 }
87 }
88 a[k]=m;
89 printf("%d\n",m);
90 }
91 else printf("%d\n",a[k]);
92
93 }
94 }
95
现在看来当时的程序真是挺臃肿的，这是我的直观想法，每一个节点就是一个结构体，里面有该节点的值和标记它是好人还是坏人的flag，以及指向下一个节点的指针，开始杀人时就循链检查，发现标记为0的是好人，说明当前m不合适，退出m加1，开始新一轮的搜索，否则继续找下一个。在开始新的一轮的搜索时，一定要还原原来的链，否则会出错，我原来是直接删掉节点了，后来发现无法恢复，就改成了将标记改为2。恢复的时候再改过来就行。这种方法很直观，但是效率很低，算到10就不行了。
后来，我上网搜索了一下别人的代码，发现用的是很巧妙的数学方法，根本连数组都不用建，真慨叹人类的智慧啊！
1#include<stdio.h>
2
3int main()
4{
5 int a[14]={0};
6 int k=0,m=0;
7 while(scanf("%d",&k)==1)
8 {
9 if(k==0)
10 break;
11 if(a[k]==0)
12 {
13 for(m=k+1;;m++)
14 {
15 int n=2*k;
16 int sp=0;
17 while(n>k)
18 {
19 sp=(sp+m-1)%n;
20 if(sp<k)
21 break;
22 n--;
23 }
24 if(n==k)
25 {
26 a[k]=m;
27 printf("%d\n",a[k]);
28 break;
29 }
30 }
31 }
32 else printf("%d\n",a[k]);
33 }
34 return 0;
35 }
36
整整比我的缩短了快两倍，简单的数字就可以判断了，程序也很好理解，执行速度也很快。在遇到有环的时候，可以试试sp=(sp+m-1)%n的访问形式，简单高效。
除此之外，这道题在做的时候，要注意重复输入的问题，可以将之前计算的结果保存下来，遇到重复输入了就直接检查数组输出，又可以节省时间了。
还有一种更暴力的方法：打表。因为输入的k,0<k<14,所以可以私底下直接算出k=1,2.......13的值，直接switch选择输出，
，有点白痴了。