猴子选大王数据结构课程设计报告内附详细注释

1.需求分析问题定义：一堆猴子都有编号，编号是1，2，3…n,这群猴子（n个）按照1-n的顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。m，n键盘输入，且m

问题分析：根据任务描述可知，编号是1，2，3…n的一群猴子按照1-n的顺序围坐一圈，因此可以用指针指向数组的方法给数组赋值，输入n值和m值，为保证m

#include

#include //使用calloc()函数

void FindKing_pointer(int,int,int*);//移动指针法找大王void Initialize(int,int*);//初始化数组整形和指针型int main()

{

int m,n,*ptr;

printf("输入猴子数与出局时报的数\n");

scanf("%d %d",&n,&m);

while(n

{

printf("输入数据有误，请重新输入!\n"); printf("输入猴子数与出局时报的数\n"); scanf("%d %d",&n,&m);

}

ptr=(int *)calloc(n,sizeof(int));

Initialize(n,ptr);

FindKing_pointer(m,n,ptr);

free(ptr);

return 0;

if(ptr2==ptr+n)

ptr2=ptr;

/*指针所指元素不为0时计数器加1.*/

if(*ptr2!=0)

i++;

/*计数器数到m时将指针所指元素设为0*/ if(i==m)

{

*ptr2=i=0;

count--; //用于终止循环

}

}

/*最后不为0的元素的值即为大王的编号*/

for(ptr2=ptr;;ptr2++)

{

if(*ptr2!=0)

{

printf("第%d个猴子是大王\n",*ptr2);

break;

}

}

}

/*思想是猴子围坐一圈，有N个猴子，开始数数，数到第M个猴子，该猴子就出列，

然后再从该猴子的下一个猴子开始数到第M个猴子，直到只剩下一个猴子时。该猴子就是所要选得大王*/

4.结果分析

5.设计总结

在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪

才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许多新的问题需要被解决，但同时它也是一个比较重要的过程，因为在程序调试过程中，你会学到很多新的东西，从而增加你编程的经验。通过本次实习，温固了数据结构的相关知识，加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程基本内容的理解，进一步熟悉了VC++编程环境，巩固并提高了分析问题、解决实际问题的能力。

用C编写程序猴子选大王

湖南人文科技学院计算机系 课程设计说明书 课程名称: 数据结构 课程代码: 题目: 猴子选大王 年级/专业/班: 06级计算机科学与技术专业一班 学生姓名: 学号:06408109 06408102 06408107 06408122

06408103 指导教师: 刘刚常 开题时间: 2008 年 6 月16 日 完成时间: 2008 年 6 月29 日

目录 摘要 (3) 一、引言 (4) 二、设计目的与任务 (4) 三、设计方案 (5) 1、总体设计 (5) 2、详细设计 (8) 3、程序清单 (14) 4、程序调试与体会 (22) 5、运行结果 (23) 四、结论 (24) 五、致谢 (24) 六、参考文献 (25)

摘要 本文首先介绍顺序表和链表并作以比较，我们分别使用循环队列和循环链表来解决猴子选大王的问题,程序使用了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

猴子选大王课程设计报告

课程设计报告 课程设计题目：猴子选大王 学生姓名:吴兆 专业:软件工程 班级:1321813 学号:201320181306 指导教师:吴建东 2015年1 月9 日 东华理工大学

目录一：需求分析 1.问题描述 2.基本要求 3.需求分析 二：概念设计 三：详细设计 四：调试分析和测试结果五：总结 六：源代码

一：需求分析 1.问题描述 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m 的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 2.基本要求 输入数据：输入m,n m,n 为整数，n

程序流程图如下： 否 是 三：详细设计 1.程序中使用的存储结构struct L { int num; struct L *next; }; int n; int i=0; 2.程序中使用的循环结构开始 进行1-m的报数 删除第n只猴子 剩下的猴子 数是否为1 输出猴子大王的序号 结束

猴子选大王

