C语言教学 第20章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,*,*,第,20,章,猴子选大王游戏,问题描述,问题分析及实现,开发过程常见问题及解决,第,20,章,猴子选大王游戏,问题描述,问题分析及实现,开发过程常见问题及解决,第,20,章,猴子选大王游戏,问题描述,问题分析及实现,开发过程常见问题及解决,第,20,章,猴子选大王游戏,问题描述,问题分析及实现,开发过程常见问题及解决,猴子选大王游戏,猴子选大王（亚瑟夫环）是数据结构和算法中常见的一类问题。有人使用循环队列实现，有人使用链表实现。本章将使用数组的回溯算法实现选猴王的算法程序。,20.1,问题描述,有,M,只猴子围成一圈，每只各一个从,1,到,M,中的编号，打算从中选出一个大王；经过协商，决定出选大王的规则：从第一个开始循环报数，数到,N,的猴子出圈，最后剩下来的就是大王。,在本章，我们以此问题作为研究对象，通过编写程序，来输出站成一圈猴子的出圈顺序号。,20.2,问题分析及实现,20.2.1,问题分析,20.2.2,问题实现,20.2.3,程序运行,20.2,问题分析及实现,拿到这个算法问题，首先想到的前面提到的要领：看清、想明、把握每一个细节。,根据问题描述可知，我们要实现的是输出猴子出圈的顺序。简单举例：,9,个猴子数到,3,出圈，则应打印：,3,，,6,，,9,，以下将仔细地分析问题并实现算法。,20.2.1,问题分析,而我们的将要开发的程序，就是为了使这些猴子最后留下大王，每个淘汰出圈的猴子。这里将猴子进行顺序编号。,假设猴子编号从,1,开始至,30,，则以数到,3,为例，从,1,开始数猴子，至第三只猴子时，出圈，此时，圈子应该有,1,，,2,，,4,，,5,，,630,，则继续从第,4,只从头数起，将第,4,只猴子做为第,1,号，依此类推，这样，就产生了出圈的顺序号：,3,，,6,，,9,，,12,，,15.29,，那么最后出圈的猴子即为猴王。,20.2.2,问题实现,本小节就通过编程来实现此问题，实现的代码如下。,1.,让猴子站成一圈,如何让猴子站成一圈呢？根据问题分析结果，采用整型一维数组中保存猴子顺序号，即表示站成一排。代码如下（代码,20-1.txt,）。,20.2.2,问题实现,01 #include,02 #include,03 #define MAX 30/*,定义猴子总数为,30*/,04,int,i,j,k,temp,;,05,int,MonkeyMAX,S,;,06 void init(),07 ,08,for(i,=0;i,MAX;i,+),09,Monkeyi,=i+1;,10,for(i,=0;i=0;i-),05,printf,(,第,%3d,只猴子出圈,!,nr,Monkeyi,);/*,输出结果*,/,06,printf,(,猴王是,:,第,%d,只猴子,nr,Monkeyi+1);/*,输出结果*,/,07 ,20.2.2,问题实现,3.,回溯法求猴子出圈顺序,在主程序中，要求用户输入出队序数，即数到,S,，就让序号是,S,的猴子出队。回溯法是：将猴子总个数循环，第一次循环都是将当前需要出圈的猴子排到数组末尾。这样，当全部猴子循环一遍后，数组头的猴子即为猴王。从数组尾开始向头循环输出，即为猴子出圈序列。代码如下（代码,20-3.txt,）,20.2.2,问题实现,01 void main(),02 ,03 init();,04,printf,(,请输入出队的序数：,);,05,scanf(%d,&S,);/*,读取猴子出队序数*,/,06,07,for(i,=MAX-1;i=0;i-),08 ,09,for(k,=1;k=,S;k,+),10 ,11 temp=Monkey0;,12,for(j,=0;j,i;j,+),13 ,14,Monkeyj,=Monkeyj+1;,15 ,16,Monkeyi,=temp;,17 ,18 ,20 output();,20 ,20.2.3,程序运行,单击,【,调试,】,工具栏中的按钮，根据提示输入出队的序数，即数到几就出列，按,【Enter】,键，输出结果如下。,20.3,开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。, 有时，如果程序修改后，查看不到结果的变化，需要仔细阅读程序，看是否有地方修改错误。, 此程序的难点之一是如何正确理解回溯算法，这是程序设计中的一个难点。本章的算法，类似于堆栈的概念，要从这个方面理解会容易的多，通过回溯求解，把数组看作是,后进先出,的堆栈，将求出的第一个解放置到数据最末，即“栈”底部，最后一个解放置到“栈”顶，但输出结果时，从“栈”底输入。,