20151910042-刘鹏-C实验19-求解亚瑟夫问题1
需积分: 0 25 浏览量
2022-08-08
22:38:58
上传
评论
收藏 46KB DOCX 举报
1
云南大学数学与统计学实验教学中心
《高级语言程序设计》实验报告
课程名称：程序设计和算法语言
学期：2016~2017 学年上学期
成绩：
指导教师：赵越
学生姓名：刘鹏
学生学号：20151910042
实验名称：数组程序设计
实验编号：No.19
实验日期：2018 年 8 月 16 日
实验学时：2
学院：数学与统计学院
专业：信息与计算科学
年级：2015 级
一、 实验目的
1． 掌握数组的概念和使用方法。练习动态分配与释放数组空间的方法。
2． 体会模型设计在程序设计中的应用。
二、 实验环境
Windows10 Pro Workstation 17134.165；
Cygwin GCC 编译器。
三、 实验内
设有
n
个人围做在圆桌周围，从某个位置开始用自然数进行编号为
1, 2,⋯,n
。然后从编号为
k
的人从
1
开
始报数,数到
m
的人便出列；下一个人（第
m
+
1
个）又从容不迫开始报数，数到
m
的人便是第二个出列的人。
如此继续下去直到最后一个人出列为止。要求输出这个出列的顺序。
这个问题称为雅瑟夫问题。
具体要求如下:
（1）
n
，
m
，
k
由键盘输入，输入前要有提示。
（2）在输入
n
后，动态建立方法说明中所需要建立的数组空间；程序运行结束时释放该存储空间。
（3）在输出时，各编号之间用两个空格来分隔。
（4）分别用
n
=
8
，
m
=
4
，
k
=
1
以及
n
=
10
，
m
=
12
，
k
=
4
调试运行你的程序。
方法提示:
设以自然数
1, 2,⋯,n
为元素构成一个环形队列，并用一个长度为
n
+
1
的一维数组
a
存放各元素，即数组元
素
a
i
表示元素
i
的下一个元素。显然，在开始时，该数组的各元素如下：
a
i
=
i
+
1,
i
=
1, 2,
⋯
, n
―
1
a
i
=
1,
i
=
n
（为直观起见，其中数组元素
a
0
不用），随着报数的进行，不断地有元素从队列中出来，这个数组中的元素
值也在不断地变化，即当有元素出列后，某些元素
i
的下一个元素就不一定是
i
+
1
了。
一般来说，假设当前要出列的元素为
k
，它的前一个元素为
1
，则有
a
1
=
k
，且
k
的下个元素为
a
k
。即当前状
态为
⋯
,
1,
k
,
a
k
,
⋯
，当
k
出列以后，将变为
⋯,
1,
k
,
a
k
,
⋯
，此时
1
的下一个元素已不是
k
，而是原来
k
的下
评论0