精华内容
下载资源
问答
  • hoare logic

    2015-12-28 10:18:45
    是霍尔逻辑的一个教案之类的文档,反正看看对了解霍尔逻辑的基础以及基本概念还是很有效的.
  • 霍尔逻辑Hoare Logic

    千次阅读 2021-01-14 20:48:12
    霍尔逻辑(英语:Hoare Logic),又称弗洛伊德-霍尔逻辑(Floyd–Hoare logic),是英国计算机科学家东尼·霍尔开发的形式系统,这个系统的用途是为了使用严格的数理逻辑推理来替计算机程序的正确性提供一组逻辑规则...


    霍尔逻辑的概念

    对于这个新概念,我们首先要知道什么是霍尔逻辑,霍尔逻辑能用来做些什么?

    摘抄一下百度百科的原句:

    霍尔逻辑(英语:Hoare Logic),又称弗洛伊德-霍尔逻辑(Floyd–Hoare logic),是英国计算机科学家东尼·霍尔开发的形式系统,这个系统的用途是为了使用严格的数理逻辑推理来替计算机程序的正确性提供一组逻辑规则。

    简要来说霍尔逻辑是一种用于验证程序正确性的逻辑规则。

    霍尔逻辑表示为一个三元组,可以称之为“Hoare Triples”,它表示为如下形式:
    { ϕ } P { ψ } \{\phi\}P\{\psi\} {ϕ}P{ψ}

    ϕ \phi ϕ被称为前置条件,P是程序片段 ψ \psi ψ称为后置条件

    用自然语言描述一下它的含义就是,如果程序片段P在满足条件 ϕ \phi ϕ的情况下开始,那么P的执行会在满足 ψ \psi ψ的状态下结束。

    我们用一个实际的例子填上去

    { x ≥ 0 } x = x + 1 { x ≠ 0 } \{x\ge 0\}x=x+1\{x\ne 0\} {x0}x=x+1{x=0}

    也就是说,该程序以x≥0的情况下开始执行,并且运行x=x+1这条语句,程序运行结束时要求满足x≠0这个条件。

    部分正确与完全正确

    看看上面的程序片段P,我们考虑一种情况,如程序片段P一直执行下去不终止会发生什么?例如,现在程序片段P里面有个类似于while(true)的东西,而且循环里面又没有break语句,这种情况下压根没有P结束这个概念,所以后置条件 ψ \psi ψ在这种情况下是真是假都是无所谓的,所以也可以使后置条件 ψ \psi ψ为假来表示程序P不会终止。

    在不能保证程序终止的情况下,我们称为程序部分正确(partial correctness),如果我们能够保证程序一定终止,并且满足在 ϕ \phi ϕ成立的情况下执行P后 ψ \psi ψ成立,那么我们称为完全正确(total correctness)

    所以部分正确与完全正确的区别就在于是否要求程序终止

    规则(Rules)

    空语句(Empty statement axiom schema)

    { P } s k i p { P } ‾ \overline{\{P\}skip\{P\}} {P}skip{P}

    空语句不会更改程序的状态,所以程序执行前成立的条件,在空语句执行之后也成立

    赋值语句(Assignment axiom schema)

    { P [ E / x ] } x : = E { P } ‾ \overline{\{P[E/ x]\}x:=E\{P\}} {P[E/x]}x:=E{P}

    如果前置条件的变量没有经过赋值的修改,那么该变量条件可以直接放到后置条件上

    相关例子:
    { x + 1 = 43 } y : = x + 1 { y = 43 } { x + 1 ≤ N } x : = x + 1 { x ≤ N } \{x+1=43\}y:=x+1\{y=43\} \\ \{x+1\le N\}x:=x+1\{x\le N\} {x+1=43}y:=x+1{y=43}{x+1N}x:=x+1{xN}

    合成规则(Rule of composition)
    { P } S { Q } , { Q } T { R } { P } S ; T { R } \dfrac{\{P\}S\{Q\} , \{Q\}T\{R\}}{\{P\}S;T\{R\}} {P}S;T{R}{P}S{Q},{Q}T{R}

    其中Q称为中间条件

    例如
    { x + 1 = 43 } y : = x + 1 { y = 43 } a n d { y = 43 } z : = y { z = 43 } \{x+1=43\}y:=x+1\{y=43\} \\ and \\ \{y=43\}z:=y\{z=43\} {x+1=43}y:=x+1{y=43}and{y=43}z:=y{z=43}

    根据合成规则,可以合并为
    { x + 1 = 43 } y : = x + 1 ; z : = y { z = 43 } \{x+1=43\}y:=x+1;z:=y\{z=43\} {x+1=43}y:=x+1;z:=y{z=43}

    条件规则(Conditional rule)
    { B ∧ P } S { Q } , { ¬ B ∧ P } T { Q } { P } if B then S else T endif { Q } \dfrac{\{B\wedge P\}S\{Q\} , \{\lnot B\wedge P\}T\{Q\}}{\{P\}\text{if B then S else T endif}\{Q\}} {P}if B then S else T endif{Q}{BP}S{Q},{¬BP}T{Q}

    推导规则(Consequence rule)
    P 1 → P 2 , { P 2 } S { Q 2 } , Q 2 → Q 1 { P 1 } S { Q 1 } \dfrac{P_{1}\rightarrow P_{2},\{P_{2}\}S\{Q_{2}\},Q_{2}\rightarrow Q_{1}}{\{P_{1}\}S\{Q_{1}\}} {P1}S{Q1}P1P2,{P2}S{Q2},Q2Q1

    这个规则允许加强前置条件 P 2 P_{2} P2,或者削弱后置条件 Q 2 Q_{2} Q2

    说到强弱条件这个概念,我们来举个例子:
    x < 3 x<3 x<3这个条件强于 x < 5 x<5 x<5这个条件,因为 x < 3 x<3 x<3这个条件的范围更小,它对变量的约束力更强

    循环规则(While rule)
    { P ∧ B } S { P } { P } while B do S done { ¬ B ∧ P } \dfrac{\{P\wedge B\}S\{P\}}{\{P\}\text{while B do S done}\{\lnot B \wedge P\}} {P}while B do S done{¬BP}{PB}S{P}

    规则应用

    证明阶乘

    证明求证阶乘的程序工作正确

    ( ∣ T ∣ ) y = 1 ; z = 0 ; w h i l e ( z ! = x ) { z = z + 1 ; y = y ∗ z } ( ∣ y = x ! ∣ ) (|T|)y=1;z=0;while(z != x)\{z=z+1; y=y*z\}(|y=x!|) (T)y=1;z=0;while(z!=x){z=z+1;y=yz}(y=x!)

    证明过程
    { 1 = 1 } y=1 { y = 1 } { ⊤ } y=1 { y = 1 } i   ( y = 1 ∧ 0 = 0 ) z = 0 ( y = 1 ∧ z = 0 ) ( y = 1 ) z = 0 ( y = 1 ∧ z = 0 ) i ( ⊤ ) y = 1 ; z = 0 ( y = 1 ∧ z = 0 ) c \dfrac{\dfrac{\{1=1\}\text{y=1}\{y=1\}}{\{\top\}\text{y=1}\{y=1\}}i\text{ }\dfrac{(y=1\wedge0=0)z=0(y=1\wedge z=0)}{(y=1)z=0(y=1\wedge z=0)}i}{(\top)y=1;z=0(y=1\wedge z=0)}c ()y=1;z=0(y=1z=0){}y=1{y=1}{1=1}y=1{y=1}i (y=1)z=0(y=1z=0)(y=10=0)z=0(y=1z=0)ic

    \\

    ( y ⋅ ( z + 1 ) = ( z + 1 ) ! ) z = z + 1 ( y ⋅ z = z ! ) ( y = z ! ∧ z ≠ x ) z = z + 1 ( y ⋅ z = z ! ) i ( y ⋅ z = z ! ) y = y ∗ z ( y = z ! ) ( y = z ! ∧ z ≠ x ) z = z + 1 ; y = y ∗ z ( y = z ! ) c ( y = z ! ) while (z!=x){z=z+1;y=y*z} ( y = z ! ∧ z = x ) w ( y = 1 ∧ z = 0 ) while(z!=x){z=z+1;y=y*z}(y=x!) i \dfrac{\dfrac{\dfrac{\dfrac{(y·(z+1)=(z+1)!)z=z+1(y·z=z!)}{(y=z!\wedge z\neq x)z=z+1(y·z=z!)}i\qquad (y·z=z!)y=y*z(y=z!)}{(y=z!\wedge z\neq x)z=z+1;y=y*z(y=z!)}c}{(y=z!)\text{while (z!=x)\{z=z+1;y=y*z\}}(y=z!\wedge z=x)}w}{(y=1\wedge z=0)\text{while(z!=x)\{z=z+1;y=y*z\}(y=x!)}}i (y=1z=0)while(z!=x){z=z+1;y=y*z}(y=x!)(y=z!)while (z!=x){z=z+1;y=y*z}(y=z!z=x)(y=z!z=x)z=z+1;y=yz(y=z!)(y=z!z=x)z=z+1(yz=z!)(y(z+1)=(z+1)!)z=z+1(yz=z!)i(yz=z!)y=yz(y=z!)cwi

    由上面的两式,经过合成规则推倒后,可以得出最原始的程序是正确的

    再证明另外一个阶乘程序:

    在这里插入图片描述

    这个程序就相当于上面的那个程序反着来,比较难的点就是从什么地方开始证明

    ( y ⋅ ( x − 1 ) = ( x − 1 ) ! ∧ x > 0 ) x = x − 1 ( y ⋅ x = x ! ∧ x > 0 ) ( y = ( x − 2 ) ! ∧ x ≠ 1 ∧ x > 0 ) x = x − 1 ( y ⋅ x = x ! ∧ x > 0 ) i ( y ⋅ x = x ! ∧ x > 0 ) y = y ∗ x ( y = x ! ∧ x > 0 ) ( y = ( x − 2 ) ! ∧ x ≠ 1 ∧ x > 0 ) x = x − 1 ; y = y ∗ x ( y = x ! ∧ x > 0 ) c ( y = ( x − 2 ) ! ∧ x > 0 ) while (x!=1)do{x=x-1;y=y*x} ( y = z ! ∧ z = x ∧ x > 0 ) w ( y = 1 ∧ x = n ) while(x!=1)do{x=x-1;y=y*x} ( y = n ! ∧ n > 0 ) ( x = n ) y = 1 ( y = 1 , x = n ) i ( x = n ) y=1,while (x!=1) do {x=x-1;y=y*x} ( y = n ! ∧ n > 0 ) c \dfrac{\dfrac{\dfrac{\dfrac{\dfrac{(y·(x-1)=(x-1)!\wedge x>0)x=x-1(y·x=x!\wedge x>0)}{(y=(x-2)!\wedge x\neq 1\wedge x>0)x=x-1(y·x=x!\wedge x>0)}i\qquad (y·x=x!\wedge x>0)y=y*x(y=x!\wedge x>0)}{(y=(x-2)!\wedge x\neq 1\wedge x>0)x=x-1;y=y*x(y=x!\wedge x>0)}c}{(y=(x-2)!\wedge x>0)\text{while (x!=1)do\{x=x-1;y=y*x\}}(y=z!\wedge z=x\wedge x>0)}w}{(y=1\wedge x=n)\text{while(x!=1)do\{x=x-1;y=y*x\}}(y=n!\wedge n>0)\qquad (x=n)y=1(y=1,x=n)}i}{(x=n)\text{y=1,while (x!=1) do \{x=x-1;y=y*x\}}(y=n!\wedge n>0)}c (x=n)y=1,while (x!=1) do {x=x-1;y=y*x}(y=n!n>0)(y=1x=n)while(x!=1)do{x=x-1;y=y*x}(y=n!n>0)(x=n)y=1(y=1,x=n)(y=(x2)!x>0)while (x!=1)do{x=x-1;y=y*x}(y=z!z=xx>0)(y=(x2)!x=1x>0)x=x1;y=yx(y=x!x>0)(y=(x2)!x=1x>0)x=x1(yx=x!x>0)(y(x1)=(x1)!x>0)x=x1(yx=x!x>0)i(yx=x!x>0)y=yx(y=x!x>0)cwic

    ( y ⋅ ( x − 1 ) ! = n ! ∧ x > 0 ) x = x − 1 ( y ⋅ x ! = n ! ∧ x > 0 ) ( y ⋅ x ! = n ! ∧ x > 0 ) y = y ∗ x ( y ⋅ ( x − 1 ) ! = n ! ∧ x > 0 ) ( y ⋅ x ! = n ! ∧ x > 0 ) x = x − 1 ; y = y ∗ x ( y ⋅ x ! = n ! ∧ x > 0 ) c ( y ⋅ x ! = n ! ∧ x > 0 ∧ x ≠ 1 ) x = x − 1 ; y = y ∗ x ( y ⋅ x ! = n ! ∧ x > 0 ) i ( y ⋅ x ! = n ! ∧ x > 0 ) w h i l e ( x ≠ 1 ) { x = x − 1 ; y = y ∗ x } ( y ⋅ x ! = n ! ∧ x = 1 ∧ x > 0 ) w ( y ⋅ x ! = n ! ∧ x > 0 ) w h i l e ( x ≠ 1 ) { x = x − 1 ; y = y ∗ x } ( y ⋅ x ! = n ! ∧ x > 0 ) ( x ! = n ! ) y = 1 ( y ⋅ x ! = n ! ∧ x > 0 ) i ( x ! = n ! ) y = 1 ; w h i l e ( x ≠ 1 ) { x = x − 1 ; y = y ∗ x } ( y ⋅ x ! = n ! ∧ x > 0 ) } c ( x = n ) y = 1 ; w h i l e ( x ≠ 1 ) { x = x − 1 ; y = y ∗ x } ( y ⋅ x ! = n ! ∧ n > 0 ) } \dfrac{\dfrac{\dfrac{\dfrac{\dfrac{\dfrac{(y·(x-1)!=n!\wedge x>0)x=x-1(y·x!=n!\wedge x>0)\qquad (y·x!=n!\wedge x>0)y=y*x(y·(x-1)!=n!\wedge x>0)}{(y·x!=n!\wedge x>0)x=x-1;y=y*x(y·x!=n!\wedge x>0)}c}{(y·x!=n!\wedge x>0\wedge x\neq 1)x=x-1;y=y*x(y·x!=n!\wedge x>0)}i}{(y·x!=n!\wedge x>0)while(x\neq 1)\{x=x-1;y=y*x\}(y·x!=n!\wedge x=1\wedge x>0)}w}{(y·x!=n!\wedge x>0)while(x\neq 1)\{x=x-1;y=y*x\}(y·x!=n!\wedge x>0) \qquad(x!=n!)y=1(y·x!=n!\wedge x>0) }i}{(x!=n!)y=1;while(x\neq 1)\{x=x-1;y=y*x\}(y·x!=n!\wedge x>0)\}}c}{(x=n)y=1;while(x\neq 1)\{x=x-1;y=y*x\}(y·x!=n!\wedge n>0)\}} (x=n)y=1;while(x=1){x=x1;y=yx}(yx!=n!n>0)}(x!=n!)y=1;while(x=1){x=x1;y=yx}(yx!=n!x>0)}(yx!=n!x>0)while(x=1){x=x1;y=yx}(yx!=n!x>0)(x!=n!)y=1(yx!=n!x>0)(yx!=n!x>0)while(x=1){x=x1;y=yx}(yx!=n!x=1x>0)(yx!=n!x>0x=1)x=x1;y=yx(yx!=n!x>0)(yx!=n!x>0)x=x1;y=yx(yx!=n!x>0)(y(x1)!=n!x>0)x=x1(yx!=n!x>0)(yx!=n!x>0)y=yx(y(x1)!=n!x>0)ciwic

    优点

    • 能够证明程序的正确性
    • 具有一般Logic的特点,包括可靠性和完备性等
    • 直观

    缺点

    • 手工证明
    • 高代价
    • 不能处理很多程序特征,例如指针等类型
    展开全文
  • 快速排序之hoare

    2019-08-27 14:00:36
    hoare法 首先我们来看它的基本思路: 第一步:选择待排序数组中的三个值,分别是首尾还有中值,start,end 和mid 第二步:对三个数进行排序,从小到大, 第三步:保护基准值,swap(src + mid, src + end - 1)...

                                                       hoare法

    首先我们来看它的基本思路:

        第一步:选择待排序数组中的三个值,分别是首尾还有中值,start,end 和mid
        第二步:对三个数进行排序,从小到大,
        第三步:保护基准值,swap(src + mid, src + end - 1);也就是基准值和倒数第二个元素交换
        第四步:a = start + 1, b = end - 2,b向前找比基准值小的,a向后找比基准值大的,找到之后 交换所指向的值,然后将基准值和a指向的值交换 (因为是从小到大排序a找的大的,应该在数组后面所以基准值和它换),产生左边的都比基准值小,右边的都比基准值大,然后a作为二叉树的根返回,重复上面四步操作,直到类似形状的二叉树被遍历完为止

    代码实现:

    int hoareway(int* src, int start,int end)
    {
    	int a = start + 1, b = end - 2;
    	int mid = (start + end) / 2;
    	if (src[start] > src[mid])
    	{
    		swap(src + start, src + mid);
    	}
    	if (src[mid] > src[end])
    	{
    		swap(src + mid, src + end);
    	}
    	if (src[start] > src[mid])
    	{
    		swap(src + start, src + mid);
    		/*上面是三数排序部分*/
    	}
    	if (end-mid<=2)
    	{
    		return mid;
    		/*如果小于4个数直接返回输出*/
    	}
    	/*保护基准值*/
    	swap(src + mid, src + end - 1);
    	while (a <= b)
    	{
     		while (a < end-1 && src[a] <= src[end-1])
    		{
    
    			a++;
    		}
    		while (b > 0 && src[b] >= src[end-1])
    		{
    			b--;
    
    		}
    		if (a == b && (a == 1 || a == end-1))
    		{
    			break;
    			/*一种是找到同一个值,一种是找到了已经三数排好的地方,此时就不用排*/
    		}
    		if (a < b)
    		{
    			swap(src + a, src + b);
    			/* 交换*/
    		}
    		
    	}
    	swap(src + a, src + end - 1);
    	return a;
    }
    
    void dealquicksort(int *src, int start, int end)
    {
    	int mid;
    	if (start<end)
    	{
    		mid = hoareway( src,  start,   end);
    		dealquicksort( src, start, mid-1);
    		dealquicksort(src, mid + 1, end);
    	}
    }
    void quicksort(int *src, int n)
    {
    	//快速排序
    	dealquicksort(src, 0, n-1);
    }

    如果递归思想有不明白请看https://blog.csdn.net/weixin_43447989/article/details/100054493

    EOF

    展开全文
  • 快速排序(Hoare法实现partition)

    千次阅读 2019-11-10 10:49:05
    Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归...

    一、什么是快速排序?

    快速排序(Quicksort)是对冒泡排序的一种改进。
    快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    二、快速排序的排序流程
    快速排序是通过多次比较和交换来实现排序的。

    • 首先在待排序列中确定一个基准值,遍历整个序列,将小于(可包含等于)基准值的元素放到基准值左边,将大于(可包含等于)基准值的元素放到其右边。(降序序列可将位置调整)
    • 此时基准值将序列分割成俩个部分,左边的元素全部小于基准值,右边的元素全部大于基准值。
    • 将分割的左右俩部分进行如上俩步操作,实则为递归。
    • 通过递归将左右俩侧排好序,直至分割的小序列个数为1,排序全部完成。

    以上为快速排序的思路和排序流程。

    从上面的信息我们可以得出:
    (1)排序之前需要确定一个基准值,在这里我们约定基准值为每个序列的第一个元素。
    (2)排序需要递归,递归函数的形参列表为待排序序列。递归出口是形参列表的序列的元素个数为1.

    递归函数:

    public static void quickSortInter(int[] arr,int left,int right){
            if(left >= right){//当数组长度小于等于1时return
                return;
            }
            int pivotIndex = partition(arr,left,right);//基准值下标
    
            //递归方法,用partition将数组分为左右俩个小数组,用同样的方法将小数组分割,直至小数组元素个数小于等于1
            quickSortInter (arr,left,pivotIndex-1);
            quickSortInter (arr,pivotIndex+1,right);
    
        }
    

    但是如何以基准值为界,将待排序列分为左右俩个部分呢?
    我们有三种方式实现partiton:

    1. Hoare法
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述在这里插入图片描述
      Hoare法实现partition核心代码:
     public static int partition(int[] arr,int left,int right){
            int begin = left;
            int end = right;
            int pivot = arr[left];//基准值
            
            //遍历整个数字,以基准值为标准分割数组
            while(begin < end) {
                while (begin < end && arr[end] >= pivot) {
                    end--;
                }
                while (begin < end && arr[begin] <= pivot) {
                    begin++;
                }
                swap(arr,begin,end);
            }
            // 遍历完整个数组后,begin的位置是小于pivot的最后一个数字,将其与left(基准值)的值交换
            // 此时begin左边的都是小于基准值的数字,右边都是大于基准值的数字,成功将数字分割
            swap(arr,begin,left);
            return begin;
        }
    

    完整代码:
    https://github.com/WangWenQian12/Java_Practice/blob/master/JavaSE/IDEA/Sort/QuickSort/QuickSort1/src/QuickSort.java

    其他俩种方法之后更新……

    展开全文
  • 想要做到上述这一点,基本方法(称为霍尔(Hoare)法))如下: 1、将需要排序的区间中的第一个数据作为基准数据,记为key 2、从区间的最后一个数据向前寻找小于key的数据,记为end 3、从区间的第一个数据向后寻找...

    原理

    快速排序的本质是给基准数据寻找合适位置的过程。以升序为例,每一趟排序结束以后,可以保证基准数据左边的数据全部小于它,右边的数据全部大于它,这也表明这一基准数据已经处于它的最终位置了。

    想要做到上述这一点,基本方法(称为霍尔(Hoare)法))如下:
    1、将需要排序的区间中的第一个数据作为基准数据,记为key
    2、从区间的最后一个数据向前寻找小于key的数据,记为end
    3、从区间的第一个数据向后寻找大于key的数据,记为begin
    4、交换begin和end所在位置的数据,重复2、3的操作
    5、若begin和end相遇,则将区间第一个数据(即key)与相遇位置的数据交换,此时完成了一趟排序,key数据已经处于最终的位置。函数返回相遇位置。

    之后通过递归调用的方式对相遇位置的左边和右边区间分别执行上述步骤,直到整个区间的每个数据都处于其最终位置,数组就有序了。

    可参考下图例子:
    在这里插入图片描述
    根据以上思路编写的代码如下:

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
    
    void printArr(int* arr, int len){
    	for (int i = 0; i < len; i++){
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    }
    
    void Swap(int* a, int* b){
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int* arr, int begin, int end){
    	int start = begin;
    	int key = arr[start];
    	while (begin < end){
    		while (begin < end && arr[end] >= key){
    			end--;
    		}
    		while (begin < end && arr[begin] <= key){
    			begin++;
    		}
    		Swap(&arr[begin], &arr[end]);
    	}
    	Swap(&arr[start], &arr[begin]);
    	return begin;
    }
    
    void quickSort(int* arr, int begin, int end){
    	if (begin >= end){
    		return;
    	}
    	int div = partition(arr, begin, end);
    	quickSort(arr, begin, div - 1);
    	quickSort(arr, div + 1, end);
    }
    
    void testQuickSort(){
    	int arr[] = { 10, 1, 3, 2, 0, 7, 5, 4, 6, 8, 9 };
    	int len = sizeof(arr) / sizeof(arr[0]);
    	printArr(arr, len);
    	quickSort(arr, 0, len - 1);
    	printArr(arr, len);
    }
    
    int main(){
    
    	testQuickSort();
    
    	system("pause");
    	return 0;
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • Hoare划分的正确性)本章中的PARTITION算法并不是其最初的版本。下面给出的是最早由C. R. Hoare所设计的划分算法:    a. 试说明HOARE-PARTITION在数组A = {13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21}上的操作...
  • //用与存放因无法进入管程的阻塞队列&&因为调用signal阻塞自身的线程(Hoare) static interf IM = new interf ( lock ) ; public static void wait ( String id , cond declar , interf IM ) ...
  • 这是Hoare和He的(UTP)在Isabelle / HOL证明助手中的语义嵌入。 我们以Feliachi,Gaudel和Wolff(2010)首次创建的浅层嵌入为基础来实现这一特定实现,但是我们还结合了Foster,Zeyda和Woodcock(2015)在Isabelle...
  • // * 基本上与Hoare版本类似 // * 1.将基准值的元素保存起来,并将该处当做一个坑 // * 2.begin从待排序序列的 最左边开始向右边遍历 ,找到比基准值大的停止,将该元素填入坑,并将begin处当做坑 // * 3.end...
  • Unifying Theories of Programming (UTP) deals with program semantics. It shows how denotational semantics, operational semantics and algebraic semantics can be combined in a unified framework for the ...
  • Hoare划分的正确性 题目:本章中给出的PARTITION算法并不是其最初的版本。下面给出的是最初由C.A.R.Hoare设计的划分算法。 HOARE-PARTITION(A,p,r): 1 x <- A[p] 2 i <- p-1 3 j <- r+1 4 ...
  • Hoare逻辑理论和ACSL语法规范的基础上,设计一种针对密码软件的形式化验证系统,由程序规范、验证推理规则、可靠性策略、验证推理等模块组成。以OpenSSL中RC4算法的软件实现为例,对其功能正确性、保险性和信息流...
  • } } } 2、基于Hoare划分的快速排序算法 Hoare划分是一种更为复杂的划分方式,但是这也是在网上最为流行的一个划分方式。 我们假设有一个数组a[0, n-1],其子数组为a[l, r](0 ),假定首个元素为枢轴p,下面从数组两端...
  • 快速排序的最早划分方法:Hoare划分

    千次阅读 2017-08-12 16:00:25
    快速排序的划分过程最早由C.R.Hoare设计,伪代码如下:HOARE-PARTITION(A,p,r) x=A[p] i=p-1 j=r+1 while TRUE repeat j=j-1 until A[j] repeat i=i+1 until A[i]>=x if i exchange A
  • hoare_wlp_fstar-源码

    2021-06-15 03:21:17
    hoare_wlp_fstar
  • 代码展示 #define _CRT_SECURE_NO_WARNINGS 1 #include #include //hoare版本 void Swap(int* pa, int *pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } void _QuickSort1(int left, int right, int *arr) { int ...
  • 做力扣的一道题目: 169 多数元素 的时候,用到了快速排序,所以复习了一下快排。 一、快排 快排思想就是: 选定一个哨兵元素pivot; 把小于pivot的元素放在pivot左边,大于pivot的放在右边,这样,划分完后pivot就...
  • 下面的文字是Erlang Solutions对Tony Hoare教授的采访内容。我在看视频的时候,将这些内容记了下来。非常难得的一段史料。该采访的文字稿在Erlang Solutions Blog上有放出来,请以视频和博客上的文字为准。 I’m ...
  • 快速排序hoare版本挖坑法前后指针版本 快速排序:快速排序算法通过多次比较和交换来实现排序 基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两...
  • 坐姿的QC连续性和QFS域的Hoare幂域
  • Hoare的分区方案golang

    2017-09-03 16:52:00
    <p>Quicksort with Hoare's partitioning <pre><code>// Hoare's partitioning scheme func PartitionHoare(arr []int, low, high int) int { length := len(arr) if length == 0 { panic("Array size is 0")...
  • quicksort-java Hoare的Quick Sort在Java中的实现
  • 快速排序 其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列...hoare版本 挖坑法 前后指针法 图示: 代码实现: //快速排序hoare版本 int PartSort1(int*...
  • 1.1 原理 从待排序区间选择一个数,作为基准值(pivot); Partition: 遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的左边,将比基准值大的...1.3.1 Hoare法 //hoare版本 public int partitionHo
  • libccr C语言中带有pthread的简单易用的条件关键区域(CCR)。 CCR是具有以下形式的高级同步构造: region R when C do S 其中R是该区域的名称,C是一个条件,S是关键部分。 上面的陈述被翻译成 ...
  • 而划分后枢轴的位置也就是它的最终位置,这样就完成了枢轴的归位 一般常用的划分方法有三种:Hoare法,挖坑法,双指针法,下面就来一一讲解 单趟排序—划分 HoareHoare法的思路非常简单, 就是交换比枢轴大的值和...
  • 资源有两份:一是中文电子版,周巢尘译的。中文版的通信顺序进程教材,主要有7章的内容。第一章是进程,第二章是并发性,第三章是非确定性,第四章是通信,第五章是顺序进程,第六章是资源...二是CSPbook_2004_Hoare
  • 快速排序思路(Hoare版),代码实现

    热门讨论 2021-09-01 22:42:13
    快速排序是一种相对比较快的排序,它的思想为: 选取待排序元素序列中的一个元素作为基准值,然后(以升序为例)比基准值小的元素放在基准值左边,比基准值大的元素放在基准值右边,这样的话,原先待排序序列就被...
  • 快速排序的思想:  快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值 ,按照该基准值将待排序集合分割成两个子序列,左子序列中的所有元素小于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,963
精华内容 3,585
关键字:

hoare