一、猴子选大王课题描述 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1 到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 猴子选大王系统设计 1、猴子选大王总体设计结构图 2、系统数据的数据结构设计 猴子的存放采用链式存储结构，利用循环链表来实现建立的，其表示方法是递归定义的. (1)、变量说明 程序中使用的存储结构:ListNode结构体 Struct ListNode{ Int data; //数据域 Struct ListNode *nextPtr; //指向后继结点的指针域 }; Int monkeys,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) //用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指向链表中拆下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; } currentPtr1=prePtr1; /*currentPtr1指向上一个结点，为下一次数数做准备*/

数据结构--猴子选大王

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

摘要 本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题---猴子选大王。从而使复杂的选举工作变得明朗化。 全程序以数据结构（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

猴子选大王课程设计说明书

数学与计算机学院 课程设计说明书课程名称: 数据结构课程设计 课程代码: 6014389 题目: 猴子选大王 年级/专业/班: 2010级软件工程2班 学生姓名: 蒋童 学号: 开始时间: 2011 年11 月9 日 完成时间: 2011 年12 月30 日 课程设计成绩： 指导教师签名：年月日数据结构课程设计任务书

学院名称：数学与计算机学院课程代码：__ 6014389______ 专业：软件工程年级：2班 一、设计题目 猴子选大王 二、主要内容 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 三、具体要求及应提交的材料 要求：使用数组和循环链表等两种以上的存储方式来做 输入数据：输入m,n m,n 为整数，n

六、推荐参考资料 [1] 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 [2] 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年 5月。 [3] 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年 9月 [4] 朱战立.数据结构(C++语言描述)（第二版本）.高等出版社出版.2004 年4月 [5] 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月 [6] 徐孝凯等著.数据结构（C语言描述）.清华大学出版社.2004 指导教师签名日期年月日 系主任审核日期年月日 目录 摘要................................. 错误！未定义书签。引言.................................. 错误！未定义书签。 1 需求分析.............................. 错误！未定义书签。 1.1任务与分析..................................... 错误！未定义书签。 1.2测试数据....................................... 错误！未定义书签。 2 概要设计.............................. 错误！未定义书签。 2.1 ADT描述....................................... 错误！未定义书签。 2.2程序模块结构................................... 错误！未定义书签。 2.21 结构体定义................................... 错误！未定义书签。 2.3 各功能模块.................................... 错误！未定义书签。 3 详细设计............................. 错误！未定义书签。

猴子选大王数据结构课程设计报告(内附详细注释)

1.需求分析 问题定义：一堆猴子都有编号，编号是1，2，3…n,这群猴子（n个）按照1-n的顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。m，n键盘输入，且m

If(Ptr2==ptr+n) Ptr2=ptr; 保证猴子围成圈 N i++ Y N Y N Y break 3.详细设计 #include #include //使用calloc()函数 void FindKing_pointer(int,int,int*);//移动指针法找大王 void Initialize(int,int*);//初始化数组 整形和指针型 int main() { int m,n,*ptr; printf("输入猴子数与出局时报的数\n"); scanf("%d %d",&n,&m); while(n

猴子选大王循环链表实现

C++ n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始没顺时针方向让猴子从1，2，...，m依次报数，凡是报到m的猴子，就让其出圈，取消候选资格。然后不停地按顺时针方向逐一让报到m者出圈，是的剩下的一个就是猴王。 #include using namespace std; struct monkey //结构声明 { int num; //整型数，用于记录猴子号 monkey *next; //monkey结构指针 }; monkey *head,*tail; //monkey结构指针，全局变量 void creat(int nn) //被调用函数 { //函数体开始 int i; //整型变量i，用于计数 monkey *p,*q; //声明monkey结构指针p,q p=new monkey; //为p分配内存空间 p->num=1; //初始化p结点num域为1 p->next=NULL; //初始化p结点next域为空 head=p; //链表头指针head赋值为p q=p; //q赋值为p for(i=2;i<=nn;i=i+1) //利用循环结构构造链表 { p=new monkey; //为p配内存空间 p->num=i; //初始化p结点num域为i，表示猴子号 q->next=p; //将p点加到链表尾部 q=p; //让指向链表尾部结点 p->next=NULL; //链表尾部指向空 } tail=q; //链表尾 tail->next=head; //链表尾部指向链表头，形成循环链表 } //被调用函数select,mm表示结点删除间隔 void select(int mm) { //函数体开始 int x=0; //声明整型值x，并初始化为0 monkey *p,*q; //声明指针变量p,q q=tail; //q赋值给tail，指向循环链表尾部 do //直到型循环，用于循环删除指定间隔的结点 {

数据结构上机实验程序--猴子选大王

#include #include struct Monkeyking { int data; struct Monkeyking *next; }; void main() { struct Monkeyking *head, *s, *q, *t,*p,*h; int n, k, count=0, i,j; printf("输入猴子总数:"); scanf("%d",&k); printf("\n"); printf("输入报号起始猴子编号:"); scanf("%d",&j); printf("\n"); printf("输入报号间隔数:"); scanf("%d",&n); printf("\n"); for(i=0; idata=i+1; s->next=NULL; if(i==0) { head=s; q=head; } else { q->next=s; q=q->next; } }//建立一个单链表 q->next=head;//将单链表组成环状 printf("输出猴子原始的编号:"); q=head; while(q->next!=head) { printf("%d ",q->data); q=q->next; }//依次输出节点的值

printf("%d ",q->data); printf("\n"); printf("\n"); q=head; for (i=0;inext; } q=p; printf("输出被淘汰的猴子编号:"); if (n==1) { for (i=1;i<=k;i++) { t=q; q=q->next; t->next=h; h=t; } for (i=1;i<=k;i++) { printf("%d ",h->data);//倒序输出淘汰猴子的编号，第一个编号为大王h=h->next; } printf("\n"); } else { do { count++; if(count==n-1) { t=q->next; q->next=t->next; t->next=h; h=t; count=0; } q=q->next; } while(q->next!=q); q->next=h; h=q;

数据结构课程设计 猴子选大王

题目：n只猴子要选大王，选举办法如下：所有猴子按1,2,3……n编号围成一圈，从第一圈开始顺序1，2……m报数，凡报到m号的退出圈外，如此循环报数，直到圈内只剩一只猴子时，这只猴子就是大王。 利用单向循环链表存储结构模拟此过程，输出选出的大王编号。 程序：#include #include #define n 19 #define m 4 typedef struct monkey { int num; struct monkey *next; } Monkey,*LINK; void main() { LINK p,head,p2; int i; head=p=p2=(LINK)malloc(sizeof(Monkey)); for(i=1;inext=p; p2=p; } p2->next=head; p=head; printf("对猴子进行编号！\n"); for(i=1;i<=n;i++) { p->num=i; printf("%d号猴子：%d\n",p->num,p->num); p=p->next; } i=0; p=head; while(1) { i++; printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break; if(i==m) { i=0; printf("%d号猴被淘汰\n",p->num);

printf("\n"); p2->next=p->next; p=p2->next; continue; } else { if(i==m-1) p2=p; p=p->next; } } printf("胜出:%d",p->num); } #include #include #define n 19 #define m 4 typedef struct monkey { int num; struct monkey *next; } Monkey,*LINK; void main() { LINK p,head,p2; int i; head=p=p2=(LINK)malloc(sizeof(Monkey));//三个指针指向同一块内存 for(i=1;inext=p; p2=p; }

