当前课程知识点:程序设计基础 >  第五章 分治思想与递归 >  5.4 分书与八皇后 >  5.4.6 代码解说——分书问题

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

5.4.6 代码解说——分书问题在线视频

5.4.6 代码解说——分书问题

下一节:5.4.7 代码解说——八皇后问题

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

5.4.6 代码解说——分书问题课程教案、知识点、字幕

好 我们先来看分书这个问题的代码

我们一边读着代码一边再来解释这里面的每个变量

每条语句到底是怎么跟算法相对应的

这是分书问题的源代码

我把它分成两个部分 两屏

首先看到的是整个程序的总体的样子

那么很显然按照我们以前所讲到的

在我们这个课里面每一个题都要用到cout来输出一些东西

所以我们在程序的顶上面会出现

include using namespace std;

这个可以认为是一个固有的吧

因为每个题都会用到这个cout

那么接下来大家看到的两个变量

大家看到前面这个地方有两个变量

分别表示你算出来的方案数num

下面是一个take 它是一个五个元素的一维数组

它表示对这个书它的分配情况

把每一个元素去代表了一个用户

也就是用户的编号去作为下标

去记录这个人到底喜欢哪一本书

所以take[3]就表示编号为3的那个人他喜欢哪一本书

喜欢的那本书的编号就存放到take[3]这个数组单元里面去

接下来是一个叫做限制条件的标记

我们叫做布尔的一个数组 是一个assigned

也是一个五个元素 它代表了这五本书有没有分配出去

如果分配出去了相应的元素就是true

如果没有它就是false

再往下是一个二维的数组

这就是题目里面说到的每一个人喜欢哪些书

每一本数被哪些人所喜欢

这样的一个二维数组

里面的元素0和1分别表示相应的书是不是被相应的人所喜欢

注意在这个二维数组在定义的时候 对它进行了初始化

这个初始的格式和我们一维数组初始化的格式是类似的

都是一个花括号 里面是用逗号隔开的一个个的初始化的值

而我们是一个二维数组 所以每一个初始化的值又是一个数组

于是又得用一个括号把它括起来

然后这个括号里面的元素也得初始化

所以就变成了00110这样一个东西 被逗号隔开 花括号括起来

然后再来一次一次的

就把这个二维数组给初始化了

好了这是讲到了几个全局的变量 它的含义

下面我们看程序的主体部分

两个函数 一个是程序的主函数main函数

一个是我们要去实现的try这个函数

让我去尝试着给每个人分书

所以人的id我们用int来表示它

那么这个细节我们待会看

先看这main函数里面写些什么了

先把这个总的框架领会了 再来看它的实现的细节

那么每一个刚刚说到的全局变量

除了那个like之外

这个num take assigned它们都是要去赋一个初值的

num是方案数 把它赋成0

然后这个assigned 书有没有被分出去

很显然刚开始的时候这五本书都没有被分出去

所以我用一个for循环 给它的每个元素赋值成false

至于说take这个元素 由于我们在后面的算法里面每一次都会给它赋值

会把它原来的值 无论它是有定义的还是没定义的值会把它覆盖掉

所以我们在主程序里面就没有对它进行初始化

把它空在这个地方

好了有了这样的一些操作之后

我们来看在主程序里面调用了try(0)这样的一种函数调用

它表示从第0个人 或者说从a开始来给他分书

我们说过了 一个人是一行

在我们算法里面是一行一行的去尝试

把这个问题分成了行这样的子问题来组成的

那么从第一行去尝试

也就是从a这个人开始尝试

try[0]就表示了这样的一个意思

怎么去try这个0呢 我们看下一页

这就是try的函数的实现

我们首先可以看到 在这个程序里面

分成两大部分 上面这部分表示递归的中止条件

就是所有的读者都已经分配到合适的书籍

所以就可以中止了

下面这个部分

是对id这一行或者id这个user 这个用户

来为他来尝试 看看到底哪本书适合他

枚举嘛 我们前面讲过了 枚举每一列

