《烫手山芋问题》

《数据结构》课程设计报告（烫手山芋问题）学院：班级：学号：姓名：指导教师：目录一、需求分析 (2)二、概要设计 (3)三、详细设计 (4)四、调试分析 (8)五、用户手册 (9)六、测试结果 (10)七、附录 (11)1一、需求分析1.1问题描述一群小孩编号为1，2，3，…，n(n>0)围成一圈，有一个刚出锅的山芋在他们之间传递。

假设刚开始由1号拿着山芋，然后依次计数把山芋交给下一个小孩，当数到某个特定的k时，拿着山芋的小孩退出游戏，然后从下一个小孩重新开始计数，如此不断，最后剩下的那个孩子就是幸运者。

要求设计一个程序模拟次过程，并给出不同的n，k组合下那个幸运者是谁？要求：输入数据：输入n，k且n，k都为整数，n>k。

输入形式：中文提示按照n个孩子，数特定的数k的方法，输出最后剩下的那个幸运的小孩是第多少号，建立一个函数来实现此功能。

1.2基本要求（1）输入的形式和输入值的范围按照程序的规定和提示在允许的范围内输入数据，范围应该是在一定范围内的整数。

（2）输入的形式包括系统提示的语句和最后按照程序得出的结果。

（3）程序执行的命令包括构造数组；构造循环函数；构造返回函数，返回结果；运行、2输入整数n，k，得到结果；程序结束。

（4）程序所能达到的功能按照规定的提示进行相应的运行并给出合理的结果。

在用户输入信息后根据程序的要求输入用户希望得到的结果。

二、概要设计为实现上述程序功能，可以利用单向循环链表存储结构模拟此过程，输出选出得到烫手山芋的幸运小孩是第几号。

1、程序中用到的定义有：int choose 定义了一个选择函数{ int n； int k； //用来确定小孩的总数和数到的某个特定的值。

int *a=new int[k]；//用来申请动态内存空间。

int x；int sum//一个用来累积计数初始化，另一个是用来循环计数的。

}然后定义了一个核心的算法，用while语句来选择淘汰的小孩，当选择完毕后再用for循环语句来确定最后拿到烫手山芋的那个小孩。

Void main 主函数，主要用来提示用户输入相应的数字，然后调用相应的函数算出需求的数字，再将最后结果输出。

32、函数中的调用关系；在choose函数中使用了两个循环函数，分别用了while循环，for循环。

主函数调用了choose 函数并输出了最后得到山芋的那个幸运小孩。

三、详细设计a)创建主函数的代码表示如下：void main(){int n,k；cout<< "请输入小孩的总数和数到的某个特定值："；cin>>n>>k；cout<<"第" <<choose(n,k)+1<<"个小孩拿到烫手的山芋"<<endl；}在主函数中我们首先让使用者根据我们的提示输入数据，然后将数据传输给程序，当程序运行完成后输出结果。

b)刚开始时所需要的定义如下：int choose (int n, int k)//定义小孩的总数和数到的某个特定值{4int i;//给孩子编号int *a=new int[k];//申请动态内存空间int sum=0; //循环计数int x;//用来做累积计数的c)然后就是算法的主要思想我所希望的算法是：用一个含有n个元素的数组a，初始时a[i]中存放孩子的编号i，计数器sum的值为0。

从a[i]开始循环报数，每报到k时，便打印出a[i]的值（退出圈外的孩子的编号），同时将a[i]的值改为0（以后他不参加报数），计数器的值重新置为0。

该函数一直进行到n-1个孩子全部退出圈外为止，最后剩下的那个孩子就是拿到烫手山芋的。

然后给所有的孩子一个标号，首先全部为1号，如果在运行中1号被修改为0号了，那么对应编号的孩子就被淘汰了。

for(i=0;i<k;i++)a[i]=1;//孩子状态初始化，1表示可能拿到烫手山芋，0表示没有希望了。

先进行编号然后进行标记。

x=k;//累积计数初始化，大于1表示还有人“抢”山芋这个时候注意了，一定要先给一个x用来累积计数的数值，并且要是个动态变化的，先给每个小孩有得到山芋的机会，所以令x=k。

接下来就应该进入第一个循环了。

