约瑟夫问题

一问题描述

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个模块：

主程序模块；

创建循环链表模块；

找节点模块；

删节点模块；

各模块调用关系如下图所示：

4 约舍夫问题的伪码算法

void main( )

{

输入参与的人数；

输入第一个密码；

创建无头节点的循环链表；

输出第一个出列元素；

输出剩余出列元素；

}

四详细设计

1 实现概要设计的数据类型

typedef struct LNode

{int data;int num;struct LNode *next;}LNode,*linklist; //无头节点的循环链表的节点类型

2 每个子函数的算法

linklist creat(int n)

{/*构造一个长度为n的无头节点的循环链表,并返回指向最后一个节

点的指针*/

linklist head,s; //head为头节点标记s为链表中节点

int i;

s=head=(linklist)malloc(sizeof(LNode)); //创建头节点

for(i=1;i

{s->data=i;

printf("num%d: ",i);

scanf("%d",&(s->num));/*输入第i个人的密码*/

while(s->num<=0)

{/*如果输入的s->num小于等于0,要求重新输入*/ printf("请重新输入\nnum%d: ",i);

scanf("%d",&s->num);

}

s->next=(linklist)malloc(sizeof(LNode)); //开辟下一个节点s=s->next;

}

s->data=i;

printf("num%d: ",i);

scanf("%d",&(s->num));

s->next=head;

return(s);

}

linklist find(int m,linklist s) //找到当前元素后面第m个元素{

int i;

for(i=0;i

s=s->next;

return(s); //返回找到元素的指针

}

void print(into &mint &n,linklist &s)

{

linklist p;

s=find(m,s); //找到待删除的元素

printf("%d ",s->next->data);/*输出找到的元素*/

m=s->next->num;/*将此元素从链表中删除,并释放此节点*/ p=s->next;

s->next=s->next->next;

free(p);

--n; //约舍夫环中节点数少一

}

3 主程序算法

void main( )

{/*解决约舍夫问题的主函数*/

int n,m; //n为约舍夫环内初始人数m为初始密码

printf("type in n :");

scanf("%d",&n);/*输入n*/

while(n<=0)

{/*如果输入的n小于等于0,要求重新输入*/

printf("please type n in again \ntype in n :");

scanf("%d",&n);

}

printf("type in m :");

scanf("%d",&m);/*输入m*/

while(m<0)

{/*如果输入的m小于0,要求重新输入*/

printf("please type m in again \ntype in m :");

scanf("%d",&m);

}

linklist s;

s=creat(n);/*创建无头节点的循环链表,返回指向最后一个元素的指针*/

printf("the sequence is ");

print(m,n,s);//输出第一个出列的元素

while(n)

{

print(m,n,s);//输出剩余出列的元素

}

printf("\n");

}

4 函数调用关系图

五调试分析

调试过程中出现过如下问题：

1 开始编程序时没考虑输入错误的问题，导致输入错误后程序出错

2 编程序时删除节点子程序结束条件出错

3 对开辟的节点用完后没有释放

六使用说明

程序运行后按提示输入n和m的值，在输入约舍夫环中每个人的密

码，运行即可得到出列顺序

七测试结果

进入程序后要求输入n的值

然后输入m的值

再输入每个人的密码

最后得到出列顺序

八附录（源程序）

这里附上两种源程序，本质上相同，只是第一个程序按老师要求写为很多子函数形式，第二

个是我已开始编的，一个大函数。

程序一：

#include "stdio.h"

#include "stdlib.h"

typedef struct LNode

{int data;int num;struct LNode *next;}LNode,*linklist;

linklist creat(int n)

{/*构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针*/

linklist head,s;

int i;

s=head=(linklist)malloc(sizeof(LNode));

for(i=1;i

{s->data=i;

printf("num%d: ",i);

scanf("%d",&(s->num));/*输入第i个人的密码*/

while(s->num<=0)

{/*如果输入的s->num小于等于0,要求重新输入*/

printf("请重新输入\nnum%d: ",i);

scanf("%d",&s->num);

}

s->next=(linklist)malloc(sizeof(LNode));

s=s->next;

}

s->data=i;

printf("num%d: ",i);

scanf("%d",&(s->num));

s->next=head;

return(s);

}

linklist find(int m,linklist s) //找到当前元素后面第m个元素{

int i;

for(i=0;i

s=s->next;

return(s);

}

void print(int &m,int &n,linklist &s)

{

linklist p;

s=find(m,s);

printf("%d ",s->next->data);/*输出找到的元素*/

m=s->next->num;/*将此元素从链表中删除,并释放此节点*/ p=s->next;

s->next=s->next->next;

free(p);

--n;

}

void main()

{/*解决约舍夫问题的主函数*/

int n,m;

printf("type in n :");

scanf("%d",&n);/*输入n*/

while(n<=0)

{/*如果输入的n小于等于0,要求重新输入*/

printf("please type n in again \ntype in n :");

scanf("%d",&n);

}

printf("type in m :");

scanf("%d",&m);/*输入m*/

while(m<0)

{/*如果输入的m小于0,要求重新输入*/

printf("please type m in again \ntype in m :");

scanf("%d",&m);

}

linklist s;

s=creat(n);/*创建无头节点的循环链表,返回指向最后一个元素的指针*/

printf("the sequence is ");

print(m,n,s);//输出第一个出列的元素

while(n)

{

print(m,n,s);//输出剩余出列的元素

}

printf("\n");

}

程序二

#include "stdio.h"

#include "stdlib.h"

typedef struct LNode

{int data;int num;struct LNode *next;}LNode,*linklist;

linklist creat(int n)

{/*构造一个长度为n的无头节点的循环链表,并返回指向最后一个节

点的指针*/

linklist head,s;

int i;

s=head=(linklist)malloc(sizeof(LNode));

for(i=1;i

{s->data=i;

printf("num%d: ",i);

scanf("%d",&(s->num));/*输入第i个人的密码*/ while(s->num<=0)

{/*如果输入的s->num小于等于0,要求重新输入*/ printf("请重新输入\nnum%d: ",i);

scanf("%d",&s->num);

}

s->next=(linklist)malloc(sizeof(LNode));

s=s->next;

}

s->data=i;

printf("num%d: ",i);

scanf("%d",&(s->num));

s->next=head;

return(s);

}

void main()

{/*解决约舍夫问题的主函数*/

int n,m;

printf("type in n :");

scanf("%d",&n);/*输入n*/

while(n<=0)

{/*如果输入的n小于等于0,要求重新输入*/

printf("please type n in again \ntype in n :");

scanf("%d",&n);

}

printf("type in m :");

scanf("%d",&m);/*输入m*/

while(m<0)

{/*如果输入的m小于0,要求重新输入*/

printf("please type m in again \ntype in m :");

scanf("%d",&m);

}

linklist s,p;

s=creat(n);/*创建无头节点的循环链表,返回指向最后一个元素的指针*/

printf("the sequence is ");

int i;

for(i=0;inext;

printf("%d ",s->next->data);

m=s->next->num;/*将此元素从链表中删除,并释放此节点*/ p=s->next;

s->next=s->next->next;

free(p);

--n;

while(n)

{for(i=0;inext;

printf("%d ",s->next->data);

m=s->next->num;/*将此元素从链表中删除,并释放此节点*/ p=s->next;

s->next=s->next->next;

free(p);

--n;

}

printf("\n");

}

线性表的顺序存储及解决约瑟夫问题

线性表的顺序存储 一、实验目的 1.掌握线性表的顺序存储结构。 2.能熟练地利用顺序存储结构实现线性表的基本操作。 3.能熟练地掌握顺序存储结构中算法的实现。 二、实验内容 1.建立含有若干个元素的顺序表，并将结果在屏幕上输出。 2.对刚建立的顺序表实现插入、删除、修改、查找，并将结果在屏幕上输出。 3.解决约瑟夫问题：假设有n个人按1、2、3、…、n的顺序围成一圈，现在，从第s 个人开始按1、2、3、…、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。试用顺序表解决这个问题。 三、算法描述 1.第1题、第2题的算法提示 对第1题，先定义顺序表的数据类型，然后以1～n的序号建立顺序表，将输出结果单独定义成一个函数，以便后面反复使用它。对第2题，为操作方便，将插入、删除、修改、查找等操作都定义成单独的子函数形式。为查看这些操作的效果，可以在调用前后分别输出表的结果。 2.第3题的算法提示 对于第3题，可以将n个人的编号存入一个一维数组中，表的长度就是人数n，因此，就可以用一维数组来代替顺序表。算法的思想是：先求出出圈人的编号，用一个临时单元保存它，然后从出圈人的后一个开始，直到最后一个，都按顺序向前移动一个位置，再将临时单元中的出圈人编号存入最后。当这个重复步骤完成后，数组中存放的是出圈人的逆序列。本题中，围圈的人数n、出圈的报数号m、开始报数的位置s在程序中预先给定为10、3、2。当然，也可以从键盘临时输入。 四、源程序 第1、2题的源程序及程序清单 #include using namespace std; const int MaxSize=100; class List{ public: List(){length=0;} // 建立一个空表 List(int a[], int n); //建立一个长度为n的顺序表 ~List(){} int Length(){return length;} //求线性表的长度

约瑟夫问题求解

约瑟夫问题求解 一、问题描述。 1、实验题目 约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n 的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，再从下个人开始新一轮报数，如此反复，直到剩下最后一人则为获胜者。试设计一个程序求出出列顺序。 2、实验要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3、测试数据 n=7，7 个人的密码依次为：3，1，7，2，4，8，4 。m的初值为20，则正确的出列顺序应为6，1，4，7，2，3，5。 4、输入输出 输入数据：建立输入处理输入数据，输入n输入以及每个人的密码；m的初值。输出形式：建立一个输出函数，输出正确的序列。 二、需求分析 1、本程序实现求解约瑟夫问题， 2、程序运行后，要求用户指定初始报数上限值，然后读取个人密码。 输入数据：建立输入处理输入数据，输入m的初值，n,输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的序列输出。 三、概要设计 定义的抽象数据类型： 栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai|ai∈ElemSet,i=1,2,...,n, n≥0,ElemSet为元素集合} 数据关系：R={|ai-1,ai ∈D,i=1,2,...,n} 基本操作： InitStack(&S); //构造空栈 DestroyStack(&S); //销毁栈 ClearStack(&S); //将栈置空 StackEmpty(S); //检查栈是否为空 StackLength(S); //返回栈中元素个数

约瑟夫森效应

约瑟夫森效应（超导隧道效应） 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个模块： 主程序模块； 创建循环链表模块； 找节点模块； 删节点模块； 各模块调用关系如下图所示：

约瑟夫环问题讲解

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;

约瑟夫环的代码及算法思想

约瑟夫环 约瑟夫环问题是指n个人围成一个圆圈，然后按照某种方式进行报数，比如我所写的是按照1,2,3的顺序报数，所有报3的人退出圈子，剩下的人继续按照1,2,3的顺序报数，直到只剩下一个人，求这个人在最初的圈子中是第几号。 源代码： #include #include #include #define LEN sizeof(ysf) typedef struct _ysf { int num; struct _ysf *next; }ysf;//定义结构体 ysf *addTile(ysf *head,int j) { ysf *p = (ysf *)malloc(LEN); ysf *pt; int i; pt = head; for(i = 1;i<=j;i++) { if(head == NULL) { p->num = i; head = p; pt = p; head->next = NULL; } else { p->num = i; pt->next = p; pt = p; p->next =NULL; } p = (ysf *)malloc(LEN); } pt->next = head; free(p); p = NULL;

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; }//主函数

约 瑟 夫 环 问 题 的 三 种 解 法 ( 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开始报数，不断重复，求最后幸存的人最

约瑟夫问题算法及数据结构课程设计报告

线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组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__':

约瑟夫问题及变种

“约瑟夫”问题及若干变种 例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

约瑟夫环问题

约瑟夫环问题 问题描述： 有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是右侧重新编号的)

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

《计算机软件技术基础》实验报告 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）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码

抽杀问题 约瑟夫问题

[阅读材料]世界名题与小升初之： 抽杀问题（約瑟夫问题） --马到成功老师 在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。 先给大家介绍这一问题的由来。 据说著名犹太历史学家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

约瑟夫环问题

一、实验题目： 约瑟夫环问题。 二、实验内容： 设编号为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

约瑟夫斯问题求解

实验一：约瑟夫斯问题求解 一、问题描述 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）创建循环链表的流程图

约瑟夫环问题源代码(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语言算法(循环链表)

算法：n个人围成一圈，每个人都有一个互不相同的密码，该密码是一个整数值，选择一个人作为起点，然后顺时针从1到k（k为起始点手中的密码值）数数。数到k的人退出圈子，然后从下一个人开始继续从1到j（j为刚退出圈子人的密码数）数数，数到j的人退出圈子。重复上述操作，直到最后一人 代码如下： # include # include //free(),malloc()所在库文件 # define n 9 //数字个数 # define overflow 0 //判断溢出情况 int keyw[n]={4,7,5,9,3,2,6,1,8}; //欲处理数的数组 typedef struct lnode //声明结构体，包括两个成员，一个是数值，另一个是指向下个结点的指针 { int keyword; struct lnode *next; }lnode,* linklist; void joseph(linklist p,int m,int x) //定义约瑟夫环函数：p为循环列表头结点，m 为初始值，x为数组长度 { linklist q; //声明变量 int i; if(x==0)return; q=p; m%=x; if(m==0)m=x; for(i=1;i<=m;i++) //找到下一个结点 { p=q; q=p->next; } p->next=q->next; i=q->keyword; printf("%5d",q->keyword); free(q); joseph(p,i,x-1); //递归调用 } int main() { int i,m; linklist lhead,p,q;

约 瑟 夫 环 问 题 的 三 种 解 法

约瑟夫环问题的简单解法（数学公式法） 关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达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)

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

实验报告 实验课名称：数据结构实验一 实验名称：约瑟夫环问题 时间 班级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++)