算法经典“钓鱼”问题详解 基于贪心算法

初始条件

在一条水平路边，有 n2 ≤ n ≤ 25个钓鱼池，从左到右编号为1、2、3、……、n。小明有H1 ≤ H ≤ 16个小时的空余时间，他希望用这些时间钓到尽量多的鱼。他从池塘1出发向池塘n走，有选择地在一些池塘边停留一定的时间钓鱼，最后在某一个池边结束钓鱼。小明测出从第i个池塘到第i+1个池塘需要走5Ti分钟的路。还测出在第i个池边停留，第一个5分钟可以钓到鱼量Fi，以后再每钓5分钟鱼，鱼量减少Di。假设没有其他人钓鱼，也没有其它因素影响小明钓到期望数量的鱼。

要求完成的主要任务

基本要求

请编程求出能钓最多鱼的方案。很显然，在分析本题数据前你需要首先构造出数据。

究竟在应该每个池塘停留多久？这正是需要你通过算法进行计算的。上述表格的具体数值可以通过随机函数生成，但你得注意不要让首个5分钟可以钓到的鱼量和每隔五分钟减少的鱼量的差值太过离谱。

另外，由于输出内容较多，一屏往往显示不完，所以输出结果必须保存到文本文件中以便单独查看。

输入输出

总过有多少个池塘，以及小明总共有多少时间，可以在程序运行时从键盘输入。上述表格数据应提供两种方式输入：1)通过随机函数生成，且可以二进制形式保存到用于输入的文件中；2)通过输入文件读入。

经过计算以后的输出格式（示例）为：见1.4 数据输出的形式

实现提示

从题目可以看出，小明每做一件事情所花费的时间都是5分钟为一个基本单位，因此可以直接用5分钟作为一个基本计时单位来简化处理方式。尽管各个池塘的可钓鱼量并不均等，但我们可以假定这些池塘是按照鱼量从大到小排列的（想想看为什么？），然后枚举这些池塘每一个可操作时段的理论收获值，并通过贪心算法来计算最大可钓鱼量。亦即可以每次选一个鱼最多的池塘钓一次鱼，对于每个池塘来说，由于在任何时候鱼的数目只和小明在该池塘钓鱼的时长有关，而和钓鱼的总时长无关，所以这个策略一定是最优的。问题只在于，每个池塘是否应该一直钓到无鱼可钓为止？这就是需要你动脑筋去思考的问题了。如果这个问题你能找到一条清晰的思路来解决，将对你的编程思维模式起到极好的锻炼作用。

1. 需求分析

1.1 题意解析

依题意，这是一个使用贪心算法求最值的问题，但它又不是简单的找到鱼最多的池塘然后去钓鱼的问题。对于本题而言，题目主人公的时间有限，每次钓鱼会消耗时间，主人公在池塘间移动也会消耗时间，作者需要在有限的时间内，帮助主人公获取最多的鱼。另外，池塘也是动态的，在主人公钓鱼后，下一次钓鱼的数量会减少。本课题转换成算法导向后的表述形式为：

对于有n条记录的顺序表，已知每条记录的索引值i、到达鱼塘所需时间ti、钓五分钟鱼可获得的鱼量fi、每次钓鱼后鱼量减少量di和小明拥有的时间T小时。小明每钓一次鱼会消耗5分钟，同时该池塘fi递减为fi-di。设小明最远走到第m个池塘m<n，一共钓了c次鱼，需要求在 情况下，得总收获鱼量S最大值。

1.2 数据的输入形式

根据题目要求，数据需要从二进制文件中读入或者由程序随机生成。但仍然需要保留人工由键盘输入的输入模式，以生成测试用的二进制文件，便于后期测试与调试。

1.3 数据输入的范围

此题中的数据需要输入的有：钓鱼总时间、池塘个数以及每个池塘对应的信息。依题意，钓鱼总时间为H小时，1 ≤ H ≤ 16；池塘个数n个，2 ≤ n ≤ 25。

具体到每一个池塘的数据，题目要求不要让首个5分钟可以钓到的鱼量f和每隔五分钟减少的鱼量d的差值太过离谱。根据分析，对它们进行d不得高于f的1/2，并且不得少于十分之一，即⌊f/10⌋ < d < ⌊f/2⌋的约束是比较合理。另外，题目还未规定每个池塘具体参数的数据，结合客观实际的钓鱼场景，现设定5≤ t ≤ 40（分钟），3 ≤ f ≤ 40，1 ≤ d ≤ 20。

1.4 数据输出的形式

根据题目要求的输出格式，主要以文本的形式分别在终端和文件中输出，输出中包括题目主人公的钓鱼时间，池塘的总数和各池塘的具体参数，以及在每一个池塘中钓鱼的具体过程：前往某个池塘花了多久，停了多长时间，每五分钟钓了多少的鱼还有获得鱼的总量，最后还要有路途耗时、钓鱼耗时、总计耗时和获得鱼量的总数统计信息。该输出方式直观清晰，数据量大，不仅能清晰的反映钓鱼的过程和结果，还便于程序的调试。具体如下：

小明拥有的时间：H小时，合计60H分钟池塘总数：n各池塘参数：池塘编号行程时间首次鱼量递减鱼量1t1f1d12t2f2d2……具体过程：抵达1号池塘：花费时间t1分钟，停留时间c1分钟，获得鱼量f1+(f1-d1)+(f1-2*d1)+…抵达2号池塘：花费时间t2分钟，停留时间c2分钟，获得鱼量f2+…抵达3号池塘：花费时间t3分钟，停留时间c3分钟，获得鱼量f3+(f3-d3)+f3 mod d3=………最终统计结果，小明路途花费合计xxx分钟，在各池塘停留合计yyy分钟，总计耗时zzz分钟，获得鱼量合计www条。

虽然该输出由以上的优点，但在c语言程序实现中略显麻烦。特别是在每一个池塘的具体过程的输出中，不同的钓鱼情况会有不同的输出：没有停留的池塘，直接输出0；停留了一次的池塘，直接输出fi；停留了多次的池塘，需要根据停留次数输出(fi-c*di)，且第一次是fi，第二次是(fi-di)，最后一次是(fi-c*di)或者fi mod di的值，并且在最后带上“=该池塘收获总量”。

