约瑟夫环

华北电力大学

实 验 报 告

实验名称 约瑟夫环

课程名称 算法与数据结构

学生姓名： 号： 成 绩：

指导教师： 实验日期： | |

| |

专业班级： 学

（实验报告如打印，纸张用A4，左装订；页边距：上下2.5cm,左2.9cm, 右2.1cm；字体：宋体小四号，1.25倍行距。） 验证性、综合性实验报告应含的主要内容：

一、实验目的及要求 二、所用仪器、设备 三、实验原理 四、实验方法与步骤 五、实验结果与数据处理

六、讨论与结论（对实验现象、实验故障及处理方法、实验中存在的问题等进行分析和讨论，对实验的进一步想法或改进意见）七、所附实验输出的结果或数据

设计性实验报告应含的主要内容：

一、设计要求 二、选择的方案 三、所用仪器、设备 四、实验方法与步骤 五、实验结果与数据处理 六、结论（依据“设计要求”） 七、所附实验输出的结果或数据

* 封面左侧印痕处装订

华 北 电 力 大 学 实 验 报 告

一、 实验目的及要求 目的：针对约瑟夫（Josephus）问题，设计程序求出出列顺序。 要求：1. 利用单向循环链表存储结构模拟此过程。 2. 利用顺序结构模拟此过程。 问题描述：约瑟夫（Josephus）环问题是指：编号为1、2、…、n的n个人按顺时针方向围坐一圈，每人有一个正整数编号。从某个位置上的人开始报数，数到m的人便出列；下一个人（第m+1个人）又从1数起，数到m的人便是第2个出列的人；一次重复下去，直到最后一个人出列，于是得到一个新的次序，求出出列顺序。 二、 选择的方案 1. 利用单向循环链表存储结构模拟此过程。 2. 利用顺序结构模拟此过程。 三、 所用仪器、设备 计算机、Visual C++ 6.0 四、 实验的代码： 1、利用单向循环链表存储结构模拟此过程。代码如下： #include typedef struct ListNode { int num; struct ListNode *next; }*Pointer; ListNode *CreateLinklist(int num[],int n) { int i; Pointer head = new ListNode; head->num = num[0]; head->next = head; Pointer r = head;

3 / 7

华 北 电 力 大 学 实 验 报 告

for(i=1;inext; Pointer s = new ListNode; s->num = num[i]; s->next = head; r->next = s; r = s; static int l = 0; while(l4 / 7

Pointer p = new ListNode; p->next = h; h = p; p = h->next; for(i=1;inum; p = p->next; h = h->next; 华 北 电 力 大 学 实 验 报 告

} for(k=0;knext = p->next; h = h->next; delete p; cout<>n; cout<<\"输入出列序号 m = \"; cin>>m; cout<<\"输入起数位置 s = \"; cin>>s; int *num= new int [n]; for(i=0;i void Josephus_Linearlist(int data[],int n,int m,int s) {

5 / 7

华 北 电 力 大 学 实 验 报 告

int i=s-1,j=0; static int k=0,l=1; while(k>n; cout<<\"输入出列序号 m = \"; cin>>m; cout<<\"输入起数位置 s = \"; cin>>s; int i;

6 / 7

if(l==m) { } i++; l++; if(i==n) i = k; int temp = data[i]; for(j=i;j>k;j--) data[j] = data[j-1]; data[k] = temp; k++; l = 0; 华 北 电 力 大 学 实 验 报 告

int *data= new int [n]; for(i=0;i7 / 7