主题:大家救命啊 一个约瑟夫环的问题 明天要考试用啊
风行水色
[专家分:0] 发布于 2006-06-16 18:41:00
我们数据结构明天要实验课答辩了 题目我还没有眉目呢 哪个大侠帮下忙哈 用单循环连表的 谢谢大家
约瑟夫环
【问题描述】
约瑟夫环问题的一种描述是:编号为1,2,...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1开始报数,如此下去,知道所有人全部出列为止。试设计一个程序求出出列顺序。
【基本要求】
利用单向循环链表存储结构模拟此过程,按照出列的顺序印出个人的编号。
【测试数据】
m的初值为20;n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6(正确地出列顺序为6,1,4,7,2,3,5)。
【实现提示】
程序运行后,首先要求用户指定初始报数上限值,然后读取个人的密码。可设n<=30,此题所用的循环链表中不需要“头结点”,请注意空表和非空表的界限。
【选作内容】
向上述程序中添加在顺序结构上实现的部分。
回复列表 (共2个回复)
沙发
hohohaha [专家分:580] 发布于 2006-06-16 22:06:00
哎,别紧张,网上多的事,发个标准加注释的答案给你
/*约瑟夫环问题*/
/* 编号为1.2.3...n的n(n>0)个人按顺时针方向围坐一圈,每人有一个整数密码,开始时*/
/*任选一个整数作为报数上限m,从第一个开始顺时针方向自一起顺序报数,报m的人出列*/
/*将他的密码作为新的m值,从他的下一个人开始重新报数。如此下去,直到所有人全部 */
/*列为止,令n最大为30,要求设计一个程序模拟此过程,并求出出列编号序列。 */
#include<stdlib.h> /*杂类声明*/
#include<stdio.h>
struct dnode{
int num, key;
struct dnode *prior,*next;
};
void main(){
int n,m,i,k;
struct dnode *head,*p,*s;
printf("________________________________________________________________________________");
printf("--------------------------------------------------------------------------------");
printf("\t\t\t The question of YSFH\n\n\n");
printf("Please input num of person and first password:");
scanf("%d,%d",&n,&m);
printf("\n");
while(n<0||m<0){ /*当人数小于零,或者初始密码小于零时报错,重新输入*/
printf("error!num,password should >0\n");
scanf("%d,%d",&n,&m);
}
s=(struct dnode*)malloc(sizeof(struct dnode));
for(i=1;i<=n;i++){
if(i==1)
head=s;
p=s; /*P指向新建的接点*/
p->num=i;
printf("Please input %d password:", i);
scanf("%d",&p->key);
printf("\n");
while(p->key<0){ /*当密码小于零时报错,重新输入*/
printf("error!password should >0\n");
scanf("%d",&p->key);
}
s=(struct dnode*)malloc(sizeof(struct dnode)); /*创建下一个结点,*/
/*连接在P后*/
p->next=s; /*创建下一个结点,连接在P后*/
s->prior=p;
}
p->next=head; /*所有结点创建完毕,把尾指针与头指针相连*/
head->prior=p;
free(s);
p=head;
printf("\n\nDequeue Sequence :\t");
for(i=1;i<=n;i++){
for(k=1;k<=m;k++) /*找到要删除结点的下一个结点,并保存要删除结点*/
p=p->next; /*中的密码,以作为下次循环的条件*/
m=p->prior->key;
printf(" --> %d",p->prior->num);
p->prior->prior->next=p; /*删除结点,作结点前后结点的连接*/
p->prior=p->prior->prior;
if(i%8==0)
printf("\n\t\t\t");
}
for(i=1;i<5;i++)
printf("\n");
printf("----------------------------------------------------------------------------[YM]");
printf("________________________________________________________________________________");
getch(); /*使运行时画面停留在结果处*/
}
板凳
weylen [专家分:30] 发布于 2006-06-20 17:02:00
谢谢了 我也急着要
我来回复