2008年12月11日星期四

从有序数组中找两个数求和等于某个给定的数

问题:
给一个正整数c,一个升序的正整数数组a=a1,...,an,找ai, aj使得ai+aj=c
算法:
i=1
j=n
while i<=j
{
case ai+aj==c, return true
case ai+aj<c, i++
case ai+aj>c, j--
}
return false
思路:
造一个方阵bij=ai+aj,则b对称,且bij<c蕴含bij左上区域都<c,只能向右或向下找,而我们从右上角开始,因此只能向下找。j++后,指针又在可能区域的右上角了。
正确性证明:
首先,算法显然至多n步后返回。
如果算法返回true,则显然ai+aj=c成立。
如果算法返回false,来证不存在bij满足bij=c。
由对称性,只需要证明bij!=c对于任意i<=j成立即可。
归纳法,显然当n=1时成立,若n-1时成立,来看n>=2时。
因为算法返回false,且n>=2,因此至少循环第一次b1n!=c,那么有两种情况
b1n<c,则b1j<c对任意j=1,...,n成立,n阶上三角去掉了第一行,剩下的是n-1阶的上三角,指针移到(2,n),是这个n-1阶上三角的右上角。
b1n>c,则bin>c对任意i=1,...,n成立,n阶上三角去掉了最后一列,剩下的还是n-1阶的上三角,指针移到(1,n-1),还是这个n-1阶上三角的右上角。
故由归纳假设,n时成立。

没有评论: