猴子选大王,顺序表

篇一：用C++编写程序 猴子选大王

湖南人文科技学院计算机系

课程设计说明书

课 程 名 称: 数 据 结 构 课 程 代 码: 题 目: 猴 子 选 大 王 年级/专业/班: 06级计算机科学与技术专业一班 学 生 姓 名:

学 号: 06408109 06408102 06408107 06408122 06408103 指 导 教 师: 刘 刚 常 开 题 时 间: 2008 年 6 月 16 日 完 成 时 间: 2008 年 6 月 29 日

目 录

摘 要 .................................................................................................................................... 2

一、引 言 .............................................................................................................................. 3

二、设计目的与任务 .............................................................................................................. 3

三、设计方案 .......................................................................................................................... 4

1、总体设计 ............................................................................................................................ 4

2、详细设计 ............................................................................................................................ 6

3、程序清单 .......................................................................................................................... 10

4、程序调试与体会 .............................................................................................................. 14

5、运行结果 .......................................................................................................................... 15

四、结 论 ............................................................................................................................ 16

五、致 谢 ............................................................................................................................ 16

六、参考文献 ........................................................................................................................ 16

摘 要

本文首先介绍顺序表和链表并作以比较，我们分别使用循环队列和循环链表来解决猴子选大王的问题,程序使用了C语言编写,有很少一部分函数是用C++编写的，有比较详细的中文注释并在VC++下调试运行通过。整个程序使用中文界面,并有相应的提示信息,便于操作和程序运行。

关键词：循环队列；循环链表； 存储结构

Abstract

This paper details the difference of sequence list and linklist.We respectively use queue and circular queue and circular linked list to solve the seek elected king of the monkey problem . The procedure write with C language ，a very small part function is used by the C + +,and has chinese explanatory note.What’s more,it was debugged in VC++ debugger and run very well.The whole procedure,with Chinese interface and thecorresponding hints,is convenient to run and easy to be operated.

Keywords : circular queue；circular linked list ； storage structure

《数据结构》课程设计

——猴子选大王

一、引 言

数据结构是一门非常重要的基础学科，但是实验内容大都不能很好的和实际应用结合起来。从而让很多学生认为学习数据结构并没有很大的作用。但本实验运用数据结构的知识，很好的解决了一个对于人脑来说比较烦琐的实际问题。

链表是一种以链式结构存储的线性表，特点是数据元素可以用任意的存储单元存储， 线性表中逻辑上相邻的两元素存储空间可以是不连续的。 同时为了表示逻辑关系， 每个数据元素除了存放自身的数据信息外还要存储一个指示其直接后继的信息。队列是一种先进先出的线性表。它只允许在的表的一端进行插入，而在另一端删除元素。循环队列是队列的顺序表示和实现。从时间上考虑顺序表中插入和删除元素的时间复杂度为O(N) , 查找元素的时间复杂度为O(1); 而链表中插入和删除元素的时间复杂度为O(1) , 查找元素的时间复杂度为O(N)。而链表中除了存放自身的数据信息外, 还要存放后继结点的地址信息, 存储密度不高。

本设计分别通过一个顺序存储结构和一个链表存储结构，再加适当函数与改变，就简明的解决了猴子选大王这个实际问题，其中顺序存储结构我们使用的是循环队列。依次按要求淘汰猴子一直到找到猴王，并依次显示被淘汰猴子的编号，输出猴王的编号。该程序具有一定的通俗性与实用性，其他类似的算法均可借鉴和参考使用。该程序清单详细具体、全面，为了使组员之间能够很好的理解各自完成的程序，促进组员之间的沟通，我们在程序中添加了较多的注释和说明，具有很强的可读性。

二、设计目的与任务

1、本课程设计的目的

1) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能并培养学生进行规范化软件设计的能力。

2) 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题；

3) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4) 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。

5) 使学生会使用各种计算机资料和有关参考资料，提高学生进行程序设计基本能力。

2、本课程设计的任务

问题描述：

1）分别使用顺序和链表二种存储结构

2）功能实现：一群猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

输入数据：输入m,n 。其中m,n 为整数，n

输出形式：依次显示离开圈的猴子编号，并且输出为大王的猴子编号。

三、设计方案

1、总体设计