猴子选大王课程设计说明书

数学与计算机学院 课程设计说明书 课程名称: 数据结构课程设计 课程代码: 6014389 题目: 猴子选大王 年级/专业/班: 2010级软件工程2班 学生姓名: 蒋童 学号: 312010********* 开始时间: 2011 年 11 月 9 日 完成时间: 2011 年 12 月 30 日 课程设计成绩： 指导教师签名：年月日

数据结构课程设计任务书 学院名称：数学与计算机学院课程代码：__ 6014389______ 专业：软件工程年级：2班 一、设计题目 猴子选大王 二、主要内容 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 三、具体要求及应提交的材料 要求：使用数组和循环链表等两种以上的存储方式来做 输入数据：输入m,n m,n 为整数，n

按教学计划规定，数据结构课程设计为2周，其进度及时间大致分配如下： 六、推荐参考资料 [1] 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 [2] 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年 5月。 [3] 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年 9月 [4] 朱战立.数据结构(C++语言描述)（第二版本）.高等出版社出版.2004 年4月 [5] 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月 [6] 徐孝凯等著.数据结构（C语言描述）.清华大学出版社.2004 指导教师签名日期年月日 系主任审核日期年月日

C语言-猴子选大王

1.#include #include #include void SelectKing(int MonkeyNum, int CallNum); void main() { int MonkeyNum; int CallNum; /* 输入猴子的个数*/ printf("Monkey Num = "); scanf("%d", &MonkeyNum); /* 输入M的值*/ printf("Call Num = "); scanf("%d", &CallNum); SelectKing(MonkeyNum, CallNum); } void SelectKing(int MonkeyNum, int CallNum) { int *Monkeys; // 申请一个数组，表示所有的猴子； int counter = 0; //计数，当计数为猴子个数时表示选到最后一个猴子了； int position = 0; // 位置，数组的下标，轮流遍历数组进行报数； int token = 0; // 令牌，将报数时数到M的猴子砍掉； // 申请猴子个数大小的数组，把桌子摆上。 Monkeys = (int *)malloc(sizeof(int)* MonkeyNum); if (NULL == Monkeys) { printf("So many monkeys, system error.\n"); return; } // 将数组的所有内容初始化为0，被砍掉的猴子设置为1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); // 循环，直到选中大王 while(counter != MonkeyNum)

