为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

约瑟夫生死者游戏

2018-09-14 9页 doc 23KB 117阅读

用户头像

is_650122

暂无简介

举报
约瑟夫生死者游戏约瑟夫生死者游戏 黄淮学院 “数据结构”课程设计 报告 系 (院): 计算机科学系 设计题目: 专业班级: 小组成员: 指导教师: 完成时间: 2009~2010学年第二学期 [问题描述] 约瑟夫(Joeph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列...
约瑟夫生死者游戏
约瑟夫生死者游戏 黄淮学院 “数据结构”课程设计 系 (院): 计算机科学系 设计题目: 专业班级: 小组成员: 指导教师: 完成时间: 2009~2010学年第二学期 [问题描述] 约瑟夫(Joeph)问题的一种描述是:编号为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)。 [实现提示] 程序运行后首先要求用户指定初始报数上限值,然后读取各人的密码。设n?30。 一、需求分析 二、概要设计 本程序中用到的所有抽象数据类型的定义、主程序的以及各程序模块之间的层次(调用)关系。 typedef struct Node { int Index; 在当前环中所处的位置,即编号 int Password; 在当前环中的所带的密码 struct Node *next; }JosephuNode; 使用单循环链表创建约瑟夫环 JosephuNode *Creat_Node(int numbers) 约瑟夫环 void Josephu(JosephuNode *head,int Password) 三、详细设计 实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法。 本程序主要是以建立单循环链表的形式,建立起一个约瑟夫环,然后根据之前创立的结点,输入结点里的一些数据,如下 typedef struct Node { int Index; 在当前环中所处的位置,即编号 int Password; 在当前环中的所带的密码 struct Node *next; }JosephuNode; 程序有主函数开始,首先,提示输入创建约瑟夫环环数以及每个环上所带的密码。然后,开始调用JosephuNode *Creat_Node函数,利用单循环链表建立起约瑟夫环,tail->next = head;就是将最后一个结点的后继指向头结点,函数结尾 return head; 将约瑟夫环的头指针返回,并将它赋值head,然后主函数继续调用Josephu函数,通过讲head和Password引入函数,以建立两个嵌套循环输出并实现如下功能: 编号是1,2,……,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。 四、设计与调试分析 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个 游戏过程,不仅程序写起来比较烦,而且时间复杂度高达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 --> 0 k+1 --> 1 k+2 --> 2 ... ... k-2 --> n-2 k-1 --> n-1 变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这 个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x 变回去不刚好就是n个人情况的解吗,~~变回去的很简单,相 信大家都可以推出来:x‘=(x+k)%n 如何知道(n-1)个人报数的问题的解,对,只要知道(n-2)个人的解就 行了。(n-2)个人的解呢,当然是先求(n-3)的情况 ---- 这显然就是 一个倒推问题~好了,思路出来了,下面写递推公式: 令f表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然 是f[n] 递推公式 f[1]=0; f=(f[i-1]+m)%i; (i>1) 有了这个公式,我们要做的就是从1-n顺序算出f的数值,最后结 果是f[n]。因为实际生活中编号总是从1开始,我们输出f[n]+1 由于是逐级递推,不需要保存每个f,程序也是异常简单: #include 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+1); } 这个算法的时间复杂度为O(n),相对于模拟算法已经有了很大的提高 。算n,m等于一百万,一千万的情况不是问题了。可见,适当地运用 数学策略,不仅可以让编程变得简单,而且往往会成倍地提高算法执 行效率。 五 、用户 注:任意输入一个数据后进入系统,然后根据系统提示操作即可。 六、 测试成果 七、附录(源程序清单) #include #include typedef struct Node { int Index; int Password; struct Node *next; }JosephuNode; /////////////////////////////////////////////// 使用单循环链表创建约瑟夫环 JosephuNode *Creat_Node(int numbers) { int i,pass; JosephuNode *head, *tail; head = tail = (JosephuNode *)malloc(sizeof(JosephuNode)); //申请头结点 for (i = 1; i Index = i; printf("\t\t请输入第%d号所带密码: ",i); //输入当前结点所带密码 scanf("%d",&pass); tail->Password=pass; tail->next = (JosephuNode *)malloc(sizeof(JosephuNode)); //申请一个新结点 tail = tail->next; //指针指向下一个结点 } tail->Index = i; printf("\t\t请输入第%d号所带密码: ",i); scanf("%d",&pass); tail->Password=pass; tail->next = head; //将尾结点指针指向表头 return head; }//Creat_Node ///////////////////////////////////////////////// 约瑟夫环 void Josephu(JosephuNode *head,int Password) { int i,j; JosephuNode *tail; for (i = 1; tail != head; ++i) { for (j = 1; j next; } tail->next = head->next; printf("\n\t\t第%d个出局的人的编号是:%d\t密码是:%d",i,head->Index,head->Password); Password=head->Password; free(head); head = tail->next; } i =head->Password; j=head->Index; printf("\n\t\t第7个出局的人的编号是:%d\t密码是:%d\n",j,i); free(head); } //Josephu ///////////////////////////////////// void main() { int numbers, Password; char stop; JosephuNode *head; printf("\t\t----------------- 约瑟夫环问题 -----------------\n"); printf("\t\t例如:输入约瑟夫问题的人数和起始密码:7,20\n"); printf("\t\t---------------------------------------------------\n"); do { printf("\t\t开始...\n\t\t输入约瑟夫环问题的人数和起始密码:"); scanf("%d,%d", &numbers, &Password); head=Creat_Node(numbers); printf("\t\t---------------\n"); printf("\t\t输出结果如下\n"); Josephu(head,Password); printf("\t\t-----------------------------------------------\n"); printf("\t\t是否继续进行,是Y(y),否N(n)\t"); getchar(); scanf("%c",&stop); getchar(); printf("\t\t-----------------------------------------------\n"); }while(stop=='y'||stop=='Y'); } 八、课程设计心得 此程序目前的缺点在于,结点密码数据类型定义的存储类型是int型,不能超过-2147483648,2147483648,一旦超过则程序输出结果有误,另一个缺点就是程序运行当中,一旦中途输入出现错误,则无法返回,必须将当前操作结束等到下个主函数的循环开始,或者直接退出重新运行此程序。优点则在于程序运行速度较快,不会出现输出结果有误的问题 经过这次集中上机的实验,从开始选题到自己上手还是编写程序的过程中,我学会了很多的东西,以前对C语言的知识和算法总是模棱两可的,经过这次练习,在某些方面上还是经过了加强的训练。此次,实验,从开始构建循环链表然后实现约瑟夫环功能的过程中,中途也遇见一些问题,但都逐一克服,相信在这 次的实验中提升了较大的自身动手实践能力。
/
本文档为【约瑟夫生死者游戏】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索