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&&j { p=p->next; 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&&j { p=p->next; 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; while(p->next!=head&&j {p=p->next;j++;} if(j!=i) {cout<<"erro!!!!!!!!!"; return 0;} *x=p->data; return 1; } //判断是否为空 int MyNotEmpty(Scnode *head) { if(head->next==head) return 0; else return 1; } //删除P结点所指结点的下一个结点(也就是下面函数中的pre结点的下一个结点) void MyDelete(Scnode *p) { Scnode *q=p->next; p->next=p->next->next; free(q); } //关键的函数 void MyRing(Scnode *head,int m) { Scnode *pre,*curr; int i; pre=head; curr=head->next; while(MyNotEmpty(head)==1)//这个喜欢是外层的把人循环完 { for(int i=1;i pre=curr; curr=curr->next; if(curr==head)//防止curr结点指向head，为什么呢，因为curr=curr-next移动过程中是要计数的 { pre=curr; curr=curr->next; } } cout<<" "< m=curr->data.chipher;//这里重新赋值到新的密码m，注意此处的写法curr- >data.chipher curr=curr->next;//从下一个结点开始计数 if(curr==head) curr=curr->next;//问题同上。 MyDelete(pre);//删除被指定到的结点 } cout< } void main() { DataType test[7]={{1,3},{2,1},{3,7},{4,2},{5,4},{6,8},{7,4}}; int n=7,m=20,i; Scnode *head; MyInit(&head); for(i=1;i<=n;i++) MyInsert(head,i,test[i-1]); MyRing(head,m); } 数据结构：约瑟夫环问题的求解，链表数组，简单高效 2008-03-25 14:59 约瑟夫问题：12个人排成一圈，从1号报数，凡是数到5的人就走出队列(出局)，然后继续报数，求最后一个出局的人。 编号为1，2，......，n的n个人按照顺时针方向围坐一圈。从第一个人开始顺时针方向自1开始报数，报到m时停止报数。报m 的人出列，从他在顺时针方向的下一个人开始重新报数，如此下去，直到所有人全部出列为止。方法1: /** * 名称: * * 描述: * * Copyright: Copyright 2008 * 创建日期 Mar 25, 2008 * 作者 zhangtianshun * E-mail zhangts8888@https://www.doczj.com/doc/1d6507557.html, * 版本 1.0 */ public class JosephCircle { public JosephCircle() { // TODO Auto-generated constructor stub } public static int josephCircle(int totalNum, int perNum) { int count[] = new int[totalNum]; for (int i = 0; i < count.length; i++) { count[i] = i + 1; } int flag = 0; int k = 0, n = 0; while (flag != 11) { for (k = 0; k < count.length; k++) { if (count[k] != 0) { n++; if (n % perNum == 0) { count[k] = 0; flag++; } } } } for (k = 0; k < count.length; k++) { if (count[k] != 0) { n = count[k]; break; } } return n; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int total = 12; int per = 5; JosephCircle joseph = new JosephCircle(); int last = -1; last = joseph.josephCircle(total, per); System.out.println("最后出列人的编号是: " + last); } } 方法2： /** * 名称: * * 描述: * * Copyright: Copyright 2008 * 创建日期 Mar 25, 2008 * 作者 zhangtianshun * MSN zhangts8888@https://www.doczj.com/doc/1d6507557.html, * E-mail zhangts8888@https://www.doczj.com/doc/1d6507557.html, * 版本 1.0 */ public class Josephus { /** * 约瑟夫环的求解思路:最简单的方法是用循环链表实现. * 现在用数组实现链表的效果.数组下标+1为数字编号, * 数组的值为下一个数组的地址.这样实现了链表的效果. * 当报数count=step-1时,删除下一个节点,节点值赋为-1. * 以此循环,直到数组元素都值为-1,最后删除的即为结果. */ public Josephus() { super(); } /** * 约瑟夫问题的求解 * @param array 待处理的整形数组 * @param size 待处理的数组长度 * @param step 步长 * @return Int 最后出列人的编号. */ public int joseph(int array[],final int size,final int step) { int flag = -1; //初始化数组链表,数组元素的值为下一个节点下标//即为: 1->2->3......(size-1)->0 for(int i=0;i array[i] = i+1; array[size-1] = 0; /** * intRemain 当前剩下的有效节点 * intDeleted 最好删除的一个节点的下班 * intCurrent 当前数组元素的下标值 * intCount 计数器 */ int intRemain,intDeleted,intCurrent,intCount; intRemain = size; intDeleted = -1; intCurrent = 0; intCount = 0; do { //当前节点有效的标准是:不等于-1(flag) if(array[intCurrent] != flag) { intCount++; //删除一个节点 if(step - intCount == 1) { //删除后一个节点,主要是将当前节点的向量指向下一个节点的下一个节点intDeleted = array[intCurrent]; array[intCurrent] = array[intDeleted]; array[intDeleted] = -1; intRemain--; intCount = 0; } } //当删除最好一个节点元素后,intCurrent的值变为-1.这之后数组就不能再被访问了. intCurrent = array[intCurrent]; }while(intRemain !=0 ); return intDeleted +1 ; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub char num = '7'; System.out.println((int)num); int array[] = new int[12]; //人数 int size = 12; //出局的倍数 int step = 5; int last = -1; Josephus ysf = new Josephus(); last = ysf.joseph(array, size, step); System.out.println("最后出列人的编号是: "+last); 单循环链表解决约瑟夫环问题] 约瑟夫问题的：编号为1，2，....,N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值M，从第一个人开始按顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密 码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 解决思路还是很简单的，主要是要会熟练运用单循环链表的数据结构，通过 单循环链表模拟围坐的一圈人，然后根据相应的密码进行报数，然后删除相应的链表节点。下面是C代码： #include #include #define MAX_NODE_NUM 100 #define TRUE 1U #define FALSE 0U typedef struct NodeType { int id; int cipher; struct NodeType *next; } NodeType; /* 创建单向循环链表 */ static void CreaList(NodeType **, const int); /* 运行"约瑟夫环"问题 */ static void StatGame(NodeType **, int); /* 打印循环链表 */ static void PrntList(const NodeType *); /* 得到一个结点 */ static NodeType *GetNode(const int, const int); /* 测试链表是否为空, 空为TRUE，非空为FALSE */ static unsigned EmptyList(const NodeType *); int main(void) { int n, m; NodeType *pHead = NULL; while (1) { printf("请输入人数n（最多%d个）: ", MAX_NODE_NUM); scanf("%d", &n); printf("和初始密码m: "); scanf("%d", &m); if (n > MAX_NODE_NUM) { printf("人数太多，请重新输入！\n"); continue; } else break; } CreaList(&pHead, n); printf("\n------------ 循环链表原始打印 -------------\n"); PrntList(pHead); printf("\n-------------删除出队情况打印 -------------\n"); StatGame(&pHead, m); } static void CreaList(NodeType **ppHead, const int n) { int i, iCipher; NodeType *pNew, *pCur; for (i = 1; i <= n; i++) { printf("输入第%d个人的密码: ", i); scanf("%d", &iCipher); pNew = GetNode(i, iCipher); if (*ppHead == NULL) { *ppHead = pCur = pNew; pCur->next = *ppHead; } else { pNew->next = pCur->next; pCur->next = pNew; pCur = pNew; } } printf("完成单向循环链表的创建!\n"); } static void StatGame(NodeType **ppHead, int iCipher) { int iCounter, iFlag = 1; NodeType *pPrv, *pCur, *pDel; pPrv = pCur = *ppHead; /* 将pPrv初始为指向尾结点，为删除作好准备 */ while (pPrv->next != *ppHead) pPrv = pPrv->next; while (iFlag) { for (iCounter = 1; iCounter < iCipher; iCounter++) { pPrv = pCur; pCur = pCur->next; } if (pPrv == pCur) iFlag = 0; pDel = pCur; /* 删除pCur指向的结点，即有人出列 */ pPrv->next = pCur->next; pCur = pCur->next; iCipher = pDel->cipher; printf("第%d个人出列, 密码: %d\n", pDel->id, pDel->cipher); free(pDel); } *ppHead = NULL; getchar(); } static void PrntList(const NodeType *pHead) { const NodeType *pCur = pHead; if (EmptyList(pHead)) return; do { printf("第%d个人, 密码: %d\n", pCur->id, pCur->cipher); pCur = pCur->next; } while (pCur != pHead); getchar(); } static NodeType *GetNode(const int iId, const int iCipher) { NodeType *pNew; pNew = (NodeType *)malloc(sizeof(NodeType)); if(!pNew) { printf("Error, the memory is not enough!\n"); exit(-1); } pNew->id = iId; pNew->cipher = iCipher; pNew->next = NULL; return pNew; } static unsigned EmptyList(const NodeType *pHead) { if(!pHead) { printf("The list is empty!\n"); return TRUE; } return FALSE; } 原题： 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。（约瑟夫环问题 Josephus） 提示： 由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。 为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一 个整型一维数组。如：int quit[n];n为一个根据实际问题定义的一个足够大的整数。 代码： /******************************************************************** created: 2006/06/14 filename: C:\Documents and Settings\Administrator\桌面\tmpp\josephus.c file path: C:\Documents and Settings\Administrator\桌面\tmpp file base: josephus file ext: c author: A.TNG version: 0.0.1 purpose: 实现 Josephus 环问题 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值， 直至全部输出。写出C程序。（约瑟夫环问题 Josephus） ********************************************************************* / #include #include #include #include /* 结构体和函数声明 */ typedef struct _node_t { int n_num; struct _node_t *next; } node_t; node_t *node_t_create(int n); node_t *node_t_get(node_t **pn, int m); /* 功能函数实现 */ /* * name: node_t_create * params: * n [in] 输入要构造的链表的个数 * return: * 返回构造成功的环形单向链表指针 * notes: * 构造节点数量为 n 的环形单向链表 * * author: A.TNG 2006/06/14 17:56 */ node_t * node_t_create(int n) { node_t *p_ret = NULL; if (0 != n) { int n_idx = 1; node_t *p_node = NULL; /* 构造 n 个 node_t */ p_node = (node_t *) malloc(n * sizeof(node_t)); if (NULL == p_node) return NULL; else memset(p_node, 0, n * sizeof(node_t)); /* 内存空间申请成功 */ p_ret = p_node; for (; n_idx < n; n_idx++) { p_node->n_num = n_idx; p_node->next = p_node + 1; p_node = p_node->next; } p_node->n_num = n; p_node->next = p_ret; } return p_ret; } /* * name: main * params: * none * return: * int * notes: * main function * * author: A.TNG 2006/06/14 18:11 */ int main() { int n, m; node_t *p_list, *p_iter; n = 20; m = 6; /* 构造环形单向链表 */ p_list = node_t_create(n); /* Josephus 循环取数 */ p_iter = p_list; m %= n; while (p_iter != p_iter->next) { int i = 1; /* 取到第 m-1 个节点 */ for (; i < m - 1; i++) { p_iter = p_iter->next; } /* 输出第 m 个节点的值 */ printf("%d\n", p_iter->next->n_num); /* 从链表中删除第 m 个节点 */ p_iter->next = p_iter->next->next; p_iter = p_iter->next; } printf("%d\n", p_iter->n_num); /* 释放申请的空间 */ free(p_list); system("PAUSE"); } 代码一: #include int main() { const int n=10; int a[n],c=5; for(int i =0;i { static int j=-1; int t=0; while(t if(a[++j]%n!=n) t++; a[j%=n]=0; cout< } cout< return 0; 代码二: #include int main() { const int n=20; int a[n],c=3; for(int i=0;i { static int j=-1; int t=0; while(t if(a[(++j)%n]!=0) t++; a[j%=n]=0; cout< } cout< } #include void sort(int a[],int &n) { cout<<"请输入你要删除的编号:"; int m;cin>>m; while(n) { int t=m%n; if(t==0)t=n; cout< { int hold=a[0]; for(int j=0;j a[j]=a[j+1]; } a[n-1]=hold; i++; } n--; } cout< } void main() { int a[]={1,2,3,4,5,6,7,8,9,10}; int n=sizeof(a)/sizeof(*a); sort(a,n); } 代码三: #include using namespace std; int jsf[100]; int main() { int n,m,t,cl=0; //input--------- cin>>n; t=n; for(int i=0; i cin>>m; while(t) { for(int i=cl,j=0; ; i++) { if(jsf[i%n]) j++; if(m==j) { cl=i%n+1; cout< jsf[i%n]=0; break; } } t--; } return 0; } 代码四: int Josephus(int *Child,int n,int m) { int i=-1,j=0,k=1; while(1) { for(j=0;j { i=(i+1)%n; if(Child[i]!=-1) j++; } if(k==n) { cout< break; } cout< Child[i]=-1; k=k+1; } cout< return 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）掌握线性表的基本操作，如插入、删除、检索等在链式存储结构上的运算。 课程实验报告 题目：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 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值，从他在顺时针方向上的下一个人开始重新从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={ 线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移 约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 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,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; }//主函数 基础成绩：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 课程设计报告 课程名称：数据结构课程设计课程设计题目：约瑟夫环问题 姓名：余明旭 系：计算机科学与技术专业：计算机科学与技术年级：2010级 学号：100310236 指导教师：陈老师 职称：学生 一、需求分析 1、输入的形式和输入值的范围： 本程序中，输入报数上限值n，初始报数者s，初始报数者携带的密码m1，n-2个人携带的密码m（最后一人携带的密码没用），均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。 2、输出的形式： 从屏幕显示出列顺序。 3、程序所能够达到的功能： 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4、测试数据： 输入 8 1 4 4 4 4 4 4 4 输出 4 8 5 2 1 3 7 6 一、详细设计 以单向循环链表实现该结构： 1、抽象数据类型的定义为： struct LNode { ElemType data; LNode* next; }; 2、本程序包含以下模块： 主程序模块： Void main() { 初始化； 输入数据； 执行功能； 显示结果； } 各功能模块：实现单链表的各项功能。 Void fun() { } 3、各模块的调用关系： 三、调试分析 程序的编写和调试基本正常，遇到的问题主要是：指针的指向的边界问题，如何每次正确找到出列的人的位置。 解决方法： for(int j=1;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__': 信息学院 数据结构实验报告 学号：姓名：班级 课程名称：数据结构实验名称：约瑟夫环 实验性质：①综合性实验√②设计性实验③验证性实验实验时间：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() 武汉工业学院数学与计算机学院 数据结构课程设计 设计题目：约瑟夫环 专业大类计算机 班级计算机6班 学号 100702129 姓名王元 指导教师李禹生 2011年9月3 日 一．选题背景： 题目：约瑟夫环 问题描述： 编号为1,2，…..，n的n个人按顺时针方向围坐圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新重新从1报数，如此下去，直至所有人全部出列为止。 基本要求： ⑴建立模型，确定存储结构； ⑵对任意 n个人，密码为 m，实现约瑟夫环问题； ⑶出圈的顺序可以依次输出，也可以用一个数组存储。 设计指导思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。其次，建立一个不带头结点的循环链表并由头指针 first 指示。最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图 2-1 所示。 二．方案论证： 本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构体node，然后给他开辟一个储存空间；利用头指针head标记链表，利用尾指针向后移将建立的结点连接成我们需要的单循环链表， 过程如下： 约瑟夫问题中的人数个数即为链表的长度，链表中node->num 编号n，node->data为每个人的密码。建立单循环链表后，通过初始报数上限找到出列的结点，输出该结点的node->num值，将该结点中的data中数作为新密码开始下一个步的开始，将该结点从链表中删除，并释放该结点的空间。重复此过程，直到剩下最后一个结点，就直接将该结点中的num值输出，删除该结点，并释放该结点的空间。输出的num值即为约瑟夫中人的编号。 三．过程论述： typedef struct node { int data; int num; struct node *next; }listnode; 定义一个结构体用来储存学生的编号和所携带的密码 for(i=1;i<=n;i++) { printf("输入第%d号同学的密码:",i); scanf("%d",&j);//输入学生所带密码 p1->next=(listnode*)malloc(sizeof(listnode));//建立一个新的空间，并将它的地址赋给p1->next p1=p1->next; p1->data=j; p1->num=i;//对结点的num和data成员赋值 p1->next=head->next;//构成单循环链表 } 定义指针p1，然后建立一个新结点并将p1->next指向它的地址，然后将这个地址赋给p1，最后将head->next赋给p1->next,构成一个单循环链表，并不断在尾部插入新的结点，直至所有人都进入循环链表中，而且在循环的过程中给结点的num和data成员赋值 约瑟夫环问题 问题描述： 有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) 三、测试数据 (1) 四、算法思想 (2) 五、模块划分 (3) 六、数据结构 (4) 七、源程序 (4) 八、界面设计 (6) 九、运行与测试 (6) 十、总结 (8) 十一、思考与感悟 (9) 课程设计设计报告书 一、问题描述 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码（整数），留作其出圈后应报到后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 二、基本要求 (1)输入的形式和输入值的范围：输入的形式是以数字的形式输入，输入范围为-2147483648～2147483648 (2)输出的形式：字符串形式输出 (3)程序所能达到的功能：达到符合约瑟夫环要求的响应功能。 三、测试数据 进入程序，显示“1.开始游戏0.退出游戏”输入非0数进入游戏，输入0退出游戏。 进入游戏后显示“输入总人数”，输入大于0的整数；若输入错误，则光标处清空，重新输入。 后提示“输入开始人的序号”；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。 后提示“输入间隔数字”，范围是任意正整数；若输入错误，则光标处清空，重新输入。 按回车键，显示结果，并重新询问“1.开始游戏0.退出游戏”。 一、实验题目： 约瑟夫环问题。 二、实验内容： 设编号为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.目的 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 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 约瑟夫环原理演示图约瑟夫环(内含源代码)
约瑟夫环实验报告
约瑟夫环课程设计实验报告
约瑟夫环问题讲解
约瑟夫环实验报告
约瑟夫问题算法及数据结构课程设计报告
约 瑟 夫 环 问 题 的 三 种 解 法 ( 2 0 2 0 )
约瑟夫环的代码及算法思想
数据结构实验报告(约瑟夫环)
课程设计(约瑟夫环)[1]
约 瑟 夫 环 问 题 的 三 种 解 法
数据结构实验报告 约瑟夫环问题
数据结构约瑟夫环的课程设计报告
约瑟夫环问题
数据结构约瑟夫环课程设计报告书
约瑟夫环问题
数据结构实验报告(实验二 约瑟夫环)
数据结构实验约瑟夫环..
相关主题
文本预览