正好之前写过基础的约瑟夫环,稍作修改就可以满足你的题目
#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开始记。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)