当前课程知识点:程序设计基础 >  第六章 递推与动态规划 >  6.2 分鱼问题 >  6.2.2 从A到E递推

返回《程序设计基础》慕课在线视频课程列表

6.2.2 从A到E递推在线视频

6.2.2 从A到E递推

下一节:6.2.3 从E到A递推

返回《程序设计基础》慕课在线视频列表

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.1.1 什么是程序?什么是语言?

--1.1.2 什么是程序设计?

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

--1.5 总结

-程设论道

--程设论道

-师生问答

--师生问答一:怎样学好程序设计

--师生问答二:语言选择

--师生问答三:关于函数

-第一章 编程初步--语法自测

第二章 变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的 读/写 操作

--2.6.6 指针的 加/减 操作

--公告

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

--程设论道

-师生问答

--师生问答

-第二章 变量与代数思维--语法自测

第三章 逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一:字符与ASCII码表

--师生问答二:其他循环语句、运算符优先级与变量作用域

-第三章 逻辑推理与枚举解题--语法自测

第四章 筛法与查找

-4.1 插花游戏

--4.1.1 问题提出(求素数)

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.1 提问

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

--4.6.1 总结

-程设论道

--程设论道一:数组与编码思维

--程设论道二:筛法

-师生问答

--师生问答一:函数与面向过程编程

--师生问答二:数组的下标越界

-第四章 筛法与查找--语法自测

第五章 分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章 分治思想与递归--语法自测

第六章 递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第六章 递推与动态规划--语法自测

第七章 文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.2 结构

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

--7.4.1 总结

-程设论道

--程设论道

-师生问答

--师生问答

-第七章 文本数据处理--语法自测

第八章 非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第八章 非文本数据处理--语法自测

第九章 可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

-第九章 可配置的程序设计--语法自测

6.2.2 从A到E递推笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。