出圈问题实验报告.pdfVIP

实验报告

——约瑟夫出圈问题

一、问题描述

1、题目内容

约瑟夫(Joseph)问题的一种描述是:编号为1,2,...,n的n个人按顺时针

方向围坐一圈,每人持有一个(正整数)。一开始选任一个正整数作为报数上

限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将它的作为新的m值。试设计一个程序求出出列顺序。

2、基本要求

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

3、测试数据

m的初值为20；n=7，7个人的依次为：3，1，7，2，4，8，4（正确的

出列顺序应为6，1，4，7，2，3，5）。

二、需求分析

1.程序所能达到的基本功能

可以对任意人数、任意、任意出圈值输出它的出圈顺序

2.输入的形式和输入值的范围

输入形式及范围：（1）、先经提醒“n”时，输入人数n；

n＞0且n为整数；

（2）、经提醒“上限人数m”时，输入出圈上限m；

m0且m为整数；

（3）、经提醒“thesecretnumberofdis”时，输入第d个人的；

d0且d为整数；

3.输出的形式

基本如下：

“

出圈的顺序依次为：←

N1＿N2＿……＿Nn←（“＿”表示空格“←”表示回车，以下皆同）

”

4.测试数据的要求

（1）、输入要求数据，输出要求结果；

（2）、输入特殊数据，输出预计结果；

ⅰ、若输入n≤0，则输出“nmustbeapositiveinteger.←”

ⅱ、若输入n=1，则输出“只有1.←”

ⅲ、若输入m≤0,则输出“mmustbeapositiveinteger.←”

ⅳ、若输入人的中有≤0，则输出“thesecretmustbeapositiveinteger.←”

（3）、测试数据最好为5—10个，及m尽量是较小的自然数，便于计算，判断正

误，计算机也不会花费较长时间。

三、概要设计

1.所需的ADT，他们的作用

ADTLinkList{

数据对象：D={aiai∈ElemType,i=1,2,…,n,n≥0}

数据关系：R1{a,aa,a∈D,aa,i=2,…,n}

i−1ii−1ii−1i

基本操作：

InitList(L)

操作结果：构造一个空的有序表L。

ListLength(L)

初始条件：链表L存在；