精华内容
下载资源
问答
  • 循环不变式为算法思想,用于判断算法的正确性,通常通过三条性质证明:初始化、保持、终止。 1、初始化。比如插入算法开始第一次迭代之前,只有一个元素,显然成立。 2、保持。也就是算法循环过程中不变的特性...

    数学归纳法:

    最简单和常见的数学归纳法是证明当 n等于任意一个自然数时某命题成立。证明分下面两步:
    1. 证明当 n= 1时命题成立。
    2. 假设 n= m时命题成立,那么可以 推导出在 n= m+1时命题也成立。( m代表任意自然数)
    这种方法的原理在于:首先证明在某个起点值时命题成立,然后证明从一个值到下一个值的过程有效。当这两点都已经证明,那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成 多米诺效应也许更容易理解一些。例如:你有一列很长的直立着的多米诺骨牌,如果你可以:
    1. 证明第一张骨牌会倒。
    2. 证明只要任意一张骨牌倒了,那么与其相邻的下一张骨牌也会倒。
    3. 那么便可以下结论:所有的骨牌都会倒下。
    循环不变式:

    循环不变式为算法思想,用于判断算法的正确性,通常通过三条性质证明:初始化、保持、终止。

    1、初始化。比如插入算法开始第一次迭代之前,只有一个元素,显然成立。

    2、保持。也就是算法循环过程中不变的特性,比如插入排序,每次排完前面的序列都是排好序的。

    3、终止。循环结束时,可以保证算法正确,比如插入排序,前面n-1次都是排好序的,那么最后一次也是排好序的。



    正确算法的循环过程中总是存在一个维持不变的特性,这个特性一直保持到循环结束乃至算法结束,这样就可以保证算法的正确了。
    比方说插入排序,算法每次循环后,前n个数一定是排好序的(n为已经循环的次数)。由于这个特性一直成立,到算法结束时,所有N个数一定是排

    展开全文
  •  本文以经典的二分查找为例,介绍如何使用循环不变式理解算法并利用循环不变式在原始算法的基础上根据需要产生算法的变体。谨以本文献给在理解算法思路时没有头绪而又不甘心于死记硬背的人。  二分查找究竟有...

    序言

      本文以经典的二分查找为例,介绍如何使用循环不变式来理解算法并利用循环不变式在原始算法的基础上根据需要产生算法的变体。谨以本文献给在理解算法思路时没有头绪而又不甘心于死记硬背的人。

      二分查找究竟有多重要?《编程之美》第2.16节的最长递增子序列算法,如果想实现O(n2)到O(nlogn)的时间复杂度下降,必须借助于二分算法的变形。其实很多算法都是这样,如果出现了在有序序列中元素的查找,使用二分查找总能提升原先使用线性查找的算法。

      然而,虽然很多人觉得二分查找简单,但随手写一写却不能得到正确的结果:死循环、边界条件等等问题伴随着出现。《编程珠玑》第四章提到:提供充足的时间,仅有约10%的专业程序员能够完成一个正确的二分查找。当然,正确的二分查找和变体在算法书籍以及网络上随处可得,但是如果不加以理解,如何掌握?理解时,又往往因想不清楚,一知半解,效果有限。我在看相关的变体算法时就觉得一片茫然,不得要领:或许这个算法可以这么写,稍微变下要求就不能这么写了;举正例说明算法在某些情况下可以正常工作、举反例说明算法有错误固然可行,但仅有例子是不够的,怎样一劳永逸地证明自己几经修改的算法之正确?如果每一个变体都进行孤立地理解,那么太花费时间,而且效果也不好。如何解决这个问题?在思考方法和查阅书籍之后发现,还是要靠循环不变式来完成算法正确性的理论支撑。

      或许你曾了解过循环不变式,但如果不使用的话,是看不到它的强大之处的:不仅仅能帮助你证明算法正确性,同时也帮助你理解算法,甚至能帮助你在基本算法的基础上,构造出符合要求的相应算法变体。这些都将在后文的各个算法说明中看到。

     

    知识准备

      结合《算法导论》和《编程珠玑》,下面说明循环不变式的概念与性质。

      循环不变式主要用来帮助理解算法的正确性。形式上很类似与数学归纳法,它是一个需要保证正确断言。对于循环不变式,必须证明它的三个性质:

    初始化:它在循环的第一轮迭代开始之前,应该是正确的。

    保持:如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。

    终止:循环能够终止,并且可以得到期望的结果。

     

    文章说明

    (1)在推导每次数组减少的长度时,mid是不能代换成(left+right)/2的。这种形式代表了非整型的运算,没有舍去小数部分,而在代码中实际的mid是会舍去小数部分的。

    (2)代码部分的=和==意义同C语言;文字说明部分的=代表赋值,==代表等式推导或者逻辑判断,由上下文而定。

    (3)除了3和5外,最初的各个变体代码参考于:二分查找,你真的会吗? 为了符合思路的前后连贯和说明循环不变式,做了一些修改。原文的测试很方便,读者可以自行参考。

     

    1.二分查找值为key的下标,如果不存在返回-1。

    循环不变式

      如果key存在于原始数组[0,n-1],那么它一定在[left,right]中。

    初始化

      第一轮循环开始之前,处理的数组就是原始数组,这时显然成立。

    保持

      每次循环开始前,key存在于待处理数组array[left, ..., right]中。

      对于array[mid]<key,array[left, ..., mid]均小于key,key只可能存在于array[mid+1, ..., right]中;

      对于array[mid]>key,array[mid, ..., right]均大于key,key只可能存在于array[left, ..., mid-1]中;

      对于array[mid]==key,查找到了key对应的下标,直接返回。

      在前两种情况中,数组长度每次至少减少1(实际减少的长度分别是mid-left+1和right-mid+1),直到由1(left==right)变为0(left>right),不会发生死循环。

    终止

      结束时,left>right,待处理数组为空,表示key不存在于所有步骤的待处理数组,再结合每一步排除的部分数组中也不可能有key,因此key不存在于原数组。

    [cpp]  view plain copy
    1. int binsearch(int * array, int length, int key)  
    2. {  
    3.     if(!array)  
    4.         return -1;  
    5.     int left = 0, right = length,mid;  
    6.     while(left <= right)  
    7.     {  
    8.         mid = (left + right)/2;  
    9.         if(array[mid] < key)  
    10.         {  
    11.             left = mid + 1;  
    12.         }else if(array[mid] > key)  
    13.         {  
    14.             right = mid - 1;  
    15.         }else  
    16.             return mid;  
    17.     }  
    18.     return -1;  
    19. }  

    2.二分查找返回key(可能有重复)第一次出现的下标x,如果不存在返回-1

    循环不变式

      如果key存在于数组,那么key第一次出现的下标x一定在[left,right]中,且有array[left]<=key, array[right]>=key。

    初始化

      第一轮循环开始之前,处理的数组是[0,n-1],这时显然成立。

    保持

      每次循环开始前,如果key存在于原数组,那么x存在于待处理数组array[left, ..., right]中。

      对于array[mid]<key,array[left, ..., mid]均小于key,x只可能存在于array[mid+1, ..., right]中。数组减少的长度为mid-left+1,至少为1。

      否则,array[mid]>=key, array[mid]是array[mid, ..., right]中第一个大于等于key的元素,后续的等于key的元素(如果有)不可能对应于下标x,舍去。此时x在[left, ..., mid]之中。数组减少的长度为right-(mid+1)+1,即right-mid,根据while的条件,当right==mid时为0。此时right==left,循环结束。

    终止

      此时left>=right。在每次循环结束时,left总是x的第一个可能下标,array[right]总是第一个等于key或者大于key的元素。

      那么对应于left==right的情况,检查array[left]即可获得key是否存在,若存在则下标为x;

      对于left>right的情况,其实是不用考虑的。因为left==上一次循环的mid+1,而mid<=right。若mid+1>right,意味着mid == right,但此时必有left == right,这一轮循环从开始就不可能进入。

    [cpp]  view plain copy
    1. int binsearch_first(int * array, int length,int key)  
    2. {  
    3.     if(!array)  
    4.         return -1;  
    5.     int left = 0, right = length-1,mid;  
    6.     while(left < right)  
    7.     {  
    8.         mid = (left + right)/2;  
    9.         if(array[mid] < key)  
    10.             left = mid+1;  
    11.      else  
    12.             right = mid;  
    13.     }  
    14.     if(array[left] == key)  
    15.         return left;  
    16.     return -1;  
    17. }  

    3.二分查找返回key(可能有重复)最后一次出现的下标x,如果不存在返回-1(模仿2的第一版)

    循环不变式

      如果key存在于数组,那么key最后一次出现的下标x一定在[left,right]中,且有array[left]<=key, array[right]>=key。

    初始化

      第一轮循环开始之前,处理的数组是[0,n-1],这时显然成立。

    保持

      每次循环开始前,如果key存在于原数组,那么x存在于待处理数组array[left, ..., right]中。

      对于array[mid]<key,array[left, ..., mid]均小于key,x只可能存在于array[mid+1, ..., right]中。数组减少的长度为mid-left+1,至少为1。

      对于array[mid]==key, array[mid]是array[left, ..., mid]中最后一个值为key的元素,那么x的候选只能在array[mid, ... ,right]中,数组减少长度为mid-left。除非left == right或left == right-1,否则数组长度至少减小1。由于while的条件,只有后一种情况可能发生,如果不进行干预会陷入死循环,加入判断分支即可解决。

      对于array[mid]>key, array[mid, ..., right]均大于key,x只可能在[left, ..., mid-1]之中。数组减少的长度为(right-mid)+1,同样至少为1。

    终止

      此时left>=right,right总是从数组末尾向开始的倒序中第一个候选的x,检查它的值是否符合要求即可。

      而left总是上一轮删掉失去x资格的元素后的第一个元素,不过这里用不到。

    说明:

      与上一种不同,这个算法不能简单地根据对称,从上一个算法直接改过来,由于整数除法总是舍弃小数,mid有时会离left更近一些。所以这种算法只是沿着上一个算法思路的改进,看上去并不是很漂亮。

    [cpp]  view plain copy
    1. int binsearch_last(int * array, int length, int key)  
    2. {  
    3.     if(!array)  
    4.         return -1;  
    5.     int left = 0, right = length,mid;  
    6.     while(left < right)  
    7.     {  
    8.         mid = (left + right)/2;  
    9.         if(array[mid] > key)  
    10.             right = mid - 1;  
    11.         else if(array[mid] == key)  
    12.             if(left == mid)  
    13.                 if(array[right] == key)  
    14.                     return right;  
    15.                 else  
    16.                     return left;  
    17.             else  
    18.                 left = mid;  
    19.         else  
    20.             left = mid + 1;  
    21.     }  
    22.       
    23.     if(array[right] == key)  
    24.         return right;  
    25.     return -1;  
    26. }  

    4.二分查找返回key(可能有重复)最后一次出现的下标x,如果不存在返回-1(修改版)

      根据3中的讨论,可以发现不能直接照搬的原因是mid=(left+right)/2的舍弃小数,在left+1==right且array[left]=key时,如果不加以人为干预会导致死循环。既然最终需要干预,干脆把需要干预的时机设置为终止条件就行了。

      使用while(left<right-1)可以保证每次循环时数组长度都会至少减一,终止时数组长度可能为2(left+1==right)、1(left==mid,上一次循环时right取mid==left),但是不可能为0。(每一次循环前总有left<=mid<=right,无论令left=mid还是令right=mid,都不会发生left>right)。同3一样,right总是指向数组中候选的最后一个可能为key的下标,此时只需先检查right后检查left是否为key就能确定x的位置。这样就说明了循环不变式的保持和终止,就不再形式化地写下来了。

      对于两种情况的合并:array[mid] == key时,mid有可能是x,不能将其排除;array[mid]<key时,如果让left = mid+1,不会违反循环不变式的条件。但是由上面的讨论可知,将left=mid也是可以的,在达到终止条件前能保证数组长度单调减少。因此把两种情况合并成最终形式。

    [cpp]  view plain copy
    1. int binsearch_last_v2(int * array, int length, int key)  
    2. {  
    3.     if(!array)    return -1;  
    4.     int left =0, right = length-1,mid;  
    5.     while(left < right -1)  
    6.     {  
    7.         mid = (left + right)/2;  
    8.         if(array[mid] <= key)  
    9.             left = mid;  
    10.         else  
    11.             right = mid;  
    12.     }  
    13.   
    14.     if(array[right] == key)  
    15.         return right;  
    16.     else if(array[left] == key)  
    17.         return left;  
    18.     else  
    19.         return -1;  
    20. }  

    5.二分查找返回key(可能有重复)最后一次出现的下标x,如果不存在返回-1(利用2的方法)

      如果想最大限度地利用已有的函数,那么把需要处理的数组倒序,然后直接使用方法2,再把得到的第一次出现的下标做一次减法就可以得到最后一次出现的下标,略。

     

    6.二分查找返回刚好小于key的元素下标x,如果不存在返回-1

      如果第一反应是通过2的方法找出第一个为key的元素,返回它的下标减1,那么就错了:这个二分查找并没有要求key本身在数组中。

    循环不变式

      如果原始数组中存在比key小的元素,那么原始数组中符合要求的元素存在于待处理的数组。

    初始化

      第一轮循环开始之前,处理的数组是[0,n-1],这时显然成立。

    保持

      每次循环开始前,x存在于待处理数组array[left, ..., right]中。

      先用一个循环的条件为right>=left,违反则意味着x不存在。写下array[mid]的比较判断分支:

    (1) array[mid]<key, 意味着x只可能在array[mid, ..., right]之间,下一次循环令left = mid,数组长度减少了(mid-1)-left+1 == mid-left,这个长度减少量只有在right-left<=1时小于1。

    (2)array[mid]>=key,意味着x只可能在array[left ,... ,mid-1]之间,下一次循环令right = mid-1,同样推导出数组长度至少减少了1。

    这样,把循环条件缩小为right>left+1,和4一样,保证了(1)中每次循环必然使数组长度减少,而且终止时也和4的情况类似:终止时待处理数组长度只能为2或1或者空(left>right)。

    终止

       接着保持中的讨论,结束时,符合的x要么在最终的数组中,要么既不在最终的数组中也不在原始的数组中(因为每一次循环都是剔除不符合要求的下标)。

      数组长度为2时,right==left+1,此时先检查right后检查left。如果都不符合其值小于key,那么返回-1。数组长度为1时,只用检查一次;数组长度为0时,这两个都是无效的,检查时仍然不符合条件。把这三种情况综合起来,可以写出通用的检查代码。反过来,根据精简的代码来理解这三种情况比正向地先给出直观方法再精简要难一些。

    [cpp]  view plain copy
    1. int binsearch_last_less(int * array, int length, int key)  
    2. {  
    3.     if(!array)  
    4.         return -1;  
    5.     int left = 0, right = length,mid;  
    6.     while(left < right - 1)  
    7.     {  
    8.         mid = (left + right)/2;  
    9.         if(array[mid] < key)  
    10.             left = mid;  
    11.         else  
    12.             right = mid - 1;  
    13.     }  
    14.     if(array[right] < key)  
    15.         return right;  
    16.     else if(array[left] < key)  
    17.         return left;  
    18.     else  
    19.         return -1;  
    20. }  

    7.二分查找返回刚好大于key的元素下标x,如果不存在返回-1

      和6很类似,但如果只是修改循环中下标的改变而不修改循环条件是不合适的,下面仍要进行严谨的说明和修正。

    循环不变式

      如果原始数组中存在比key大的元素,那么原始数组中符合要求的元素对应下标x存在于待处理的数组。

    初始化:

      第一轮循环开始之前,处理的数组是[0,n-1],这时显然成立。

    保持:

      每次循环开始前,x存在于待处理数组array[left, ..., right]中。

      仍然先把执行while循环的条件暂时写为right>=left,违反则意味着x不存在。写下array[mid]的比较判断分支:

    (1) array[mid]<=key, 意味着x只可能在array[mid+1, ..., right]之间,下一次循环令left = mid,数组长度减少了mid-left+1,减少量至少为1。

    (2)array[mid]>key,意味着x只可能在array[left ,... ,mid]之间,下一次循环令right = mid,数组长度减少了right-(mid+1)+1== right-mid,只有在right==mid时为0,此时left==right==mid。因此,循环条件必须由right>=left收缩为right>left才能避免left==right时前者会进入的死循环。

    终止:

      由循环的终止条件,此时left>=right。类似2的分析,left>right是不可能的,只有left==right。此时检查array[right]>key成立否就可以下结论了,它是唯一的候选元素。

    补充说明:

      如果是对数组进行动态维护,返回值-1可以改为length+1,表示下一个需要填入元素的位置。

    [cpp]  view plain copy
    1. int binsearch_first_more(int * array, int length, int key)  
    2. {  
    3.     if(!array)  
    4.         return -1;  
    5.     int left = 0, right = length-1,mid;  
    6.     while(left < right)  
    7.     {  
    8.         int mid = (left+right)/2;  
    9.         if(array[mid] <= key)  
    10.             left = mid + 1;  
    11.         else  
    12.             right = mid;  
    13.     }  
    14.     if(array[right] > key)  
    15.         return right;  
    16.     return -1;  
    17. }  

    8.总结:如何写出正确的二分查找代码?

      结合以上各个算法,可以找出根据需要写二分查找的规律和具体步骤,比死记硬背要强不少,万变不离其宗嘛:

      (1)大体框架必然是二分,那么循环的key与array[mid]的比较必不可少,这是基本框架;

      (2)循环的条件可以先写一个粗略的,比如原始的while(left<=right)就行,这个循环条件在后面可能需要修改;

      (3)确定每次二分的过程,要保证所求的元素必然不在被排除的元素中,换句话说,所求的元素要么在保留的其余元素中,要么可能从一开始就不存在于原始的元素中;

      (4)检查每次排除是否会导致保留的候选元素个数的减少?如果没有,分析这个边界条件,如果它能导致循环的结束,那么没有问题;否则,就会陷入死循环。为了避免死循环,需要修改循环条件,使这些情况能够终结。新的循环条件可能有多种选择:while(left<right)、while(left<right-1)等等,这些循环条件的变种同时意味着循环终止时候选数组的形态。

      (5)结合新的循环条件,分析终止时的候选元素的形态,并对分析要查找的下标是否它们之中、同时是如何表示的。

      对于(3),有一些二分算法实现不是这样的,它会使left或right在最后一次循环时越界,相应的left或right是查找的目标的最终候选,这一点在理解时需要注意。当然,不利用这个思路也可以写出能完成功能的二分查找,而且易于理解。

    展开全文
  • 循环不变式理解

    千次阅读 2017-05-19 01:18:22
    从算法导论里边,接触到循环不变式这个概念(Loop-invariant),算法导论给出证明过程如下: 初始化:循环的第一次迭代之前,它为真。... 首先理解一下为什么要用循环不变式去证明算法的正确性。假

      从算法导论里边,接触到循环不变式这个概念(Loop-invariant),算法导论给出证明过程如下:
    初始化:循环的第一次迭代之前,它为真。
    保持:如果循环的某次迭代之前它为真,那么下次迭代之前它仍为真。
    终止:在循环终止时,不变式为我们提供一个有用的性质,该性质有助于证明算法是正确的。
      首先理解一下为什么要用循环不变式去证明算法的正确性。假如是一个车间的流水线,那么我们为了要保证产品的合格率,有一种做法就是保证前一道工序合格,我这一道工序也合格的话,那么成品终将是合格的,但是这只能针对顺序语句,条件判断语句if能够去检验。但是如果生产线中存在环,我们该怎么办呢?因为每次进入环的产品都不一样,就无法针对单一的一次去做判断。虽然有环,产品有区别,但是他们有共同的一个性质,我们可以找到一个不变量去评判一个产品是否合格。
    我们这次拿斐波那契数列解释一下其含义。

    #include <iostream>
    using namespace std;
    int fbnq(int n){
        int a = 0;
        int b = 1;
        int tem;
        for(int i = 0;i < n;i++)
        {
        tem = a;
        a = b;
        b = a + b; 
        }
        return b;
    }
    int main(){
        cout<<fbnq(5)<<endl;
        return 0;

      初始化:首先证明在第一次循环迭代之前(i = 0)时,循环不变式 立。可以要证明fbnq(0) == 0(a) && fbnq(1) == 1(b)成立。代入 后发现成立。
      保持:再去证明 fbnq(i) == a && fbnq(i+1) == b每次迭代城前 成立。由于对于前边的j=0,1,2,3,4…i-1都已验证成立,那么得到的 fbnq(i) == a,fbnq(i+1) == b也会成立。这是所得斐波那契数列都得 出正确结果,那么下一次迭代增加fbnq(i+1) == a,fbnq(i+2) == b也 将保持循环不变式。
      终止:导致for循环终止的条件时i>=n,因为每次循环i都要加1,那么 有必要使i=n。在循环不变式中用n替代掉i,此时我们的fbnq(n)已经得出 了由原来fbnq(n-1)推理而来的中却结论,此时我们可以推断fbnq(n)已经 得到我们预想的结果。

    展开全文
  • 循环不变式

    千次阅读 2018-12-21 18:28:37
    循环不变式其主要是用来帮助我们理解和证明算法的正确性。 关于循环不变式我们必须证明三个性质: 初始化:它在循环的第一轮迭代开始之前,应该是正确的。 保持:如果在某一次循环迭代开始之前是正确的,那么在下一...

    循环不变式

    循环不变式其主要是用来帮助我们理解和证明算法的正确性。
    关于循环不变式我们必须证明三个性质:

    • 初始化:它在循环的第一轮迭代开始之前,应该是正确的。
    • 保持:如果在某一次循环迭代开始之前是正确的,那么在下一次迭代开始之前,它也应该保持正确。
    • 结束:当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。

    插入排序的证明

    for j = 2 to A.length
        key = A[j]
        // Insert A[j] into the sorted sequence A[1..j-1].
        i = j-1
        while i > 0 and A[i] > key
            A[i+1] = A[i]
            i = i -1
        A[i+1] = key
    
    • 初始化:在第一轮迭代开始之前,证明其正确性。此时j=2,A[1…j-1]中只有一个元素A[1],显然,一个元素是已经排序的了。所以,证明了循环不变式在第一轮迭代之前是成立的。
    • 保持:接下来要证明在每轮迭代中,循环不变式保持成立。迭代之前,假设A[1…j-1]是已经排好序的序列,待排序的元素A[j]依次与A[j-1]、A[j-2]进行比较,如果A[j-1]等大于A[j],则依次将其向右移动一位,当遇到开始小于A[j]的元素时,则A[j]找到了合适的插入位置,插入之后,整个序列又是排好序的了。即在假设j成立的情况下,j+1也成立,循环不变式在迭代过程中保持成立。
    • 终止:最后,分析一下循环结束时候的情况。当j=n+1时,循环结束,此时A[1…n]中已经有n个元素,且已经排好序,就是排好序的数组A[1…n],所以算法正确。
    展开全文
  • 而在计算机科学中,循环不变式同样作为一种演绎推理法用于理解和证明算法的正确性。从下文的介绍中可以看出,循环不变式和数学归纳法有着许多的相似之处。 2. 循环不变式的三条性质 循环不变式...
  • 循环不变式主要用来辅助我们理解算法的正确性,对于循环不变式,必须证明它的三个性质 初始化:它在循环的第一轮迭代开始之前,应该是正确的。保持:如果在某一次循环迭代开始之前是正确的,那么在下一次迭代开始...
  • 循环不变式的介绍 循环不变式是用来证明算法正确性的一种方法。当设计一个算法设计到循环时,就可以使用循环不变式来去验证算法的正确性。从个人角度来看,我认为循环不变式的使用可以使设计算法者的逻辑更加严谨。...
  • 循环不变式证明算法的正确性循环不变式主要用来辅助我们理解算法的正确性,对于循环不变式,必须证明它的三个性质(有些类似于数学归纳法的意味): 初始化:它在循环的第一轮迭代开始之前,应该是正确的。 保持:...
  • 循环不变式证明算法的正确性

    千次阅读 2019-05-24 17:12:00
    循环不变式证明算法的正确性循环不变式主要用来辅助我们理解算法的正确性,对于循环不变式,必须证明它的三个性质(有些类似于数学归纳法的意味): 初始化:它在循环的第一轮迭代开始之前,应该是正确的。保持:...
  • 循环不变式:个人理解为具有循环不变性的循环变量 循环不变性:在程序循环中不断的重复相同的动作的特性 排序中,每次循环都需要: 1. 保持元素还是原先的元素 2. 每一次的循环都能部分的排好顺序 当程序结束的...
  • 循环不变式,百度的解释:一般而言,用这个式子表示希望得到的结果,如果在循环的每一步,这个式子都是正确的,那么循环结束后,这个式子也正确,并得到了期望的结果。这就算定义了吧。  它的三个性质,初始化、...
  • 个人理解循环不变式(性)从本质上应该类似于数学归纳法中要证明的那个公式或者性质 , 相当于上面提到的n=m成立这一性质,首先证明循环不变式成立(性)( Initialization )( Maintenance ),即循环1到无穷次...
  • 循环不变式(Loop invariant)

    千次阅读 2012-05-03 22:32:59
    循环不变式(Loop invariant) 个人理解,欢迎讨论 背景知识: Hoare 逻辑(也叫做Floyd–Hoare 逻辑)是英国计算机科学家 东尼·霍尔 开发的形式系统,随后为 Hoare 和其他研究者所精制。它发表于东尼·霍尔 1969...
  • 循环不变式 算法导论第二章中的原文是:We state these properties of A[1 ‥ j -1] formally as a loop invariant。其中举的例子是插入排序,每次循环从数组A中取出第j个元素插入有序区A[1 .. j-1],然后递增j。...
  • 「算法导论」:到底什么是循环不变式

    千次阅读 多人点赞 2014-06-28 18:40:34
     我的理解是,循环不变式表达的是在循环过程中的一种状态。 第一、对于插入排序来说,每轮循环利用的都是原数组中的前j-1个元素,这里体现的是“不变”,意思是对于每一轮的子集a[1..j-1],它所有的元素就是原数组...
  • 循环不变式主要用来帮助理解算法的正确性。形式上很类似与数学归纳法,它是一个需要保证正确断言。对于循环不变式,必须证明它的三个性质: 初始化:它在循环的第一轮迭代开始之前,应该是正确的。 保持:...
  • 每次循环迭代i增加1,所以此时i=length,在循环不变式中将i用length代替,有子数组a[0..length-1]由原来在a[0..length-1]中的元素组成,但已经按序排列。因为子数组a[0..length-1]就是整个数组,所以整个数组已经...
  • 循环不变式其实不仅仅在本问题中可以大显身手,其实在 循环不变式 是一种思想,在以后的很多问题中,我们要证明算法的正确性等等都需要用到这个强有力的工具 4.若干变体描述以及代码示例 我们二分查找描述操作...
  • ——利用循环不变式理解二分查找及其变体的正确性以及构造方式   debug之脚手架  听起来挺玄乎,其实所谓的脚手架,就是在debug版本里加入的为了验证程序是否正确的额外代码,比如一条为了确定循环中...
  • 循环不定可以用来证明一个算法的正确性: 比如我现在有一个算法A,我要证明它的正确性:步骤如下: 第0步:定义循环不定; 第1步:证明循环不定在算法开始的时候是正确的; 第2步:证明循环不定在算法...
  • 如何写出正确的二分查找?

    千次阅读 2016-03-31 21:37:20
    ——利用循环不变式理解二分查找及其变体的正确性以及构造方式 转载自:http://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html# 序言  本文以经典的二分查找为例,介绍如何使用循环不变式...
  • 你真的理解函数编程吗?

    万次阅读 2018-04-12 10:43:24
    你是否觉得函数各种概念难于理解?本场 Chat 将为你解答。我将为你分享亲身学习和理解关于函数编程的经验: 高阶函数、闭包、匿名函数等 高阶函数和闭包是啥关系? 柯里化 函数编程思维 适合人群: 如果你...
  • 理解函数编程

    千次阅读 2017-04-06 13:54:43
    相信大家平时或多或少听过不少关于“函数编程” (FP)相关的词语,有些Geek经常吹捧函数的优点或者特性比如:纯函数无副作用、不变的数据、高阶函数、流计算模式、尾递归、柯里化等等,再加上目前的函数理论...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,608
精华内容 17,443
关键字:

循环不变式的理解