《算法导论》2.3-7 检查集合中是否存在两数字和为指定的X--算法和证明

时间:2022-04-22 14:35:14

习题2.3-7:设计一个算法,对于一个给定的包含n个整数的集合S和另一个给定的整数X,该算法可以在《算法导论》2.3-7 检查集合中是否存在两数字和为指定的X--算法和证明时间内确定S中是否存在两个元素,使得它们的和恰为X。

解题思路:首先应该想到的是先用一个《算法导论》2.3-7 检查集合中是否存在两数字和为指定的X--算法和证明的排序算法对S中的元素进行排序。接下来有两种处理思路,第一种思路是遍历已经排好序了的S中的所有元素a,并采用

二分查找的方法在S中查找X-a,如果能够找到,那么说明S中确实存在两个元素的和为X,算法终止。这种思路很显然是满足《算法导论》2.3-7 检查集合中是否存在两数字和为指定的X--算法和证明的限制要求的;第二种思路是我自己

想出的一个算法,这个算法也很简单,但是其正确性不是很好证明。

思路1:

CheckSum( A[1…n] , X )
1    MergeSort( A ) //从小到大排序
2    for i = 1 to n
3        if  BinarySearch( A[1…n] , X-A[i] ) != –1 //假设BinarySearch在找不到指定元素的时候返回-1
4              return true
5    return false

思路2:

CheckSum( A[1…n] , X)
1    MergeSort( A ) //从小到大排序
2    i = 1
3    j = n
4    while( i < j)
5        if( A[i] + A[j] == X)
6             return true
7        else if( A[i] + A[j] > X)
8             j--
9        else if( A[i] + A[j] < X)
10           i++
11   return false

算法正确性证明:

思路1的正确性是显而易见的;思路2的正确性就不那么直观,其可能令人感到困惑的地方在于:思路2会不会漏掉某些情况?下面开始思路2的证明,

但是因为我也是初学,证明过程不是很严谨和规范。

首先,假设S中“不”包含两个和为X的元素,那么思路2的第5行的测试条件永远不会成真,那么最终算法一定会返回false。因此,证明思路2的正确性

便转化成证明:

若S中存在两个元素a和b,使得a+b==X,那么算法一定会返回true。(*)

为了证明(*)成立,下面首先证明思路2的算法在执行过程中满足如下的特性:

若S中存在两个元素a和b,使得a+b==X(不妨设a<=b),则在思路2的算法执行过程汇中,每一次迭代开始之前(即算法第4行执行之前),A[i…j]都包含a和b。(#)

下面采用归纳法证明(#)的成立:(令 ik,jk 分别表示第 k 轮迭代开始之前 i 和 j 的取值,A[ik…jk]表示第k轮迭代开始之前的A[i…j])

证明:
1、第 1 轮迭代开始之前,i1=1,j1=n。A[ik…jk]即为A[1…n],a和b很显然包含在A[1…n]中,结论成立。
2、若第 k 轮迭代开始之前,A[ik…jk]包含a和b。则按照算法的执行步骤:
     (1)如果A[ik]+A[jk]==X,算法返回true,算法终止。
     (2)如果A[ik]+A[jk] > X,算法使得jk值减1,即第 k+1 轮迭代开始之前,ik+1 = ik,jk+1 = jk - 1。下面证
             明A[jk]不可能是a或者b中的任何一个: 
             (2.1)因为a<b,且A[ik…jk]包含a和b,所以A[jk]不可能是a。
             (2.2)假设A[jk]等于b,因为A[]是从小到大排序的,所以,必然有:
                        A[jk]+A[jk-1] > A[jk]+A[jk-2] > A[jk]+A[jk-3] > … > A[jk]+A[ik+1] >A[jk]+A[ik] > X,即:
                        b+A[jk-1] > b+A[jk-2] > b+A[jk-3] > … > b+A[ik+1] >b+A[ik] > X
                        也就是说a不可能是A[ik…jk-1]中的任何一个元素,这和前提:A[ik…jk]包含a和b 矛盾,所以假
                        设错误,所以A[jk]不是b。
              因为A[ik…jk]中包含a和b,而又已经证明A[jk]不是a或者b,又ik+1 = ik,jk+1 = jk - 1 ,所以,在第k+
              1轮迭代开始之前,A[ik+1…jk+1]一定包含a和b。
     (3)如果A[ik]+A[jk] < X,同理可证第k+1轮迭代开始之前A[ik+1,jk+1]一定包含a和b。 
3、由1、和2、可知,每一次迭代开始之前,A[i…j]都包含a和b。

现在(#)已经得到证明,而由(#)证(*)是很直观的。因为A[i…j]中始终包含a和b,并且每一次迭代A[i…j]的规模小一,所以,最坏的情况是迭代一直执行到i+1=j的

时候,因为此时A[i,j]包含a和b,所以A[i]一定是a,A[j]一定是b,算法检测到A[i]+A[j] = a+b=X,算法返回true。

总结:以上便是全部内容,从理论上讲思路2应该要比思路1要快(虽然它们都是《算法导论》2.3-7 检查集合中是否存在两数字和为指定的X--算法和证明)。但是很明显地,思路1的正确性更加直观。