《猴子选大王.docx》由会员分享，可在线阅读，更多相关《猴子选大王.docx（6页珍藏版）》请在三一办公上搜索。
1、猴子选大王一、 猴子选大王课题描述 一堆猴子都有编号，编号是1，2，3 .m ,这群猴子按照1到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 猴子选大王系统设计 1、猴子选大王总体设计结构图 2、系统数据的数据结构设计 猴子的存放采用链式存储结构，利用循环链表来实现建立的，其表示方法是递归定义的. (1)、变量说明 程序中使用的存储结构:ListNode结构体 Struct ListNode Int data; /数据域 Struct ListNode *nextPtr; /指向后继结点的指针域 ; Int mon
2、keys,count /分别为猴子的个数和猴子的报数 HeadPtr,tailPtr，currentPtr /分别为链表的头结点，尾结点和结点 HeadPtr1,headPtr2 /分别为选大王的单循环链表和由淘汰的猴子所构成的链表 (2)、函数说明 DestroyList (LISTNODEPTR headPtr) /用destroylist函数来释放选大王链表的各个结点 CreateList (int n) /创建循环链表，容纳n个猴子 Printf(“input the amount of monkeys:”) /用printf函数来提示输入的内容 Scanf(“%d”,&monkeys
3、) /用scanf函数来输入猴子的个数 Printf(“input the count number:”) /用printf函数来提示报数的数 Scanf(“%d”,&count) /用scanf函数来输入每次数到的猴子就出局 (3)、while循环说明 while(currentPtr1!=currentPtr1-nextPtr) /*往后数一个猴子*/ prePtr1=currentPtr1; currentPtr1=currentPtr1-nextPtr; count+; /*若数到n，则淘汰currentPtr指向的猴子*/ if(count%n=0) /*从headPtr1指向链表中
4、拆下currentPtr指向的结点*/ prePtr1-nextPtr=currentPtr1-nextPtr; currentPtr1-nextPtr=NULL; /*将currentPtr1指向的结点插入到headPtr2指向链表中*/ if(headPtr2=NULL)/*若headPtr2指向的为空链表*/ headPtr2=currentPtr1; tailPtr2=currentPtr1; else /*将拆下来的结点组装到headPtr2指向的链表上*/ tailPtr2-nextPtr=currentPtr1; tailPtr2=tailPtr2-nextPtr; curren
5、tPtr1=prePtr1; /*currentPtr1指向上一个结点，为下一次数数做准备*/ 二、 猴子选大王重点及关键技术分析 程序通过循环链表较好的实现了猴子选大王的功能，但是还是有许多值得思考的地方。 1、由于N = 1的情况比较复杂，程序中对它作了模糊处理，没有复杂化，直接用n=2。 2、无论是用链表还是用数组实现都有一个共同点：要模拟整个过程，不仅程序比较烦，而且时间复杂度高达O(n*m)，当n，m非常大的时候，几乎是没有办法在短时间算内出结果的。后来注意到原问题仅仅是要求出最后的猴子大王的序号，而不是要模拟整个过程。为了讨论方便，先把问题稍微改变一下，并不影响原意： 问题描述：n
6、个人: 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变回到x=(x+k)%n 不刚好就是n个人情况的解吗！ 如何知道(n-1)个人报数的问题的解？只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 - 这显然就是一个倒推问题！到这里，思路出来了，下面就开始写递推公式： 令fi
7、表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是fn 递推公式 f1=0; fi=(fi-1+m)%i; (i1) 有了这个公式，所要做的就是从1-n顺序算出fi的数值，最后结果是fn。因为实际生活中编号总是从1开始，我们输出fn+1 由于是逐级递推，不需要保存每个fi，程序也是异常简单： #include “stdio.h” Void main int n, m, i, s=0; printf (n和m的值是：n ); scanf(%d%d, &n, &m); for (i=2; i=n; i+) s=(s+m)%i; printf (猴王是 %dn, s+1); 这个算法的时间复
8、杂度为O(n)，相对于模拟算法已经有了很大的提高。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。 但是我总觉得这样做，太简单了，然后我就想到用链表来存放猴子数，并且做好是能把淘汰的猴子的序列显示出来，然后就想到了用两个链表来完成，一个链表用来表示选大王的循环链表，另一个用来表示淘汰的猴子所组成的表。 在怎个设计的过程中，使用到的有”数据结构中的遍历”、“创建 ”、“删除 、“释放”以及指针和链表的一些操作,这些都是有一些难度的. 三、 猴子选大王设计结构与分析 在修改程序的时候，出现了很多很多的错误，有一些很基本的，也有一些是我不能解决的，但最后通过一些办
9、法，一步步的调试，最后终于调试成功了。 1、运行成功后显示画面如下图所示 2、输入猴子数89后显示的画面如下图所示 3、数入count报数为8后显示的画面如下图所示 本次截图总共有三个结果，第一个为猴子的总数为89只，报数道8，则那只猴子出局。最后结构为，第9号猴子是大王。 四、 猴子选大王进度安排 在第十周和十一周，我主要是对“猴子选大王”这个课题进行了全方面的分析，想出了初步解决此问题的一些算法，和确定了我所用的开发工具以及开发语言。 在十二周到十四周，我主要着重在写代码这一部分，我选择了C语言来实现课题，但由于有些东西有点模棱两可，所以在网上和书上找了一些别人用过的函数和借用了一些算法思想，来完成初代码。特别是在写遍历链表时，由于在学数据结构的时候，都没怎么弄懂，所以，在写这一部分的代码时，都是借用别人的。
