可搜索,可注册,可登录,致敬逗比大佬!尽在救援版逗比根据地 dbgjd.com
投稿文章 | 广告合作 | Telegram 群组 / 公告频道 / 使用教程

约瑟夫环问题的C语言算法实现

News felisharhoads92 24℃ 0评论

约瑟夫(Joseph)问题的一种描述是:编号为 1,2,…..,n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值 m,从第一个人开始按顺时针方向自 1 开始顺序报数,报到 m 时停止报数。报 m 的人出列,将他的密码作为新的 m 值,从他在顺时针方 向上的下一个人开始重新从 1 报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。

基本要求

利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。

测试数据

n=7, 7 个人的密码依次为:3,1,7,2,4,8,4,首先 m 值为 6(正 确的出列顺序应为 6,1,4,7,2,3,5),输出的密码为 8,3,2,4,1, 7,4.

实现提示

程序运行后,首先要求用户指定初始报数上限值,然后读取各人的密 码。可设 n<=30。此题所用的循环链表中不需要“头节点”,请注意空表和非空表的界限。

算法代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct Student)

struct Student //用链表建立学生数据类型
{
int number;
int password;
struct Student *next;
};


struct Student *creat(void) //输入具体学生信息,约定0,0结束
{
struct Student *head;
struct Student *p1,*p2;
int n=0;
p1=p2=(struct Student *)malloc(LEN);
scanf("%d,%d",&p1->number,&p1->password);
head=NULL;
while(p1->number!=0)
{
n=n+1;
if(n==1)head=p1;
else p2->next=p1;
p2=p1;
p1=(struct Student *)malloc(LEN);
scanf("%d,%d",&p1->number,&p1->password);
}
p2->next=head;
return(head);
}

void Joseph(struct Student *head,int count) //游戏环节,按照约瑟夫环规则运行,并输出结果
{
int m;
struct Student *p;
p=head;

for(m=1;m<count-1;m++)
p=p->next;
printf("%d,%d/n",(p->next)->number,(p->next)->password);
count=p->next->password;
p->next=p->next->next;
do{
for(m=1;m<count;m++)
p=p->next;
printf("%d,%d/n",(p->next)->number,(p->next)->password);
count=p->next->password;
p->next=p->next->next;

}while(p!=p->next);

printf("%d,%d/n",p->number,p->password);
}

void main() //主函数,输入学生信息和上限值
{
struct Student *Head;
int num;
printf("请输入个人的序号和密码:/n");
Head=creat();
printf("请指定初始报数上限值:/n");
scanf("%d",&num);
Joseph(Head,num);
}
运行结果:

约瑟夫环问题的C语言算法实现


约瑟夫环问题的C语言算法实现

转载请注明:逗比根据地 » 约瑟夫环问题的C语言算法实现

喜欢 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址