用c语言实现约瑟夫环

正好之前写过基础的察雀约瑟夫环，稍作修改就可以满足你的题目

#include <stdio.h>

#include <stdlib.h>

typedef struct _node {

    int id

    int key

    struct _node *next

} Linklist

int main() {

int n, m

scanf("%d %d", &n, &m)

int i, count = 0

Linklist *head = (Linklist*)malloc(sizeof(Linklist)), *tail = head

head->id = 1

scanf("%d", &head->key)

head->next = head

for(i = 2 i <= n i++) {

Linklist *p = (Linklist*)malloc(sizeof(Linklist))

p->id = i

scanf("%d", &p->key)

p->next = head

tail->next = 世没败p

tail = p

}

while(head != tail) {

if(++count % m) {

tail = head

} else {

    m = head->key

    count = 0

printf("%d "搜颤, head->id)

tail->next = head->next

free(head)

}

head = tail->next

}

printf("%d\n", head->id)

free(head)

return 0

}

#include<stdio.h>

struct

list//建立一个结构体，慧带岁包括每个人的编号，密码和下一级的指针

{

int

id

int

code

struct

list

*next

}

typedef

struct

list

list//把结构体用list表示

list*

input(int

n)//链表的初始化

{

list

*p,*q,*l

int

i,m

p=new

list

l=new

list

l->next=NULL

p=l

p->id=1//第一个人的初始化

scanf("%d",&m)

p->code=m

for(i=2i<=ni++)//第二个人到第num个人的初始化

{

q=new

list

q->id=i

scanf("%d",&m)

q->code=m

q->next=NULL

p->next=q

p=q

}

p->next=l//使表尾指向表头，成循环链表

return

p

}

int

main()

{

int

num,m1,i

list

*q,*p

while(scanf("%d",&num)!=EOF)

{

printf("第一次的密码为:")

scanf("%d",&m1)

p=input(num)

//printf("%4d\n",head->id)

printf("出队的顺序为:")

while(p->next!=p)

{

for(i=1i<=m1i++)

{

q=p

p=p->next

//printf("--\n"前睁,p->id)

}

m1=p->code

printf("%4d",p->行前id)

q->next=p->next

delete

p

p=q

}

printf("%4d",p->id)

delete

p

printf("\n")

}

}

怎么了，代码看不懂？

约瑟夫环（约瑟夫问旅岁题）是一个数学的应用问题：已知n个人（拆绝睁以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

首先我们列出一些有关约瑟夫环的结果：

1 1 2 2 3 2 4 1 5 4 6 1 7 4 8 7 9 1 10 4

11 7 12 10 13 13 14 2 15 5 16 8 17 11 18 14 19 17 20 2021 2 22 5 23 8 24 11 25 14 26 17 27 20 28 23 29 26 30 29

31 1 32 4 33 7 34 10 35 13 36 16 37 19 38 22 39 25 40 28

41 31 42 34 43 37 44 40 45 43 46 46 47 2 48 5 49 8 50 11

51 14 52 17 53 20 54 23 55 26 56 29 57 32 58 35 59 38 60 41

61 44 62 47 63 50 64 53 65 56 66 59 67 62 68 65 69 68 70 171 4 72 7 73 10 74 13 75 16 76 19 77 22 78 25 79 28 80 31

81 34 82 37 83 40 84 43 85 46 86 49 87 52 88 55 89 58 90 61

91 64 92 67 93 70 94 73 95 76 96 79 97 82 98 85 99 88 100 91

意思是，前一个数为约瑟夫环的人数，后一个数为宏宽最后出去的人的号码。

从上面的表中我们可以归纳出以下两个规则：

规则1:若上一组数字中最后保留号比人数少一，则下一数从1开始记。

例如第三组（3,2）为上一组，最后保留好为2，比3少1，下一组的数字（4,1），最后保留号为1

规则2:若上一组数字为最后保留号与人数相等，则下一数从2开始记。

---