当前课程知识点:程序设计基础 > 第六章 递推与动态规划 > 6.2 分鱼问题 > 6.2.2 从A到E递推
这个问题挺有意思的
那每个人醒来以后都看到一堆鱼
然后把它分成了五份 还多了一条
那么要求每个人看到的鱼有多少条呢
很自然的想到说
我们可以用一个数组来表示每个人醒来时看到的鱼的数目
那么我们可以让num[0]来表示A看到的鱼
num[1]表示B看到的鱼 以此类推
那么根据分鱼的方法我们可以知道
下一个人 我们可以写成num[i+1]
他看到的鱼的数目是多少呢
应该是前一个人剩下的
前一个人也就是num[i]是扔掉一条 就是减掉1
那么分成五份 他拿走一份以后剩下的是四份
所以我们可以用一个式子来表示就是
num[i+1]就等于num[i]减1 先除以5然后再乘以4
当然这只是数学的一个递推的式子
那我们的分鱼是有它的物理意义的
在物理意义下 我们扔掉一条鱼以后
确实应该可以分成五份 而不会出现半条鱼的情况
那这个就是我们一个生活中问题的
如果抽象成数学公式以后要注意的一点小的地方
那么对题意理解了之后 我们大概就可以想到
该怎么来计算这个问题了
所以我们也画出了这个问题解决它的一个流程图
那用我们以前的知识说
这样的问题实际上我们可以用枚举的方法
我们就是不断的枚举总的鱼的数目
那么看看到底哪一个最小的数目是可以满足题目要求的
同时我们就可以把每个人看到的鱼计算出来
所以我们可以仔细的看一下我们流程图中的一个步骤
那么我们大的框架是对A醒来时看到的鱼的数目进行枚举
那么我们根据刚才提示大家物理的意义的限制
我们要保证A看到的鱼确实是扔掉一条以后是可以分成五份的
那么A拿走鱼以后 我们就可以计算B看到了多少鱼
我们要计算num[1]
同样我们要检查B是不是也是扔掉一条鱼以后能分成五份呢
如果满足条件 那么我们可以进行下一步的计算
如果不满足条件
显然是因为我们枚举的A看到的鱼的数目有点小问题
我们就得继续枚举下一个值了
所以这个就是我们整个一个枚举的逻辑
那么代码就可以对照着这样一个流程图去实现
首先我们定义一下数组
它们分别表示每个人所看到的鱼的数目
然后这一个大大的枚举 我们A看到的数目从1条鱼开始
逐步的往后去尝试
那么什么时候结束呢
那么现在不知道 那么for循环中间的条件是空的
我们要根据后面计算的过程中间
发现的第一个满足条件的鱼的数目
就是题目要求的至少的鱼的数目
那么 对照着流程图 我们首先判断
是不是A看到的鱼能够去掉一条能分成五份
然后计算B看到的鱼的数目
然后检查B所面对这些鱼 能不能扔掉一条以后分成五份
然后计算C 判断C是不是满足条件
计算D D看到的鱼的数目是不是满足条件
然后我们计算E E虽然最后一个人
可是根据题目的意思 他仍然是要按这个方法去分鱼的
所以最后E也有一个判断的条件
在这个过程中间 只要我们发现说 当前的值是不满足条件的
我们就必须进行下一个鱼的数目的枚举
在我们代码中间用continue直接停止当前循环体的执行
而进入下一轮的循环
如果最后所有的条件都满足了
那我们就可以退出循环去输出我们的答案了
那么显然这时候我们的循环变量 num[0]就是A看到的鱼的数目
而且我们循环体中得到的每一个值
就是其余几个人依次看到的鱼的数量
那细心的同学已经发现了 在我们循环体中有很多类似的代码
这个题目只是五个人 如果题目里面有五十个人 五百个人
难道我们就把这种非常类似的代码不断的重复写进去吗
那当然我们希望有更好的办法
既然这些代码这么类似 只有下标不同
很自然想到说我们可以用循环来控制简单的几行代码来
代替现在所有的看起来重复的代码
我们研究了一下发现说这儿的num的计算从1算到4
所以我们的循环可以用for来控制 让循环变量从1到4
对照着我们红框的部分 我们首先都是先进行计算
判断说现在看到的鱼的数目是不是
能满足扔掉一条能分五份这么一个限制条件
那这里面跟原来代码略有点小不同在于
原来我们一旦发现不满足条件
我们可以用continue来终止这个循环体的执行
来进行下一轮的循环
可是由于我们现在已经把它放在了一个循环中间
所以如果我们要跳出这个循环的话 就不再进行计算的时候
它只是跳出一个内层循环
而我们希望是直接从num[0]这个地方进行下一个枚举
那么怎么办呢 这儿有个小技巧
也是我们很常用的一个小技巧
就是我们会设一个标志
标志说我到底是所有的鱼的数目都算完了 还是说我中间半途我退出了
那么对于这一个具体的问题来讲
我们发现说其实循环变量就可以作为我们一个小的标志了
也就是说如果 我把num[1][2][3][4]都计算完了
那必然我的答案就已经找到了
如果我提前退出
那么肯定这个循环变量就不是由于不满足循环的条件退出的
所以我们可以看到说 我们用if语句再次检查了一下说
这个循环变量i是否是满足for循环这个条件的
如果是满足for循环条件 那么它本来应该还在循环啊
说明它必然是因为不满足中间计算的一些限制条件而退出的
所以对于这种for循环的提前退出
我们应该尝试下一个枚举值
那么如果发现说它确实是不满足了循环条件
那么它是属于已经计算得到了结果的情况
那我们自然就按原来的的循环体那边的break就可以了
所以我们把这一块代码可以用这样一个循环控制
实际上我们这段代码还可以做进一步的优化
有的同学其实也已经发现了 既然每个人都是扔掉一条鱼才能分五份
那么对于A来说 他的枚举是没必要一条一条去增加的
因为如果上一个可能枚举值是扔掉一条能够分五份的话
那显然至少要增加5才可能满足条件
所以我们的枚举步长可以直接是取五 而不用一条一条往上增长
这样既可以减少循环次数 另外由于我们步长
就保证了扔到一条能够被5整除
也就可以去掉了那一行对于num[0]模5余1的判断了
那有的同学还发现了这个问题 也就是说
既然扔掉一条鱼以后能分成5份
而计算机里头 我们以前已经学过了
整数除以整数 得到的还是整数
所以实际上我们可以把(num[i]-1)/5呢
就简单写成 num[i]/5
因为计算机特殊的计算规则保证
两个整数相除得到的还是整数
那最后呢我们还想讨论一下初始值的问题
显然num[0] 1是不可能的 6也是不对
实际上如果我们真正把我们的代码执行一遍会发现说
E所看到的鱼已经有一千多条了
也就是我们num[0]从1开始去枚举 其实完全没有必要
那么我们可以估算一下 因为最后一个人看到的鱼至少是6条
因为他扔掉一条还能分五份
那么前一个人大概是它的四分之五倍
所以我们可以大概估算一下说
A他看到的鱼大概是6乘以了四分之五的四次方
大概是这么一个数目
我们按一下计算器大概可以知道说 差不多是15
所以A所看到的鱼的数目 我们至少可以从16来开始枚举的
那么这一些代码的优化 实际上也是一个很好的习惯
就让我们去逐步的把一个代码不断的越做越漂亮
这个也是我们成为一个优秀的程序员必不可少的一个过程
那么有同学又问问题了 既然我们在枚举的时候
A看到的鱼的数目 实际上是我们通过最后一个人 倒过来估计的
那为什么不直接从最后一个人开始去枚举呢
也就是我先枚举E可能看到鱼的数目
然后倒着来递推说A看到多少鱼呢
-1.1 基础知识
-1.2 买菜问题
-1.3 数学运算
-1.4 补充说明
-1.5 总结
--1.5 总结
-程设论道
--程设论道
-师生问答
-第一章 编程初步--语法自测
-2.1 关于超级计算器的几点思考
-2.2 电子秤模拟 — 背景介绍及需求分析
-2.3 电子秤模拟 — 代码实现
-2.4 变量定义与变量类型
-2.5 猜数游戏与数据表示
-2.6 关于变量的讨论
--公告
-2.7 变量体现的计算思维
-程设论道
--程设论道
-师生问答
--师生问答
-第二章 变量与代数思维--语法自测
-3.1 谁做的好事——语义表示
-3.2 谁做的好事——真假检查
-3.3 谁做的好事——循环枚举
-3.4 谁是嫌疑犯——多重循环枚举
-3.5 谁是嫌疑犯——破案线索表示
-3.6 谁是嫌疑犯——用二进制枚举
-程设论道
--程设论道一
--程设论道二
--程设论道三
-师生问答
-第三章 逻辑推理与枚举解题--语法自测
-4.1 插花游戏
-4.2 筛法
-4.3 线性查找
-4.4 折半查找
--4.4.1 提问
-4.5 排序问题
-4.6 总结
--4.6.1 总结
-程设论道
--程设论道二:筛法
-师生问答
-第四章 筛法与查找--语法自测
-5.1 阶乘
-5.2 排序
-5.3 矩阵填充
-5.4 分书与八皇后
-5.5 青蛙过河
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答一
--师生问答二
-第五章 分治思想与递归--语法自测
-6.1 兔子数列问题
-6.2 分鱼问题
-6.3 橱窗的插花问题
-6.4 最长公共子序列问题
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第六章 递推与动态规划--语法自测
-7.1 统计记录总数
-7.2 统计活跃用户数
-7.3 统计在线时长
--7.3.2 结构
-7.4 总结
--7.4.1 总结
-程设论道
--程设论道
-师生问答
--师生问答
-第七章 文本数据处理--语法自测
-8.1 将数据组织成链表
-8.2 提高链表访问效率 —— 哈希链表
-8.3 以二进制文件存储链表
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第八章 非文本数据处理--语法自测
-9.1 自动售卖程序
-9.2 配制水果信息
-9.3 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测