回 帖 发 新 帖 刷新版面

主题:大家救命啊  一个约瑟夫环的问题  明天要考试用啊

我们数据结构明天要实验课答辩了  题目我还没有眉目呢  哪个大侠帮下忙哈  用单循环连表的   谢谢大家



约瑟夫环

【问题描述】

  约瑟夫环问题的一种描述是:编号为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个回复)

沙发

哎,别紧张,网上多的事,发个标准加注释的答案给你

/*约瑟夫环问题*/
/* 编号为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();                /*使运行时画面停留在结果处*/
}

板凳

谢谢了   我也急着要

我来回复

您尚未登录,请登录后再回复。点此登录或注册