用顺序表解决约瑟夫环问题.

计算机科学与工程学院《算法与数据结构》试验报告[一]

专业班级试验地点

学生学号指导教师

学生姓名试验时间

试验项目算法与数据结构

试验类别基础性（）设计性（）综合性（√）其它（）

试验目的及要求（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。

成

绩评定表

类别评分标准分值得分合计

上机表现积极出勤、遵守纪律

主动完成设计任务

30分

程序与报告程序代码规范、功能正确

报告详实完整、体现收获

70分

备注：

评阅教师：

日期：年月日

试验内容

一、实验目的和要求

1、实验目的：

（1）掌握用VC++上机调试线性表的基本方法；

（2）掌握顺序表的存储结构以及基本运算的实现。

2、实验内容

约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针

方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的

下一个人开始重新从1报数，报到m时停止并且报m的人出列。如

此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，

对任意给定的m和n，求出出列编号序列。

3、实验要求：用顺序表实现。

二、设计分析

根据实验要求，采用顺序表来完成本次实验。

实验中采用一维数组屁【】，先将n个人的编号存入到p[0]p[n-1]。从编号为1的人 (下标t=0)开始循环报数，数到m的人(下标t=(t+m-1)%i)p[t]，输出并将其从数组中删除（即将后面的元素前移一个位置），每次报数的起始位置就是上次报数的出列位置。反复执行直到出列n个人为止。

三、源程序代码

#include

#include

#include

#define MaxSize 100

typedef struct List

{

int data[MaxSize];

int length;

}*Sqlist;

void InitList(Sqlist &L)

{

L=(Sqlist)malloc(sizeof(Sqlist));

L->length=0;

}

void CreateList(Sqlist &L)