5while(x>1){x=0;for(i=0;i<k;i++){sum+=a[i];if(sum==n)sum=a[i]=0;//淘汰倒霉孩子x+=a[i];}}在这个循环中我们要注意到三个问题第一是最后只能有一个出来，所以必须是在x>1的情况下进行循环，不然这个循环就没有意义了。

第二是必须要使x=0，不然在运行中便无法运行。

虽然提示时并没有出错。

第三是sum=0也不能忘记了，不然后面不认识这个动态数值，第二个也不认识x这个数值。

在程序里面也还得注意到淘汰孩子时也必须同时将相应的数值附为0，这样就不会影响后面程序的运行了。

在这个循环中里面有个for循环，这个循环就是本函数的核心所6在，在这个循环里首先要定义号初始值，然后在判断一遍后必须时值进行相应的恢复，不然以后的程序就无法进行了，这个是相当重要的。

在程序里变量的位置也是十分重要的。

有些值一开始就要固定好，淡有些值是要随程序的响应而变化的，并且其中有些变化后还得还原，这是中间特别容易犯的错误。

d)另外一个循环的代码如下：for(i=0;i<k;i++)if(a[i]!=0)return i;//找到幸运孩子编号（从0开始）在这个循环中，是将其中唯一一个标记为1的小孩选择出来。

刚才我们已经完成了选择，接下来就是通过一个循环把这个1对应的小孩的编号找到，并通过已经给好的动态数值将其返回后表达出来，这样才能算是完成了整个选择。

但在这个程序中一定要注意我们的小孩编号从什么开始的，如果从0开始则主函数中一定要加上1，如果从1开始，则函数本身没有错误，但在逻辑上有错误，因为数组都是从0开始的，这一点要切记。

e)函数的调用关系图反映了演示程序的层次结构：7Main总的来说，这个函数是主函数调用了上面的选择函数，关系不复杂，比较容易理解和运行。

四、调试分析1、刚开始时曾忽略了一些变量参数的标识，使调试程序时费时不少。

今后应重视确定参数的变量和赋值属性的区分与标识。

2、忘记给定义的数值赋初值，这使得我在很多时候不知道运行时为什么数值总是不怎么变化。

3、 不懂得函数之间数值的连接，没处理好数值之间的关系使得我在写程序的时候总是被弄得晕头转向。

4、 主要的运行函数不会完整的表达出来，总是要少一些东西，所以对于程序的完整性没有把握好。

5、 算法的时空分析：先用一个函数choose 来淘汰一些小孩，然后用while 循环和for 循环函数来选择和确定拿到烫手山芋的那个幸运小孩，再用一函数返回那个拿到烫手山芋的幸运小孩的编号，最后用主函数输出结果。

86、本实习作业采用循环结构的程序设计方法，将程序划分choosewhile for为三个层次结构，使得设计时思路清晰，实现调试顺利，各函数之间具有较好的连接，确实得到了一次良好的程序设计训练。

五、用户手册进进入演示程序后即显示文本方式的用户界面：输入小孩总数后按空格再输入数到的某个特定值，最后按回车键即显示出我们所要的结果了。

9六、测试结果例如：我们输入10 3程序内部便开始了运行，图表解释如下：12345678910 111111111 1 110111111 1 110110111 1 110110110 1 100110110 1 100110010 1 000110000 1 000100000 1 0001000000然后由最后留下来的1对应的号码把它传给变量i，最后再通过函数将数值i+1输送出来。

敲下回车键，即显示出:第4个小孩拿到烫手的山芋结果清单：10七、附录1、源程序清单：2、#include "stdafx.h"3、#include <iostream>4、using namespace std;5、int choose(int n,int k)6、{7、int x;8、int i;9、int*a=new int[k];//申请动态内存空间10、for(i=0;i<k;i++)1111、a[i]=1;// 孩子状态初始化，1表示可能拿到烫手山芋，0表示没有希望了。

12、int sum=0;//循环计数13、x=k;// 累积计数初始化，大于1表示还有人“抢”山芋，为0表示没有希望了14、while(x>1)15、{16、x=0;17、for(i=0;i<k;i++)18、{19、sum+=a[i];20、if(sum==n)21、sum=a[i]=0;//淘汰倒霉小孩22、x+=a[i];23、}24、}25、for(i=0;i<k;i++)26、if(a[i]!=0)27、return i;//找到幸运小孩编号（从0开始的）28、 }1229、void main()30、{31、int n,k;32、cout<< "请输入小孩的总数和数到的某个特定值："<<endl;33、cin>>n>>k;34、cout<< "第" <<choose(n,k)+1<< "个小孩拿到烫手的山芋" <<endl;35、}结论对于数据结构课程设计，我学到了进行一个设计由三点很重要：一个是细心，一个是尝试，还有就是要沉得住气。

刚开始的时候我一直就为选择哪个题目而为难，后来我结合自己所学的知识选了个与书本很接近，而且比较容易的题目，这样一来可以多参考一下书本，并且也能发挥自己的想象。

看自己打算如何借鉴和修改一下使之成为自己的。

从整个情况来看我觉得更多的还是自己的尝试。

因为毕竟和书本不同加上自己学得也不是很好，所以不断的出现问题，需要不断的修改，修改以后还是会出现问题，又得改。

这样往复多次，很多情况下想放弃，因为不知道到底哪里出了错，当时人很气愤。

可是一个为了完成的需要而且想继续取得好成绩吧，我还是沉下心来好好的体会失败，13最后在老师和同学们的帮助下我还是做完了这个课程设计，我心里还是很高兴的。

所以我觉得细心、尝试、沉得住气是很非常重要的，再次感谢老师的教导！！14。