约瑟夫环问题即设有n个人坐成一个圈，从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人再次出列，如此循环，知道所有人都出列为止，最后按照出列顺序输出
约瑟夫环问题的三种方法，
利用数组问题解决：
#include
#include
#pragma warning (disable:4996)
int main(void)
{
printf("请输入总数：\n");
int m;
scanf("%d", &m);
printf("请输入间隔数：\n");
int n;
scanf("%d", &n);
int *a = (int *)malloc(sizeof(int)*m);
int count = 0;
for (int i = 0; i < m; i++)
{
a[i] = i + 1;
}
for (int k = 0; k < m; k++)
{
int l = 0;
while (l < n)
{
l++;
count++;
if (a[(count - 1) % m] == 0)//一旦这个这个数为0，l--，继续寻找
{
l--;
}
}
printf("%d-->", a[(count - 1) % m]);
a[(count - 1) % m] = 0;//每输出一个数，就进行清除，此处为假删除
}
}
用循环链表解决，建立一个循环链表，每删除一个数据，节点释放，此处为真删除
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "math.h"
#pragma warning (disable:4996)
#define LEN sizeof(struct linklist)
typedef struct linklist
{
int num;
struct linklist *next;
}list;
struct linklist * create_list(int n)// 建立一个存储n个数据的循环链表{
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "math.h"
#pragma warning (disable:4996)
#define LEN sizeof(struct linklist)
typedef struct linklist
{
int num;
struct linklist *next;
}list;
struct linklist * create_list(int n)// 建立一个存储n个数据的循环链表{
list *head;
list *p1, *p2; //首先建立循环链表
head = (struct linklist *)malloc(LEN);//头结点的创立
p2 = head;//将p2指针赋初值
p2->next = NULL;
p1 = NULL;
int i;
if (head == NULL)
{
printf("创建链表失败");
return NULL;
}
for (i = 0; i < n; i++) //创立一个n个数据的循环链表
{
p1 = (struct linklist *)malloc(LEN);
p1->num = i + 1;
p2->next = p1;
p2 = p1;
p1->next = NULL;
}
p1->next = head->next;// 将最后一个节点的数据指向第一个节点
return head;
}
void josephus(struct linklist *head, int n, int m) {
list *p1, *p2;
p1 = head->next;
p2 = NULL;
list *temp;
int i, j;
if (head == NULL)
{
printf("传输数据有误");
return;
}
for (i = 0; i < n; i++)
{
for (j = 1; j < m; j++)
{
p2 = p1;
p1 = p1->next;
}
printf("%d---->", p1->num);
temp = p1;
p2->next = temp->next;//删除这个节点
p1 = temp->next;
free(temp);
}
}
void main()
{
int n, m;
list *head;
printf("请输入多少人参与杀人游戏");
scanf("%d", &n);
printf("请输入每几个人死去一个");
scanf("%d", &m);
head = create_list(n);
josephus(head, n, m);
}
数学方法实现，最简单的方法当然是求出递推关系式，然后直接编程，非常容易。
#include
#pragma warning (disable:4996)
int main(void)
{
int n, m, i, s = 0;
printf("N M = ");
scanf("%d%d", &n, &m);
for (i = 2; i <= n; i++)
s = (s + m) % i;
printf("The winner is %d\n", s);
return 0;
}
/*这是一个递推关系式，最后一个人编号假设为X，如果从n-1个人中的编号可以求出n个，那么便可以依次类推。
假设第m个人被杀则
重新编号
m m+1 m+2 ......n-2 n-1 0 ...... m-2
0 1 2 ........n-2-m n-1-m n-1-m-2... n-2
X
假设幸存者在n-1队列中编号为X
那么可以知道在n编号中的X为X+m, 举例X=2，那么m+2为队列n中的编号
由于X+m可能会越界，所以（X+m）% n。
本例假设m 中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 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尾节点不用修改。 伪代码阐释如下： 约瑟夫森效应（超导隧道效应） 1962年，英国剑桥大学的研究生约瑟夫森从理论上预言：当两块超导体（S）之间用很薄 的氧化物绝缘层（I）隔开，形成S－I－S结构，将出现量子隧道效应．这种结构称为隧道结，即使在结的两端电压为0时，也可以存在超导电流．这种超导隧道效应现在称为约瑟夫森效应．1911年，荷兰莱顿大学的卡茂林·昂尼斯意外地发现，将汞冷却到-268.98°C时，汞的电阻突然消失；后来他又发现许多金属和合金都具有与上述汞相类似的低温下失去电阻的特性，由于它的特殊导电性能，卡茂林·昂尼斯称之为超导态。卡茂林由于他的这一发现获得了1913年诺贝尔奖。 这一发现引起了世界范围内的震动。在他之后，人们开始把处于超导状态的导体称之为“超导体”。超导体的直流电阻率在一定的低温下突然消失，被称作零电阻效应。导体没有了电阻，电流流经超导体时就不发生热损耗，电流可以毫无阻力地在导线中形成强大的电流，从而产生超强磁场。 1933年，荷兰的迈斯纳和奥森菲尔德共同发现了超导体的另一个极为重要的性质，当金属处在超导状态时，这一超导体内的磁感兴强度为零，却把原来存在于体内的磁场排挤出去。对单晶锡球进行实验发现：锡球过渡到超导态时，锡球周围的磁场突然发生变化，磁力线似乎一下子被排斥到超导体之外去了，人们将这种现象称之为“迈斯纳效应”。 后来人们还做过这样一个实验：在一个浅平的锡盘中，放入一个体积很小但磁性很强的永久磁体，然后把温度降低，使锡盘出现超导性，这时可以看到，小磁铁竟然离开锡盘表面，慢慢地飘起，悬浮不动。 迈斯纳效应有着重要的意义，它可以用来判别物质是否具有超性。 超导材料和超导技术有着广阔的应用前景。超导现象中的迈斯纳效应使人们可以到用此原理制造超导列车和超导船，由于这些交通工具将在悬浮无磨擦状态下运行，这将大大提高它们的速度和安静性，并有效减少机械磨损。利用超导悬浮可制造无磨损轴承，将轴承转速提高到每分钟10万转以上。超导列车已于70年代成功地进行了载人可行性试验，1987年开始，日本国开始试运行，但经常出现失效现象，出现这种现象可能是由于高速行驶产生的颠簸造成的。超导船已于1992年1月27日下水试航，目前尚未进入实用化阶段。利用超导材料制造交通工具在技术上还存在一定的障碍，但它势必会引发交通工具革命的一次浪潮。 超导材料的零电阻特性可以用来输电和制造大型磁体。超高压输电会有很大的损耗，而利用超导体则可最大限度地降低损耗，但由于临界温度较高的超导体还未进入实用阶段，从而限制了超导输电的采用。随着技术的发展，新超导材料的不断涌现，超导输电的希望能在不久的将来得以实现。 现有的高温超导体还处于必须用液态氮来冷却的状态，但它仍旧被认为是20世纪最伟大的发现之一。超导九十年 1911年卡茂林－昂尼斯意外地发现，将汞冷却到－268.98℃时，汞的电阻突然消失；后来他发现许多金属和合金都具有与上述汞相类似的低温下失去电阻的特性 1913年卡茂林－昂尼斯在诺贝尔领奖演说中指出：低温下金属电阻的消失“不是逐渐的，而是突然的”，水银在4．2K进入了一种新状态，由于它的特殊导电性能，可以称为超导态” 1932年霍尔姆和卡茂林－昂尼斯都在实验中发现，隔着极薄一层氧化物的两块处于超导状态的金属，没有外加电压时也有电流流过 1933年荷兰的迈斯纳和奥森菲尔德共同发现了超导体的一个极为重要的性质 1935年德国人伦敦兄弟提出了一个超导电性的电动力学理论 1950年美籍德国人弗茹里赫与美国伊利诺斯大学的巴丁经过复杂的研究和推论后，同时提出：超导电性是电子与晶格振动相互作用而产生的。他们都认为金属中的电子在点阵中被正离子所包围，正离子被电子吸引而影响到正离子振动，并吸引其它电子形成了超导电流。接着，美国伊利诺斯大学的巴丁、库柏和斯里弗提出超导电量子理论，他们认为：在超导态金属中电子以晶格波为媒介相互吸引而形成电子对，无数电子对相互重叠又常常互换搭配对象形成一个整体，电子对作为一个整体的流动产生了超导电流。由于拆开电子对需要一定能量，因此超导体中基态和激发态之间存在能量差，即能隙。这一重要的理论预言了电 一问题描述 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）。 二需求分析 程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列 三概要设计 利用单项循环链表存储结构模拟此过程 1 循环链表的抽象数据类型 循环链表是单链表的一种变化形式，把单链表的最后一个节点的next指针指向第一个节点，整个链表就形成了一个环。 2 循环链表的基本操作（仅列出用在本程序的） creat(n) 操作结果：构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针 find(m,s) 初始条件：循环链表存在 操作结果：找到当前元素（即s）后面第m个元素 print(&m,&n,&s) 初始条件：循环链表存在 操作结果：从s中删除约舍夫问题中下一个被删除的元素，并将此元素显示在屏幕上 3 本程序包括4个模块： 主程序模块； 创建循环链表模块； 找节点模块； 删节点模块； 各模块调用关系如下图所示： 一．需求分析 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={ 《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：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、测试结果： 约瑟夫环 约瑟夫环问题是指n个人围成一个圆圈，然后按照某种方式进行报数，比如我所写的是按照1,2,3的顺序报数，所有报3的人退出圈子，剩下的人继续按照1,2,3的顺序报数，直到只剩下一个人，求这个人在最初的圈子中是第几号。 源代码： #include return head; }//使用尾插生成一个长度为n的链表，链表节点中的数据域依次为1-n；ysf *dele(ysf *head) { ysf *pt = NULL; int count = 1; while (head->next != head) { count++;//标识 pt = head; head = head->next; if(count == 3)//寻找到报数为3的节点 { head = head->next; free(pt->next); pt->next = head; count = 1; } } head->next = NULL; return head; }//寻找到会报数为3的节点，将其删除 void showList(ysf *head) { ysf *p = head; while (p != NULL) { printf("最终剩下的是："); printf("%d\n",p->num); p = p->next; } }//展示最终剩下的那个节点 int main() { ysf *head = NULL; int i; printf("请输入一共几个数字："); scanf("%d",&i); head = addTile(head,i); head = dele(head); showList(head); return 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开始报数，不断重复，求最后幸存的人最 《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期： 一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n-- 四、源程序代码 //Joseph问题求解算法的设计与实现 #include 线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移 约瑟夫环问题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__': 《计算机软件技术基础》实验报告 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）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码 “约瑟夫”问题及若干变种 例1、约瑟夫问题(Josephus) [问题描述] M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N 报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。 M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。 例如，输入8 3，输出：7。 [问题分析1] 这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。 在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。 程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current 表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。参考程序如下： program josephus1a {模拟法，用数组下标表示猴子的编号} const maxm=10000; var m,n,count,current,out,i:integer; monkey:array [1..maxm] of integer; begin write('Input m,n:'); readln(m,n); for i:=1 to m do monkey[i]:=1; out:=0; count:=0; current:=0; while out [阅读材料]世界名题与小升初之： 抽杀问题（約瑟夫问题） --马到成功老师 在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。 先给大家介绍这一问题的由来。 据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特後，39 個犹太人与Josephus及他的朋友躲到一個洞中，39個犹太人決定宁愿死也不要被人抓到，于是決定了一个自杀方式，41個人排成一个圆圈，由第1個人开始报数，每报数到第3人该人就必須自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他將朋友与自己安排在第16個与第31個位置，于是逃过了这场死亡游戏。 解法 約瑟夫问题可用代数分析來求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆内圈是排列顺序，而外圈是自杀顺序，如下图所示： 使用程式来求解的话，只要将阵列当作环状来处理就可以了，在陈列中由计数1开始，每找到三个无资料区就填入一个计数，直接计数來求解的話，只要將阵列当作环状来处理就可以了，在阵列中由計数1开始，每找到三个无资料区就填入一个計数，直而計数达41为止，然后將阵列由索引1开始列出，就可以得知每个位置的自杀順序，这就是約瑟夫排列，41個人报数3的約瑟夫排列如下所示： 14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23 约瑟夫环问题 问题描述： 有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．实验题目：约瑟夫斯问题的一种描述是：编号为1，2，……n的n个人按顺时针方向围坐一圈，每人持有一个密码9(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按照顺时针方向自1开始报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。 2．基本要求：利用单向循环链表模拟此过程，按照出列的顺序印出各人编号。 3．测试数据：n=7,7个人的密码依次为3，1，7，2，4，8，4.m的初始值为6（正确的出列顺序应为6，1，4，7，2，3，5。 二、需求分析 1．程序所能达到的基本可能：本程序能够按出列顺序印出各人编号，程序运行后显示提示信息，提示用户输入人数n,初始报数值m，n个人的密码，程序需自动考虑重复的，用户输入完毕后，程序自动输出运算结果。 2．输入的形式及输入值范围：输入人数n,初始报数值m，n个人的密码，所有值均为正整数int型。 3．输出的形式：输出的是按出列顺序印出各人编号，为正整数int型。 4．测试数据要求：测试数据要求为int型 三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以单向循环链表有序链表表示集合 数据类型。 1. 单向循环链表抽象数据类型定义： typedef struct node { ElemType data; ElemType num; struct node *next; }SLNODE; 基本操作： struct node *create_sl(int n);//创建单向循环链表 2.主程序流程及其模块调用关系 1）创建循环链表的流程图 基础成绩：82分《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现 专业：网络工程 班级：网络102 姓名：张晨曦 学号： 102534 完成日期：2012/6/20 一、试验内容 约瑟夫（Joseph ）问题的一种描述是：编号为1，2，…，n 的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m ，从第一个人开始按顺时针方向自1开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 四、源程序代码 #include 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(j 《约瑟夫环》实验报告 专业：网络工程班级 学号姓名 一、问题描述： 约瑟夫问题的一种描述是：编号为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值 当0 算法：n个人围成一圈，每个人都有一个互不相同的密码，该密码是一个整数值，选择一个人作为起点，然后顺时针从1到k（k为起始点手中的密码值）数数。数到k的人退出圈子，然后从下一个人开始继续从1到j（j为刚退出圈子人的密码数）数数，数到j的人退出圈子。重复上述操作，直到最后一人 代码如下： # include 实验报告 实验课名称：数据结构实验一 实验名称：约瑟夫环问题 时间 班级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++)约瑟夫问题数据结构实验报告汇总.
约瑟夫森效应
约瑟夫问题
约瑟夫环实验报告
约瑟夫环课程设计实验报告
约瑟夫环的代码及算法思想
约 瑟 夫 环 问 题 的 三 种 解 法 ( 2 0 2 0 )
数据结构实验报告(约瑟夫环)
约瑟夫问题算法及数据结构课程设计报告
约 瑟 夫 环 问 题 的 三 种 解 法
数据结构实验报告—约瑟夫问题求解
约瑟夫问题及变种
抽杀问题 约瑟夫问题
约瑟夫环问题
约瑟夫斯问题求解
数据结构实验报告(约瑟夫环)
C语言实现约瑟夫环
约瑟夫问题的C语言算法(循环链表)
约瑟夫环问题 实验报告完整版
相关主题
文本预览