1.5 程序目标

（1）通过文件或者随机的形式获取池塘和小明的数据；

（2）人工或者随机生成池塘数据并保存在二进制文件当中；

（3）将获得的数据正确地计算为正确并带有过程的结果；

（4）显示从文件读取或者随机生成的数据；

（5）显示每一步详细的计算过程；

（6）显示最终的结果；

（7）在输入错误或非法时做出正确的响应并提供重新输入的机会；

1.6 测试数据

（1）池塘个数：n，2 ≤ n ≤ 25，特别是2与25。

（2）空闲时间：H，1 ≤ H ≤ 16，特别是1。

（3）具体池塘参数：5≤ t ≤ 40，3 ≤ f ≤ 40，1 ≤ d ≤ 20，特别是d = f/2和d = f/10。

（4）每个池塘参数相同的情况。

（5）空闲时间大于钓完所有鱼的情况，空闲时间刚好够钓完所有鱼的情况，使用不同时间钓鱼结果相同的情况，一般情况。

（6）需要人工输入时不合法数据。

2. 概要设计

2.1 算法思路

由题目描述，小明所有的行为都是以5分钟为单位进行，故在分析以及程序实现的过程中将小时、分钟等时间简化为每五分钟为一个单位的形式来表达。

小明钓鱼只有一条路，只能在该条路上前进后退，而每个池塘每五分钟可获得鱼的数量与小明在哪以及从哪来无关，且后退消耗的时间必将导致钓鱼的时间减少。故无需考虑小明钓鱼时是否会回头选择池塘钓鱼，只需要考虑在每个池塘停留的时间。根据题目提示，使用贪心算法，计算时直接考虑在当前情况下可钓鱼的最多的池塘，进行一次钓鱼并记录收情况和鱼量变化情况，然后根据鱼量重新排序池塘，再去鱼最多的池塘钓鱼，重复以上过程，直至鱼钓完或者是时间用完停止。

但问题出现了，如何确定小明最远要去到几号池塘呢？这就需要通过循环的方式，从每个池塘都钓鱼开始计算，计算到只在一个池塘中钓鱼的情况，然后通过比较，确定钓鱼数量最多，以及用时最少的情况输出。

具体的算法思路是：

1）将n个池塘根据首次鱼量由大到小排序；

2）将小明空闲时间扣除掉前往这些池塘的路途时间之和；

3）小明“前往”鱼最多的池塘钓鱼，该池塘的首次鱼量减掉递减鱼量，小明的空闲时间扣除此次钓鱼的时间；

4）重新根据首次鱼量排序池塘；

5）重复3）至4）步，直至鱼钓完或者是时间用完，记录下钓鱼过程、钓鱼用时以及获得的鱼的数量；

6）恢复所有池塘到初始状态，剔除最远的一个池塘，重复1）至5）步，直至计算到只剩一个池塘；

7）比较不同池塘数量情况下的钓鱼用时和获得鱼量，选择用时最短、鱼量最多的情况保存输出。

2.2 技术路线

数据存储

池塘在一条水平路边，不会有池塘的删除或者插入，非常适合使用顺序表，C语言中的数组来存储。但在上述的算法中，涉及到对池塘排序，不可使用池塘存储时的数组索引来标识池塘，需要另外增加一个属性。

每一个池塘有行程时间、首次鱼量、递减鱼量三个重要属性，这些在C语言中可以使用int型来存储。另外，为了唯一地标识每一个池塘，池塘还需要加一个编号，也使用int型存储。综上，在本题中，一个池塘在C语言中使用一个由四个int组成的结构体存储。

数据初始化

本题中数据来源有随机生成，为了降低程序的复杂性，初始化池塘数据一律使用随机生成，随机出来的数据符合题目要求和以上的规定。人工输入数据时直接覆盖随机生成的数据，不再单独初始化。

排序

以上算法中涉及到两次排序，一是在钓鱼前，根据首次鱼量排序，二是恢复初始的池塘状态，即根据编号排序。根据鱼量排序时，不妨设想以下情景：小明只剩一次钓鱼的机会，有两个池塘都有着最大的相同的首次鱼量，如果小明去更远的地方钓鱼，就意味着将鱼送回家时需要花费更多的力气，不太划算。因此，在进行根据鱼量的排序时，对排序算法的稳定性有要求，故使用冒泡排序的方法。但在根据编号排序时，由于编号不可能相同，因此就没必要要求排序算法的稳定性，使用快速排序。当然，本题需要排序数据量最高也不到30，无论是冒泡排序还是快速排序，虽然时间复杂度上不同，但在实际程序中的时间表现差别不大。

钓鱼过程记录

由于钓鱼过程需要在程序中多次计算然后比较，不适合与池塘数据绑定在一个结构体中。而所谓钓鱼过程，经分析，可以仅仅由某次过程所达最远的池塘编号和在每个池塘停留的时间组成，即可完整的表示一次钓鱼的过程。因此，使用一个辅助数组来存储每个池塘的停留时间。其中，数组的索引对应池塘的编号，所存储的值就是停留的时间单位。

模块设定

在上述算法中，多次涉及到给定范围随机数生成、给定关键字排序，以及在不同条件下都要进行的内存分配、“钓鱼”过程等。另外，由于此题的输出较为复杂，输出将为单独的模块。故本程序将设有获取时间、获取给定范围随机数、输出池塘数据、用户提示界面、池塘数组生成、钓鱼、输出钓鱼结果、排序等模块。

调试手段

一是通过在程序中使用打断点等手段，观察其中间数据以及内部数据的变化实现代码调试与优化。二是通过程序的随机数据生成，让程序多次完成完整的计算过程并输出结果，因为此题输出完整、详细，可以通过观察输出来判断是否有错误，并结合一的方法调试。三是人工设计若干简单而又处于临界值部分的数据，进行手工计算后通过程序的人工数据生成功能输入到程序中计算，比较计算结果来判断运行正误，进而调试。

程序运行模式

程序利用C语言中goto语句实现循环的运行模式，避免用户反复启用程序不方便。在程序开始时，用户可以选择若干个程序功能，每次运行完后回到功能提示处运行，直至用户主动退出。

2.3 抽象数据类型

