数据结构约瑟夫环实验报告

实验报告

课程名：数据结构（C语言版） 实验名：约瑟夫环 姓名： 班级： 学号：

撰写时间：2014.09.20

一 实验目的与要求

1. 熟悉并掌握VC++ 编程环境 2. 复习C 语言的基本知识

3. 理解数据结构与算法的含义及重要性 二 实验内容

问题描述: n个人围成一个圈, 给一个数k, 从位置1的人开始, 从1开始报数, 将报k的人处决, 然后从下一个人开始再次从1开始报数, 将报k的人处决, 直到只留下一个人为止, 将这个人释放, 请问, 当给定了n与k后, 你应该选择哪一个位置以便最终被释放.

编写程序解决这一问题. 三 实验结果与分析

#define N 50 /*** 根据题目情景，人不会太多，设定上限50人 ***/

#include void main() {

int n, k, i, j, l, sihuo, sheng = 0,bianhao[N]; /*n是总人数，k是自杀的人数到的数字，//bianhao[N]给每个人编号，i给成员编号*/ printf(\总人数:\ scanf(\

printf(\数到此数字被处决:\

scanf(\； //给每个人编号

for (i = 0; i <= N - 1; i++) {

bianhao[i] = 1; } j = -1;

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

for (l = 0; l

sihuo= 1; //用1和0代表死亡或者存活 while (sihuo) {

if (bianhao[j]==0) j++; if (j == n) j = 0;

if (bianhao[j] == 1) sihuo = 0; } }

bianhao[j] = 0; }

for (i = 0; i

if (bianhao[i] == 1) sheng = i; }

printf(\剩下的人编号: %d\\n\}

图1. 共5个人，处决报4的人

图2. 共4个人，处决报3的人

图3. 共6个人，处决报4的人

图4. 共7个人，处决报2的人

实验分析：如程序中所示