欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

约瑟夫环

程序员文章站 2023-09-01 18:41:55
题目描述 有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位。 有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位。 输入 初始人数n 初始人数n 输出 最后一人的初始 ......

  

题目描述

有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 }