共有回帖数 0 个
-
第一部分：
问题示例：连通性（connectivity)
假如已知一个整数对（pair)序列，其中每个整数代表某种类型的一个对象，而且将p-q对解释成“p与q连通”。
假定关系“与.......”是可传递的：
如果p与q连通，同时q与r连通，则p与r连通.
我们的目的是编写一段程序，从集合(set）中过滤额外连接对；当程序输入一个对p-q，仅当程序此时已经看到的对不能通过可传递性证明p与q连通时，它才输出该对。如果前面的对表明p与q
连通，则程序应该忽略p-q，并继续输入下一个对。如：
3-4 3-4
4-9 4-9
8-0 8-0
2-3 2-3
5-6 5-6
2-9 2-3-4-9
5-9 5-9
7-3 7-3
4-8 4-8
5-6 5-6
0-2 0-8-4-3-2
6-1 6-1
注释
已知一个代表对象间连通性的整数对序列（一楼左边一列）
连通性算法的任务是输出那些提供了新连通的对（中间一列）如：对2-9不在输出列中，
因为前面的连通暗示存在2-3-4-9连通（右边的为推论佐证）
好了，我先吃饭去了
由于算法非常多，内容也非常广泛
所以我只能列举几个
希望大家谅解
今天讲的是：
连通性问题的快速查找解决方案：
#include stdio.h
#define N 10000
main()
{
int i,p,q,t,id[N];
for(i=0;iN;i++)
id=i;
while(scanf("%d %dn",&p,&q)==2)
{
if(id[p]==id[q])continue;
for(t=id[p],i=0;iN;i++)
if(id==t) id=id[q];
printf("%d %dn",p,q);
}
}
这个程序从标准输入读取一个小于N的非负整数对序列（“p q 对”的意思是“连通对象p与对象q”）,并且打印表示尚未连通对象的对。该程序使用了一个数组id，其中每项对应一个对象。
它具有以下属性：
仅当p与q 连通时，id[p]与id[q]相等。为了简单起见，我们将N定义成一个编译时常量
(complile--time constant)
另一个办法是：从输入读取它，再动态分配id数组。（具体方法以后在讲)
连通性问题的快速并集解决方案：
如果我们用下面代码替换上面程序中的while循环体，得到的结果是同样的，但并集运算计算量少，查找运算计算量大。代码中的for循环以及后面的if语句定义了p和q连通的id数组的必要且充分条件。
赋值语句id=j实现并集运算,代码如下：
for(i=p;i!=id;i=id);
for(j=q;j!=id[j];j=id[j]);
if(i==j) continue;
id=j;
printf("%d %dn",p,q);
快速并集的加权版本
这个程序是快速并集算法（上一个）的修改版本，
它使用一个额外的数组sz完成维护的目的，
为每个对象用id==i来表示，即在关联树中节点的数量。
因此，并集运算可以连接两棵指定树中的较小者与较大者，以此阻止树中长路径的增长。
#include stdio.h
#define N 10000
main()
{int i,j,p,q,id[N],sz[N];
for(i=0;iN;i++)
{id=i;sz=1;}
while(scanf("%d %dn",&p,&q)==2)
{
for(i=p;i!=id;i=id);
for(j=q;j!=id[j];j=id[j]);
if(i==j) continue;
if(szsz[j])
{id=j;sz[j]+=sz;}
else{id[j]=i;sz+=sz[j];}
printf("%d %dn",p,q);
}
}
最坏的情况：
对于加权快速并集算法最坏的情况是，每个并集运算连接和等大小树。如果对象的数量小于2的n次方，则从任意节点到树根的距离小于n.
对分路径压缩：
如果我们用如下代码替换上一个程序中的for循环，就可以对分我们所遍历的路径长度。
这种变化的最终结果是，经过一个长运算序列后，树变得几乎完全扁平。
for(i=p;i!=id;i=id)
id=id[id];
for(j=q;j!=id[j];j=id[j])
id[j]=id[id[j]];
搜索：
每次不成功搜索，顺序搜索都搜索N个数字，而成功搜索平均搜索约N/2个数字
如果下面的每个数字成为搜索对象的几率相等，则：
（1+2+...+N)/N=(N+1)/2
为搜索的平均开销。
下面我举两个例子一：
顺序搜索：
这个函数检查数V是否在与先前保存的数字集合a[1],a[1+1],...,a[r]中，
方法是从头到尾按顺序比较每个数。
如果搜索到了末尾，而没有找到搜索对象，则返回值-1。否则，返回包含搜索目标的数组位置索引。好了费话说到这里，代码如下：
int search(int a[],int v,int l,int r)
{ int i;
for(i=1;i=r;i++)
if(v==a) return i;
return -1;
}
按最坏的情况考虑，顺序搜索在有序表中每次检查N个数，所有搜索的平均搜索量为N/2个数。
对于不成功搜索仍然需要指定一个模型。假定前提是：在有序表中N个数定义的N+1个区间中,
搜索在每个区间终止的几率均等。因此，立即可以得到下式：
（1+2+...+N+N)/N=(N+3)/2
在表中第N项之前，之后终止的未成功搜索的开销都是相同值：N
二：
二分搜索：
这个程序与上一个功能相同，但效率更高
int search(int a[],int v,int l,int r)
{
while(r=l)
{
int m=(l+r)/2;
if(v==a[m]) return m;
if(va[m]) r=m-1;
else l=m+1;
}
return -1;
}
楼主 2016-03-26 14:20 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
