当前课程知识点：程序设计基础 > 第六章递推与动态规划 > 6.3 橱窗的插花问题 > 6.3.4 采用递推的优化算法

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

6.3.4 采用递推的优化算法在线视频

6.3.4 采用递推的优化算法

下一节:6.3.5.1 采用动态规划算法—优化分析

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

6.3.4 采用递推的优化算法课程教案、知识点、字幕

我们用枚举的方法解决了橱窗的插花问题

有些敏感的同学可能已经发现了

这个枚举方法里头应该存在很多重复的计算

有什么重复的计算呢

我们可以来看

就用我们之前的例子

对于0号1号2号花插在0号1号2号花瓶的这种方案

我们去计算整个的美感得分和的时候

显然我们要把0号花插在0号花瓶的美感

加上1号花插在1号花瓶的美感加起来

然后再加上最后那朵花

插在2号花瓶里的美感值

但是对于另一种插花方案

就是我们这表示的01011的方案

我们首先是同样要把0号花1号花插在

前两个花瓶的美感得分和算出来

然后再加上最后一朵花插在3号花瓶的值

加在一起

如果我们还有第三种方案

它是10011的插花方案

那么前两朵花的美感得分和

还要加上第三朵花插在4号花瓶的美感值

所以对于这三种方案来讲

前两朵花的插花方案是相同的

表现在我们计算它们的美感得分和的时候

我们都需要把前两朵花的美感得分和算一遍

所以这部分的计算

我们实际上是算了好几次的

那么如果我们想把这个代码的效率提高

就应该想个办法什么办法呢

当然为了避免重复计算

我们就需要把已经算过的结果保存起来

也就是说

我们需要保存一个部分的插花的美感得分和

比如说我们这为了解说方便

我们就给它取名字叫partial sum

就部分的美感得分和

那么对于前面的三种插花情况

我们最好能够保存一个11

这么一种插花方案的部分的美感得分和

那么再前进一步想一想

其实11这种方案的部分美感得分和

也应该是类似的方法计算出来的

也就是说实际上这种部分的美感和对11来讲

它应该是对于第一朵花

已经插在一个花瓶里的美感得分

再加上第二朵花插在一个

新的花瓶里的美感值

是这么相加计算得到的

也就是说

我们从一个特殊的情况细想

它其实应该是符合一种比较普遍的递推规律的

所以我们重新整理一下这样一个递推的式子

那就应该是这样的

对于某一种插花方案

i 当然在代码中间

我们知道它是一种二进制的表示

那么这样一种插花的方案

有可能是一个最终的方案

也可能只是插了一部分的花

那么我们都把它叫成partial_sum

这么一个得分的美感和

它是怎么计算得到的呢

它应该是去掉了最高位的那个1

所谓i的最高位的1

也就是我们最后最晚插的那朵花

那朵花我们不看

我们看前面已经插的那些花

应该是前面那些花的部分美感的得分和

加上了最后一朵花

刚插上的这朵花的美感值

那么最后这朵花的美感值比较容易知道的

我们只要想一想它是在哪个位置呢

那就表示它对应的哪个花瓶

然后本身这朵花有它的编号

所以写成的递推公式大概是这个样子

那么这个递推公式

我们要考虑一下它的初始值是多少呢

我们可以想到

第一朵花插上去之前是没有花的

因此我们的初值显然

是对于所有花瓶都不插花的状态

也就是i等于0的时候它的初值

那么既然所有花瓶都没有插花

我们可以认为整个的美感得分和

或者部分的美感得分和应该是0

这就是递推的一个初值

有了这个想法就可以知道

我们如果把枚举和递推结合起来

就能得到一个效率高一些的算法

那么在写具体代码之前

我们也需要再细化一下之前一个叫Count1的函数

原来我们只需要

数一下其中有几个1表示有几朵花

但现在我们还得知道这个方案里头

最后插的花在哪个位置

因为到时候i要减掉这个位置上的1

所以我们改写一下这个函数增加了一个参数

大家看到我们用一个引用

作为函数的参数

用high表示在这个二进制表示中间

最高位的1到底是在哪个位上

那么在具体代码实现里头

我们high的赋初值是赋1

然后在数binary的1的个数的时候

顺便如果发现这一位是1

我们就把high置成这一个位置

所以当循环从0 一直到v位结束以后

就自然得到了最高位的1所在的位置

比较一下我们的流程

把原来那个流程图稍微细化一下改变一下

加上新的递推思想就能得到一个新的流程图了

大家看一下我用红色标记在这里

我们现在多了一个部分美感得分和的数组

所以我们要重新定义一个数组

并且它的初值是0的时候取值为0

然后在枚举方案中间

就不是简单的统计一个合法方案了

凡是所有的插花的数目小于等于f的

都是一种部分的插花方案

那么这个是我们要计算的具体插花方案

同时找到最高位的那个1

然后对于合法的部分方案

再去计算它的美感得分和

而且这时候计算用的是递推的方式

请看我们具体的代码

我们把新的部分补充上去

我们需要定义这一个数组

然后在枚举的时候

调用了ToBinary之后

还要调用新的count1函数

除了得到插花数量以后

还有最高位的1到底在哪里

然后我们判断它是不是一个合法的部分插花方案

对于合法的部分就可以

进行基于递推式子的计算

怎么去掉最高位的1

i减去了1 左移high位

那么最后那朵花到底插在那个花瓶里

美感值是多少呢

它所在花瓶的编号就是high的值

第几朵花呢

我们知道是第flowers朵花

所以它的编号应该是flowers减一

这样我们就能得到部分的美感和了

最后如果部分插花方案

就是最终的方案因为我们看到

flowers等于f表示正好插了f朵花

那么就应该考虑它是不是所求的最优方案

那么同样的维护一下最优的方案

和最优的方案下的美感得分和

就可以了

程序设计基础课程列表：

第一章编程初步

-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 总结

-程设论道

-师生问答

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

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

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

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

第二章变量与代数思维

-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.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

-程设论道

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

--程设论道二：筛法

-师生问答

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

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

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

第五章分治思想与递归

-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.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

-程设论道

-师生问答

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

第八章非文本数据处理

-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.3.4 采用递推的优化算法笔记与讨论

也许你还感兴趣的课程:

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