1）使用顺序存储结构实现

我们选择的是使用一个循环队列来完成这个设计。定义并构造一个空循环队列，把猴子按照1到m的顺序依次进入该队列，再按题目要求把被淘汰的猴子踢出队列，使用两个循环把被淘汰猴子的编号和猴王的编号分别输出。

本设计使用循环队列求解猴子选大王的问题，程序中定义的数据结构如下：

定义一个循环队列typedef struct SqQueue

进队列 int EnQueue(SqQueue &Q,QElemType e)

出队列int DeQueue(SqQueue &Q,QElemType &e)

主程序包含模块：

typedef struct SqQueue

{ //定义一个循环队列

}SqQueue;

int InitQueue(SqQueue &Q)

{ //初始化}

int EnQueue(SqQueue &Q,QElemType e)

{ //进队列

} //EnQueue() end

int DeQueue(SqQueue &Q,QElemType &e)

篇二：数据结构猴子选大王

猴子选大王

1. 题目要求：

任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：

输入数据：输入m,n m,n 为整数，n

输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。

2. 应用程序功能

程序运行结果如下：

3. 输入数据类型、格式和内容限制

输入数据为整型，切勿输入整形以外数据类型，否则程序将报错。

4. 主要算法模块描述

流程图：

5. 源程序代码

#include "iostream"

#include "stdlib.h"

using namespace std;

typedef struct node{

int data;

struct node *next;//定义结点指针

}ListNode;

typedef ListNode *Linklist;//自定义链表类型

ListNode *q,*p;

Linklist head=(Linklist)malloc(sizeof(ListNode));//申请头结点

/*******按将猴子数量编号并存入链表*******/

Linklist Create(int n)

{

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;//返回链表头指针

}

/****************打印链表***************/

void printlist(Linklist head)

{

p=head->next;

while(p)

{//打印链表直至链表结尾

cout<data<<" ";

p=p->next;

}

}

/**************删除被选到的猴子*****************/

void Delete(ListNode *b,ListNode *pb) /*pb为删除结点的前驱*/ {

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)

{

for(j=0;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 main()

{

int i,c,k,flag=0;

cout<<"请输入猴子数量"<

cin>>i;

cout<<"--------------将猴子顺序编号--------------"<

cout<

{

cout<<"第几个猴子离开？"<

cin>>c;

if(c>i) cout<<"输入数量大于猴子数量，请重新输入"<

}

k=King(head,c,i);//调用猴子先大王函数

cout<<"大王编号为 "<

}

篇三：数据结构--猴子选大王

课程设计说明书

课题名称： 猴子选大王 学生学号： 专业班级： 计算机科学与技术 学生姓名： 学生成绩： 指导教师： 课题工作时间： 至

摘 要

本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题---猴子选大王。从而使复杂的选举工作变得明朗化。

全程序以数据结构（C语言）中的循环单链表为主要的设计支柱，利用了C语言简洁紧凑、灵活方便，语法限制不太严格，程序设计自由度大，生成目标代码质量高，程序执行效率高等方面的优点。循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环，基于这样的特点，它适合处理具有环形结构的数据元素序列。

在程序代码的编写中，运用了结构体类型（struct Node），动态申请内存空间函数malloc（），释放动态申请内存空间函数free（）等类型，同时也具有多种循环、条件语句控制程序流向，如：嵌套if else语句，多重for循环语句，还有链表中结点指针（p->next），从而使程序完全结构化。

这样编写出的完整程序代码可以实现“猴子选大王”功能，输入猴子的数目m，循环数n，对m个猴子进行编号，通过嵌套if else语句，for语句，一遍一遍的循环，判断，删除，直到只剩下最后一个猴子，即大王。这样就可以实现所需的基本功能了。 关键词：数据结构；循环；单链表

Abstract

The main purpose of the program design process to solve the form of "Joseph Ring" in the election --- monkey king. So complex it became clear the election.

All procedures for data structures (C language) in single-cycle design of the main pillars of the list, using the C language simple and compact, flexible and convenient, the syntax is not strictly limited, program design flexibility to produce high quality object code, program execution the advantages of higher efficiency. Single-loop single-linked list is another form of list, its structural features is the last node list pointer field is no longer the end of the tag, but point to the list the first node, so that form a ring list, based on Such features, it has a ring structure for the data processing sequence of elements. The preparation of the program code, the use of a structure type (struct Node), dynamic application memory function malloc (), the release of dynamic memory functions for free () and other types, but also with a variety of loop, conditional statements control program flow such as: nested if else statements, multiple for loop, there is a linked list node pointer (p-> next), to make the program fully structured.

Write such a code can achieve a complete "Monkey King selected" feature, enter the number of monkeys m, cycles n, for number of monkeys on the m-by nested if else statements, for statements, loop over and over again, judge, removed until there are only a monkey, or king. This can achieve the required basic function.

Keywords: data structures; circulation; single linked list

篇四：数据结构 猴子选大王

【完成题目1】猴子选大王

【问题描述】

一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1--m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

【基本要求】

输入数据：输入m,n。 m,n 为整数，n

输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。

【算法设计】

通过对“猴子选大王”问题的分析，由于本题目的数据元素的个数不可预知，所以使用链表。链表是动态的，可以在需要的时候增长和减少其长度，而数组是在编译时分派内存的，事业其大小是不可改变的，而且会出现内存浪费的情况。我认为单循环链表能较好，在建立循环链表时，因为链表的大小由输入决定，因此与匹配的结点数也是变化的，所以要进行动态内存分配。

注意：输入数据为整型，切勿输入整形以外数据类型，否则程序将报错。

#include 为包含的库函数

Linklist Create(int n)// 创建循环链表 n为猴子总数

int King(Linklist head,int n,int i)//选出大王来

【源代码】

#include

#include

using namespace std;

typedef struct node

{

int data; struct node *next;//定义结点指针

}ListNode;

typedef ListNode *Linklist;//自定义链表类型/Malloc 向系统申请分配指定size个字节的内存空间 ListNode *q,*p;

Linklist head=(Linklist)malloc(sizeof(ListNode));//申请头结点

/*******按将猴子数量编号并存入链表*******/

Linklist Create(int n)

{

int i; p=head; p->next=NULL; for(i=1;i<=n;i++)

}

} return head;//返回链表头指针 q=(ListNode *)malloc(sizeof(ListNode)); q->data=i; p->next=q; p=q; p->next=NULL;

/****************打印链表***************/

void printlist(Linklist head)

{

}

/**************删除被选到的猴子*****************/

void Delete(ListNode *b,ListNode *pb) /*pb为删除结点的前驱*/

{

}

/**************猴子选大王（数n个）**************/

int King(Linklist head,int n,int i)

{

int j,k; ListNode *pp,*t; /*删除节点前驱*/ p=head; if(i==1) { for(j=0;jnext) t=head;//当删除的结点为最后一个结点时，t指向头结点 pp=p; p=p->next; if(!p) p=head->next; return i; while(i!=1) pb->next=b->next; free(b); p=head->next; while(p) {//打印链表直至链表结尾 } cout<data<<" "; p=p->next;

}

} Delete(p,pp); p=t; i--; k=pp->data;//将最后一只猴子的编号赋值给k return k;//返回最后一只猴子编号

void main()

{

} int i,c,k,flag=0;//falg：整型变量，与int相似 cout<<"请输入猴子数量"<>i; cout<<"--------------将猴子顺序编号--------------"<>c; if(c>i) cout<<"输入数量大于猴子数量，请重新输入"<

【结果截图】

【收获及体会】

猴子选大王是一个数据结构很古老很经典的问题，融知识性和娱乐性为一体，能让人产生较大兴趣。

在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程构思中选算法是一个很重要的概念，只有确定用这么算法后才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许多新的问题需要被解决，但同时它也是一个比较重要的过程。

通过本次实习，温固了数据结构的相关知识，加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程基本内容的理解，进一步熟悉了VC++编程环境，巩固并提高了分析问题、解决实际问题的能力。

做任何一件事情都需要一个过程，在这个过程中，面对许多问题，我们尽最大的努力寻找解决方法，现学现用新的知识，不断积累经验，为未来的发展打下基础。我们是在学习，但是我们真正要学的是学习的能力，我们享受这个过程，因为它引领我们进步

篇五：猴子选大王问题

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。 *问题分析与算法设计

约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。

题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。

[编辑本段]

约瑟夫问题的一般形式：

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，

3。最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

C++代码示例:

#include

using namespace std; void main() { int n,m,a[101],k,i,j,num; //计数器是从1开始的,所以100个人用101

cout<<"请输入参加游戏的玩家人数(不超过100人):";

cin>>n;

cout<<"----------------------------------------"<

if(n>100)

{

cout<<"玩家太多,请重新登陆此程序!"<

return;

}

cout<<"输入游戏中要玩的数字:";

cin>>m;

cout<<"----------------------------------------"<

for(i=1;i<=n;i++)

{

a【i】=1;//注意百度百科里不让使用ASCII里的方括号，这里是中文字符集里的方括号， }

j=0;

k=0;

for(i=1;i<=n+1;i++){

if(a【i】==1){

j=j+a【i】;

if(j==m) { j=0; a【i】=0;

k++;

}

if(k==n){

num=i;

break;

}

}

if(i==n+1)

i=0;

}

cout<<"最后获胜的玩家是第 "<

cout<<"----------------------------------------"<

}

写完密码约瑟夫就想到原来看到约瑟夫问题的一个数学解法 很巧妙很简单 不过只能推出最后一个出列的人

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。 为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m mod n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod 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) mod n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的

解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式

f[1]=0;

f=(f+m) mod i; (i>1)

有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1

由于是逐级递推，不需要保存每个f，程序也是异常简单：

c++

#include

int main()

{

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);

}

pascal

var n,m,i,s:integer;

begin

write('N M ='); read(n,m); for i:=2 to n do s:=(s+m) mod i;

writeln('The winner is ',s+1);

end.

这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。

约瑟夫问题10e100版(from vijios)

描述 Description

n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。

输入格式 Input Format

一个正整数n，表示人的个数。输入数据保证数字n不超过100位。

输出格式 Output Format

一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。

样例输入 Sample Input

9

样例输出 Sample Output

3

时间限制 Time Limitation

各个测试点1s

注释 Hint 样例说明 当n=9时，退出圈子的人的编号依次为： 2 4 6 8 1 5 9 7

最后剩下的人编号为3

初见这道题，可能会想到模拟。可是数据实在太大啦！！

我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8...时的结果是1，1，3，1，3，5，7，1...

有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4...

这样就好弄了！！

大体思路如下：

①read(a)

②b:=1,c:=1{b为某一组的元素个数，c为现在所加到的数}

③while c

⑥c:=c-b{退到前一组}

⑦x:=a-c{算出目标为所在组的第几个元素}

⑧ans:=x*2-1{求出该元素}

⑨write(ans)

有了思路，再加上高精度就可以了。我写的代码比较猥琐，因为是先把上面的思路敲进去，再写过程，又把一些简单的过程合到主程序中了，所以有点乱，也有点猥琐。起提供思路的作用还是完全可以的吧~~~

var a,b,c:array[1..105]of integer;

la,lb,lc,i:integer;

s:string;

procedure incc;

var i:integer;

begin

for i:=1 to 105 do c:=c+b;

for i:=1 to 104 do if c>9 then

begin

c:=c+c div 10;

c:=c mod 10;

end;

end;

function cxiaoa:boolean;

var i:integer;

begin

cxiaoa:=false;

for i:=105 downto 1 do

if c

else if c>a then break;

end;

procedure doubleb;

var i:integer; begin for i:=1 to 105 do b:=b*2; for i:=1 to 104 do if b>9 then begin

b:=b+b div 10;

b:=b mod 10;

end;

end;

procedure decc;

var i,j:integer;

begin

for i:=1 to 104 do

if c>=b then c:=c-b else begin

j:=i+1;

while c[j]=0 do inc(j); while j>i do

begin

c[j]:=c[j]-1;

c[j-1]:=c[j-1]+10; dec(j); end; c:=c-b;

end;

end;

procedure fua;

var i:integer;

begin

for i:=1 to 104 do

if a>c then a:=a-c else begin

a:=a-1;

a:=a+10;

a:=a-c;

end;

end;

procedure outit;

var i,j:integer;

begin

for i:=1 to 105 do a:=a*2; for i:=1 to 104 do if a>9 then begin

体裁作文