（一）基本问题
1.问题描述
设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。
2.数据结构设计
首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：
struct Node
{
int data;
Node *next;
};
其次，建立一个不带头结点的循环链表并由头指针first指示
3.算法设计
1、工作指针first，r，s，p，q初始化
2、输入人数（n）和报数（m）
3、循环n次，用尾插法创建链表
Node *q;
for(int i=1;i<=n;i++)
{
Node *p;
p=new Node;
p-> data =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);}
4、输入报数的起始人号数k;
5、Node *q = new Node;计数器初始化i=1;
6、循环n次删除结点并报出位置（其中第一个人后移k个）
当i 移动指针m-2次p=p->next; 删除p结点的后一结点q q=p->next; p->next=q->next; *L = p->next; 报出位置后Delete q; 计数器i++; 运行流程图 代码和相关解释 #include using namespace std; struct Node//循环节点的定义 { int data;//编号 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);//计算环上所有人数函数 开始 输入m 和n 创建链表 k>n-1 移动指针p 删除p 后一结点q 指针p 后移，k++ 输出n 结束 Y N void main()//主函数 //在主函数中，完成人数（n）和报数（m）的输入和工作指针的初始化{ 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->data=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<<"尾指针异常!"< } void Joseph(Node *L,int n,int m)//输出每次出列的人 { int k; cout<<"请输入第一个报数人："; cin>>k; if(k<1||k>n){cout<<"请输入1-"< { cout<<"\n出列顺序:\n"; for(int i=1;i { Node *q = new Node; if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数else q=DeleteList(&L,m,q); cout<<"号数："< delete q;//释放出列人的存储空间 } cout<<"最后一个出列号数是："< } Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人 { if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式 Node *p; p=*L; int j=0; while(j q = p->next; p->next=p->next->next; *L = p->next; return(q); } int LengthList(Node *L)//计算环上的人数 { if(L){cout<<"尾指针错误!"< else { int i=1; Node *p=L->next; while(p!=L) { i++; p=p->next; } return(i); } } 复杂度分析： 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; } 时间复杂度：O（n） if(i==1) i+=LengthList(*L); Node *p; p=*L; int j=0; while(j q = p->next; p->next=p->next->next; *L = p->next; return(q); 时间复杂度：O（n2） 算法的空间复杂度：O（n2） 4.界面设计 请输入报数人数n 请输入所报数M 请输入第一个报数人 —— 以下列出依次报数的结 果 5. 运行、测试与分析 (二)采用顺序存储结构如何实现约瑟夫环问题 代码和解释 #include #include #include #define MaxSize 50 typedef char ElemType; typedef struct Seqlist {//线性表顺序存储结构定义 ElemType *elem[MaxSize];//存放顺序表数据元素 int length;//当前长度 }*JSeqlist;//线性表存储结构类型名 JSeqlist Int_SeqList(void) {//顺序表初始化 JSeqlist L; L=(JSeqlist)malloc(sizeof(struct Seqlist)); if(L!=NULL) L->length=0; else printf("超出范围！！"); return L; } ElemType *Locate_SeqList(JSeqlist L,int p) {//查找线性表中下标为P的元素 if(p>=0&&L->length) return(L->elem[p]); else {printf("顺序表中不存在相关元素"); return NULL; } } int Insert_SeqList(JSeqlist L,int i,ElemType *x) {//在顺序表中指定元素前插入X int j; if(L->length==MaxSize)//L.length是最后一个元素的位置{printf("线性表已满，无法进行插入操作！！！！\n"); return 0; } if(i<0||i>L->length) {printf("插入位置不对，超出顺序表长度\n"); return 0; } if(i==0) {L->elem[i]=x; L->length=L->length+1; return 1; } for(j=L->length;j>=i;j--) {L->elem[j]=x;} L->length++; return 1; } int Delete_JSeqlist(JSeqlist L,int i) {//在顺序表中删除第i个元素 int j; if(i<0||i>L->length-1) { printf("删除位置不对，超出顺序表的长度啦\n"); return 0; } for(j=i;j L->elem[j]=L->elem[j+1]; L->length--; return 1; } void josephus(JSeqlist L,int start,int m) {//josephus问题求解的非常牛逼的函数 int s,i; ElemType *w; s=start-1; for(i=L->length;i>0;i--) { s=(s+m-1)%i; w=Locate_SeqList(L,s); printf("出列人员为：%s\n",w); Delete_JSeqlist(L,s); } } int main (void) { JSeqlist Josephus; int n,m,i,k,s; Josephus=Int_SeqList();//顺序表初始化 printf(" 约瑟夫环问题顺序表求解_愚人节特别版\n\n"); printf("请输入本问题中总人数m="); scanf("%d",&n); printf("请输入本问题开始人员的位置S="); scanf("%d",&s); printf("请输入本问题的计数值m="); scanf("%d",&m); printf("请输入本问题中这些人的名字\n"); for(i=0;i { printf("第%d位置的人员的名字为:",(i+1)); Josephus->elem[i]=(ElemType *)calloc(10,sizeof(char)); scanf("%s",Josephus->elem[i]); k=Insert_SeqList(Josephus,i,Josephus->elem[i]); if(k==0) exit(1); } josephus(Josephus,s,m); free(Josephus); getchar(); return 0; } 运行结果 (三)密码不同 #include struct CList { int password; int number; struct CList *next; }; typedef struct CList CNode; typedef CNode *CLink; CLink CreateList(int length) { CLink head; CLink before; CLink new_node; int i; head=new CNode; if(head==NULL) return NULL; cout << "Please Input Password 1 :" << endl; cin >> head->password; head->number=1; head->next=NULL; before=head; for(i=1;i { new_node=new CNode; if(new_node == NULL) return NULL; new_node->number = i+1; cout << "Please Input Password " << new_node->number << ":" < cin >> new_node->password; new_node->next = NULL; before->next=new_node; before=new_node; } new_node->next =head; return head; } int main() { CLink head; CLink ptr,back,last; int i,j,m,n; cout << "Please Input the Number of Persons: " << endl; cin >> n; cout << "Please Input the First Password M: " << endl; cin >> m; head=CreateList(n); ptr=head; for(i=0;i { for(j=0;j { back=ptr;//定位最后一个数的接点赋值给back ptr=back->next; } cout <<"第"< m=ptr->password; if(ptr==head) { last=head; while(last->next!=head) last=last->next; last->next=head->next; delete ptr; ptr=last->next; head=ptr; } else { back->next=ptr->next; delete ptr; ptr=back->next; } } return 0; } 运行结果 （三）心得体会： 1.编程是个很细致的工作，尤其是在写顺序表的时候，涉及的函数很多，函数名中最初为了看在清晰，涉及成单词首字母是大写的，但是后来在函数调用的时候，就忘记了最初命名的 时候是大写的了，导致编译的时候不能识别。 2.通过这个实验，理解了数据结构是数学在编程中的应用，是程序涉及和算法设计的基础，在计算机相关学科总占有举足轻重的地位 (一)基本问题 1?问题描述 设有编号为1,2,…小的n (n> 0)个人围成一个圈，每个人持有一个密码m。从第一个 人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m, 实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点 定义为如下结构类型： struct Node { int data; Node *n ext; }； 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 1、工作指针first, r, s, p, q初始化 2、输入人数（n）和报数（m） 3、循环n次，用尾插法创建链表 Node *q; for（i nt i=1;i<=n ;i++） { Node *p; p=new Node; p-> data =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);} 4、输入报数的起始人号数k; 5、Node *q = new Node; 计数器初始化i=1; 6、循环n 次删除结点并报出位置(其中第一个人后移当 k 个) i 课程实验报告 题目：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的人时自动跳过（已出圈），当数 数据结构课程设计实验 学校：江西农业大学 班级：软件1115班 姓名：朱利斌 学号：20111976 课程：数据结构课程设计 指导教师：彭玉莹 实验一：约瑟夫问题 问题简述： 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码Ki（整数），留作其出圈后应报到Ki 后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 一、题目内容及要求 【问题描述】 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 【要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 2）掌握线性表的基本操作，如插入、删除、检索等在链式存储结构上的运算。 2009年02月24日星期二下午 05:03 问题描述:约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M 的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。#include 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&&j 一问题描述 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={ 约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 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开始报数，不断重复，求最后幸存的人最 计算机科学与工程学院 《算法与数据结构》试验报告[一] 专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼 学生姓名肖宇博试验时间2012-2-29 试验项目算法与数据结构 试验类别基础性（）设计性（）综合性（√）其它（） 试验目的及要求（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个人的序号，另一个用来存储n个人的出队顺序及序号。 程序中充分考虑了如果出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示！否则继续出队！ 三、源程序代码 #include 基础成绩：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(j 约瑟夫环问题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__': 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 信息学院 数据结构实验报告 学号：姓名：班级 课程名称：数据结构实验名称：约瑟夫环 实验性质：①综合性实验√②设计性实验③验证性实验实验时间：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是右侧重新编号的) C语言课程设计报告约瑟夫环胡存夫 沈阳航空航天大学 课程设计报告 课程设计名称：C语言课程设计课程设计题目：约瑟夫环 院（系）：计算机学院 专业：计算机科学与技术班级：3410301 学号： 姓名：胡存夫 指导教师：丁一军 目录 1 课程设计介绍 ......................................................... 错误!未定义书签。 1.1课程设计内容及要求 ........................................... 错误!未定义书签。 1.2系统需求............................................................... 错误!未定义书签。 2 课程设计原理 ......................................................... 错误!未定义书签。 2.1课设题目粗略分析 ............................................... 错误!未定义书签。 2.2.1 功能模块图..................................................... 错误!未定义书签。 2.2.2 流程图分析..................................................... 错误!未定义书签。 3 调试与分析............................................................. 错误!未定义书签。 3.1调试过程............................................................... 错误!未定义书签。参考文献 .................................................................... 错误!未定义书签。附录（关键部分程序清单） ................................... 错误!未定义书签。 《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：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、测试结果： 一、实验题目： 约瑟夫环问题。 二、实验内容： 设编号为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 韶关学院 学生实验报告册 实验课程名称：数据结构与算法 实验项目名称：实验二线性表及其应用 约瑟夫环 实验类型（打√）：（基础、综合、设计√） 院系：信息工程学院计算机系专业：***** 姓名：*** 学号：***** 指导老师：陈正铭 韶关学院教务处编制 一、实验预习报告内容 二、实验原始（数据）记录 实验时间：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;j （一）基本问题 1.问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node { int data; Node *next; }; 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 1、工作指针first，r，s，p，q初始化 2、输入人数（n）和报数（m） 3、循环n次，用尾插法创建链表 Node *q; for(int i=1;i<=n;i++) { Node *p; p=new Node; p-> data =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);} 4、输入报数的起始人号数k; 5、Node *q = new Node;计数器初始化i=1; 6、循环n次删除结点并报出位置（其中第一个人后移k个） 当i 数据结构课程设计题目 1.目的 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 2.内容 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 约瑟夫环问题的描述是：设编号为1，2，…，n的n个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。 3.设计： 1）对设计内容进行分析 2）逻辑设计 1、循环链表抽象数据类型定义 typedef struct LNode//定义单循环链表中节点的结构 { int num;//编号 int pwd;//password struct LNode *next;//指向下一结点的指针 }LNode; 2、本程序包含一下几个模块 （1）构造结点模块 LNode *createNode(int m_num,int m_pwd) { 图2 约瑟夫环原理演示图 《计算机软件技术基础》实验报告 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）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码c语言实现约瑟夫环问题
约瑟夫环实验报告
约瑟夫环(内含源代码)
约瑟夫环问题讲解
约瑟夫问题
约瑟夫环实验报告
约 瑟 夫 环 问 题 的 三 种 解 法 ( 2 0 2 0 )
顺序表实现约瑟夫环的问题c语言
数据结构实验报告(约瑟夫环)
约 瑟 夫 环 问 题 的 三 种 解 法
数据结构经典题目及c语言代码
数据结构实验报告 约瑟夫环问题
约瑟夫环问题
C语言课程设计报告约瑟夫环胡存夫
约瑟夫环课程设计实验报告
约瑟夫环问题
数据结构实验报告(实验二 约瑟夫环)
c语言实现约瑟夫环问题
数据结构实验约瑟夫环..
数据结构实验报告—约瑟夫问题求解
相关主题
文本预览