猴子选大王C语言课程设计

猴子选大王 一、设计目的 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。 二、设计内容 1、系统名称：猴子选大王 按照规定的要求，选出最后的一只猴子，为大王。 2、要求： 一堆有编号的猴子，编号为1，2，3……m，这群猴子（m个）按照1-m的顺序围坐一圈，从第一开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中剩下最后一只猴子，则该猴子为大王。 三、程序设计步骤 1）采用主要的数据结构类型。 采用了链表的存储方式，属于链接存储结构。

for(i=1;inext=p; p2=p; } 以下是用于存储结点的结构体的定义: typedef struct monkey { int num; struct monkey *next; } Monkey,*LINK; 基本算法： 这个算法的主要流程为： 从控制台读取猴子的数量和报数的最大数——>对猴子进行编号，并用链表来存储——>让链表中的猴子进行报数，对于报数为m的猴子则从链表中删除——>当链表中只剩下一个报数后则停止这个过程，这最后一个猴子即选出来的大王。 以下为为猴子建立链表： for(i=1;inext=p; p2=p; } 以下为猴子进行编号： for(i=1;i<=n;i++) //对猴子进行编号 { p->num=i; //printf("%d号猴子：%d\n",p->num,p->num); p=p->next; } 以下为最主要的算法过程，是通过一个While循环来控制的，是让猴子报数的过程，并删除报数为m的猴子： while(1) { i++; //当链表只剩最后一个元素了则跳出循环，此时报数已完成 printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break; if(i==m) { i=0; printf("%d号猴被淘汰\n",p->num); printf("\n");

常用经典算法(整理中)

Ｃ语言经典算法及程序 算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。 一、一些简单算法 1.求两个整数的最大公约数、最小公倍数 2.判断素数 3.验证哥德巴赫猜想 4.超级素数 5.猴子选大王 6.数的全排列 7.迭代法求平方根 二、排序算法 1.选择排序 2.冒泡排序 3.插入排序 4.快速排序 5.第K小元素 6.二分查找法

三、高精度数算法 1.已知Ｐ，且P×S=11...1，求Ｓ及１的个数 2.高精度数加法 3.高精度数减法 4.高精度数乘法 5.高精度数除法 6.高精度数阶乘 7. Fibonacci数列 四、数据结构相关问题 1.左右括号配对 2.多项式相加 3.N叉树 五、复杂算法 1．N女王问题 六、动态规划实例应用 1．求序列的最大连续序列和 2．求序列的最长下降子序列长度 3．数塔问题（解法一） 4．数塔问题（解法二）

