约瑟夫环

　　

题目描述

有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位。

输入

初始人数n

输出

最后一人的初始编号

样例输入

3

样例输出

2
　使用无头循环单链表即可

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 typedef struct huan {
 4 unsigned int a; 
 5 struct  huan *pnext; 
 6 }huan;
 7 huan *create(int n) {
 8     huan *phead, *pnew = null;    int i;
 9     phead = (huan*)malloc(sizeof(huan));
10     phead->a = 1;
11     phead->pnext = null;
12     huan *cyclic = phead;
13         for (i = 2; i <= n; i++) {
14         pnew = (huan*)malloc(sizeof(huan));
15         pnew->a = i;
16         pnew->pnext = null;
17         cyclic->pnext = pnew;
18         cyclic = cyclic->pnext;
19     }
20     cyclic->pnext = phead;
21     return phead;
22 }
23 void sort(huan *head) {
24      huan *pbefore, *p;
25      p = head; pbefore =null;
26     while (p->pnext!=p) {
27         for (int i = 1; i < 3; i++) {
28             pbefore = p;
29             p = p->pnext;
30         }
31         pbefore->pnext = p->pnext;
32         free(p);
33         p = pbefore->pnext;
34         
35 }
36     printf("%d", p->a);
37     free(p);
38     
39     
40 }
41 
42 int main() {
43     int n; huan *p;
44     scanf("%d", &n);
45     p = create(n);
46     sort(p);
47     
48 }