当前位置：文档之家 › 数据结构 猴子选大王

数据结构 猴子选大王

  • 格式：pdf
  • 大小：180.00 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

monkey

monkey

课程设计说明书
2.1.4 2.1.4．创建单向基本链表基本算法
创建循环单链表函数 采用头插法创建单向循环链表 Status CreateList(elemtype m) { List head, p; head = (List)malloc(sizeof(struct Node)); //*为头指针申请两个空间*// head->next = head; //*一共有 m 个猴子，所以建立含有 m 个结点的单向循环链表*// for (i = 1; i < m; ++i) { p = (List)malloc(sizeof(struct Node)); / /*为结点申请两个空间*// p->next = head->next; head->next = p; }//*利用 for 循环实现链表的创建*// p = head; //*将指针 p 指向表头*//
No.8
沈阳大学
课程设计说明书
2.1.6 2.1.6 主函数方案设计
No.9
在主函数中首先设计程序的登陆界面信息，用户可以根据界面的提示，完成猴子选大 王的基本操作过程，为了使操作更加人性化，使输入猴子的数目 m 和决定要淘汰的猴子 编号 n，通过键盘输入，若输入错误是（m<n）,界面将用英文提示输入错误请重新输入， ，若输入正确，程序将显示运行后的结果,显示最后猴子大王的编号，并显示被淘汰猴子 的编号，程序运行完毕。 在主函数中，在用户输入结束后，分别调用创建链表函数 CreateList(elemtype m)和猴 子选大王参数 LinkedList(elemtype num_monkey, elemtype number)，经过一些列的运 算，最后得出猴子大王的编号，及其被淘汰的猴子的编号，以上即为函数的基本功能的 实现过程。

约瑟夫问题

约瑟夫问题
}
cout<<endl;
return 0;
}
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ
，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，
这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
int main()
{
int i,j,nx[10000] = {0},n[10000] = {0},m[10000] = {1},counter[2] = {0};//数组要足够大才能不停止运行
{ j = j % nx[i]; //求余实现循环从0-n移动或用if判断实现循环
if(n[j] == 0)
{ counter[0]++; //计数器记录具有某一特点的数的次数
if(counter[0] % m[i] == 0)n[j] = 1,counter[1]+& = 0;j < nx[i];j++)
if(!n[j])cout<<j + 1<<endl;
for(j = 0;j < 10000;j++)n[j] = 0;for(j = 0;j < 2;j++)counter[j] = 0; //初始化需要重新使用的变量
for(i = 1;m[i - 1] != 0;i++) //利用m[]只有最后的值为0判定，不使用m[0]并赋值为1，其余默认为0
cin>>nx[i]>>m[i];
for(i = 1;m[i] != 0;i++)

数据结构课程设计报告

数据结构课程设计报告

*****数据结构课程设计题目: 赫夫曼树的建立运动会分数统计订票系统猴子选大王图的建立与输出姓名：***学号 ****专业：计算机科学与技术指导教师：****2006年9月20日目录一：绪言 (3)1.1课题设计背景 (3)1.2课题研究的目的和意义…………………………….3.1.3课题研究的内容 (4)二：主菜单设计 (4)2.1主菜单 (4)2.2主菜单源代码 (4)2.3主菜单流程图 (5)三：具体程序设计 (6)3.1赫夫曼树的建立 (6)3.2运动会设计 (8)3.3订票系统 (12)3.4猴子选大王 (15)3.5图的建立及输出 (16)四：总结与展望 (19)五：参考文献 (19).1.绪言1．1 课题背景《数据结构》作为一门独立的课程最早是美国的一些大学开设的，1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。

从60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。

从70年代中期到80年代初，各种版本的数据结构著作就相继出现。

目前在我国，《数据结构》也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。

《数据结构》在计算机科学中是一门综合性的专业基础课。

数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。

在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。

因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。

Res_猴子选大王2

Res_猴子选大王2

5.4.8 实验项目5-14：猴子选大王1、实验名称：猴子选大王2、实验目的：（1）熟练使用循环控制。

（2）熟练理解和掌握二维数组存储结构的使用技巧。

3、实验任务（1）实验内容：一群猴子要选新猴王。

新猴王的选择方法是：让n只候选猴子围成一圈，从某位置起顺序编号为1~n号。

从第1号开始报数（从1到3），凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。

如此不断循环，最后剩下的一只猴子就选为猴王。

请问是原来第几号猴子当选猴王？（2）实验要求：输入一个正整数n（n<=100），写一个程序来模拟这个过程，输出猴王的序号。

测试用例：4、实验要点分析（1）问题分析：用循环的方法模拟选猴王的过程。

一种简单的方法是对n只猴子用1~n 编号，编号存放在大小为n的一维整数数组中，若某编号的猴子要退出圈子，则把其编号改为-1。

若数组中只剩一个非-1的编号时，该编号的猴子就是大王。

开始时数组中的元素是从1到n的整数，表示都在“圈子”中，凡报到3的猴子退出圈子，即置为-1。

再依次查找下一只在“圈子”中的猴子，并重新开始报数。

这个过程进行n-1次，就只剩下一只编号不是-1的猴子了。

这种方法在寻找“下一个在圈子中的猴子”时可能会遇到很多“-1”而浪费时间。

另一种改进的方法是把n只猴子用0~n-1编号，数组的下标表示猴子的编号，数组元素的值表示相邻下一只在圈子中的猴子编号。

比如，n=5时，初始的数组M的内容如下表: 下标：0 1 2 3 4当2号猴子（报数轮到3）退出圈子时，1号猴子的下一只相邻猴子就是3号猴子了，实现时只需一个赋值M[1]=M[2]（即原来2号猴子的下一只相邻猴子成了1号猴子的下一只相邻猴子）。

数组M的内容变成了下表:下标：0 1 2 3 4这样做的好处有两个，一是第i号猴子的下一只相邻猴子就是M[i]，不需要用一个循环去找了；二是不用当心数组M下标的访问会越界。

（2）实现要点：1）循环控制结构。

第20章猴子选大王游戏

第20章猴子选大王游戏
➢ 在本章，我们以此问题作为研究对象， 通过编写程序，来输出站成一圈猴子的 出圈顺序号。
20.2 问题分析及实现
➢ 20.2.1 问题分析 ➢ 20.2.2 问题实现 ➢ 20.2.3 程序运行
20.2 问题分析及实现
➢ 拿到这个算法问题，首先想到的前面提到的 要领：看清、想明、把握每一个细节。
猴子选大王游戏
➢ 猴子选大王（亚瑟夫环）是数据结构和算法 中常见的一类问题。有人使用循环队列实现， 有人使用链表实现。本章将使用数组的回溯 算法实现选猴王的算法程序。
20.1 问题描述
➢ 有M只猴子围成一圈，每只各一个从1 到M中的编号，打算从中选出一个大王； 经过协商，决定出选大王的规则：从第 一个开始循环报数，数到N的猴子出圈， 最后剩下来的就是大王。
11
printf("%d ",Monkey[i]); /*让猴子站成一圈*/
12 printf("\n");
13 }
20.2.2 问题实现
➢ 2. 将结果输出 ➢ 将回溯结果输出至屏幕，以循环打印的方式，
调用标准输入输出函数printf，将结果回显。 代码如下（代码20-2.txt）
20.2.2 问题实现
20.2.2 问题实现
➢ 本小节就通过编程来实现此问题，实现的代 码如下。
➢ 1. 让猴子站成一圈 ➢ 如何让猴子站成一圈呢？根据问题分析结n 果，
采用整型一n维数组中保存猴子顺序号n，即表 示站成一排。代码如下（代码20-1.txt）。
20.2.2 问题实现
01 #include<stdio.h>
第20章
猴子选大王游戏
问题描述 问题分析及实现 开发过程常见问题及解决

数据结构课程设计(附代码)-数据结构设计

数据结构课程设计(附代码)-数据结构设计

上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级姓名学号指导教师日期一.目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力表。

3、输出功能：void print(LinkList *head);通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。

知道不满足循环语句，程序再次回到菜单选择功能界面。

4、删除功能：LinkList *Delete(LinkList *head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。

5、插入功能：LinkList *Insert(LinkList *head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。

链表长度加一，重新存储。

(5) 程序的输入与输出描述输入：调用LinkList *create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用void print(LinkList *head)函数，输出学生的记录。

(6) 程序测试主菜单：成绩管理系统的主界面：学生成绩记录的输入：输出学生成绩记录：学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）(7) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。

数据结构习题及答案与实验指导(数组和广义表)5

第5章数组和广义表本章所讨论的多维数组和广义表是对线性表的推广，其特点是数据元素仍可被视为一个表。

要求熟悉多维数组的逻辑结构、存储结构，广义表的逻辑结构、表示形式，以及矩阵的压缩存储的有关内容。

重点提示：●多维数组的存储方式和存取特点●特殊矩阵的存储●稀疏矩阵的存储●广义表的表示形式5-1 重点难点指导5-1-1 相关术语1．特殊矩阵要点：矩阵中非零元素或零元素的分布有一定规律的矩阵。

2．对称矩阵要点：一种特殊矩阵；n阶方阵的元素满足性质：a ij=a ji（0≤i，j≤n-1）。

3．三角矩阵要点：以主对角线划分，有上三角矩阵和下三角矩阵两种；主对角线以下，不包括主对角线中的元素，均为常数c，称为上三角矩阵；主对角线以上，不包括主对角线中的元素，均为常数c，称为下三角矩阵。

4．对角矩阵要点：非零元素集中在以主对角线为中心的带状区域中，也称带状矩阵。

5．稀疏矩阵要点：矩阵中非零元素的个数远小于矩阵元素总数的矩阵。

6．三元组表要点：是稀疏矩阵的一种存储结构；将稀疏矩阵的非零元素的三元组（行、列和值）按行优先的顺序排列；得到结点均是三元组的线性表。

7．广义表要点：是线性表的推广；是n个元素a1,a2,…,a n的有限序列；其中a i或者是原子或者是广义表；通常记为LS=(a1,a2,…,a n)，LS为广义表的名字。

5-1-2 多维数组1．对n维数组逻辑结构的理解n维数组可视为由n-1维数组为元素的线性结构。

举例：一个m行n列的二维数组可视为由m个一维数组为元素组成的线性结构，其中每个一维数组又由n 个单元素组成。

]a ,,a ,[a A A A A a a a a a a a a a Amn in i2i1i m 21mnv m2m12n 22211n 1211 =⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=其中2．数组的顺序存储方式（1）行优先顺序——将数组元素按行向量排列，即第i ＋1行紧接在第i 行后面。

猴子算法

一、猴子选大王：（1）M只猴子要选大王，选举办法如下：所有猴子按1-M编号围坐一圈，从1号开始按顺序1，2，，，K报数，凡报到K的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和K由输入文件提供，要求在输出文件中打印出最后剩下的猴子的编号。

数据规模（M<=1000,K<=10）【输入文件】输入文件monkey.in 的第1 行，为两个正整数，用一个空格隔开:M K【输出文件】输出文件monkey.out 只有一个正整数,输出最后一个猴子的编号【输入样例】7 3【输出样例】4这就是顶顶有名的约瑟夫问题。

这是一个据说是由古罗马著名史学家Josephus提出的问题演变而来的。

称之为约瑟夫问题。

很多资料上对这一问题解释得过于繁杂，实现起来不好理解。

在这里介绍一下本人的一些想法以供大家参考。

这个题目其实就是一种编程的经验问题。

我们可以假设猴子就位的状态用1表示，把猴子离开的状态用0表示。

那么我们就可以用一个a[M]的数组来存放M个猴子是否就位的状态。

我们可以一边报数一边遍历该数组，每遇到第K个1时，就把当前位置的1变为0，表示当前位置的猴子已经出局了。

一直循环遍历到我们的状态数组只有一个1的时候，这个存放1的数组下标再加上1（因为数组下标是由0开始的，所以要加1）即为选出的大王的编号。

想法很简单，现在关键的问题是如何解决当报数到第M个猴子的时候如何使得下一个报数重新回到第1个猴子处，也就是如何使用一维数组来解决环型问题的求解技巧。

大家想一下当我们的猴子围成圈坐的时候，问题其实由简单的一维数组变成了首尾相接的环型数组，也就是我们数据结构中的环型队列。

假设p为当前数组某一元素的下标，对于一维数组来说，我们只要p++就可以移动到下一个元素的位置上。

那么当p=M时，如果我们直接使用p++的话，p的值就超出了a[M]数组的最大长度，我们想要的是p++之后等于0。

那么如何实现呢？解决环型数组循环遍历元素的方法：对于环型数组移动下标时，我们如果每次在p++之后再加上p=p%M的话就能解决先前遇到的越界的问题。

(完整版)数据结构经典题目及c语言代码

《数据结构》课程设计题目(程序实现采用C语言)题目1：猴子选王(学时:3）一堆猴子都有编号，编号是1，2,3 .。

.m，这群猴子（m个)按照1-m的顺序围坐一圈，从第1开始数，每数到第n个,该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王.要求:m及n要求从键盘输入,存储方式采用向量及链表两种方式实现该问题求解.//链表#include 〈stdio.h〉＃include 〈stdlib.h>// 链表节点typedef struct _RingNode｛int pos；struct _RingNode ＊next;}RingNode， *RingNodePtr；// 创建约瑟夫环，pHead:链表头指针,count：链表元素个数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 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；pCurr = pCurr—〉next;if （pPrev == pCurr)｛// 最后一个printf("\nKing is %d", pCurr—〉pos）; // 显示出圈循序 free（pCurr)；break；}i++;｝}int main（）｛int n = 0, m = 0；RingNodePtr pHead = NULL;printf("M（person count）= ”）;scanf(”％d”, &m);printf("N（out number) = "）;scanf(”％d”， &n）;if(m 〈= 0 |｜ n <= 0）｛printf("Input Error\n”)；return 0;}// 建立链表pHead = (RingNodePtr)malloc（sizeof（RingNode））； pHead->pos = 1;pHead->next = NULL;CreateRing(pHead， m);// 开始出圈printf("\nKick Order： ")；KickFromRing(pHead， n）；printf(”\n"）;system(”pause”）；return 0；}//数组做：#include<stdio。

C++猴子选大王 choose monkey king

return0;
}
猴子状态初始化为1表示可能被选上为0表明没希望了
#include <iostream>
usingnamespacestd;
classmonkey
{
private:intnum,del;
public:
monkey(intn,intd):num(n),del(d){}//构造函数
intchoose(intnum,intdel)
}
delete[]a;
}
};
intmain()
{
intnum,del;
cout<<"请输入猴子总数M和淘汰号N：";
cin>>num>>del;
monkeymonkeygroup(num,del);
cout<<"第"<<monkeygroup.choose(num,del)+1<<"个猴子为大王!"<<endl;
{
countOne=0;
for(i=0;i<num;i++)
{
sum+=a[i];
if(sum==del)
sum=a[i]=0; //淘汰倒霉猴子；
countOne+=a[i];
}
}
for(i=0;i<num;i++)
if(a[i]!=0){
delete[]a;
return i; //找到幸运猴子编号（从0开始的）；
{
inti;
int*a;
a = newint[num];
for(i[i]=1; //猴子状态初始化，为1表示可能被选上，为0表明没希望了；
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

出为大王的猴子是几号 ，建立一个函数来实现此功能。
【算法设计】
通过对“猴子选大王”问题的分析，由于本题目的数据 元素的个数不可预知，所以使用链表。链表是动态的，可以 在需要的时候增长和减少其长度，而数组是在编译时分派内 存的，事业其大小是不可改变的，而且会出现内存浪费的情 况。我认为单循环链表能较好，在建立循环链表时，因为链 表的大小由输入决定，因此与匹配的结点数也是变化的，所 以要进行动态内存分配。
{ cout<<"第几个猴子离开？"<<endl; cin>>c; if(c>i) cout<<"输入数量大于猴子数量，请重新输入"<<endl; if(c<i||c==i) flag=1;
} k=King(head,c,i);//调用猴子选大王函数 cout<<"大王编号为 "<<k<<endl; }
通过本次实习，温固了数据结构的相关知识，加深对课内 所学的有关数据的逻辑结构和存储表示、数据结构的选择和应 用、算法的设计和时空效率分析等课程基本内容的理解，进一 步熟悉了VC++编程环境，巩固并提高了分析问题、解决实际问 题的能力。 做任何一件事情都需要一个过程，在这个过程中，面对许多问
题，我们尽最大的努力寻找解决方法，现学现用新的知识，不 断积累经验，为未来的发展打下基础。我们是在学习，但是我 们真正要学的是学习的能力，我们享受这个过程，因为它引领 我们进步
注意：输入数据为整型，切勿输入整形以外数据类型， 否则程序将报错。
#include <stdio.h>为包含的库函数 Linklist Create(int n)// 创建循环链表 n为猴子总数 int King(Linklist head,int n,int i)//选出大王来
【源代码】
#include <iostream> #include <stdlib.h> using namespace std; typedef struct node {
int i; p=head; p->next=NULL; for(i=1;i<=n;i++) {//将猴子顺序编号
q=(ListNode *)malloc(sizeof(ListNode)); q->data=i; p->next=q; p=q; p->next=NULL; } return head;//返回链表头指针 }
【完成题目1】猴子选大王 【问题描述】
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m
个）按照1--m的顺序围坐一圈，从第1开始数，每数到第N个，
该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一
只猴子，则该猴子为大王。
【基本要求】
输入数据：输入m,n。 m,n 为整数，n<m；
输出形式：中文提示按照m个猴子，数n 个数的方法，输
for(j=0;j<n;j++) {//数到第n个猴子
pp=p; p=p->next; if(!p) p=head->next; } if(!p->next) t=head;//当删除的结点为最后一个结点时，t指向头结 点 else t=pp; Delete(p,pp); p=t; i--; } k=pp->data;//将最后一只猴子的编号赋值给k return k;//返回最后一只猴子编号 }
【结果截图】
【收获及体会】
猴子选大王是一个数据结构很古兴趣。
在课程设计中，首先要看清问题，将问题要求理解透彻， 在构思要如何实现，要用到哪些函数，要用什么算法，在课程 构思中选算法是一个很重要的概念，只有确定用这么算法后才 能接下来的工作，将流程图画在纸上，再依次编写代码，在程 序设计中，编写代码只是一个方面，调试才是关键。它是一个 相当繁琐的过程，有许多新的问题需要被解决，但同时它也是 一个比较重要的过程。
/****************打印链表***************/ void printlist(Linklist head) {
p=head->next; while(p) {//打印链表直至链表结尾
cout<<p->data<<" "; p=p->next; } }
/**************删除被选到的猴子*****************/ void Delete(ListNode *b,ListNode *pb) /*pb为删除结点的前驱*/ {
int data; struct node *next;//定义结点指针 }ListNode;
typedef ListNode *Linklist;//自定义链表类型/Malloc 向系统申请分配指定 size个字节的内存空间 ListNode *q,*p; Linklist head=(Linklist)malloc(sizeof(ListNode));//申请头结点 /*******按将猴子数量编号并存入链表*******/ Linklist Create(int n) {
void main() {
int i,c,k,flag=0;//falg：整型变量，与int相似 cout<<"请输入猴子数量"<<endl; cin>>i; cout<<"--------------将猴子顺序编号--------------"<<endl; printlist(Create(i));//调用将猴子顺序编号的函数 cout<<endl<<"-----------------编号结束-----------------"<<endl; while(!flag)
pb->next=b->next; free(b);
}
/**************猴子选大王（数n个）**************/ int King(Linklist head,int n,int i) {
int j,k; ListNode *pp,*t; /*删除节点前驱*/ p=head; if(i==1) return i; while(i!=1) {