大家好 我不会长时间通过解释声明式方法来引起您的注意，我将尝试建议使用逻辑编程语言解决另一个问题，作为对问题及其解决方案的声明式视图的一种选择。

任务391. 完美矩形

给定N个轴对齐的矩形（其中N> 0），确定它们是否全部一起形成矩形区域的精确覆盖。
每个矩形都表示为左下角和右上角。 例如，单位正方形表示为[1,1,2,2]。 （左下角的坐标是（1，1），右上角的坐标是（2，2））。

示例1：矩形= [
[1,1,3,3]，
[3,1,4,2]，
[3,2,4,4]，
[1,3,2,4]，
[2,3,3,4]
返回true。 所有5个矩形一起形成一个矩形区域的确切覆盖范围。
...
示例3：矩形=
[[1,1,3,3]，
[3,1,4,2]，
[1,3,2,4]，
[3,2,4,4]
返回false。 因为顶部中心有一个缝隙。

考虑到措辞，第二天过去了，这当然不是打开老式灯的为期一周的课程，但是我仍然想介绍这项工作的结果。 为了解决所有可用的测试，我们进行了几次尝试。

初始数据由一个列表表示，我简要地提醒您，该列表为[Head | Tail]，其中Tail是一个列表，该列表也为空[] 。

我们制定1

有必要计算所有矩形的总面积，找到描述它们的矩形的最大尺寸，并比较这两个总和（如果这意味着所有矩形均等地覆盖该区域）。 同时，检查矩形是否不相交，我们将每个新矩形添加到列表中，根据条件，它不应重叠并与所有先前的矩形相交。

为此，我使用了尾递归（也称为下降递归），这是表示循环的最“必要”方法。 在一个这样的“循环”中，我们立即找到面积的总和，以及所描述矩形的最小左角和最大直角，加长，累积一组图形，并检查是否没有交集。

像这样：

findsum([], Sres,Sres,LConerRes,LConerRes,RConerRes,RConerRes,_). findsum([[Lx,Ly,Rx,Ry]|T], Scur,Sres,LConerCur,LConerRes,RConerCur,RConerRes,RectList):- mincon(Lx:Ly,LConerCur,LConerCur2), maxcon(Rx:Ry,RConerCur,RConerCur2), Scur2 is Scur+(Rx-Lx)*(Ry-Ly), not(chekin([Lx,Ly,Rx,Ry],RectList)), findsum(T, Scur2,Sres,LConerCur2,LConerRes,RConerCur2,RConerRes,[[Lx,Ly,Rx,Ry]|RectList]). 

在Prolog中，变量是未知的，无法更改，它们为空或具有值，这需要几个变量，即初始变量和结果变量，当我们到达列表的末尾时，当前值将成为结果（规则的第一行）。 与命令式语言不同， 支持 要理解程序行，您需要想象导致它的整个路径，并且所有变量都可以具有自己的累积“历史”，就在那儿，程序的每一行仅在当前规则的上下文中，而所有影响其的状态 有 进入规则。

因此：

 %   mincon(X1:Y1,X2:Y2,X1:Y1):-X1=<X2,Y1=<Y2,!. mincon(_,X2:Y2,X2:Y2). %  maxcon(X1:Y1,X2:Y2,X1:Y1):-X1>=X2,Y1>=Y2,!. maxcon(_,X2:Y2,X2:Y2). 

在此，为了表示角度，使用形式为X：Y的“结构项”，这是将多个值组合成结构的机会，因此，说一个元组，只有任何运算都可以是函子。 并剪裁 “！”可让您在规则的第二行中不指定条件，这是提高计算效率的一种方式。

后来发现，最重要的是检查矩形的非相交，它们在列表中累积：

 %    chekin(X,[R|_]):-cross(X,R),!. chekin(X,[_|T]):-chekin(X,T). %     ,    cross(X,X):-!. cross(X,Y):-cross2(X,Y),!. cross(X,Y):-cross2(Y,X). %,       cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11<X22,X22=<X12,Y11<Y22,Y22=<Y12,!.%rt cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11=<X21,X21<X12,Y11<Y22,Y22=<Y12,!.%lt cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11<X22,X22=<X12,Y11=<Y21,Y21<Y12,!.%rb cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11=<X21,X21<X12,Y11=<Y21,Y21<Y12. %lb 

矩形的交点，这是在第一个内的另一个顶部中的四个选项。

最后的声明：

 isRectangleCover(Rects):- [[Lx,Ly,Rx,Ry]|_]=Rects, findsum(Rects,0,S,Lx:Ly,LconerX:LconerY,Rx:Ry,RconerX:RconerY,[]),!, S=:= (RconerX-LconerX)*(RconerY-LconerY). 

在输入处，使用一列图形，我们将第一个作为左，右角的初始值，然后遍历所有这些角，计算总面积，并验证所获得的总和。 我注意到，如果有一个矩形的交集，则搜索数量“拒绝”，返回“下降”，这意味着没有什么可以比较这些数量。 如果输入列表中没有单个数字，则会发生相同的情况，这将导致失败，没有可验证的内容...

接下来，我在现有测试上运行此实现，并引用前40个：

 %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]),true). :-assert_are_equal(isRectangleCover([[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[0,0,4,1]]),false). 

 :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[4,0,5,1],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),true). :-assert_are_equal(isRectangleCover([[0,0,4,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,3,3],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[1,1,2,2],[2,1,3,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,3,2],[1,0,2,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,1,2],[0,2,1,3],[0,3,1,4]]),true). :-assert_are_equal(isRectangleCover([[0,0,1,1],[1,0,2,1],[2,0,3,1],[3,0,4,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,2,2],[1,1,3,3],[2,0,3,1],[0,3,3,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,1],[0,1,2,3],[1,0,2,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[2,2,4,4],[4,1,5,4],[1,3,2,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,2,1],[1,0,2,1],[0,2,2,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,2,1],[0,1,2,2],[0,2,1,3],[1,0,2,1]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[0,1,1,2],[1,0,2,1],[0,2,3,3],[2,0,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,4],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,3],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,5,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[0,2,1,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,3],[1,1,2,2],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,4,4],[1,3,4,5],[1,6,4,7]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,1],[0,1,2,3],[2,0,3,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[1,1,2,2],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[1,1,2,2],[1,1,2,2],[2,1,3,2],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[2,1,3,2],[2,1,3,2],[2,1,3,2],[3,1,4,2]]),false). :-assert_are_equal(isRectangleCover([[0,1,2,3],[0,1,1,2],[2,2,3,3],[1,0,3,1],[2,0,3,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,2,1,3],[1,1,2,2],[2,0,3,1],[2,2,3,3],[1,0,2,3],[0,1,3,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,1,2],[0,2,1,3],[1,0,2,1],[1,0,2,1],[1,2,2,3],[2,0,3,1],[2,1,3,2],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[-1,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[1,0,2,1],[1,0,3,1],[3,0,4,1]]),false). :-assert_are_equal(isRectangleCover([[1,2,4,4],[1,0,4,1],[0,2,1,3],[0,1,3,2],[3,1,4,2],[0,3,1,4],[0,0,1,1]]),true). 

这不是终点，这是“困难”部分的任务，在41个测试中，他们提供了10,000个矩形的列表，在最近的所有五个测试中，我得到的时间都在几秒钟内：

 test 41:length=10000 goal->ok:212/sec test 42:length=3982 goal->ok:21/sec test 43:length=10222 goal->ok:146/sec test 44:length=10779 goal->ok:41/sec test 45:length=11000 goal->ok:199/sec 

我无法带来输入值，它们不适合编辑器，我将像这样附加测试41 。

措辞2

以前的方法，使用该列表来累加数字，结果是非常无效的，这种变化表明了它本身-而不是复杂度n ^ 2，取n * log（n）。 您可以使用树来检查矩形列表的交点。

Prolog的二叉树也是一个结构化术语，并且作为递归定义的列表，该树为空或包含一个值和两个子树 。

为此，我使用三重函子：t（LeftTree，RootValue，RightTree），并且空树为[]。

一个简单的数字树，其左边的顺序较小，而右边的顺序较大，可以这样表示：

 add_to_tree(X,[],t([],X,[])). add_to_tree(X,t(L,Root,R),t(L,Root,NewR)):- X<Root,!,add_to_tree(X,R,NewR). add_to_tree(X,t(L,Root,R),t(NewL,Root,R)):- add_to_tree(X,L,NewL). 

在I. Bratko的经典著作“人工智能序言中的编程”中，给出了许多由AVL平衡的2-3棵树的实现...

我建议按以下方式解决矩形排序的问题：如果矩形位于另一个矩形的右侧，则它们不相交，应检查左侧的矩形是否相交。 在右边，这是当其中一个的右角小于第二个的左角时：

 righter([X1,_,_,_],[_,_,X2,_]):-X1>X2. 

在树中累积数字并检查相交的任务可能看起来像这样，当新的矩形位于根的右侧时，则需要在右侧进行检查，否则请在左侧进行检查：

 treechk(X,[],t([],X,[])). treechk([X1,Y1,X2,Y2],t(L,[X1,Y11,X2,Y22],R),t(L,[X1,Yr,X2,Yr2],R)):- (Y1=Y22;Y2=Y11),!,Yr is min(Y1,Y11),Yr2 is max(Y2,Y22). %union treechk(X,t(L,Root,R),t(L,Root,NewR)):- righter(X,Root),!,treechk(X,R,NewR). treechk(X,t(L,Root,R),t(NewL,Root,R)):- not(cross(X,Root)),treechk(X,L,NewL). 

立即考虑另一个 把戏 如果矩形的宽度相同且具有相同的面，则可以将它们合并为一个而不添加到树中，而只需在一个节点中更改矩形的大小即可。 测试41为此进行了测试，这些数据为：[[0，-1,1,0]，[0,0,1,1]，[0,1,1,2]，[0,2,1， 3]，[0,3,1,4]，[0,4,1,5]，[0,5,1,6]，[0,6,1,7]，[0,7,1， 8]，[0,8,1,9]，[0,9,1,10]，[0,10,1,11]，[0,11,1,12]，[0,12,1， 13]，[0,13,1,14]，...，[0,9998,1,9999]]。

我们将这些改进与以前的解决方案结合在一起，我将对它们进行全面的改进，并进行一些改进：

 treechk(X,[],t([],X,[])). treechk([X1,Y1,X2,Y2],t(L,[X1,Y11,X2,Y22],R),t(L,[X1,Yr,X2,Yr2],R)):- (Y1=Y22;Y2=Y11),!,Yr is min(Y1,Y11),Yr2 is max(Y2,Y22). %union treechk(X,t(L,Root,R),t(L,Root,NewR)):- righter(X,Root),!,treechk(X,R,NewR). treechk(X,t(L,Root,R),t(NewL,Root,R)):- not(cross(X,Root)),treechk(X,L,NewL). righter([X1,_,_,_],[_,_,X2,_]):-X1>X2. findsum([],Sres,Sres,LConerRes,LConerRes,RConerRes,RConerRes,_). findsum([[Lx,Ly,Rx,Ry]|T],Scur,Sres,LConerCur,LConerRes,RConerCur,RConerRes,RectTree):- coner(Lx:Ly,LConerCur,=<,LConerCur2), coner(Rx:Ry,RConerCur,>=,RConerCur2), Scur2 is Scur+abs(Rx-Lx)*abs(Ry-Ly), treechk([Lx,Ly,Rx,Ry],RectTree,RectTree2),!, findsum(T,Scur2,Sres,LConerCur2,LConerRes,RConerCur2,RConerRes,RectTree2). isRectangleCover(Rects):- [[Lx,Ly,Rx,Ry]|_]=Rects, findsum(Rects,0,S,Lx:Ly,LconerX:LconerY,Rx:Ry,RconerX:RconerY,[]),!, S=:= abs(RconerX-LconerX)*abs(RconerY-LconerY). coner(X1:Y1,X2:Y2,Dir,X1:Y1):-apply(Dir,[X1,X2]),apply(Dir,[Y1,Y2]),!. coner(_,XY,_,XY). cross(X,X):-!. cross(X,Y):-cross2(X,Y),!. cross(X,Y):-cross2(Y,X). cross2([X11,Y11,X12,Y12],[_,_,X22,Y22]):-X11<X22,X22=<X12, Y11<Y22,Y22=<Y12,!. %right-top cross2([X11,Y11,X12,Y12],[X21,_,_,Y22]):-X11=<X21,X21<X12, Y11<Y22,Y22=<Y12,!. %left-top cross2([X11,Y11,X12,Y12],[_,Y21,X22,_]):-X11<X22,X22=<X12, Y11=<Y21,Y21<Y12,!. %right-bottom cross2([X11,Y11,X12,Y12],[X21,Y21,_,_]):-X11=<X21,X21<X12, Y11=<Y21,Y21<Y12. %left-bottom 

这是“大量”测试的运行时：

 goal-true->ok:0/sec 41:length=10000 goal-true->ok:0/sec 42:length=3982 goal-true->ok:0/sec 43:length=10222 goal-true->ok:2/sec 44:length=10779 goal-false->ok:1/sec 45:length=11000 goal-true->ok:1/sec 

我将完成这项改进，所有测试均正确通过，时间令人满意。 谁有兴趣，我建议您在线或在这里尝试。

合计

与功能编程相关的文章在门户网站上的出现频率恒定。 我谈到了声明式方法的另一个方面-逻辑编程。 您可以使用逻辑描述来表示任务，其中包括事实和规则，前提和后果，关系和递归关系。 任务描述必须变成描述它的一组关系。 结果是将问题分解为更简单的组件的结果。

声明性语言的程序可以用作一组语句，这些语句应该构造一个结果，这是成功制定问题的一种解决方案。 优化可能包括，例如，可能需要澄清控制矩形相交的方法的“过程”描述；可以构建树结构以进行更有效的计算。

并且...在半年前的某个地方，Prolog从源代码的样式中消失了，我使用了它。 我必须指定一个“姐姐”埃尔朗。 但这不是像“流行”那样吗，Fortran和BASIC不在列表中，语言的评价是多少？