闭包算法
‘壹’ java 中到底什么叫闭包 另外，快排的算法我懂， 但到底什么样的程序才叫快排呢……望指点~
什么是闭包
闭包的概念，不同资料给出了好几种。
闭包：包含了自由(未绑定)变量的代码块，这些变量不是在这个代码块中或者任何全局上下文中定义的，而是定义代码块的环境中定义的。也就是下面两部分：
要执行的代码块(由于自由变量存在，相关变量引用没有释放)
为自由变量提供绑定的计算环境(作用域)
闭包：一种函数对象或者匿名函数，作为参数传递，可以动态的创建与返回
闭包：具有闭合作用域的匿名函数
第一层理解：闭包是具有特别作用域规则且可以作为参数的代码块
3.times {puts "Inside the times method."}
Results:
Inside the times method.
Inside the times method.
Inside the times method.
第二层理解：给上述的代码块扩展一个参数列表，使方法或函数可以与这个代码通讯
['lions', 'tigers', 'bears'].each {|item| puts item}
Results:
lions
tigers
bears
第三层理解：将这样的代码块作为参数传递
animals = ['lions', 'tigers', 'bears'].collect {|item| item.upcase}
puts animals.join(" and ") + " oh, my."
LIONS and TIGERS and BEARS oh, my.
第四层理解：定义代码块的环境的名称空间和使用它的函数之间的作用域本质上是一个作用域,即：作用域是闭合的
tax = 0.08
prices = [4.45, 6.34, 3.78]
tax_table = prices.collect {|price| {:price =＞ price, :tax =＞ price * tax}}
tax_table.collect {|item| puts "Price: #{item[:price]} Tax: #{item[:tax]}"}
Results:
Price: 4.45 Tax: 0.356
Price: 6.34 Tax: 0.5072
Price: 3.78 Tax: 0.3024
按照SCIP定义：闭包就是一个携带有本地状态的函数
我对闭包的理解
闭包具有函数的性质
能完成一定的功能的代码块
能够预定义参数和引用作用域中的参数
能够在需要的地方被调用
闭包可以看成对象
能够作为参数传递
作用域的作用
作用域设定一个运行空间，但是作用域本身也很无赖，作用域知道自己能干什么，但是不知道具体要怎么做。只要作用域真正要用的时候，见到了闭包里面的代码块，作用域才算功德圆满了。这就是所谓“动态”的一种体现吧
作用域决定了闭包中代码块的使用方法
作用域决定了闭包中预设参数的本质，如参数的个数，类型
疑问：还没有搞清楚一个问题，在这里请教一下知道的
在闭包里面作用域提供的参数 是怎么和闭包里面预设的参数一一对应起来的呢？见下面代码
printMapClosure = {| key, value| puts key + "=" + value }
[ "yue" : "wu", "lane" : "burks", "sudha" : "saseethiaseeleethialeselan" ].each(printMapClosure)
result:yue=wu
lane=burks
sudha=saseethiaseeleethialeselan
我想知道为什么 key就对应yue，lane，sudha呢？而value就会对应wu，burks，sasee...呢？
作用域决定了闭包的最终处理结果
总结：闭包是一种被作用域限制的函数对象
另附：未来Java可能会采用的两种闭包形式
BGGA方案
说明：扩展了类型系统，引入了 function 类型，即函数都带有一个类型参数列表、返回类型和 throws 子句。
代码：完成求平方和
sumOfSquares = mapRece(myBigCollection,
{ Double x =＞ x * x },
{ Double x, Double y =＞ x + y });
CICE方案
说明：通过定义更简化的内部类来完成对闭包的支持
代码：完成求平方和
Double sumOfSquares = mapRece(myBigCollection,
UnaryFunction＜Double＞(Double x) { return x*x; },
BinaryFunction＜Double, Double＞(Double x, Double y) { return x+y; });
‘贰’ 数据库闭包的计算
闭包就是由一个属性直接或间接推导出的所有属性的集合，例如：
f={a->b,b->c,a->d,e->f}
由a可直接得到b和d，间接得到c，则a的闭包就是{a,b,c,d}
‘叁’ Warshall算法求传递闭包，Python语言~
def __warshall(self, a):
assert (len(row) == len(a) for row in a)
n = len(a)
#请在下面编程实现Roy-Warshall求传递闭包的算法
#参数a：为一个关系矩阵
# 请删除pass后编程实现该方法功能
for i in range(n) :
for j in range(n):
if a[j][i] == 1:
for k in range(n):
a[j][k] = a[j][k] | a[i][k]
# 请在上面编写程序，不要修改下面代码
return a
‘肆’ 二元关系的关系的闭包
设R是非空集合A上的关系， R的自反（对称或传递）闭包是A上的关系R' ，满足
(1) R'是自反的（对称的或传递的）
(2)
(3) 对A上任何包含R的自反（对称或传递）关系R''有
一般将R的自反闭包记作r(R)，对称闭包记作s(R) ，传递闭包记作t(R)。
下列给出了构造闭包的方法：对于有限集合A 上的关系R ，存在一个正整数s，使得 ，且s不超过A的元素数。
求传递闭包是图论中一个非常重要的问题，例如给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。可以直接利用关系矩阵相乘来求传递闭包，但那样做复杂度比较高；好一点的办法是在计算矩阵相乘的时候用分治法降低时间复杂度；但最好的方法是利用基于动态规划的Floyd-Warshall算法来求传递闭包。
‘伍’ 设有函数依赖集F={AB->CE,A->C,GP->B,EP->A,CDE->P,HB->P,D->HG,ABC->PG},计算属性集D关于F的闭包D
首先，求闭包的算法：
输入：有限的属性集合U，它上面的函数依赖集F，
和U的一个子集X。
输出：X关于F的属性闭包X+ 。
方法: (1)置初始X(0)= X(1)=X;
(2)如果X(0)X(1)，置X(0)=X(1)，否则转向(4)；
(3)对F中的每一个函数依赖YZ,若 YX(1)，
置X(1)=X(1)Z，并转(2) ；
(4) 输出X(1)，即为X+ 。算法终止。
下面，利用上面算法解题，
X(0)=Φ，X(1)=D
因为x(0) ≠x(1),所以令X（0）=D
由D->HG得X（1）=D U HG=DHG
因为x(0) ≠x(1),所以令X（0）=DHG
因为此时没有关于DHG的函数依赖了，所以X（1）=DHG不变
此时X(0)= X(1)所以D的闭包等于DHG
以上为初学者必须掌握的基本算法（应该还有其他的，我们老师只讲了这种滴~）
其实根本不用这么复杂，熟悉了可以直接写结果
X(0)=D
由D->HG得X（1）=D U HG=DHG
因为此时没有关于DHG的函数依赖了，所以X（2）=DHG不变
X（1）=X（2）循环结束，D的闭包等于DHG
（望采纳哦~~~~~）
‘陆’ 离散数学中传递闭包怎么求 通俗一点
方法：warshall法，即运行n次，每次使得MR[n][i],MR[i][n]都为1时使得MR[i][j]为1,否则还是为MR[i][j]。
传递闭包的计算过程一般可以用Warshell算法描述：
For 每个节点i Do
For 每个节点j Do
If j能到i Then
For 每个节点k Do
a[j, k] := a[j, k] Or ( a[j, i] And a[ i, k] )
其中a数组为布尔数组，用来描述两个节点是否相连，可以看做一个无权图的邻接矩阵。算法过程跟Floyd很相似，三重循环，枚举每个中间节点。不过传递闭包只需要求出两个节点是否相连，而不用求其间的最短路径长。
传递性：对于一个节点i，如果j能到i，i能到k，那么j就能到k。求传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，就知道任意两个节点之间是否相连。
传递闭包的定义：R’是R（不具有传递性质）变动最少的步骤得到的具有传递性质的关系。
(6)闭包算法扩展阅读
算法实例：
#include<stdio.h>
#define
N
10
int
judge(int
k,int
i,int
j)
{
if(i==1
&&
j==1){
return
1;
}
return
k;
}
void
warShall(int
MR[N][N],int
n)
{
for(int
k=0;k<n;k++){
for(int
i=0;i<n;i++){
for(int
j=0;j<n;j++){
if(i!=k
||
j!=k){
MR[i][j]=judge(MR[i][j],MR[k][j],MR[i][k]);
}
}
}
}
}
int
main()
{
int
MR[10][10];
int
mul;
scanf("%d",&mul);
for(int
i=0;i<mul;i++){
for(int
j=0;j<mul;j++){
scanf("%d",&MR[i][j]);
}
}
printf("求传递闭包为:\n");
warShall(MR,mul);
for(int
i=0;i<mul;i++){
for(int
j=0;j<mul;j++){
printf("%d
",MR[i][j]);
}
printf("\n");
}
return
0;
}
运行结果：
参考资料：网络-传递闭包
‘柒’ 求计算机求解关系R的传递闭包 C语言算法
传递闭包,最简单的技术是采用 【弗洛伊德算法】
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
1.若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
2.若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。
代码请见：
‘捌’ 数据库属性集合的闭包怎么求
计算属性集闭包X+的算法如下：
输入：X，F
输出：
X+
迭代算法的步骤：
①
选取X+的初始值为X
，即X+＝{X}；
②
计算X+，
X+＝{XZ}
，其中Z要满足如下条件：
YX+，且F中存在一函数依赖Y→Z。实际上就是以X+中的属性子集作为函数依赖的决定因素，在F中搜索函数依赖集，找到函数依赖的被决定属性Z放到X+中。
③
判断：如果X+没有变化？或X+等于U？则X+就是所求的结果，算法终止。否则转②。
因为U是有穷的，所以上述迭代过程经过有限步骤之后就会终止。
‘玖’ 数据库原理中属性集的闭包及其算法重要吗
考虑到安全性的话
是很重要的
比如说
方法
A
{
属性
a
方法
B{
a=1;
return
a;
}
}
这样
不管外部如何更改属性a但调用方法A返回的始终是1
这样保证了数据不会被外部篡改
‘拾’ 数据库闭包怎么计算
已知关系模式R<U，F>，其中
U={A，B，C，D，E}；
F={AB→C，B→D，C→E，EC→B，AC→B}。
求（AB）F+ 。
解 设X（0）=AB；
(1)计算X（1）: 逐一的扫描F集合中各个函数依赖，
找左部为A，B或AB的函数依赖。得到两个：
AB→C，B→D。
于是X（1）=AB∪CD=ABCD。
(2)因为X（0）≠ X（1） ，所以再找出左部为ABCD子集的那些函数依赖，又得到AB→C，B→D， C→E，AC→B，
于是X（2）=X（1）∪BCDE=ABCDE。
(3)因为X（2）=U，算法终止
所以（AB）F+ =ABCDE。
求属性集X（X U）关于U上的函数依
赖集F 的闭包XF+
输入：X，F
输出：XF+
步骤：
（1）令X（0）=X，i=0
（2）求B，这里B = { A |( V)( W)(V→WF
∧V X（i）∧A W)}；
（3）X（i+1）=B∪X（i）
（4）判断X（i+1）= X （i）吗?
（5）若相等或X（i）=U , 则X（i）就是XF+ ,
算法终止。
（6）若否，则 i=i+l，返回第（2）步。
对于算法6.l， 令ai =|X（i）|，{ai }形成一个步长大
于1的严格递增的序列，序列的上界是 | U |，因
此该算法最多 |U| - |X| 次循环就会终止。