下载文档原格式
[题目]第1.1猴子选大王问题一：实验内容：M只猴子要选大王，选举办法如下：所有猴子按1，2……n编号围成一圈，从第一号开始顺序1,2……m,凡是报m号的退出圈外，如此循环报数直到圈内只剩一只猴子时这只猴子就是大王。
二：实验要求：利用单向循环链表模拟此过程，输出选出的大王编号。
三：程序的设计思想：（1）问题分析：“猴子选大王”问题是约瑟夫环问题的一个特例。
由于本题目的数据元素个数不可知，所以可使用链表来动态的分配内存空间。
而该问题又是一个不断的循环问题所以用循环链表来实现。
（2）总体设计：首先生成一个空链表，并给n个结点分配空间，让单链表的表尾指针指向头结点则生成一个带有n个结点的循环单链表。
再给每只猴子建立顺序的编号。
现从第一个结点开始报数，依次顺序查找出报数为m的待出列的结点（猴子）通过q->next=p->next删除该结点后继续运行否则让q成为p的前驱指针。
最后当p->next==p时停止运行，得到p所指向的结点即为猴子选出大王的编号。
四：提供测试结果：定义 n=8, m=3,测试结果如下：对猴子进行编号！1号猴子：12号猴子：23号猴子：34号猴子：45号猴子：56号猴子：67号猴子：78号猴子：82号猴子报：2 3号猴子报：3 3号猴被淘汰4号猴子报：1 5号猴子报：2 6号猴子报：3 6号猴被淘汰7号猴子报：1 8号猴子报：2 1号猴子报：3 1号猴被淘汰2号猴子报：1 4号猴子报：2 5号猴子报：3 5号猴被淘汰7号猴子报：1 8号猴子报：2 2号猴子报：3 2号猴被淘汰4号猴子报：1 7号猴子报：2 8号猴子报：3 8号猴被淘汰7号猴子报：24号猴子报：34号猴被淘汰7号猴子报：1胜出:7号猴子Press any key to continue五：程序源代码#include <stdio.h>#include <stdlib.h>#define n 8#define m 3typedef struct monkey{int num;struct monkey *next;} Monkey;int main(){Monkey *p,*head,*q;int i;head=p=q=malloc(sizeof(Monkey));//建立头指针 for(i=1;i<n;i++) //给n个结点分配空间{p=malloc(sizeof(Monkey));q=p;}q->next=head; //建立循环链表p=head;printf("对猴子进行编号！\n");for(i=1;i<=n;i++) //给n只猴子分别建立顺序编号{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) //报道m的猴子淘汰{i=0;printf("%d号猴被淘汰\n",p->num);q->next=p->next;continue;}else{if(i==m-1) q=p;p=p->next;}}printf("胜出:%d号猴子",p->num); }。
* 用数组做的，循环遍历数组，增加了一些注释，希望你能看懂。
*/#include<stdio.h>#include<stdlib.h>#include<string.h>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，被砍掉的猴子设置为1memset(Monkeys, 0, sizeof(int)*MonkeyNum);// 循环，直到选中大王while(counter != MonkeyNum){// 如果这个位置的猴子之前没有砍掉，那么报数有效if (Monkeys[position] == 0){token++; // 成功报数一个，令牌+1，继续报数直到等于M// 如果报数到M，那么将这个猴子砍去if (token == CallNum){Monkeys[position] = 1; // 设置为1，表示砍去counter++; // 计数增加token = 0; // 设置为0，下次重新报数// 如果是最后一个猴子，把它的位置打印，这个就是大王了if (counter == MonkeyNum){printf("The king is the %d monkey.\n", position+1);}}}// 下一个猴子报数position = (position + 1)%MonkeyNum;}// 释放内存，开头为所有猴子创建的桌子free(Monkeys);return;}。
“约瑟夫”问题及若⼲变种“约瑟夫”问题及若⼲变种例1、约瑟夫问题(Josephus)[问题描述]M只猴⼦要选⼤王，选举办法如下：所有猴⼦按1…M编号围坐⼀圈，从第1号开始按顺序1，2，…，N报数，凡报到N的猴⼦退出到圈外，再从下⼀个猴⼦开始继续1~ N报数，如此循环，直到圈内只剩下⼀只猴⼦时，这只猴⼦就是⼤王。
M和N由键盘输⼊，1≤N,M≤10000，打印出最后剩下的那只猴⼦的编号。
例如，输⼊8 3，输出：7。
[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变⽽来的，所以通常称为Josephus(约瑟夫)问题。
在确定程序设计⽅法之前⾸先来考虑如何组织数据，由于要记录m只猴⼦的状态，可利⽤含m个元素的数组monkey来实现。
利⽤元素下标代表猴⼦的编号，元素的值表⽰猴⼦的状态，⽤monkey[k]=1表⽰第k只猴⼦仍在圈中，monkey[k]=0则表⽰第k只猴⼦已经出圈。
程序采⽤模拟选举过程的⽅法，设变量count表⽰计数器，开始报数前将count置为0，设变量current表⽰当前报数的猴⼦编号，初始时也置为0，设变量out记录出圈猴⼦数，初始时也置为0。
每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴⼦（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴⼦作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。
然后继续往下报数，直到圈中只剩⼀只猴⼦为⽌（即out=m-1）。
参考程序如下：program josephus1a {模拟法，⽤数组下标表⽰猴⼦的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运⾏结果]下划线表⽰输⼊Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思] 时间复杂度很⼤O(M*N)，对于极限数据会超时。
猴⼦排序基本思想把⼀个⽆序的数组进⾏乱排序，然后看其是否会有序，有可能⼀次之后就有序了，也有可能很多次后依然⽆序。
最佳情况O(n)，平均O(n∗n!)，最坏可执⾏直到世界的尽头。
猴⼦排序基于⽆限猴⼦定理：⽆限猴⼦定理是数学概率的流⾏⽰例，它说明猴⼦在打字机键盘上随机敲击键，有⾜够的时间和打字机，最终将重现莎⼠⽐亚的全部作品。
根据，算法代码主体就是：while not isInOrder(num):shuffle(num)如果列表已经排序，最好的情况是O(n)。
⽽不是O(1)，因为它需要O(n) 才能找到已排序的列表。
最糟糕的情况是O(∞)，因为此算法没有上限。
缺陷乱排序，缺陷⼤得很，hh代码实现import java.util.*;public class MonkeySort {public static boolean isOrdered(Integer[] num) {for (int i = 1; i < num.length; i++) {if (num[i-1] > num[i]) {return false;}}return true;}public static void sort(Integer[] num) {List<Integer> list = Arrays.asList(num);while (!isOrdered(num)) { // 判断// System.out.println(list);Collections.shuffle(list); // 随机}}public static void main(String[] args) {Integer[] num = {3,1,2};MonkeySort.sort(num);for (int i = 0; i < num.length; i++) {System.out.print(num[i] + " ");}}}Processing math: 100%。
“约瑟夫”问题及若干变种例1、约瑟夫问题(Josephus)[问题描述]M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N 报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。
M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。
例如，输入8 3，输出：7。
[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。
在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。
利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。
程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current 表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。
每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。
然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。
参考程序如下：program josephus1a {模拟法，用数组下标表示猴子的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运行结果]下划线表示输入Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思]时间复杂度很大O(M*N)，对于极限数据会超时。
第五章数组和广义表一、选择题1. 常对数组进行的两种基本操作是（）（A）建立与删除（B）索引和修改（C）查找和修改（D）查找与索引参考答案：C2.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素( ) 的起始地址相同。
（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4]参考答案：B3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（）。
（A）80（B）100（C）240（D）270参考答案：C4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（）。
（A）SA+141（B）SA+144（C）SA+222（D）SA+225参考答案：C5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（）。
（A）SA+141（B）SA+180（C）SA+222（D）SA+225参考答案：B6.稀疏矩阵一般的压缩存储方法有两种,即（）。
（A）二维数组和三维数组（B）三元组和散列（C）三元组和十字链表（D）散列和十字链表参考答案：C7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（）。
（A）正确（B）错误参考答案：B8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i<=j),在一组数组B的下标位置k的值是（）。
（A）i(i-1)/2+j-1（B）i(i-1)/2+j（C）i(i+1)/2+j-1 (D)i(i+1)/2+j参考答案：B二、填空题1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[0][0]的地址是_____________________。
python循环报数游戏python经典面试题之一猴子报数Python循环报数游戏——Python经典面试题之一猴子报数猴子报数是一款简单却富有趣味性的游戏。
在这个游戏中，参与者按照事先约定的规则依次报数，数字超过某个指定数值的倍数时，需要说出特定单词。
本文将通过Python代码实现这个游戏，并解析这个题目在面试中的典型应用。
一、游戏规则在猴子报数游戏中，参与者按照从1开始的自然数依次报数，规则如下：1. 遇到3的倍数，需要说出"Fizz"；2. 遇到5的倍数，需要说出"Buzz"；3. 遇到同时是3和5的倍数，需要说出"FizzBuzz"；4. 其他情况下，直接说出当前数字。
例如，当参与者报数到15时，报数结果应为：1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz。
二、Python代码实现以下是使用Python编写的猴子报数游戏的代码：```pythondef monkey_count(n):result = []for i in range(1, n+1):if i % 3 == 0 and i % 5 == 0:result.append("FizzBuzz")elif i % 3 == 0:result.append("Fizz")elif i % 5 == 0:result.append("Buzz")else:result.append(str(i))return resultn = 15output = monkey_count(n)print(output)```上述代码中，我们定义了一个名为`monkey_count`的函数，该函数接受一个参数`n`，表示参与者报数的最大值。
湖南人文科技学院计算机系课程设计说明书课程名称: 数据结构课程代码:题目: 猴子选大王年级/专业/班: 06级计算机科学与技术专业一班学生姓名:学号:06408109 06408102 06408107 0640812206408103指导教师: 刘刚常开题时间: 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++下调试运行通过。
整个程序使用中文界面,并有相应的提示信息,便于操作和程序运行。
关键词：循环队列；循环链表；存储结构AbstractThis 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《数据结构》课程设计——猴子选大王一、引言数据结构是一门非常重要的基础学科，但是实验内容大都不能很好的和实际应用结合起来。
猴子选大王问题集团文件版本号：（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<iostream>usingnamespacestd;voidmain(){intn,m,a[101],k,i,j,num;//计数器是从1开始的,所以100个人用101cout<<"请输入参加游戏的玩家人数(不超过100人):";cin>>n;cout<<"----------------------------------------"<<endl;if(n>100){cout<<"玩家太多,请重新登陆此程序!"<<endl;return;}cout<<"输入游戏中要玩的数字:";cin>>m;cout<<"----------------------------------------"<<endl;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<<"最后获胜的玩家是第"<<num<<"号玩家!"<<endl;cout<<"----------------------------------------"<<endl; }写完密码约瑟夫就想到原来看到约瑟夫问题的一个数学解法很巧妙很简单不过只能推出最后一个出列的人无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。
