当前课程知识点:程序设计基础 > 第五章 分治思想与递归 > 5.4 分书与八皇后 > 5.4.6 代码解说——分书问题
好 我们先来看分书这个问题的代码
我们一边读着代码一边再来解释这里面的每个变量
每条语句到底是怎么跟算法相对应的
这是分书问题的源代码
我把它分成两个部分 两屏
首先看到的是整个程序的总体的样子
那么很显然按照我们以前所讲到的
在我们这个课里面每一个题都要用到cout来输出一些东西
所以我们在程序的顶上面会出现
include
这个可以认为是一个固有的吧
因为每个题都会用到这个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.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 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测