{

int n;

printf("您想输入的人数为:");

scanf("%d",&n);

printf("最初的顺序表为:\n");

for(int i=0;i

{

L->data[i]=i+1;

printf("%d ",L->data[i]);

L->length=n;

}

printf("\n");

}

void josephus(Sqlist &L,int m) {

int i,j,t;

t=0;

printf("最后的顺序表为:");

for(i=L->length;i>=1;i--)

{

t=(t+m-1)%i;

printf("%d ",L->data[t]);

for(j=t+1;j<=i-1;j++)

L->data[j-1]=L->data[j];

}

printf("\n");

}

void main()

{

int tt;

Sqlist L;

InitList( L);

CreateList(L);

printf("您想出列的序号为:");

scanf("%d",&tt);

josephus(L,tt);

}

四、测试用例（尽量覆盖所有分支）

1.当n>m且n%m!=0时，即当n不是m的倍数时：

n=12，m=5时约瑟夫环的实验结果为

2.当n>m且n%m=0时，即当n是m的倍数时：

n=15，m=5时约瑟夫环的实验结果为

3. 当n

n=4，m=12时约瑟夫环的实验结果为

4.当n

n=3，m=7时约瑟夫环的实验结果为

5．当n或m任一个足够大时

n=150，m=7时约瑟夫环的实验结果为

五、实验总结

约瑟夫问题数据结构实验报告汇总.

中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 2012 学年至2013 学年度第1 学期

一、实验目的 （1）掌握线性表表示和实现； （2）学会定义抽象数据类型； （3）学会分析问题，设计适当的解决方案； 二、实验内容 【问题描述】：编号为1,2,…,n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】：m 的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 三、实验步骤 （一）需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下：

约瑟夫环实验报告

一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={ | ai-1, ai ∈D , i=2,……n} 基本操作： LinkList EvaluList(int n);//对单向循环链表进行尾插入赋值 int size(LinkList L);//求链表的节点个数 Status ScanList(LinkList L);//遍历单向循环链表 Status Joseph(LinkList &L,int m);//约瑟夫环的实现 } 此抽象数据类型中的一些常量如下：#define TRUE 1 #define FALSE 0 #define OK 1

约瑟夫环实验报告

课程实验报告 题目：2016.4.6 学生姓名：黄玲 学生学号：201408070105 专业班级：智能1401 指导老师：骆嘉伟 完成日期：2016.4.6

一．需求分析 1.本实验基本要求是用数组来实现线性表，再基于线性表的基本操作（插入、删除、修改等）来实现约瑟夫问题 2.由键盘输入总人数n和出列报数m 3.在DOS界面上显示依次出圈的人的编号和最后一个留下的人,在当前文件夹里生成一个文本文件，里面是相同的输出。 4.测试数据： 输入： 10，3 输出： 3 6 9 2 7 1 8 5 10 4//DOS 3 6 9 2 7 1 8 5 10 4//TXT 二．概要设计 §抽象数据类型 为实现上述程序的逻辑功能，应以整数存储用户的输入 用线性表实现，线性表定义如下： ADT LISt 数据对象：整数 基本操作： AList(100);//构建一个最大人数为100的顺序表（数组）来存储人 Next();//指向下一个人 moveStart();//回到第一个人继续数数 Length();//查看圈里还剩多少人 currPos();//查看当前数到人的编号 getValue();//查看当前编号的人是否还在圈内 §程序的流程 以书上的代码案例为参考，编写线性表的ADT在继承线性表的基础上编写顺序表（数组）的类文件编写主函数，创建类的对象，完成程序 三．详细设计 §物理数据类型 将大小为n的数组赋好值，其值为他本身的编号，即数组下标。 §程序思路的具体步骤实现 设一个标志点，在数组中移动，同时报数，当报到m时，当前人的值变为0，出圈，然后继续移动，重新数。当数到值为0的人时自动跳过（已出圈），当数

约瑟夫环课程设计实验报告

《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日

目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列

3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果：

约瑟夫环问题讲解

2009年02月24日星期二下午 05:03 问题描述:约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M 的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。#include #include using namespace std; //结点中数据域的类型定义 typedef struct { int number;//标号 int chipher;//手中的值 }DataType; //带头结点的单循环链表 typedef struct node { DataType data; struct node *next; }Scnode; //初始化 void MyInit(Scnode **head)//指向指针的指针。 { if((*head=(Scnode *)malloc(sizeof(Scnode)))==NULL) exit(1);//动态分配 (*head)->next=*head; } //插入 int MyInsert(Scnode *head,int i,DataType x) { Scnode *p,*q; int j; p=head->next;j=1; while(p->next!=head&&jnext; j++; }

if(j!=i-1&&i!=1) {cout<<"erro!!!!!!!!!"; return 0;} if((q=(Scnode *)malloc(sizeof(Scnode)))==NULL) exit(1); q->data=x; q->next=p->next; p->next=q; return 1; } //删除 int MyDelete(Scnode *head,int i,DataType *x) { Scnode *p,*q; int j; p=head;j=1; while(p->next!=head&&jnext; j++; } if(j!=i-1) {cout<<"erro!!!!!!!!!"; return 0;} q=p->next; *x=q->data; p->next=p->next->next; free(q); return 1; } //取数据元素 int MyGet(Scnode *head,int i,DataType *x) { Scnode *p; int j; p=head;j=0;

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

《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期：

一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n--

四、源程序代码 //Joseph问题求解算法的设计与实现 #include #include struct list { int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数 . list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { key=rand() % 100; printf("第%d个人的密码:%d\n",i,key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; do{ printf("\n第%d号成员的密码为:%d",p->num,p->code); //输出链表. p=p->next; }while(p!=head); printf("\n\n输入第一个报的数:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do

约 瑟 夫 环 问 题 的 三 种 解 法 ( 2 0 2 0 )

约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 ? 以上来自百度百科约瑟夫【导师实操追-女视频】问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者【Ｑ】，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5【１】，4，6，2，3，1。 约瑟夫【０】问题其实并不难，但求解的方法多种多样；题目的

变化形式【⒈】也很多。接下来我们来对约瑟夫问题进行讨论。 1.模拟【б】解法优点 : 思维简单。?缺点：时间复杂度高达O(m*【9】n) 当n和m的值较大时，无法短时间内得到答案。 为了叙述【５】的方便我们将n个人编号为：1- n ，用一个数组vis【２】来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人【６】数? cnt 代表当前报了数的人数用t来枚举每一个位置(当tn时 t=1将人首尾相连)? 那么我们不难得出核心代码如下：bool vis[1000]; --标记当前位置的人的存活状态 int t = 0; --模拟位置 int s = 0; --死亡人数 int cnt = 0; --计数器 if(t n) t = 1; if(!vis[t]) cnt++; --如果这里有人,计数器+1 if(cnt == m) --如果此时已经等于m,这这个人死去 cnt = 0; --计数器清零 s++; --死亡人数+1 vis[t] = 1 --标记这个位置的人已经死去 coutt" "; --输出这个位置的编号 }while(s != n); 接下来我们来看另一种更为高效快速的解法数学解法 我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最

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

