当前课程知识点:程序设计基础 > 第五章 分治思想与递归 > 5.4 分书与八皇后 > 5.4.3 问题分析——区别
在讨论它们的算法
这个思路的描述之前
我们还有看一看这两个问题之间
有什么样的一种区别
除了刚才说这种斜线之外
我们如果仔细再思考的话
发现这两个问题在有
限制条件的这个上面是有一些区别的
对于分书这个问题
那么它设置元素的这个位置
它其实是有限制的
因为每本书能分给那些人
就是那些人喜欢那本书
这个是在题目里头给定了的
那所有的这样的一个分书的方案
只能是从
这些已经规定好的
这种偏好关系上去选择
换而言之
如果对于一个矩阵而言
就相当于
我是在矩阵里头画了一些区域
在这些区域里头
你才可以做一个分配的
这种元素的设置
那么其他没有这种喜好关系的
那些矩阵的元素的
这个位置是不可以填充元素呢
也就是说这样的一个集合
是由题目事先确定好的
在中间运行的当中是不会改变的
可是我们对照的八皇后发现
对于这个问题
它的首先上来
每一个位置都是可以选择的
并没有一个特定的限制
其次呢它的这个
放棋子的过程当中
这个性质的条件
它其实是有一个变化的过程
这是它们一个很重要的区别
那好 经过这样的分析
下面我们就来看看
怎么样来求解这两个问题
我们今天是尝试着要把两个
看上去不一样但是呢
有类似有共同性的题目放到一起
来看它们解题的思路
那很显然
对于求解分书 八皇后
这两个问题它的关键点
根据我们前面几章的学习
我们知道在计算机里头
一个很重要的求解问题的方法
就是使用枚举法
而我们这两个问题
分书也好
八皇后也好
它恰恰就是在问大家
到底有多少种方案
那样的一些书和那样的一个棋盘
你的的确确是有很很多种的分配方法
和放棋子的方法
那到底那一个是合理的呢
到底那一个能满足题目的要求呢
而这其实很容易想到的一个解题思路
就是枚举的方法
我依次的去把所以的方案都枚举出来
然后去看
看它们是不是满足条件
所以这个问题的关键是
你怎么能够
或者说如何
把可能的方案依次的枚举出来
那这里头我们考虑到
由于在这两个问题里头
都是行跟列
不能出现重复的元素
也就是说只能放一个元素在里头
所以呢
我们这样的一个问题
根据这个特定的性质
我们马上应该就能想到
可以把这个问题的求解
这个分解为
把它逐行来求
当然了逐列也是一样的
这个矩阵其实是
你可以在那转换一下
我们后面说行说列其实在实现程序的时候
这两种都是可行的
那么我们讲的时候可能就按行来说
分解成一行一行来求解
比方说分书
这一行代表一个人的话
那我就是一个人一个人的
给它书
八皇后 是吧
那我就一行一行
去在行上面去找到棋子(皇后)的位置
那也就是说这个问题的求解过程
就变成了
依次来确定
在每一行上面
这个元素的列位置
就是 我第一行完成了
我就不管了
然后就去弄第二行
然后弄第三行
直到5行这个分书类题
或者8行这个皇后类题
都把它处理完这个任务就完成了
所以这个时候我们原来的一个大问题
就变成了一个小问题
或者变成了5个或者8个小问题的求解
什么小问题呢
就是在一行上面
去找到一个合适的位置
去分一本书
或者呢放一个八皇后
也就是依次去确定
每行上面元素的
存放的列的位置
同时 还是由于这个行跟列
它不能重复
这样的一个要求
也就是说在每次确定了
一行上的元素之后
其实这一个相应的行或者是列
你这个元素肯定是
出现在每一行每一列的矩阵里头嘛
其实是可以理解为
可以把它们删掉
也就是说
我们发现去确定任意行上的
这个元素的位置
这样的一个过程
当我们删掉这行跟列之后
那么其实它变成了一个更小的矩阵
也就是说对于剩下的问题的求解
就变成了一个小了一些规模的
行跟列各减去1的一个新的矩阵
在里头去填元素
那么根据我们前面讲过的
这不又是一个同样的问题的再现吗
只不过这个时候问题的规模缩小了
原来是5本书5个人
由于你已经搞定一个人跟一本书了
所以呢就剩下4个人4本书
八皇后也是一样
我已经放上去一个棋子了
那就变成了一个7*7的棋盘上面
放7个皇后
这个问题就变得
跟原来的问题n*n不太一样
它缩小了
可是呢
它的这个思路
很显然又是可以运用同样的办法去求解的
所以这个里头我们就再一次的看到
当我们这么做了之后其实
很容易想到
递归是解决这两个问题的
很重要的切入点或者手段
那么当我们逐行去求解的时候
我们进一步来看
这一行一个人我要去分5本书
或者这一行八个皇后
我放到那一列上面去呢
这个里头有5个或者8个
这样的一个选择
那么到底应该选择那一列呢
很显然 每一列都有可能
这个地位是平等的
我们前面说每一行是把这个任务
承担了一个任务的子任务
一步一步来做的
每一行就是一步
那么现在每一列
其实是每一个你都有去尝试的
你尝试完了你才能综合起来
哪些列是可能满足条件的
因为我们题目要求所有的方案
所有很有可能 某些列都有可能是对的
这个时候它列跟列的关系
跟行跟行的关系不太一样
所以我们对于每一行
去列举里头的每一列
去枚举它 去尝试的时候
每一列都有可能所以这个地方
我们需要循环对每一列进行尝试
无论是分书这一行有5本书我要分给这个人
到底那本书分给他呢
挑选其中的一列代表这本书分给了他
皇后也是一样
每一列我们都要去为它尝试
那么基于这样的考虑
我们进一步来考虑
在题目里头的这个条件限制
对于题目里头
设置要求的元素的摆放是有条件限制的
当前行的一种决策
这本书
现在这个人已经占了第三本书
那就意味着
虽然第四个人可能也喜欢第三本书
但是呢已经轮不到第四个人了
因为这第一个人已经把第三本书占掉了
这其实就意味着当前行
你做的这个决策
在哪一个列上面去放一个元素
是会改变或者呢
是会影响后者的选择过程的
因此啊
一方面我们需要在每一次的决策之后
因为你要影响后面嘛
所以我要去更新或者调整这个限制条件
比方说一个空空的棋盘
你其实刚开始放第一个棋子的时候
是可以任意放的
但是这一个棋子落下去
立刻的这个对角线就不能再占了
对不对
那么其实就把
对角线这个棋盘上的位置
就等于挖出去了
那原来我是禁止这个行跟列的
或者说我原来没有棋子的时候
是空棋盘可以任意放
由于你放上去一个棋子
就导致你不能再任意去放
你受到了新的约束和限制
所以我们说
当你当前行的决策完成了之后
需要去把整个去找这个方案的后续的过程
它的限制条件
进行跟新 进行改变
那么另一个方面呢
我们也需要在进行
另外一个列的尝试的时候
要把这个限制条件呢
要恢复到这个前一列决策时候的状态
什么意思呢
就是我刚才说过了
我们的每一列其实是对等的
也就是平等的地位
每一列都要独立的去尝试
那么既然是平等的
那就意味着
在每一列去尝试的时候
它们的前提条件必须是一模一样的
大家从同一个起跑线上出发
可是我们别忘了
我们的程序是顺序执行的
当我们依次去枚举
哪一列是对或者是不对的时候
其实总有一些列是新做的
总有一些列是后做的
那么后做的列
我们怎么能够保证
它跟前面
那个排在前面去尝试的那个列
它的地位是对等的呢
它们的起始条件是一样的呢
当然得靠我们的程序代码去考证
可是我们前面刚刚说过
你每一次做了决策
就是我前面说 这个地方不错
这一列可以选择它
当我们去做这个决策的时候
为了去做后面的行
注意我们当前行
选择的某一列
我们为了去做后面那一行
就是下一个子任务的
工作的时候
我们是需要去
更新那个限制条件的
但是呢
当你做了这样的限制之后
等到后续的事情做完了
要退回去
去尝试当前行的下一列的时候
这个时候就出现了一个问题
就是你下一列需要去跟
前一列它的初始条件是一致的
所以呢
我们这个里头就是说
当我们进行另一列的尝试的时候
需要把限制条件恢复过来
那么具体怎么做
我们后面结合代码来把这个抽象的说法呢
具体化一些
那么这样的一种恢复到上次枚举之前的
条件限制的操作的步骤
我们就把它称为回溯
这个有点像电视剧里头
时光机的时光倒流到过去的某种状态
从头开始
这是我们一个基本的一个思路
也就是一行一行的去尝试
去完成这个任务
在每一行里头呢
一列一列的去尝试它
当我们确定去尝试某个列的时候
做出某种决策的时候
这个任务就缩小了
我们可以用递归的方法来去求解它
-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 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测