ADT 池塘 Pond {数据对象：pond是一个存储有一个池塘所有数据的结构体，该结构体由四个int型数据构成。数据关系：集合结构，每个pond必有4个int。基本操作：initRandomPond()操作结果：随机生成一个池塘，数据范围为题目规定。swapPond(Pond1, Pond2)初始条件：两个池塘数据存在。操作结果：交换两个池塘的数据。}

ADT 池塘顺序表 Ponds {数据对象：Ponds是一组数据池塘的集合。数据关系：线性结构，其中必存在唯一的一个“第一池塘”，必存在唯一的一个 “最后池塘”，除最后一个池塘之外，均有唯一的后继，除第一个池塘之外，均有唯一的前驱。基本操作：pondsArry(length, ponds)操作结果：随机初始化一个长为length的ponds顺序表。printPonds(ponds, len, file)初始条件：文件与ponds存在。操作结果：在终端格式化输出前len个池塘的数据，并格式化写入到file文件中。sumRouteTime(ponds, amount)初始条件：ponds存在。操作结果：计算ponds中到达第amount个池塘所需时间。copyArry(Ponds1, Ponds2, length)初始条件：(Ponds1存在。操作结果：将Ponds1中前length池塘的数据复制到Ponds2中。sortPondsByFish(ponds, amount)初始条件：ponds存在。操作结果：ponds中前amount个池塘按首次鱼量从大到小存储。sortPondsByIndex(ponds, amount)初始条件：ponds存在。操作结果：ponds中前amount个池塘按编号从小到大存储。goFishing(freeTime, ponds, pondAmount)初始条件：ponds存在。操作结果：计算在freeTime下，小明在前pondAmount个池塘中钓鱼的过程与获得鱼的数量。fishingRecord(freeTime, ponds, process)初始条件：ponds存在。操作结果：根据process和freeTime输出小明在ponds钓鱼过程。}

2.4 主程序流程

程序启动后，有五个选项，用户选择具体功能运行，运行完成后回到功能选择界面，直至用户主动结束运行。具体过程如图。

具体的，计算钓鱼过程模块的描述详见2.1算法思路中的具体思路，这里给出其流程图。

其中恢复所有池塘模块调用了排序模块。

3. 详细设计

详细设计部分包括数据结构和宏定义、功能选择和循环运行的具体实现、原题中部分问题的解答。

3.1 数据结构和宏定义

由于本题的池塘在一条路上，数据结构采用顺序表，较为简单，程序内仅使用结构体和数组。

typedef struct{int index;int distance;int fish;int decrease;} Pond; // 池塘数据

为提高程序的可读性，且便于后期的调试与修改，使用如下的宏定义：

#define MAX_DISTANCE 8// 池塘间的最大距离#define MIN_DISTANCE 1// 池塘间的最小距离#define MAX_FISH 40// 池塘一次最多可以钓的鱼#define MIN_FISH 3// 池塘一次最少可以钓的鱼#define MAX_DECREASE 20 // 池塘每次鱼量递减的最大值#define MIN_DECREASE 1// 池塘每次鱼量递减的最小值

3.2 功能选择和循环运行的具体实现

功能选择方面，实现方法是用户输入对应功能序号，通过if…else if…else与句实现，不仅可以精确且高效的使用if来识别用户需求，还可以通过else便捷过滤非法的输入。

虽然现行主流编程风格中不建议使用goto语句，但在这次解题过程中，在功能选择和循环运行的实现上面，goto语句是非常方便且简洁的。无需像嵌套使用while语句一样，在结束某段过程时，需要使用多层break语句与标志变量。

使用goto语句，还带来了更简洁高效的错误与非法输入的处理方式。在内存分配出错或者是用户输入了非法内容时，在终端输出相关错误信息后，直接跳转到功能选择模块。不仅在代码层面实现简单，逻辑清晰，更有几乎无痛的用户使用体验。

3.3 原题中部分问题的解答

为什么可以假定这些池塘是按照鱼量从大到小排列的？

本题使用贪心算法实现，通过单次钓鱼收获最多来达到总的钓鱼过程收获最多，在算法逻辑的层面上，可以看作是池塘按照鱼量从大到小排列。而且，虽然在计算时鱼塘是当作从大到小排列，但实际上钓鱼的过程仍是从池塘编号由小到大依次进行。所谓的钓鱼过程，只是每个池塘的停留时间以及最远走到那个池塘，与池塘的排序无关，这一点在程序中具体算法模块和分步输出模块分离中有所体现。另外，池塘与的数量也与小明在那个池塘，小明从哪里来无关，仅仅与小明是否在此有过停留、停留了多久有关，这也说明了计算时无需考虑池塘的排序。

每个池塘是否应该一直钓到无鱼可钓为止？

这个问题作者认为无需单独考虑。因为在算法计算时，不会考虑每一个池塘的情况，而是比较整个池塘数组中的鱼量，选择鱼最多的池塘前往钓鱼。算法在决定在哪一个池塘边多停留一会儿时，不会考虑某个池塘离无鱼可钓还要多长时间，而是考虑哪一个池塘在现阶段下，分配一个单位时间可以获得的鱼最多。这一点与亚当·斯密《国民财富的性质和原因的研究》中的“借由追求他个人的利益，往往也使他更为有效地促进了这个社会的利益，而超出他原先的意料之外。”有些神似。

4. 调试分析

4.1 Debug

生成数组的结果全为“垃圾数据”

在编写池塘数组随机初始化的函数后的调试中，作者发现池塘数组初始化出来的内容为“垃圾数据”，并没有按照给定的规则随机生成数据。分析函数中代码块，也未发现错误。最终，将错误定位到函数参数传递上。初始设定的函数原型为：

int pondsArry(int length, Pond *ponds)

意为生成指定长度的数组，存储在ponds中。然而，本函数的想法是在函数中通过malloc()函数开辟一段length*sizeof(Pond)长的空间，然后将首地址传出去。然而，通过以上函数原型设定，却是将新生成的内存指针传入到原有的ponds数组内存储了，而非改变原来数组的内存地址。正确应将函数原型修正为:

int pondsArry(int length, Pond **ponds)

通过指针的指针，完成修改数组地址的目的。然而，使用return语句的方式将指针变量从函数内传出来更加方便、直观：

Pond* pondsArry(int length)

池塘还有鱼，时间尚充足，却停止钓鱼输出结果的问题。

根据单步运行方法调试发现，在计算钓鱼过程的模块中，用于记录小明剩余时间的freeTime变量在一次循环中扣除掉路途耗时后并没有恢复到扣除路途耗时前的时间，而是在被扣除的情况下继续进入了下一循环。导致计算出来的结果时间没有用完，鱼也没有钓完。最后通过在进入循环前，新建一个freeTimeRemain变量，用于循环时计算。

4.2 输出控制

在刚刚完成输出模块代码的时，作者并没有深入研究输出部分，特别是具体过程部分的输出。输出的控制仅仅是根据输出时，根据小明是第几次停留池塘钓鱼来确定输出的内容。然而在后续的测试输出中，作者发现输出模块并不简单，需要通过分类的方式来确定输出内容。

首先，作者发现，在每一个池塘需要钓鱼钓到无鱼可钓的情况下，最后一次输出要分类。不可以单纯的输出(f-c*d)，因为f不一定可以被d整除，这个值可能小于0，不符合输出要求。因此需要在输出前判断f是否可以被整除，然后再来输出结果。

然后，作者发现在输出第一次停留时，也要十分小心，停留一次和不停留这两种情况需要另外单独考虑。在停留一次时直接输出f，不停留时输出0。同时还要调整第二次停留时输出的样式，(f-1*d)在示例中并没有出现，需要单独写一个判断分支用于输出(f-d)。

4.3 编码问题

调试过程中发现，使用VS CODE编写的程序在学工办助理位的电脑上虽能正常打开运行，但中文无法正常显示，显示为乱码：

------------------------------------------------------------| 娆㈣繋浣跨敤"閽撻奔闂"妯℃嫙绋嬪簭锛岃杈撳叆搴忓彿寮€濮?| [1]闅忔満鐢熸垚2~25涓睜濉樺苟瑙ｅ喅闂锛?| [2]浠庢枃浠朵腑璇诲彇姹犲淇℃伅骞惰В鍐抽棶棰橈紱| [3]闅忔満鐢熸垚姹犲淇℃伅骞朵繚瀛樺埌鏂囦欢褰撲腑锛?| [4]浜哄伐鐢熸垚姹犲淇℃伅骞朵繚瀛樺埌鏂囦欢褰撲腑锛?| [0]閫€鍑虹▼搴忋€?------------------------------------------------------------

通过观察学工办的设备与我的代码，发现VS CODE默认使用的是UTF-8编码，而部分老旧设备控制台默认使用GBK编码。为了对更老的设备兼容，本课程设计使用GBK编码，并在程序运行时强制调整终端编码为GBK

system("chcp 936 > NUL"); // 确保不同设备正常显示

同时在程序运行前提示用户，告知用户在打开文件形式的输出结果时，也需要注意编码情况：

!!!输出结果文本文件将会保存到程序文件所在目录的" output.txt "中。!!!本程序使用的编码是" GBK "，保存和读取的文件是64位机器的二进制文件。

此外，我认为在报告中放置控制台应用的截图是不合适的行为，控制台应用的输出就是纯文本形式，没有必要将文本截图转换为图片放置。

4.4 时空分析

时间复杂度

很显然，通过上述的主程序流程图和各模块设定描述，本程序主要耗时在计算钓鱼过程模块和输出钓鱼结果模块。在计算钓鱼过程模块中，有两层循环嵌套，一是从远到近选择池塘的循环，而是每一种情况下钓鱼的循环。第一层会循环n次，而里面一层情况较为复杂，循环的次数和小明剩余时间和每个池塘递减鱼量、首次鱼量有关。为了方便讨论，这里将时间视为充足，讨论最坏情况下的时间复杂度。最坏情况下，n个池塘小明都要去把鱼钓完，每个池塘的d都是f的十分之一，则一共要进行10*n次钓鱼。作者注意到，在每次钓完鱼后，都有一个根据首次鱼量排序的过程，使用的是冒泡排序，时间复杂度是O(n^2)。总之，在最坏情况下，计算部分的时间复杂度高达O(n^3)。

作者发现，在冒泡排序只是为了求得最大值，是没有必要的，直接通过比较法求最大的值返回池塘编号即可，这样总体的时间复杂度可以降低到O(n^2)。但更深入思考发现，除了第一次的排序，每一次冒泡排序只是在改变了一个关键字的情况下，在原来有序的表中继续排序，其时间复杂度最坏也是n，所以作者认为，虽然最坏情况下时间复杂度为O(n^3)，但最坏的情况不是本算法面对的主要情况。更主要的情况是类似于在有序表中插入一个元素，其时间复杂度为O(n)，总的时间复杂度为O(n^2).

其他部分的时间消耗与上述钓鱼模块互为并列关系，快速排序时间复杂度为O(nlogn)，输出时间消耗略显复杂。输出时，会根据池塘个数n循环，在输出每个具体的钓鱼情况时，又是一个根据停留次数最大10*n的循环，时间复杂度为O(n^2)。总之，本题的时间复杂度有三个部分导致，分别为O(n^2)、O(nlogn)、O(n^2)，总的时间复杂度为O(n^2)。

空间复杂度

本题的数据都存储在一个顺序表中，空间复杂度为O(n)。在后续流程中，会有钓鱼情况辅助数组的创建，计算钓鱼过程模块中排序后数组的创建，额外造成2*n的存储空间消耗，但每次在循环中为覆盖写，没有更大的消耗。总的来说，空间复杂度为O(n)。

4.5 经验和体会

Debug时，使用单步调试是非常有用的。单步调试清晰地展示了在面向过程的编程中，数据在每个过程中的流动方式。其可以清晰地展示程序逻辑，让编程者快速、准确地了解到程序的走向是否与自己的期望一致，快速做出Debug方案。

在面对大量分支的流程时，需要提前分类，理清不同分支中的相同点，便于后续编程。在理清了分支后，还可以做到减少分支数量，降低分支嵌套的层数，提高运行效率和增强程序的可读性。

贪心算法是在面对复杂问题时的有效解决方法。贪心算法将一个大问题分解成若干可简单完成的小问题，通过解决每个小问题，求得最优解，最终求得大问题的最优解。这种思维方式也可以运用到日常生活中，给自己解决问题提供一种新的思路。但要注意的是，贪心算法及其思维并不是万能的，在许多复杂的情况下，大问题难以分解成若干的小问题，即使分解了，也无法通过局部最优解来求得整体最优解，整体最优解需要局部来妥协。

5. 用户使用说明

用户使用较为简单，根据终端的提示操作即可。

------------------------------------------------------------| 欢迎使用"钓鱼问题"模拟程序，请输入序号开始:| [1]随机生成2~25个池塘并解决问题；| [2]从文件中读取池塘信息并解决问题；| [3]随机生成池塘信息并保存到文件当中；| [4]人工生成池塘信息并保存到文件当中；| [0]退出程序。------------------------------------------------------------>

5.1 随机生成池塘解决问题

用户输入“1”后，进入到本模块，程序会提示输入小明的空闲时间：

小明有多少小时的钓鱼时间？[0]随机一个时间；[1-16]给定的时间>

用户输入时间，程序计算后输出结果。

5.2 从文件中读取数据计算

用户输入“2”后，进入到本模块，程序会提示输入文件名和小明的空闲时间：

请输入您要打开的二进制文件:> 小明有多少小时的钓鱼时间？[0]随机一个时间；[1-16]给定的时间>

需要注意，文件应和程序文件放在同一目录下，如反复出现文件读取失败的提示，请检查程序运行权限或者文件读取权限。

5.3 随机生成数据并保存

用户输入“3”后，进入到本模块，程序会输出生成的数据和提示输入文件名：

池塘组数据生成成功，内容如下:池塘总量: [amount]各池塘参数:池塘编号行程时间首次鱼量递减鱼量[index][time][fish][desc]...请输入您要保存的文件名:>

文件将保存到程序文件所在文件夹，若存在同名文件，则将覆盖保存。

5.4 人工生成数据并保存

用户输入“4”后，进入到本模块，程序会提示用户输入需要的数量，每一个池塘具体的数据和保存到的文件。

请输入池塘的数量：> 请依次输入第1个池塘的距离、鱼量、递减数据：> ……池塘组数据生成成功，内容如下:池塘总量: [输入的数量]各池塘参数:池塘编号 行程时间 首次鱼量 递减鱼量1[输入的数据]……请输入您要保存的文件名:>

文件将保存到程序文件所在文件夹，若存在同名文件，则将覆盖保存。

5.5 退出、错误处理与文件结果查看

用户输入“0”后，程序输出提示并退出。

再见 Bye~请按任意键继续. . .

用户在任何需要输入的地方输入了非法数据，程序将输出提示并回到功能选择界面。

> 666您输入的命令有误，请检查后重试。------------------------------------------------------------| 欢迎使用"钓鱼问题"模拟程序，请输入序号开始:| [1]随机生成2~25个池塘并解决问题；| [2]从文件中读取池塘信息并解决问题；| [3]随机生成池塘信息并保存到文件当中；| [4]人工生成池塘信息并保存到文件当中；| [0]退出程序。------------------------------------------------------------>

如果程序运行出错，将输出错误原因，然后回到功能选择界面。

文本输出文件打开失败！

以文件形式输出的计算结果，将保存到与程序同目录下的“output.txt”中，此文件的编码为GBK。

6. 测试结果

根据前文分析，程序运行大概有以下几种情况：

6.1 空闲时间大于钓完所有鱼的情况（略）

6.2 空闲时间刚好够钓完所有鱼的情况（略）

6.3 使用不同时间钓鱼结果相同的情况（略）

（数据略）这个例子中，小明在前两个池塘各停留了3次后，仍有两个时间单位。他选择在前两个池塘分别停留一次和前往最后一个池塘停留一次最终收获相同。他做出了正确的选择在前两个分别停留。此例中最后一个数据并不符合输入要求规范，此例只是为了说明本程序可以应对使用不同时间钓鱼结果相同的情况。

6.4 空闲时间不够钓完所有鱼的情况（略）

7.结论

综上所述，本课程设计的程序实现了任务书中的全部要求，并额外完成了生成二进制数据的功能，同时对不同数据各种可能情况进行了讨论，程序能够正确应对求出正确的解。此外，程序还有较为良好的模块化设定，用户友好姓和鲁棒性也达到作者的期望水平。

在算法优化上，需要更深一步改进，例如求取最大值时无需排序等方面，进一步优化时间复杂度。另外，虽有初步的模块化编程思想体现，但在主程序中仍有没有实现模块化的部分，后期需要进一步调整优化。

8. 附录

为便于纸张打印，将源代码中的四个空格缩进替换成了一个空格缩进。代码较长，达700行，此处分部展示代码。

8.1 数据结构与宏

#define MAX_DISTANCE 8// 池塘间的最大距离#define MIN_DISTANCE 1// 池塘间的最小距离#define MAX_FISH 40// 池塘一次最多可以钓的鱼#define MIN_FISH 3// 池塘一次最少可以钓的鱼#define MAX_DECREASE 20 // 池塘每次鱼量递减的最大值#define MIN_DECREASE 1// 池塘每次鱼量递减的最小值typedef struct{int index;int distance;int fish;int decrease;} Pond; // 池塘数据

8.2 计算钓鱼过程

/*** @description: 使用贪婪算法，计算出最佳停留时间和数量* @param {int} freeTime 小明拥有的空闲时间* @param {Pond} ponds[] 池塘数组* @param {int} pondAmount 池塘数组的长度* @param {int} bestStayTime[] 用于记录每个池塘停留时间的数组* @param {int} *Route 用于记录停留池塘数量的整型指针* @return {int} 小明最终的收获数量*/int goFishing(int freeTime, Pond ponds[], int pondAmount, int bestStayTime[], int *Route){int gain = 0;int route = 0;for (int i = pondAmount; i > 0; i--){int thisGain = 0;Pond *sortedPonds = (Pond *)malloc(sizeof(Pond) * i);int *stayTime = (int *)calloc(i, sizeof(int));if ((sortedPonds == NULL) || (stayTime == NULL)){puts("钓鱼过程内存分配错误！");return -1;}copyArry(ponds, sortedPonds, i);int routeTime = sumRouteTime(ponds, i);int freeTimeRemain = freeTime - routeTime;sortPondsByFish(sortedPonds, i);while (freeTimeRemain > 0){if (sortedPonds[0].fish <= 0){break;}freeTimeRemain--; // 钓鱼耗时thisGain += sortedPonds[0].fish;sortedPonds[0].fish -= sortedPonds[0].decrease;stayTime[sortedPonds[0].index - 1]++;sortPondsByFish(sortedPonds, i);}if (thisGain >= gain){// 取等于是因为新的循环用的时间会比上一次更少，即单位时间钓的鱼更多，方案更优。gain = thisGain;route = i;for (int j = 0; j < i; j++){bestStayTime[j] = stayTime[j];} // end for (int j = 0; j < i; j++)} // end if (thisGain >= gain)free(stayTime);}*Route = route;return gain;}

8.3 主程序

int main(void){char cmd[2];system("chcp 936 > NUL"); // 确保不同设备正常显示puts("\n!!!输出结果文本文件将会保存到程序文件所在目录的\" output.txt \"中。\n""!!!本程序使用的编码是\" GBK \"，保存和读取的文件是64位机器的二进制文件。\n");Begin:begin();scanfInt = scanf("%s", cmd);srand((unsigned)time(NULL)); // 使用时间戳作为种子重置随机数生成if (cmd[0] == '1'){// 生成并输出随机的池塘组int freeTime;if (!(freeTime = getFreeTime())){goto Begin;}int pondAmount = randint(2, 25);Pond *ponds = pondsArry(pondAmount);int *bestStayTime = (int *)malloc(sizeof(int) * pondAmount);FILE *fileO;if (!(fileO = fopen("output.txt", "w"))){puts("文本输出文件打开失败！");goto Begin;}fprintf(fileO, "小明拥有的时间: %d小时，合计%d分钟。\n",freeTime / 12, freeTime * 5);printf("\n小明拥有的时间: %d小时，合计%d分钟。\n",freeTime / 12, freeTime * 5);fprintf(fileO, "池塘总量: %d\n", pondAmount);printf("池塘总量: %d\n", pondAmount);printPonds(ponds, pondAmount, fileO);fclose(fileO);// 计算并输出最佳钓鱼过程int route = 0;int gain = goFishing(freeTime, ponds, pondAmount, bestStayTime, &route);sortPondsByIndex(ponds, pondAmount);fishingRecord(freeTime, ponds, route, bestStayTime, gain);free(bestStayTime);bestStayTime = NULL;goto Begin;}else if (cmd[0] == '2'){// 读取文件中的数据Pond *ponds = (Pond *)malloc(sizeof(Pond) * 26);if (ponds == NULL){puts("读取文件前池塘数组初始化错误！");goto Begin;}FILE *fileP;char fileName[20] = {'\0'};printf("请输入您要打开的二进制文件: \n> ");scanfInt = scanf("%s", fileName);if (!(fileP = fopen(fileName, "rb"))){printf("您输入的文件名有误，请重试。\n");goto Begin;}int pondAmount = 0;fread(&ponds[pondAmount], sizeof(Pond), 1, fileP);while (1){pondAmount++;if (ponds[pondAmount - 1].index < 0){pondAmount--;break;}fread(&ponds[pondAmount], sizeof(Pond), 1, fileP);}// 生成和输出问题信息int freeTime;if (!(freeTime = getFreeTime())){goto Begin;}int *bestStayTime = (int *)malloc(sizeof(int) * pondAmount);FILE *fileO;if (!(fileO = fopen("output.txt", "w"))){puts("文本输出文件打开失败！");goto Begin;}fprintf(fileO, "小明拥有的时间: %d小时，合计%d分钟。\n",freeTime / 12, freeTime * 5);printf("\n小明拥有的时间: %d小时，合计%d分钟。\n",freeTime / 12, freeTime * 5);fprintf(fileO, "池塘总量: %d\n", pondAmount);printf("池塘总量: %d\n", pondAmount);printPonds(ponds, pondAmount, fileO);fclose(fileO);// 计算并输出最佳钓鱼过程int route = 0;int gain = goFishing(freeTime, ponds, pondAmount, bestStayTime, &route);sortPondsByIndex(ponds, pondAmount);fishingRecord(freeTime, ponds, route, bestStayTime, gain);free(bestStayTime);bestStayTime = NULL;free(ponds);ponds = NULL;goto Begin;}else if (cmd[0] == '3'){// 生成并输出随机的池塘组int pondAmount = randint(2, 25);Pond *ponds = pondsArry(pondAmount);printf("池塘组数据生成成功，内容如下: \n\n池塘总量: %d\n", pondAmount);printPonds(ponds, pondAmount, NULL);// 保存至文件printf("\n请输入您要保存的文件名:\n> ");while (1){char fileName[20] = {'\0'};FILE *fileP;scanfInt = scanf("%s", fileName);if (fileP = fopen(fileName, "wb")){fwrite(ponds, sizeof(Pond), pondAmount, fileP);fclose(fileP);printf("\n写入文件\"%s\"成功。\n", fileName);goto Begin;}else{printf("文件写入失败，请更换文件名或者更改程序运行目录后重试。\n");} // end if 文件保存} // end while (1) 保存失败后重新获取文件名再试goto Begin;}else if (cmd[0] == '4'){// 生成并输出随机的池塘组int pondAmount = 0;puts("请输入池塘的数量：");printf("> ");scanfInt = scanf("%d", &pondAmount);Pond *ponds = pondsArry(pondAmount);for (int i = 0; i < pondAmount; i++){printf("请依次输入第%d个池塘的距离、鱼量、递减数据：> ", i + 1);scanfInt = scanf("%d %d %d", &ponds[i].distance, &ponds[i].fish, &ponds[i].decrease);}printf("\n池塘组数据生成成功，内容如下: \n\n池塘总量: %d\n", pondAmount);printPonds(ponds, pondAmount, NULL);// 保存至文件printf("\n请输入您要保存的文件名:\n> ");while (1){char fileName[20] = {'\0'};FILE *fileP;scanfInt = scanf("%s", fileName);if (fileP = fopen(fileName, "wb")){fwrite(ponds, sizeof(Pond), pondAmount, fileP);fclose(fileP);printf("\n写入文件\"%s\"成功。\n", fileName);goto Begin;}else{printf("文件写入失败，请更换文件名或者更改程序运行目录后重试。\n");} // end if 文件保存} // end while (1) 保存失败后重新获取文件名再试}else if (cmd[0] == '0'){puts("\n再见 Bye~\n");system("PAUSE");}else{puts("您输入的命令有误，请检查后重试。");goto Begin;}return 0;}

8.4 头文件与其他模块

/*** @description: 在终端输出命令提示菜单。*/void begin(void){printf("\n------------------------------------------------------------\n""|\t欢迎使用\"钓鱼问题\"模拟程序，请输入序号开始: \n""|\t[1]\t随机生成2~25个池塘并解决问题；\n""|\t[2]\t从文件中读取池塘信息并解决问题；\n""|\t[3]\t随机生成池塘信息并保存到文件当中；\n""|\t[4]\t人工生成池塘信息并保存到文件当中；\n""|\t[0]\t退出程序。\n""------------------------------------------------------------\n\n> ");}/*** @description: 返回含指定下限与上限之间的随机整数* @param {int} min 随机数大小下限* @param {int} max 随机数大小上限* @return {int} randomNum 给定范围内的伪随机数*/int randint(int min, int max){int randomNum = 0;randomNum = rand() % (1 + max - min) + min;return randomNum;}/*** @description: 随机生成或者根据用户输入读取小明钓鱼的时间* @return {int} 小明钓鱼的时间，单位为 五分钟*/int getFreeTime(){int freeTime = 100;puts("小明有多少小时的钓鱼时间？[0]随机一个时间；[1-16]给定的时间");printf("> ");scanfInt = scanf("%d", &freeTime);if (freeTime == 0){freeTime = randint(1, 16) * 12;}else if (freeTime > 16){puts("您输入的数据有误！");return 0;}else if (scanfInt){freeTime *= 12;}else{puts("您输入的数据有误！");return 0;}return freeTime;}/*** @description: 初始化一个池塘的数据。* @param {Pond} *pond 需要初始化数据的池塘的指针*/int initRandomPond(Pond *pond){while (1){pond->distance = randint(MIN_DISTANCE, MAX_DISTANCE);pond->fish = randint(MIN_FISH, MAX_FISH);pond->decrease = randint(MIN_DECREASE, MAX_DECREASE);if ((pond->decrease <= (pond->fish + 1) / 2) &&(pond->decrease >= pond->fish / 10)){// 单次减少量不得高于总量的二分之一 并且 单次减少量不得少于总量十分之一return 0;}} // end while (1) 循环直至生成的池塘数据符合要求}/*** @description: 格式化输出池塘数组中所有池塘的信息* @param {Pond} *ponds 池塘数组* @param {int} len 数组长度* @param {FILE} *fileO 结果输出的目标文件的指针*/void printPonds(Pond *ponds, int len, FILE *fileO){if (fileO != NULL){fputs("各池塘参数: \n", fileO);fputs("池塘编号\t行程时间\t首次鱼量\t递减鱼量\n", fileO);}puts("各池塘参数: ");puts("池塘编号\t行程时间\t首次鱼量\t递减鱼量");for (int i = 0; i < len; i++){if (fileO != NULL){fprintf(fileO, "%d\t\t%d\t\t%d\t\t%d\n", ponds[i].index, ponds[i].distance,ponds[i].fish, ponds[i].decrease);}printf("%d\t\t%d\t\t%d\t\t%d\n", ponds[i].index, ponds[i].distance,ponds[i].fish, ponds[i].decrease);}}/*** @description: 生成指定长度的池塘数组* @param {int} length 池塘数组的长度* @return {Pond*} 生成的数组的地址*/Pond* pondsArry(int length){Pond* ponds = (Pond *)malloc(sizeof(Pond) * length);if (ponds == NULL){puts("生成池塘内存分配错误！");}for (int i = 0; i < length; i++){ponds[i].index = i + 1;initRandomPond(&(ponds[i]));}return ponds;}/*** @description: 计算池塘数组的所有路途时间之和* @param {Pond} *ponds 需要计算的池塘数组* @param {int} amount 池塘数组的长度* @return {int} 池塘数组的所有路途时间之和*/int sumRouteTime(Pond *ponds, int amount){int routeTime = 0;for (int i = 0; i < amount; i++){routeTime += ponds[i].distance;}return routeTime;}/*** @description: 交换两个池塘的数据* @param {Pond} *pond1 需要交换的两个池塘的地址之一* @param {Pond} *pond2 需要交换的两个池塘的地址之二*/void swapPond(Pond *pond1, Pond *pond2){Pond temp = *pond1;*pond1 = *pond2;*pond2 = temp;}/*** @description: 根据池塘最近的时间单位可钓鱼的数量倒序排序池塘数组* @param {Pond} *ponds 需要排序的池塘数组* @param {int} amount 池塘数组的长度*/void sortPondsByFish(Pond *ponds, int amount){for (int i = 0; i < amount; i++){for (int j = 0; j < amount - i; j++){if (ponds[j].fish < ponds[j + 1].fish){swapPond(&ponds[j], &ponds[j + 1]);}}} // 起泡排序}/*** @description: 复制一个池塘数组* @param {Pond} *oldA 被复制的数组* @param {Pond} *newA 复制出的数组地址* @param {int} length 新数组的长度* @return {*}*/void copyArry(Pond *oldA, Pond *newA, int length){for (int i = 0; i < length; i++){newA[i] = oldA[i];}}/*** @description: 取数组的第low个元素，将数组分为左右两部分，并返回分界索引* @param {Pond} ponds[] 待分界数组* @param {int} low 分界起点* @param {int} heigh 分界终点* @return {int} 分界点的值*/int partition(Pond ponds[], int low, int heigh){Pond temp = ponds[low];int pivotKey = ponds[low].index;while (low < heigh){while (low < heigh && ponds[low].index >= pivotKey){heigh--;}ponds[low] = ponds[heigh];while (low < heigh && ponds[low].index <= pivotKey){low++;}ponds[heigh] = ponds[low];}ponds[low] = temp;return low;}/*** @description: 递归进行子数组的排序* @param {Pond} pods[] 主数组的地址* @param {int} low 子数组的起点* @param {int} heigh 子数组的终点*/void Qsort(Pond ponds[], int low, int heigh){if (low < heigh){int pviotLoc = partition(ponds, low, heigh);Qsort(ponds, low, pviotLoc - 1);Qsort(ponds, pviotLoc + 1, heigh);}}/*** @description: 根据池塘的序号来排序* @param {Pond} *ponds 需要排序的池塘数组* @param {int} amount 池塘数组的长度*/void sortPondsByIndex(Pond *ponds, int amount){Qsort(ponds, 0, amount);} // 快速排序/*** @description: 通过鱼塘数据和停留时间计算收获量* @param {int} fish 池塘最近一次单位时间可收获的鱼量* @param {int} decrease 池塘掉一次鱼的减少量* @param {int} stayTime 小明在该池塘的停留时间* @return {int} 小明在这个池塘中钓鱼的收获*/int gainInOnePond(int fish, int decrease, int stayTime){int gain = 0;for (int i = 0; i < stayTime; i++){if (fish - decrease * i < 0){gain += fish % decrease;break;}gain += fish - decrease * i;}return gain;}/*** @description: 通过计算出的信息格式化输出钓鱼过程和结果* @param {int} freeTime 小明可用于钓鱼的时间* @param {Pond} ponds[] 池塘数组* @param {int} route 小明前往最远的池塘序号* @param {int} bestStayTime[] 小明在每个池塘的停留时间* @param {int} gain 小明总的钓鱼收获*/int fishingRecord(int freeTime, Pond ponds[], int route, int bestStayTime[], int gain){FILE *fileP;if (fileP = fopen("output.txt", "a")){int wholeStayTime = 0;int wholeRouteTime = 0;puts("具体过程: ");fprintf(fileP, "具体过程: \n");for (int i = 0; i < route; i++){int routeTime = ponds[i].distance * 5;wholeRouteTime += routeTime;int stayTime = bestStayTime[i] * 5;wholeStayTime += stayTime;printf("抵达%d号池塘:\t花费时间%d分钟, 停留时间%d分钟, 获得鱼量 ",i + 1, routeTime, stayTime);fprintf(fileP, "抵达%d号池塘:\t花费时间%d分钟, 停留时间%d分钟, 获得鱼量 ",i + 1, routeTime, stayTime);for (int j = 0; j <= bestStayTime[i]; j++){if (bestStayTime[i] == 0){puts("0");fprintf(fileP, "0\n");}else if (bestStayTime[i] == 1){if (j == 0){continue;}printf("%d\n", ponds[i].fish);fprintf(fileP, "%d\n", ponds[i].fish);}else if (bestStayTime[i] == 2){if (j == 0){continue;}else if (j == 1){printf("%d+", ponds[i].fish);fprintf(fileP, "%d+", ponds[i].fish);}else if (j == bestStayTime[i]){if (ponds[i].fish - ponds[i].decrease < ponds[i].decrease){printf("%d=%d\n", ponds[i].fish % ponds[i].decrease,gainInOnePond(ponds[i].fish, ponds[i].decrease, stayTime / 5));fprintf(fileP, "%d=%d\n", ponds[i].fish % ponds[i].decrease,gainInOnePond(ponds[i].fish, ponds[i].decrease, stayTime / 5));}else{printf("(%d-%d)=%d\n", ponds[i].fish, ponds[i].decrease,gainInOnePond(ponds[i].fish, ponds[i].decrease, stayTime / 5));fprintf(fileP, "(%d-%d)=%d\n", ponds[i].fish, ponds[i].decrease,gainInOnePond(ponds[i].fish, ponds[i].decrease, stayTime / 5));} // end if (ponds[i].fish - ponds[i].decrease * j < ponds[i].decrease)}}else if (bestStayTime[i] > 2){if (j == 0){continue;}else if (j == 1){printf("%d+", ponds[i].fish);fprintf(fileP, "%d+", ponds[i].fish);}else if (j == 2){printf("(%d-%d)+", ponds[i].fish, ponds[i].decrease);fprintf(fileP, "(%d-%d)+", ponds[i].fish, ponds[i].decrease);}else if (j == bestStayTime[i]){if (ponds[i].fish - ponds[i].decrease * (j - 1) < ponds[i].decrease){printf("%d=%d\n", ponds[i].fish % ponds[i].decrease,gainInOnePond(ponds[i].fish, ponds[i].decrease, stayTime / 5));fprintf(fileP, "%d=%d\n", ponds[i].fish % ponds[i].decrease,gainInOnePond(ponds[i].fish, ponds[i].decrease, stayTime / 5));}else{printf("(%d-%d*%d)=%d\n", ponds[i].fish, j - 1, ponds[i].decrease,gainInOnePond(ponds[i].fish, ponds[i].decrease, stayTime / 5));fprintf(fileP, "(%d-%d*%d)=%d\n", ponds[i].fish, j - 1, ponds[i].decrease,gainInOnePond(ponds[i].fish, ponds[i].decrease, stayTime / 5));} // end if (ponds[i].fish - ponds[i].decrease * j < ponds[i].decrease)}else{printf("(%d-%d*%d)+", ponds[i].fish, j - 1, ponds[i].decrease);fprintf(fileP, "(%d-%d*%d)+", ponds[i].fish, j - 1, ponds[i].decrease);}} // end if bestStayTime[i]} // end for (int j = 0; j <= bestStayTime[i]; j++)} // end for (int i = 0; i < route; i++)printf("最终统计结果，小明路途花费%d分钟，在各池塘停留合计%d分钟，""总计耗时%d分钟，获得鱼量合计%d条。\n",wholeRouteTime, wholeStayTime, wholeStayTime + wholeRouteTime, gain);fprintf(fileP,"最终统计结果，小明路途花费%d分钟，在各池塘停留合计%d分钟，""总计耗时%d分钟，获得鱼量合计%d条。\n",wholeRouteTime, wholeStayTime, wholeStayTime + wholeRouteTime, gain);}else{puts("输出文件时失败！");return -1;}fclose(fileP);return 0;}