好 我们书就是一列 枚举每一列

到底哪一列适合你呢

所以这个地方我们就是为每一本书去找到一个合适的读者

尝试它是不是适合于id这个人

好 这是总体的两个部分

跟我们的算法 伪代码写的描述是一致的

先是中止条件 然后来依次枚举

首先我们来看它的中止条件

由于是五个人 编号是从0到4

因此当id=5的时候 就意味着0到4已经处理完了

所以我们的中止条件里面 大家看 它是id等于5吗

是 已经做完了 所以num++

方案加1 然后输出这个方案

找完了嘛 成功了嘛 所以把方案输出来

那方案在哪里呢 我们前面那个代码大家看到过

有一个take数组 那里面记录了每本书到底分给谁了

所以这个时候把那个数组的内容打出来就好了

所以一个for循环 把take数组每个元素输出出来

就代表了这abcd几个人分别分的书是哪一本

这样就把它这个分配方案打出来了

最后return 没了嘛 归结了

递归递归 到最后归结到已知的东西上去了 就return了

所以这个就直接return

这是所有的递归程序都要去考虑到的怎么中止它

好了 这个东西想清楚之后 我们再去看稍稍复杂一点的

怎么去枚举行上面的每个列呢

说到枚举 我们很容易想到for循环

因为他们每一个都是对等的

所以for book从0到4

这个时候我们是从0到book<=4 每一个book来尝试一下

看它的枚举的主体

大家看在这个地方我们做了一个是否满足分书条件的一种判断

如果这本书这个人确实喜欢

那我怎么知道他喜欢呢

前面有一个数组它记录了每本书每个人是不是喜欢它

所以就是like[id][book]

如果这个元素等于1

就意味着id这个人喜欢book这本书

光喜欢还不够 这本书还得有 有没有被人借走

所以我们还得有&& 注意这个地方是一个与的条件

必须同时满足 满足什么呢 这本书没被借出去

没有被将借出去怎么表示呢

我们前面有一个assigned的数组

它就是用来记录书本是不是被分出去了

如果assigned相应的这个book相应的元素是true的话

就表示它借出去了

所以我们这里求的是一个非

也就是当里面为false的时候 这个非的运算才会得到一个true

这个与才会成立 才有条件成立 才有可能成立

所以我们 !assigned[book] 就表示这本书它有没有被分出去呢

如果既喜欢这本书 又没有被分出去

OK 那就可以分给id这个人了

怎么表示分给他啊

记下来 take[id] id这个人他喜欢哪本书呢

喜欢book这本书 存到里面去 take[id] = book

完了之后再记录book这本书分出去了

assigned[book]=true

这就是记录书本的分配情况

同时改变一些限制条件

比如assigned[book]它已经等于true了

后面这个book不能再分了

接下来我们就去尝试下一个人

根据我们前面的分析

尝试下一个人是规模缩小了的一个同性质的问题

所以接着try try(id+1) 下一个人 做递归 去完成它

递归完成后我们就需要去尝试下一列

至于这个递归它到底最后怎么走完的 那是我们不用去考虑的

因为这是递归这个程序 那个函数自身去完成的

我们只需要知道把这个任务交给它 让try去做就好了

做完了之后我们下面要进行下一列尝试

因为另外的一列也是有可能成为合理的方案的

但是在做这样的尝试之前 我们注意到前面的限制条件发生了更改

所以我们要把它退回去

在这个问题里面被更改的是assigned

所以我们把assigne[book]把它改成 恢复到原始的false的状态

这本书没有分 把那本书要回来了

要回来了于是你就可以尝试新的

所以这本书既代表你要回来了

其实也代表id这个人不要这本书了

我想再去找另一本书看看

所以再来一个循环去尝试下一个book

还是对id这个人 所以就实现了我们算法里面依次去尝试

每一本书 这样一个枚举的算法

程序设计基础课程列表:

第一章 编程初步

-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 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

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

5.4.6 代码解说——分书问题笔记与讨论

也许你还感兴趣的课程:

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