数学与计算机学院约瑟夫环问题实验报告

年级 10级学号 2010434062 姓名       成绩          

专业电气信息（计算机类）实验地点主楼402  指导教师史青宣         

实验项目       约瑟夫环问题       实验日期2011年12月26日             

一、实验目的

本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。

二、实验问题描述

设编号为1，2，···，n的n个人围坐一圈，约定编号为k（1≤k≤n）的人从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

三、实验步骤

1、实验问题分析

①由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍要是围成一个圆圈，可以使用循环表；由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，应该选用效率较高的链表结构；为了程序指针每一次都指向一个具体的代表一个人的结点而不需要进行判断，链表不带表头结点。所以，对于所有人围成的圆圈所对对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动

可以采用数据类型定义：

Typedef struct node

{

 int number;

 struct node  *next;

}Lnode,*Linklist;

    ②为了记录退出的人的先后顺序，采用一个顺序表进行存储，程序结束后再输入依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如“int quite[N];”N为一个根据实际问题定义的一个足够大的整数。

2、功能（函数）设计

根据上述分析，该算法可以由3个功能函数实现。Main（）用做数据的输入和函数的调用，Init()做链表的初始化工作，使用Josephus()做删除结点和保存输出顺序的工作，OutRing()完成序列的输出工作。

1.建立单循环链表函数  LinkList InitRingList(int n)；                                          

2.产生Josephus顺序函数  void Josephus(LinkList L,int n,int k,int m,int quit[N])

3.输出顺序表void Print(int n,int quit[N])

四、实验结果（程序）及分析

1.实验的的源代码：

// 约瑟夫环问题.cpp : Defines the entry point for the console application.

//

//#include "stdafx.h"

#include"iostream.h"

#define N 34

typedef struct Node

{

   int data;

   struct Node *next;

}Lnode,*LinkList;

LinkList InitRingList(int n)   //尾插法建立单循环链表

{

   Lnode *L,*r,*s;

   L=new Lnode;    //不带头结点

   r=L;

   for(int i=1;i<n;i++)  

   {

          s=new Lnode;

          r->data=i;

          r->next=s;

          r=s;

   }

   r->data=n;

   r->next=L;  //链表首尾相连

   L=r;    //L指向循环链表的尾结点

   return L;

}

void Josephus(LinkList L,int n,int k,int m,int quit[N])

{

   int i,j;

   Lnode *p,*q;

   p=L;

   for(int r=1;r<m;r++)

                 p=p->next;

   for(i=0;i<n;i++)

   {    

          for(j=1;j<=k-1;j++)

                 p=p->next;

          q=p->next;

          p->next=q->next;

          quit[i]=q->data;

          delete q;

   }

}

void Print(int n,int quit[N])

{

   int i;

   for(i=0;i<n;i++)

          cout<<quit[i]<<" ";

   cout<<endl;

}

int main(int argc, char* argv[])

{

   LinkList L;

   int n;

   int k;

   int m;

   cout<<"请输入围坐一圈的人数n的值:"<<endl;

   cin>>n;

   L=InitRingList(n);

   int quit[N];

   cout<<"约定从编号为m的值开始数，请输入m的值:"<<endl;

    cin>>m;

   while(m>n||m<1)

   {

     cout<<"输入错误，请重新输入："<<endl;

    cin>>m;

   }

   cout<<"要求数到k的人出列，请输入k的值:"<<endl;

   cin>>k;

   cout<<"顺序为:";

    Josephus(L,n,k,m,quit);

   Print(n,quit);

   return 0;

}

2.测试数据

A．当n的初始值为7，k的值为5，m的值为1时，正确的出列顺序为：5、3、2、4、7、1、6，经程序运行测试，结果如下：

可知程序运行正确。

B．程序的容错性测试，当输入m的值不符合问题约定时，应有错误提示给用户，指导用户正确输入，并做出相应处理，保证程序运行。测试如下：

3.测试中出现的问题

A．在此次编写中一个for循环出现的位置发生了错误，但程序仍可运行，可是这样运行出来的数据的顺序会发生错误，解决此类问题的方法是多运行几次，而且应该有这样一个概念运行出来和调试没有错误不一定代表没有了错误。

 

第二篇：实验报告1—约瑟夫环

华北水利水电学院约瑟夫环 实验报告

2010～20##学年  第 一   学期     09  级  计算机科学与技术 专业

班级： 2009119   学号： 200911902 姓名： 万婷婷  

一、   实验目的

   要求设计一个程序模拟约瑟夫环问题过程，求出出列编号序列。

二、实验要求

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

2）建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

3）建立一个输出函数，将正确的输出序列

4）测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4

三、实验内容

基本算法以及分析：

本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下

typedef struct Node

        {

        int Index;                 在当前环中所处的位置，即编号

        int Password;              在当前环中的所带的密码

        struct Node *next;

        }JosephuNode;

程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个环上所带的密码。然后,利用单循环链表建立起约瑟夫环，p ->next = head->next;就是将最后一个结点的后继指向头结点的下一个结点， 然后主函数调用Josephu函数，并实现如下功能：

编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。

四、程序源代码

1．约瑟夫环问题

#include<iostream.h>

#include<malloc.h>

#include<stdio.h>

typedef struct LNode

{

       int M;//当前出局人的编号

       int Password;//当前出局人所带密码

       struct LNode *next;

}JosephuNode;

void Josephu(int n,int m)

{

       int i,j,password;

       JosephuNode *head,*p,*q,*L;

       head=p=(JosephuNode *)malloc(sizeof(JosephuNode));

      

       for(i=1;i<=n;i++)

       {

        q=(JosephuNode *)malloc(sizeof(JosephuNode));

        p->next=q;

              q->M=i;

              printf("请输入第%d号所带密码:",      i);

              scanf("%d",&password);

              q->Password=password;

              p=q;

             

       }

   p->next=head->next;

       free(head);

       L=q->next;

       printf("出列者的编号顺序是：");

   while(p!=L)

       {

           for(j=1;j<m;j++)

              {

              p=L;

              L=L->next;

              }

       p->next=L->next;

       printf("%d,",L->M);

       m=L->Password;

       free(L);

       L=p->next;

       }

       printf("%d \n", p->M);

       free(L);

      

}

void main()

{

       int n,m;

       printf(".............约瑟夫环问题..........\n");

       printf("输入的n和m值不小于1：\n");

       printf("请输入参加的人数n:");

       scanf("%d",&n);

       printf("请输入起始报数上限值m:");

       scanf("%d",&m);

       Josephu(n,m);

}

五、运行结果

六、小结（不少于100字）

     通过这次实验，使我更加知道自己的不足和需要加强的地方，指针仍然是自己需要去加强巩固的地方。每次看到自己写的程序和网上的比较发现自己需要完善程序，而不只是编出而已，必须让自己的程序运行结果一目了然。数据结构让我感觉很有意思，让我没有了学习c语言和c++的茫然和烦恼，实验也很贴近每章学习的内容，很有效的巩固了我们的知识。