基础成绩：82分《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现 专业：网络工程 班级：网络102 姓名：张晨曦 学号： 102534 完成日期：2012/6/20 一、试验内容

- 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 struct list {

- int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数. list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; //使指针指向头节点 printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("第%d个人的密码:\n",i); scanf("%d",&key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; printf("\n\n输入初始值:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do { j=1; p=head; while(jnext;//使P指向下一结点 j++; } //报数过程. i=p->num; key=p->code; printf("%d\n",i); s->next=p->next;

数据结构实验报告—约瑟夫问题求解

《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码

约 瑟 夫 环 问 题 的 三 种 解 法

约瑟夫环问题python解法 约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。 思路是：当k是1的时候，存活的是最后一个人，当k=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下： class Node(): def __init__(self,value,next=None): self.value=value self.next=next def createLink(n): return False if n==1: return Node(1) root=Node(1) tmp=root for i in range(2,n+1): tmp.next=Node(i) tmp=tmp.next

tmp.next=root return root def showLink(root): tmp=root while True: print(tmp.value) tmp=tmp.next if tmp==None or tmp==root: def josephus(n,k): if k==1: print('survive:',n) root=createLink(n) tmp=root while True: for i in range(k-2): tmp=tmp.next print('kill:',tmp.next.value) tmp.next=tmp.next.next tmp=tmp.next if tmp.next==tmp: print('survive:',tmp.value) if __name__=='__main__':

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

信息学院 数据结构实验报告 学号：姓名：班级 课程名称：数据结构实验名称：约瑟夫环 实验性质：①综合性实验√②设计性实验③验证性实验实验时间：2017.10 试验地点： 本实验所用设备：PC及VS2010 【数据结构】： typedef struct _RingNode { int pos; // 位置 struct _RingNode *next; }RingNode, *RingNodePtr; 【算法思想】： 以单链表实现约瑟夫环 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。（约瑟夫环问题Josephus）。以环状链表实现 【算法描述】： void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 }

void PrintRing(RingNodePtr pHead) { RingNodePtr pCurr; printf("%d", pHead->pos); pCurr = pHead->next; while(pCurr != NULL) { if(pCurr->pos == 1) break; printf("\n%d", pCurr->pos); pCurr = pCurr->next; } } void KickFromRing(RingNodePtr pHead, int m) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == m) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if (pPrev == pCurr) { // 最后一个 printf("\n%d", pCurr->pos); // 显示出圈循序 free(pCurr); break; } i++; } } int main()

约瑟夫环问题

约瑟夫环问题 问题描述： 有n个人围成一个环，然后给从某个人开始顺时针从1开始报数，每报到m时，将此人出环杀死(当然不杀死也可以啊)，然后从下一个人继续从1报数，直到最后只剩下一个人，求这个唯一剩下的存活的人是谁？ 分析： 首先，我们要标示这n个人，别小看这一步，其实蛮重要的。第一种标示方法是从0开始，将n个人标示为0~n-1，第二种方法是从1开始标示，将这n个人标示为1~n。当然会有人说了，那我从x(x>=2)开始，将此n个数标示为x~x+n-1，其实我们可以把这种情况都归到第二种从1开始标示的情况，为什么可以，我们稍后分析。 第一种情况从0开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m)%n (假设当前有n个人还活在环中)。 第二种情况从1开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m-1)%n+1，于是我们就可以回答上面的问题了，如果从x开始编号的话，下一个拖出去受死的人的编号就应该是：(k+m-x)%n+x了。 其实，上面的这两种情况是完全可以在合并的，编号只是一个识别，就像名字一样，叫什么都没关系，从某个人开始出环，不管他们怎么编号，n个人出环的先后顺序都是一样的，最后该哪个人活下来是确定的，不会因为编号而改变，所以不管从几开始编号，都可以归纳为从0开始编号，其他的编号就是一个从0编号情况的一个偏移而已，从x编号的情况就相当于从0开始编号的情况下每个人的编号都+x，大小先后顺序不变~ 于是，下面的讨论都是从0开始编号的~ 怎么解决这个问题呢？ 最简单的方法是模拟，模拟这个出环过程，可以使用链表也可以使用数组，时间复杂度都是O(n*m).当然，这种解法时间复杂度太高，不可取~ 我们有O(n)的算法~ 假设从编号为0的人开始报数，当然从编号为k的人开始报数的情况也是也可以解决的，只要稍微转化就可以，至于怎么解决？我们讲完从编号为0的人开始报数的情况就明白啦~ 我们从0编号开始报数，第一个出环的人m%n-1，剩下的n-1个人组成一个新的约瑟夫环，接下来从m%n开始报数，令k=m%n，新环表示为： k, k+1, k+2, ……n-1, 0, 1, 2, …..., k-2 我们对此环重新编号，根据上面的分析，编号并不会影响实际结果。 k → 0 k+1 → 1 k+2 → 2 ... k-2 → n-2 对应关系为：x’ = (x+k)%n (其中，x’是左侧的，x是右侧重新编号的)

