Floyd-Warshall算法描述 1)适用范围： a)APSP(All Pairs Shortest Paths) b)稠密图效果最佳 c)边权可正可负 2)算法描述： a)初始化：dis[u,v]=w[u,v] b)For k:=1 to n For i:=1 to n For j:=1 to n If dis[i,j]>dis[i,k]+dis[k,j] Then Dis[I,j]:=dis[I,k]+dis[k,j] c)算法结束：dis即为所有点对的最短路径矩阵 3)算法小结：此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。时间复杂度O(n^3)。 考虑下列变形：如(I,j)∈E则dis[I,j]初始为1,else初始为0，这样的Floyd算法最后的最短路径矩阵即成为一个判断I,j是否有通路的矩阵。更简单的，我们可以把dis设成boolean类型，则每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”来代替算法描述中的蓝色部分，可以更直观地得到I,j的连通情况。
标签： Floyd-Warshall Shortest Pairs Paths
上传时间： 2013-12-01
上传用户：dyctj
(1) 、用下述两条具体规则和规则形式实现.设大写字母表示魔王语言的词汇 小写字母表示人的语言词汇 希腊字母表示可以用大写字母或小写字母代换的变量.魔王语言可含人的词汇. (2) 、B→tAdA A→sae (3) 、将魔王语言B(ehnxgz)B解释成人的语言.每个字母对应下列的语言.
上传时间： 2013-12-30
上传用户：ayfeixiao
运动会分数统计 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表
上传时间： 2016-03-23
上传用户：zhuyibin
1.有三根杆子A,B,C。A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上 经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片： 如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 此外，汉诺塔问题也是程序设计中的经典递归问题
上传时间： 2016-07-25
上传用户：gxrui1991
1. 下列说法正确的是 （ ） A. Java语言不区分大小写 B. Java程序以类为基本单位 C. JVM为Java虚拟机JVM的英文缩写 D. 运行Java程序需要先安装JDK 2. 下列说法中错误的是 ( ) A. Java语言是编译执行的 B. Java中使用了多进程技术 C. Java的单行注视以//开头 D. Java语言具有很高的安全性 3. 下面不属于Java语言特点的一项是( ) A. 安全性 B. 分布式 C. 移植性 D. 编译执行 4. 下列语句中，正确的项是 ( ) A . int $e,a,b=10 B. char c,d=’a’ C. float e=0.0d D. double c=0.0f
上传时间： 2017-01-04
上传用户：netwolf
．数据结构 假设有M个进程N类资源，则有如下数据结构： MAX[M*N] M个进程对N类资源的最大需求量 AVAILABLE[N] 系统可用资源数 ALLOCATION[M*N] M个进程已经得到N类资源的资源量 NEED[M*N] M个进程还需要N类资源的资源量 2．银行家算法 设进程I提出请求Request[N]，则银行家算法按如下规则进行判断。 (1)如果Request[N]<=NEED[I，N]，则转(2)；否则，出错。 (2)如果Request[N]<=AVAILABLE，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 3．安全性检查 (1)设置两个工作向量WORK=AVAILABLE；FINISH[M]=FALSE (2)从进程集合中找到一个满足下述条件的进程， FINISH[i]=FALSE NEED<=WORK 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 WORK=WORK+ALLOCATION FINISH=TRUE GO TO 2 (4)如所有的进程Finish[M]=true，则表示安全；否则系统不安全。
上传时间： 2014-01-05
上传用户：moshushi0009
数据结构 假设有M个进程N类资源，则有如下数据结构： MAX[M*N] M个进程对N类资源的最大需求量 AVAILABLE[N] 系统可用资源数 ALLOCATION[M*N] M个进程已经得到N类资源的资源量 NEED[M*N] M个进程还需要N类资源的资源量 2．银行家算法 设进程I提出请求Request[N]，则银行家算法按如下规则进行判断。 (1)如果Request[N]<=NEED[I，N]，则转(2)；否则，出错。 (2)如果Request[N]<=AVAILABLE，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 3．安全性检查 (1)设置两个工作向量WORK=AVAILABLE；FINISH[M]=FALSE (2)从进程集合中找到一个满足下述条件的进程， FINISH[i]=FALSE NEED<=WORK 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 WORK=WORK+ALLOCATION FINISH=TRUE GO TO 2 (4)如所有的进程Finish[M]=true，则表示安全；否则系统不安全。
上传时间： 2013-12-24
上传用户：alan-ee
一种基于二维链表的稀疏矩阵模半板类设计 A template Class of sparse matrix. Key technology: bin,2-m linked matrix. constructors: 1.normal constuctor 2.copy constuctor. 3.assignment constructor. Basic operator: 1. addition(sub) of two matrix 2. inverse of a matrix. 3. multiply of two matrix. etc.
标签： matrix technology template linked
上传时间： 2013-12-13
上传用户：lwwhust
上下文无关文法（Context-Free Grammar, CFG）是一个4元组G=(V, T, S, P)，其中，V和T是不相交的有限集，S∈V，P是一组有限的产生式规则集，形如A→α，其中A∈V，且α∈(V∪T)*。V的元素称为非终结符，T的元素称为终结符，S是一个特殊的非终结符，称为文法开始符。 设G=(V, T, S, P)是一个CFG，则G产生的语言是所有可由G产生的字符串组成的集合，即L(G)={x∈T* | Sx}。一个语言L是上下文无关语言（Context-Free Language, CFL），当且仅当存在一个CFG G，使得L=L(G)。 *⇒ 例如，设文法G：S→AB A→aA|a B→bB|b 则L(G)={a^nb^m | n,m>=1} 其中非终结符都是大写字母，开始符都是S，终结符都是小写字母。
标签： Context-Free Grammar CFG
上传时间： 2013-12-10
上传用户：gaojiao1999
Josephus排列问题定义如下：假设n个竞赛者排成一个环形。给定一个正整数m，从某个指定的第一个人开始，沿环计数，每遇到第m个人就让其出列，且计数继续进行下去。这个过程一直到所有的人都出列为止。最后出列都优胜者。每个人出列的次序定义了整数1，2，...，n的一个排列。这个排列称为一个(n,m)Josephus排列。例如，（7,3)Josephus排列为3,6,2,7,5,1,4.对于给定的1，2，...n中的k个数，Josephus想知道是否存在一个正整数m(n,m)Josephus排列的最后k个数为事先指定的这k个数。
上传时间： 2015-09-20
上传用户：zycidjl
