1 /*约瑟夫问题(单向循环链表解法)
2 先创建含有n个猴子结点的单向循环链表,然后模拟报数过程,将第m个猴子结点删除,最后当只有一个猴子结点时跳出循环,输出结果*/
3 #include<stdio.h>
4 struct Monkey{
5 int id;
6 Monkey *next;
7 };
8 int main(){
9 int n,m;
10 int i;
11 Monkey *link, *monkey, *lastmonkey;
12 while(scanf("%d%d",&n,&m), n+m != 0){
13 if(m==1){//当m为1时直接输出n
14 printf("%d
",n);
15 continue;
16 }
17
18 link=lastmonkey=NULL;
19 for(i=1;i<=n;i++){
20 monkey = new Monkey;
21 monkey->id=i;
22 monkey->next=NULL;
23 if(link == NULL){
24 link = lastmonkey = monkey;
25 }
26 else{
27 lastmonkey->next=monkey;
28 lastmonkey=monkey;
29 }
30 }
31 /*遍历
32 monkey=link;
33 while(monkey != NULL){
34 printf("%d ",monkey->id);
35 monkey= monkey->next;
36 }*/
37 lastmonkey->next=link;//构成环
38
39 int count=1;//从1开始计数
40 while(link->next != link){
41 if(count == m-1){
42 monkey=link->next;
43 link->next=monkey->next;
44 count=0;
45 delete monkey;
46 }
47 link=link->next;
48 count++;
49 }
50 printf("%d
",link->id);
51 delete link;
52 }
53 return 0;
54 }