约瑟夫环问题

一、实验题目： 约瑟夫环问题。 二、实验内容： 设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m 的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 实现：用一个不带头结点的单向循环链表表示上述约瑟夫环，结点结构可定义为： typedef struct node{ Array int pos;//位置 int code;//密码 struct node *next; }JosephNode,* JosephList;; 三、程序源代码： # include # include # define ERROR 0 # define OK 1 Typedef struct node{ int pos,code; struct node *next; }JosephNode,* JosephList; int InitList_Joseph(JosephList &h,int n) //初始Joseph环。//为什么就&h,而不是h?? { JosephNode *newp,*p; h=NULL; for(int i=1;i<=n;i++) { newp=(JosephList)malloc(sizeof(JosephNode)); if(!newp) return ERROR; newp->pos=i; printf("Please input the %dth one's code\n ",i); scanf("%d",&newp->code); if(h==NULL) {h=newp;p=newp;} else

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

韶关学院 学生实验报告册 实验课程名称：数据结构与算法 实验项目名称：实验二线性表及其应用 约瑟夫环 实验类型（打√）：（基础、综合、设计√） 院系：信息工程学院计算机系专业：***** 姓名：*** 学号：***** 指导老师：陈正铭 韶关学院教务处编制

一、实验预习报告内容

二、实验原始（数据）记录 实验时间：2007 年 4 月 4 日（星期三第7，8 节）实验同组人：

三、实验报告内容 2007年4 月5 日 注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。 2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。

【源程序】 #include "stdio.h" #include "conio.h" #include "stdlib.h" /* 设立无头结点的单循环链表*/ typedef struct LNode{ int id; /* 编号*/ int pw; /* 密码*/ struct LNode *next; }LNode,*LinkList; void main() { int m,n,pw,i=1,j=0; /* m为初始报数值，n 为参与人数，pw为密码临时保存变量，i、j 为循环变量*/ LinkList L,p,q; /* L为链表头指针，p、q为临时指针*/ printf("输入人数n(n>0):"); scanf("%d",&n); printf("输入第1 人密码:"); scanf("%d",&pw); L=(LinkList)malloc(sizeof(struct LNode)); L->id=i; L->pw=pw; L->next=L; /* 创建首结点*/ q=L; /* q指向尾结点*/ p=L; /* p指向待删除结点前驱*/ for(i=2;i<=n;i++) /* 依次输入第2……第n个参与者密码*/ { printf("输入第%d 人密码:",i); scanf("%d",&pw); p=(LinkList)malloc(sizeof(struct LNode)); p->id=i; p->pw=pw; /* 创建第i个参与者结点p */ q->next=p; /* 在尾结点q后插入新结点p */ q=p; /* 更新q指向新的尾结点p */ p->next=L; /* 新结点p的后继指针指向首结点*/ } printf("输入约瑟夫环的初始报数值m:"); scanf("%d",&m); printf("出列顺序为:"); for(i=1;i<=n;i++) /* n个参与者依次按规则出列*/ { for(j=1;jnext; /* p 指向待删除结点前驱*/ q=p->next; /* q指向待删除结点*/ p->next=q->next; /* 删除结点q */ printf("%d\t",q->id); /* 输出被删结点编号*/ m=q->pw; /* m更新为被删结点的密码值*/ free(q); /* 释放被删结点q */ } getch(); }

约瑟夫环问题源代码(C语言)

约瑟夫环问题如下：已知n 个人(n>=1)围桌一园桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m 的那个人出列。他的下一个人又从1开始报数，数到m 的那个人又出列。依此规则重复下去，直到所有人全部出列。求解最后一个出列的人的编号。 本次实验是以顺序表求解约瑟夫环问题，程序流程图及程序运行结果如下： 程序代码如下： #include #include #include using namespace std; struct Node //循环节点的定义 { int number; //编号 Node *next; }; Node *CreateList(Node *L,int &n,int &m); //建立约瑟夫环函数 void Joseph(Node *L,int n,int m); //输出每次出列号数函数 Node *DeleteList(Node **L,int i,Node *q); //寻找每次出列人的号数 int LengthList(Node *L); //计算环上所有人数函数 void main() //主函数 { system("color 75"); //设置颜色以美观 Node *L; L=NULL; //初始化尾指针 int n, m; cout<<"请输入人数N ："; cin>>n; //环的长度

if(n<1){cout<<"请输入正整数!";} //人数异常处理 else { cout<<"请输入所报数M："; cin>>m; if(m<1){cout<<"请输入正整数!";} //号数异常处理 else { L=CreateList(L,n,m); //重新给尾指针赋值 Joseph(L,n,m); } } system("pause"); } Node *CreateList(Node *L,int &n,int &m) //建立一个约瑟夫环（尾插法） { Node *q; for(int i=1;i<=n;i++) { Node *p; p=new Node; p->number=i; p->next=NULL; if(i==1) L=q=p; //工作指针的初始化 else { q->next=p; q=q->next; } } q->next=L; if(L!=NULL){return(L);} //返回尾指针 else cout<<"尾指针异常!"<>k; if(k<1||k>n){cout<<"请输入1-"<

C语言实现约瑟夫环

《约瑟夫环》实验报告 专业：网络工程班级 学号姓名 一、问题描述： 约瑟夫问题的一种描述是：编号为1，2，……，n点的n个人按顺时针方向围坐一个圈，每人持有一个密码。一开始选一个正整数作为报数上限值m，从第一个人开始从顺时针方向自1开始报数，报到m时停止。报到m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始从新从1报数，如此下去，直达所有人出列。 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。 测试数据：m的初始值为20；n=7，7个人的密码依次是3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序为6，1，4，7，2，3，5） 二、程序设计的基本思想，原理和算法描述： 采用结构体定义单链表，格式为：struct Lnode {int number; int password; struct Lnode*next; }Lnode,*p,*q,*head; 其中number是人的排列序号，password是各人所持有的密码值，next是节点指针。Lnode是节点变量，p、q是节点，head是头指针。 程序的代码：定义变量n，i,m,j 输入人的数量n If n<=0或n>30 重新输入n值 当0password 尾指针指向头指针，形成循环链表 输入初始报数上限值m 当1<=j<=n时 循环找出报m的节点p 输出报m节点的编号p->number 将p->password赋给m值 删除此节点 结束 三、源程序及注释： #include #include struct Lnode/*定义链表*/ {int number;

约瑟夫环问题 实验报告完整版

实验报告 实验课名称：数据结构实验一 实验名称：约瑟夫环问题 时间 班级000 学号000 姓名神刀公 子 1.问题描述 约瑟夫环问题 （1）问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 （2）基本要求 建立模型，确定存储结构。 对任意n个人，密码为m，实现约瑟夫环问题。 出圈的顺序可以依次输出，也可以用一个数组存储。 （3）思考： 采用顺序存储结构如何实现约瑟夫环问题？ 如果每个人持有的密码不同，应如何实现约瑟夫环问题？ 2.数据结构设计 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：struct Node { int data; //数据域 Node *next; //next指针指向下一个结点 }; 3.算法设计 问题要求建立模型，确定存储结构，之后对任意n个人，密码为m，实现约瑟夫环问题，出圈的顺序可以依次输出，也可以用一个数组存储。

设计流程图如图1.1所示。 开始 输出提示语 输入所需参数 创建链表，计算，得出结果 输出结果 结束 图1.1 设计流程图 （1）创建循环链表 由于内容的要求以及问题的方便，用循环链表作为本次实验的抽象数据类型。申请一个结点作为第一个结点，之后调用creat_list函数将后续结点一次插入链接，构造为循环链表。 NODE *link(int number) { NODE *head=NULL,*p=NULL,*q=NULL; int i=1; head=(struct node*)malloc(sizeof(struct node)); head->value=i; p=head; for(i=2; i<=number; i++)

约 瑟 夫 环 问 题 的 三 种 解 法

约瑟夫环问题的简单解法（数学公式法） 关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。 为了讨论方便，先把问题稍微改变一下，并不影响原意： 问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。 我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2并且从k开始报0。 现在我们把他们的编号做一下转换： k-2 – n-2 k-1 – n-1 解x’ —- 解为x 注意x’就是最终的解 变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，

相信大家都可以推出来：x’=(x+k)%n 如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况—- 这显然就是一个倒推问题！下面举例说明： 假设现在是6个人（编号从0到5）报数，报到（2-1）的退出，即 m=2。那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这5个人报数的问题，将序号做一下转换： 现在假设x为0,1,2,3,4的解，x’设为那么原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现，x与x’关系为x’=(x+m)%n，因此只要求出x，就可以求x’。x怎么求出呢？继续推导吧。0,1,2,3,4,，同样是第二个1出列，变为（2,3,4,0），转换下为 很简单，同样的道理，公式又出来了，x=(x”+m)%5，这里变成5了。即求n-1个人的问题就是找出n-2的人的解，n-2就是要找出n-3，等等 因此，就可以回去看上面的推导过程了。 好了，思路出来了，下面写递推公式： 令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n] 递推公式 f[i]=(f[i-1]+m)%i; (i1)

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

《数据结构》课程实验报告书 姓名：_____徐鑫_________ 学号：____2116110307____ 专业：____物联网工程____ 班级：_____1604________ 2017 年 10 月 15 日

一、实验目的 1．掌握线性表特性 2．熟练掌握线性表的基本操作 3. 利用线性表设计算法并实现 二、实验内容 1.解决约瑟夫环问题：已知n 个人（以编号1，2，3...n 分别表示）围坐在一张圆桌周围。从编号为k 的人开始报数，数到m 的那个人出列；他的下一个人又从1开始报数，数到m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 2.基本要求：1）根据题目要求设计解决约瑟夫环应用问题的数据结构。 2）要求采用C++编程语言实现设计的算法。 三、设计思路 1. 可将人的顺序简单编号，从1到n ； 构造一个循环链表，可以解决首位相连的问题； 将人的编号插入到结构体的 Data 域中； 遍历人的编号，输出参与的人的编号； 开始报数，从头报数，报到k 的人出局（删除此结点），并释放此结点。直到人数只有一个人时，退出循环，输出获胜的人。 2.存储结构设计 (循环结束条件) 3.算法的核心思想说明 确定需要删除的位置； 设置并删除该位置。

已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。 四、数据结构设计 1.类的声明和定义（要求给出完整的类声明和核心成员函数的定义） #ifndef Joseph_H #define Joseph_H #include using namespace std; struct Node//结点 { int data;//存储数据 Node *next;//下一个节点的地址 }; class CircularLinkList//单向循环链表类 { public: CircularLinkList()//构造函数 { first = new Node; first->data = NULL; first->next = first; } ~CircularLinkList() { delete first; }//析构函数 void CreateLinkList(int a[], int n); //创建单向循环链表 void PrintLinkList(); //遍历链表 void Joseph(int k,int n); //约瑟夫环实现 private: Node *first; }; #endif 2.算法实现 #include"Joseph.h" #include #include void CircularLinkList::CreateLinkList(int a[], int n) { Node *s, *r = first;//尾指针初始化 for (int i = 0;i < n;i++)//尾插法