在循环内及循环结束的时候都成立的表达式
一般而言,用这个式子表示希望得到的结果,如果在循环的每一步,这个式子都是正确的,那么循环结束后,这个式子也正确,并得到了期望的结果.
lenovo所引用的文章里的例子是这样的:
apvector<int> list(n); // n is some positive integer
int k, indexMax;
<code which assigns values to all entries in list>
indexMax = 0;
for(k = 1; k < list.length(); k++){
// invariant true here
if (list[k] > list[indexMax])
indexMax = k;
}
这是一个很简单的求最大值(在数组中的下标)的问题,在循环内// invariant true here 处可以指明始终成立的不变式为:
在当前的k之前, 最大值的下标是indexMax, 而且0<=indexMax<k
可以看出这个式子在整个循环过程中是始终成立的,所以在循环结束的时候(k=list.length()),这个式子也成立,
即:
在整个list中,最大值的下标是indexMax, 而且0<=indexMax<list.length()
这就是我们期望得到的结果,也就是说我们得到了最大值的下标
分享到:
相关推荐
这些笔记教会学生抽象地思考算法以及用于开发它们的关键算法技术。
循环不变式 循环不变式主要用来辅助我们理解算法的正确性,对于循环不变式,必须证明它的三个性质 初始化:它在循环的第一轮迭代开始之前,应该是正确的。保持:如果在某一次循环迭代开始之前是正确的,那么在下一...
eg.《算法导论》第二章,证明插入算法的正确性。1. 初始化(循环第一次迭代之前)的时候,j=2,A[1 ‥ j -1](即A[1])的“有序性”是成立的;2.
针对循环程序的部分正确性问题,在代数变迁系统理论基础上,结合约束理论提出了一种用Dixon结式生成循环不变式的算法。首先,程序被转换成代数变迁系统,再根据代数变迁关系和不变式模板构造一个多项式组,计算此...
该方法直接面向非递归算法,在形式化方法PAR的指导下,使用循环不变式的开发新策略,在得到求解递归问题的循环不变式的同时,能直接得到易读、高效且可靠的非递归算法,并通过一个具体实例进行了阐述。对使用形式化...
n-1]的平方平均值(1/n∑(0)b[i]*b[i])的规范(φ,ψ),循环不变式P, 有界函数t及其带循环程序.9) 试设计在数组b[0 .. n-1](n>0)中寻找x的位置I,且若x不在b中,则置I的值为n的程序规范(φ,ψ),循环不变式P,有界...
一种数据驱动工具,可产生足够多的循环不变量来进行程序验证。 [LoopInvGen扩展了我们的旧项目(现已停用),即PIE-前提条件推理引擎。 ] | ·| | · :page_with_curl: 论文和演讲 关于在用于“功能”综合的...
书中引入了“循环不变式”,并贯穿始终地用来证明算法的正确性。在不改动数学和分析重点的前提下,作者将第1版中的许多数学基础知识从第一部分移到了附录中。 二、本书的特点 本书在进行算法分析的过程中,保持了...
书中引入了“循环不变式”,并贯穿始终地用来证明算法的正确性。在不改动数学和分析重点的前提下,作者将第1版中的许多数学基础知识从第一部分移到了附录中。 二、本书的特点 本书在进行算法分析的过程中,保持了...
这是编译原理的源代码,涉及了编译原理的各个过程:词法分析,LL1语法分析,语义分析,中间代码生成,中间代码优化(常表达式优化,公共表达式优化,循环不变式优化),中间代码生成目标代码,目标代码的解释执行,...
一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。
一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。
第3节 产生循环不变式的一种方法 习题 第7章 递归程序及其正确性证明 第1节 迭代与递归 第2节 递归程序的一种模型 第3节 递归程序的正确性证明 习题 第8章 程序的形式推导技术 第1节 谓词变换器及其性质 第2节 面向...
一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。 本...
在有关算法的书中,有一些叙述非常严谨,但不够全面,另一些涉及了大量的题材,但又缺乏严谨性。《算法导论》将严谨性和全面性融为一体。 本书深入讨论各类算法,并...一项巧妙而又重要的修改是提前引入循环不变式,
一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材
一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。 ★...
一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。 ★...
一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。 ★...
一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。 ★...