一、一些简单算法 1.求两个整数的最大公约数、最小公倍数 最大公约数算法：(最小公倍数=两个整数之积/最大公约数) (1) 对于已知两数m，n，使得m>n； (2) m除以n得余数r； (3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) m←n，n←r，再重复执行(2)。 程序： #include "stdio.h" int main( ) { int nm,r,n,m,t; printf("please input two numbers:\n"); scan f("%d,%d”,&m,&n); nm=n*m; if (mn*/ r=m%n; while (r!=0) { m=n; n=r; r=m%n; } printf("最大公约数:%d\n",n); printf("最小公倍数:%d\n",nm/n); return 0;}

猴子选大王——课程设计

邮电与信息工程学院 课程设计说明书 课题名称：猴子选大王 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师： 课题工作时间：2010-6-22至2010-6-25

目录 摘要............................................................................................, (6) Abstract ......................................................................................, (7) 第一章课题背景.................................................................................,.. (8) 1.1课程设计的目的 (8) 1.2 课程设计的要求.............................................................................., (8) 1.3 课程设计的实验环境......................................................................,. (8) 第二章课程设计详细内容...................................................................,, (9) 2.1 问题描述......................................................................................,, (9) 2.2 程序代码精解.................................................................................,, (9) 2.3 程序结果运行...............................................................................,. (13) 总结......................................................................................., (15) 致谢.........................................................................................,.. (16) 参考文献.....................................................................................,.. (17) 附录主要程序代码....................................................................., (18)

猴子选大王问题

猴子选大王问题 集团文件版本号：（M928-T898-M248-WU2669-I2896-DQ586-M1988）

这是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 usingnamespacestd; voidmain() { intn,m,a[101],k,i,j,num;//计数器是从1开始的,所以100个人用101 cout<<"请输入参加游戏的玩家人数(不超过100人):"; cin>>n; cout<<"----------------------------------------"<100) { cout<<"玩家太多,请重新登陆此程序!"<

基础算法(一)枚举法

基础算法（一）枚举（穷举）法 无论什么类型的试题，只要能归纳出数学模型，我们尽量用解析方法求解，因为一个好的数学模型建立了客观事物间准确的运算关系。 在一时找不出解决问题的更好途径时，可以根据问题中的约束条件，将所有可能的解全部列举出来，然后逐一验证是否符合整个问题的求解要求。 一、枚举法的基本思想: 从可能的解集合中一一穷举各元素，用题目给定的检验条件判定哪些是有用的，哪些是无用的，能使命题成立的，即为其解。 这种思维方法主要是基于计算机运算速度快的特点。 二、枚举法解题思路： 1、对命题建立正确的数学模型； 2、根据命题确定数学模型中各变量的变化范围（即可能解的范围）； 3、利用循环语句、条件判断语句逐步求解或证明。 三、枚举法的特点： 算法简单，但运算量大。 对于可能确定解的范围，又一时找不到更好的算法时，可以采用枚举法。 1、求满足表达式A+B=C的所有整数解，其中A、B、C为1～3之间的整数。 2、鸡兔同笼问题（在同一个笼子里有鸡和兔子若干只，从上面看，能看到 20个头，从下面看，能看到60只脚，问鸡兔各有多少只？） 3、百钱百鸡问题（一百块钱要买一百只鸡，这一百只鸡必须包含母鸡、公 鸡和小鸡，其中，公鸡5元一只，母鸡3元一只，小鸡1元三只，问有哪些购买方案？） 4、水仙花数问题（ABC=A3+B3+C3,列出所有的整数ABC） 5、一根29厘米长的尺子，只允许在上面刻7个刻度，要能用它量出1～29 厘米的各种长度，试问刻度应该怎样选择？ 6、猴子选大王：有M个猴子围成一圈，每个有一个编号，编号从1到M。 打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。 要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王。 参考程序：

猴子选大王问题

这是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++代码示例: #i n c l u d e u s i n g n a m e s p a c e s t d; v o i d m a i n()

i n t n,m,a[101],k,i,j,n um; //计数器是从1开始的,所以100个人用101 c o u t<<"请输入参加游戏的玩家人数(不超过100人):"; c i n>>n; c o u t<<"----------------------------------------"<100) { c o u t<<"玩家太多,请重新登陆此程序!"<>m; c o u t<<"----------------------------------------"<