算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
棋盘分割
Loading...
来自 Peking University 的课程
算法基础
283 个评分
从本节课中
递归
递归调用是设计和描述算法的一种有力工具，尤其是在解决复杂问题时经常采用。它的基本思想是要解决某一问题A，可以先解决一个形式相同，但规模小一点的问题B。问题B如果解决了，那么问题A也就迎刃而解。有些问题使用传统的迭代算法是很难求解甚至无解的，而使用递归却可以很容易地解决。本模块将通过具体的例题介绍如何构造递归函数，如何设置递归终止的条件以及分析递归算法的复杂度。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
大家好，在这一小节中，我们来学习一下递归算法的第二个例题 称为叫做“棋盘分割”问题。
我们呢在这个题目当中呢，遇到了一个8*8的棋盘 我们需要对这个棋盘呢，进行一定的分割。
分割的方式呢是这样子的：我们将原来这个棋盘呢首先割下一块矩形
那么割下一块矩形之后呢，要求其剩下的部分也是一个矩形
也就是说我们把这一个棋盘通过一刀切分之后，分成了两个矩形。
那么据掉一块，是吧？对于另外一块矩形来讲，我们对它继续进行刚才
这样的方式的分割，那么分割了(n-1)次后，啊一共分了n-1次后
连同刚刚剩下的那个矩形棋盘一共有n块矩形棋盘，是吧？那么这n块矩形棋盘的话呢
每一次分割注意都只能是沿着棋盘格子的
边进行，啊我们不能跨这个格子来进行分。
我们看到，我们允许了这个切割方式呢是这样子的，是吧？比如说我第一刀 先切在这里，把这个矩形分成了左右两部分。
接着的话呢，我又分了一刀，是吧？又分了一刀。
那么把右边这块又分成了两，上下两部分。
接着呢，我又对刚才的这 下面这块呢就扔掉，又对它上面这块来进行分配，是吧？
上面这块的话呢我又分了一刀，又横着分了一刀，是吧？
那么仍旧保留下面的这一块，那么我又在中间又分了一刀，啊，那么注意，
右边这个方案呢是不允许的，啊，因为你看到，你首先先
分了一刀，是吧？又分了一刀之后呢，那么我们就理论上这一块就应该被舍弃掉了。
那么如果不是这样舍弃的话呢，那么你这一刀呢
分完之后，你没有保留两矩形，啊也就是说你现在目前这个方案不论你怎么分，都不可能实现
这样一刀下去两个矩形的方式，所以这个呢，右图呢是不可以的，我们只能按照左图这种方式来进行切分。
那么，这个棋盘当中呢，每一个格子本身实际上是有
分值的，是吧？这不是乱分的，每一个，每一个盘上每一个格子都是有分值的。
那么，这个棋盘的总分 为其所有包含分，这个格子的这个分值之和。
我们现在要做的事呢，就是我们希望能够把这个棋盘
按照上面这样子一刀两块，这样的分配方式呢
来分割成n块这个矩形的棋盘 从而使得呢，各个矩形棋盘总分的
均方差最小，啊均方差最小，那么这里给出了这个计算均方差的一个
公式，那么其中这个x均值的话呢又可以通过这样的方式累加和来除n来进行计算。
那么我们看到，这个xi呢就是第r,第i块这个矩形棋盘的总分。
那么我们希望能够通过自己去设计一个程序，来给出这个棋盘
及n是吧，那么同时呢又要求出相应的sigma的最小值。
那么注意就是，输入的这个数据呢它分为
几行，第1行呢是包含了一个整数n,也就是一共要分成几个矩形
那么第2行至第9行呢，有每行有8个不小于100的非负整数
表示这个棋盘上，因为是8*8的嘛，每一个格子的分值
那么注意每一个分值之间呢是用空格来进行分隔的，那么最后输出呢很简单，我们就输出一个数
那么它是相应的这个，啊，方差值，均方差值 那么注意就是要求，要求四舍五入精确到小数点后三位，啊。
那么这是一个样，具体的样例的输入和输出。
我们这个输入的这个样例呢，我们看到我们希望将这个8*8的矩形呢
分成3块，啊，相应的每一个这个格子上的这个值呢
分值呢就是我们底下对应这个8*8的这个矩阵所描述的这个相应值。
我们看到这个相应的这个样例的输出呢，是1.633。
那么这个题目呢，其实非常的简单，那么要注意的一点就是
这个题目的分割方式呢，实际上决定了我们后面要考虑到的这个递归的方式
那么我们说到，既然一刀下去将这个矩形分成了两块，啊，那么
实际上对应每一次的分割呢，只包含了这样4种方式，啊这样4种
也就是我们看到，我们如果以这个蓝色块作为这个，啊
非保留块，也就是不要了，就是等于是通过这一刀分割下去
之后，不需要保留的那一块，而紫色块作为保留块来看的话
那么它实际上就包含了这样一共4种方式，是吧？
我们可以有横着、竖着切这样的两种，啊纵着这样切两刀
那么分别是这个留下了这个大的块 左边，右边这一块和左边这一块，是吧。
接着呢，我们也可以横着切一刀，啊，横着切一刀
那么紫色的块表明呢是留下来的块，啊分别留下这个下面的这个块或者是上面这一块。
也就是说我们的这个棋盘分割的方式呢都可以写成这样的一个递归的表达式。
可以把它写成什么呢？如果我们要将这个棋盘划分为
k块，啊，那么这样的一个划分的这个f的这样的一个
呃分割方式呢，就可以把它分割，认为是一个
相应的去分割掉1块，啊割下的那个棋盘和f呢
这函数下，k-1个，然后比如说待分割的那个棋盘
啊它包含了k-1个，也就是我们这个，分割的这个
内容呢，就包含了割下的棋盘和待分割的棋盘，啊那么
这个割下的棋盘呢，对应就是1，那么待分割的棋盘呢就是k-1。
那么其次呢就是因为我们需要去计算这个均方差的
所以我们看看均方差上面的这个公式呢实际上可以通过这样的一个数学的整理
可以整理出来说我们实际上主要就是去计算一个平方的和，和一个去减去一个相应的
n乘上一个均 均值的这个平方，啊，所以我们看到说，如果我们要
去求最小的方差，我们实际上只需要去求
最小的这个平方和就可以了。
那么相应的我们刚才已经看到，我们说我们去计算这个
分，棋盘分割的方式呢也只有这样的4种，是吧？那么我们如果去设对应的这个fun
n,这个分割n块是吧？它的这个输入进来的这个
对应的这个坐标点，其这个矩形的坐标点呢起始点是x1,y1
那么终止点就是x2和y2,是吧？也就是说我对应有一个矩形，那么起始，起始的这个点
是x1 y1 那么这个右下角的这个终止点呢是x2 y2,啊。
那么如果我们这时候来进行一下棋盘的分割的话 那么它分成了这个n份后的最小平方和
实际上可以认为说呢，表达式可以写成这样的一个 式子，是吧?
也就是我们说好这个fun是计算的这个相应的 平方和呢，它等于是什么呢？它就可以等于说是
我对应切一刀，是吧？我对应切一刀，那么这个时候
我的这个fun（n,x1,y1,x2,y2)这个值就可以看成是
我相应这 4种不同的切割方式中最小一种
所对应的那个值，啊；那么我这4种方式分别是
我在这个相应的这个 i，说如果我有一个矩形
那么起始是x1 y1,然后
终止是x2 y2,那么这个时候如果我希望是沿
x=i这个位置来进行切分的，啊x=i这个位置来切分
那么这个时候，相应的这个点 这个点就变成了是i和y2
所以呢，我的这个fun
这个函数就可以递归地写成是 如果我
左边的这块矩形是待分割的块，那么它就是n-1,是吧？那么它的
这个左，左上角的这个起始位置呢是x1 y1,而右下角的终止位置呢
就是i y2,是吧？那么相对应的，那么割下
的那块矩阵的这个相应的值呢就自然就会是
对应的n值就是1，是吧？而它的起始点呢
就是i+1 啊i+1，就是横坐标是i+1
那么y1到x2和y2,啊所以这是第1种情况切割的。
那么第2种情况呢，是说我的这个 矩形，它仍旧沿
x=i这个位置来进行切割，但是呢我用来保留的
那个块不再是左边这块了，啊，而是这个
右边这个块。
我让右边这个块呢是n-1,啊也就是说继续准备进行划分n-1个矩阵的
而左边这块呢变成是唯一割下的那一块
那么这个时候的话呢，我的这个其他的这个横纵坐标呢仍旧是跟第1种情况是一样的。
那么第3种，啊第3种，我们刚才看到都是沿x方向去切
那么第3种情况呢就是我让它呢沿y方向
去切，啊沿y方向去切，那么我让它沿y=i这样的一个方向去切
所以我看到呢，如果说我现在呢是希望让它
上面这一块继续做
后续的一些分割，也就是待分割的块
那么我的这个起始点呢自然还是（x1，y1）,啊
那么终止点呢就是这个x2
啊i,啊（x2，i） 而下面这一块
下面这一块呢那么它就是已经被割下的块，是吧，那么它的这个
起始点就是x1,i+1及终止点x2,y2
那么反过来也是一样的，我也可以对这一块呢来进行这个
上下呢进行一下调换，我让上面这个块呢是已经割下的块
而让底下这一块呢是准备进行后续的这个分割的操作的
所以这样的情况呢，就可以准确地描述我们刚才看到的这样的4种
分割方法，是吧？有这样4种分割方法，那么我们要去看一看说我们对
哪一种分割方法具体去更好地可以求到最后的这个最小平方和的来。
那么同样地，因为它是一个 具有相同分，这个切分方式的这么一个问题，所以对于其中的这个 n-1的这个
后续还要进行分割的这个问题上呢，我们就可以
迭代地仍然去使用fun这样的一个递归的函数 那么这个原先的包含n个块的问题，就被
化简为一个n-1规模的一个
啊矩阵进行，棋盘进行分割的一个问题了，所以呢我们会看到说
对于这个，啊 棋盘分割来讲，其关键就是去设计这个fun这个
函数，使得它呢能够相应地去满足
计算得到在4种不同的划分情况下
哪一种相应得到了这个最小平方和的值呢是 这个我们所希望能够求取的，那么注意就是其中这个
fun(1,x1,y1,x2,y2)呢这样的一个值的话呢
就相当于是整个棋盘内的这个分数和的这个平方。
那么想到刚才的这样的一个利用fun递归
来进行计算，获得最小平方和的这样的一个方式呢还不够，是吧？为什么呢？
因为如果你发现你写这样的一个程序的话，它会导致这个time limit
ever!也就是刚才那个过程实际上呢还是太消耗时间了。
那么我们说对于 去计算某个fun(n,x1,y1,x2,y2)这样的
一个计算来讲，是吧？对于某一个，其中的某一个子问题，那么它可能在很多地方都被去计算了
那么每一次计算都要去重新地去递归来算这些式子呢，实际上会消耗很多的时间，啊
那么我们会，在这里呢介绍说我们通常呢会通过去设计一个表，啊我们利用一个记录表
去记录相应的 每计算出来的某，对应某一个n值中间它相应的这个平方和
是多少，那么如果下一次再用到类似的这样的一个
值的这个，啊fun值的时候呢，啊我们就直接去查表
去看说我的这个res这个表里头是否已经保存了我
对应某一个n值下，这个矩形的相应的这个
啊最小平方和的计算，啊，如果本身这个里面没有保存，啊如果是-1，那么就需要去
保存相，计算相应的值，并且将其保存在我们设计的这个记录表当中。
那么如果它不为-1的话，我们就直接可以在这个表里面去，不为-1的话，那我们就可以直接在这个
表里面去返回其相应的值，那么通过这种方式呢，就可以大大地提高 这个时间的这个，呃，消耗。
那我们来具体看一下整个这个题目所对应的
程序。我们在这个题目当中呢，首先运用了3个
全局的数组，在这3个数组当中呢，存，分别存放的第1个s
它存放的是每一个格子所对应的分数，啊
那么有了这个分数之后，我们因为是要去计算这个最小的平方
和，是吧？最后，最终计算这个最小的均方差，所以呢我们
再去计算了一个从（1,1）这个位置开始到（i,j)对应矩阵
的这个分数之和，啊也就是说我们干脆直接把相应的这个矩阵块里面的这个分数之和呢
直接累，累加计算好，放在这个相应的这个sum这个
矩阵当中，然后呢，我们还定义了一个叫做res
这样的一个fun函数所记录出来的这个记录表，用来呢存放说当你有类似的
切割位置的时候，所计算到的值就可以不用反复地来进行递归计算了，就可以直接通过这个记录表
来进行读取；之后呢我们定义了一个函数，称为叫做calSum,啊calculatesum
cal calSum呢这个函数呢，它所计算，它包含了4个参数。
这4个参数呢就是用来去计算从(x1,y1)1到(x2,y2)
所对应的矩阵，矩形的这个，啊分数之和，啊
这个矩形的话呢，我们可以看到它所返回的就是
我相应如果有一个x1 y1,左上，x2
y2 右下的话，那么它就是我可以直接
计算相应的 这一整块，啊也就是说从这个
（0,0）点到（x2,y2)整个这个矩形的和，减去谁呢？首先减去的是
这个x2，然后y1-1,就是减去这一块的内容
再减去x1-1,y2的内容，啊也就是说，从这个
嗯，x1-1
到y2这一段，这一块矩形的内容
以及这个第3块，啊也就是这个x1-1
和y1-1这部分内容，也就是说我要获得这个
矩形所对应的分数之和呢，那么我们就可以直接利用
这样对应的两个坐标点的位置所对应的其他的这个
矩形来进行这个，大矩形减去其他3个小矩形可以计算得到。
那么接着呢，就是我们在这个题目当中的这个
递归函数，f u n fun是吧，这个fun这个函数中间呢它包含了
5个参数，第1个呢就是我对于当前这个矩形要切割的这个
块数，接着就是这个矩形所在的这个位置。
那么我们看到呢，我们对于这个矩形呢
呃，所进行的这个切分，我们首先去查找一下说我当前的这个res表里面是否保留我
对应这个 切分成n块，以及对这个x1,y1,x2,y2这个矩形进行切分
这个过程是否已经计算过了，如果它不等于-1，说明它已经有相应的记录的值的话呢
我们不需要去进行其他的计算，直接返回相应记录表中的值就可以了。
如果呢它没有，那么我们就要进行后续的判断，那么当然呢
这个迭代的终止条件呢，其实呢就是我的这个 n
最后进行一次划分，啊进行一次划分，那么相应的这个一次划分呢
只需要去计算一下（x1,y1,x2,y2）它对应的这个
呃矩形的这个分数之和就可以了。
那么同时的话呢，因为我当前的这个值没有保存在表里
所以我需要把我算出来的这个t,啊它对应的这个
和的这个平方值呢，把它保存在res这个矩阵 在这个呃记录表当中
并且呢，要让它返回我相应的这个fun所计算出来的这个值。
那么除了只切割一块，就是说
只进行一次划分的这样的一个方式之外的话呢 我们会看到如果我要进行多次
划分，啊也就是说要分，把这个n次这个，就是n个这个
矩形呢进行，要把这个棋盘呢分成n块
那么在这种情况下呢，我们刚刚介绍到会有4种情况，那么这4种分割的
方式呢，实际上如果简单地去划分一下，应该可以看成是有两类。
一类的话呢，就是我会对当前的这个棋盘沿x 中间的某一个值，也就是说纵着切一下，是吧，总这切一下。
那么我们会看到如果我们就是沿x=a 这个位置来进行
切分，啊，进行切分的话，那我们for循环就是让a从x1一直循环到
x2。也就是说，对应在这个里面每一个位置上都是有可能进行切分的。
那么，这个时候的话呢，那么，这个我们看到这个棋盘就被分割成为了两份，
那么左边这份，也就是说xy1到ay2我们称之为叫做e。
啊，那么右边这块呢称之为叫做c ，小c。
这两块呢我们都可以直接通过这个calSum呢，计算其相应的这个矩形的
这个相应的分值之和。那么有了这样的切分之后，我们好要进行一项分配，是吧，我们说这个
n+1也就是说待会儿进行下一步进行分割的这个
块儿呢到底是取c还是取e所对应的内容？是吗？那么我们可以让
进一步呢不断的去切分这个左边这个块儿。
所以我们要计算的是我们要去迭代的去调用 funn-1x,
y1,a, y2然後去累加上我们接下的这一块的
这个和的平方c*c。或者呢我们去计算
让进一步去切分右边这个框，啊，让n-1。
然后切分从a+1，y1开始一直到x2,y2然後去累加上
右，呃，左边这个小块儿的这个和的平方，也就是
e的平方。我们看到我们通过去比较这样两种方式中间
更小的那种切分房式，也就是说使得其和的这个平方最小的一种方式
作为我当前的这个沿x=a方向进行
切分中间最优的那种方式去赋值给我的t，那t就暂时保存了
我当前的这个分割后的最小值。那么，如果它是
小于Min的我就让这个T呢去更新我当前的这个Min值，
否则的话呢，那么除了这个，呃，当前的这个，呃，e沿x=a方向进行切分之外；
那么同样的我们还可以沿y=b方向来进行切分，啊，y=b方向进行切分。那么可以看到
就是从相应的 这个，上面这块我们把它称之为叫做e。
下面这块我们把它称之为叫做c，啊。那么我们同样可以用calSum 去计算e和c相应的这个，呃，分值和。
那么，我们同样的是去保留上面这一部分进行进一步的后续n-1块儿的分配；
还是下面这部分进行n-1，大家要考虑两种情况是吧？
这两种情况呢，要进行一下比较，我们看一看说谁得到了这个相应的这个
呃，和的平方数最小呢，然後就把它赋值为t。那么这个时候的话呢，
t要进行一下比较，是吧，实际上它也同时跟上面的这个
沿x=a方向呢也进行了比较。我们得到了最终这个房式就是
我们得到这四种风格不同的分割方法
所最终能够看到的这个计算出的这个，呃，
矩形的这个分值之和。那么得到这个Min值呢
我们就认为是相应的，我们在这一次递归调用计算
这个情况下a以及相应x1，y1，x2，y2这样的一个组合下的这个
最终的这个结果，所以我们用来净把这个记录表呢也相应的进行一下这个，呃，更新。
完了之后呢就是return min，啊， 也就是说就可以得到这个相应的这个平方和的最小值。
那么好这个主函数呢，就非常的简单了，在main函数里头呢我们看到我们
首先呢就让它去输入相应的这个分割，希望对这个棋盘进行的分割数n，啊。
有了这个n之后呢，我们会相应的把这个棋盘中间的每一个格子所
对应的分数呢，都存放在我们定义的的这个s这样的一个二维数组中间。
那么，为了后续的这个数值计算的方便呢，我们也相应的把
对应包含每一个格子所在的这个举证的
这个累加了这个和的这个值呢，也通过这个，呃，计算呢得到
寄放在这个Sum这样的一个二维数组当中。这样也方便了我们看到刚才fun这个
呃，递归的函数中间呢，可以直接去利用其相应的这个
累加和的这个值来进行后续的一些计算。
当然呢，我们最关键的还是去调用我的这个fun
这样的一个递归函数，那么当然在开始程序
初始实行的时候我们是希望进行n次分割，那么待分割的
这个块儿呢当然是从1，1，一直到8，8，这个位坐标值的位置。
那么后续我们就可以进一步去将这个n规模的 切割呢分成到变成是n-1到n-2，一直到
到1这样的一个规模，对吧？到1这个规模。
所以呢，我们利用fun这样的一个递归函数就可以有效的计算出相应的
得到最小的平方和这样的一个计算的一个方式；从而
根据我们该才我们整理的那个公式呢，可以计算出来相应的这个result的这样一个值。
那么有了result的这个值之后呢，当然我们要去计算用result的去除以这个n方再开更号，是吧？
从而最终得出这个均方 差这样的一个值的计算。那么题目呢此外还要求我们必须要
45度并且保留小数点后三位这样的一个经度；
所以我们在cout这个时候呢，就需要去cout一下ios flags。
那么，是fixed小数点的位置，并且呢，是以小数点后方位来进行
输出这样的方式，这就是关于其它分割问题的一个求解过程。
