C语言教学 第20章.ppt

1、第20章猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,第20章猴子选大王游戏,问题描述 问题分析及实现 开发过程常见问题及解决,猴子选大王游戏,猴子选大王（亚瑟夫环）是数据结构和算法中常见的一类问题。有人使用循环队列实现，有人使用链表实现。本章将使用数组的回溯算法实现选猴王的算法程序。,20.1 问题描述,有M只猴子围成一圈，每只各一个从1到M中的编号，打算从中选出一个大王；经过协商，决定出选大王的规则：从第一个开始循环报数，数

2、到N的猴子出圈，最后剩下来的就是大王。 在本章，我们以此问题作为研究对象，通过编写程序，来输出站成一圈猴子的出圈顺序号。,20.2 问题分析及实现,20.2.1 问题分析 20.2.2 问题实现 20.2.3 程序运行,20.2 问题分析及实现,拿到这个算法问题，首先想到的前面提到的要领：看清、想明、把握每一个细节。 根据问题描述可知，我们要实现的是输出猴子出圈的顺序。简单举例：9个猴子数到3出圈，则应打印：3，6，9，以下将仔细地分析问题并实现算法。,20.2.1 问题分析,而我们的将要开发的程序，就是为了使这些猴子最后留下大王，每个淘汰出圈的猴子。这里将猴子进行顺序编号。 假设猴子编号从1

3、开始至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

4、*/ 04 int i,j,k,temp; 05 int MonkeyMAX,S; 06 void init() 07 08 for(i=0;iMAX;i+) 09 Monkeyi=i+1; 10 for(i=0;iMAX;i+) 11 printf(%d ,Monkeyi); /*让猴子站成一圈*/ 12 printf(n); 13 ,20.2.2 问题实现,2. 将结果输出 将回溯结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf，将结果回显。代码如下（代码20-2.txt）,20.2.2 问题实现,01 void output() 02 03 printf(猴子淘汰出圈的

5、顺序是:nr); 04 for(i=MAX-1;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, 20 ,20.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入出队的序数，即数到几就出列，按【Enter】键，输出结果如下。,20.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 有时，如果程序修改后，查看不到结果的变化，需要仔细阅读程序，看是否有地方修改错误。 此程序的难点之一是如何正确理解回溯算法，这是程序设计中的一个难点。本章的算法，类似于堆