如何证明以下算法的正确性？

考虑以下算法min，它将列表x，y作为参数，并以x和y的并集返回第z个最小元素。前提条件：X和Y是按升序排列的整数列表，它们是不相交的。如何证明以下算法的正确性？

公告称，其伪代码，所以索引从1开始不是0

Min(x,y,z): 
    if z = 1: 
     return(min(x[1]; y[1])) 
    if z = 2: 
     if x[1] < y[1]: 
      return(min(x[2],y[1])) 
     else: 
      return(min(x[1], y[2])) 

q = Ceiling(z/2) //round up z/2 

if x[q] < y[z-q + 1]: 
    return(Min(x[q:z], y[1:(z - q + 1)], (z-q +1))) 
else: 
    return(Min(x[1:q], B[(z -q + 1):z], q))

我可以证明它终止，因为Z保持2下降，最终将达到的基本情形之一的，但我不能证明部分正确性。

来源

2013-03-21 user65065

嗨，我认为这对计算机科学来说更合适吗？ – user65065 2013-03-21 22:44:13

你能更详细地指定算法应该做什么吗？我明白你想要'x'和'y'的元素中的第k个最小元素，即'Mix（[1,2]，[3,4]，1）= 1'（最小元素） 'Mix（[1,2]，[3,4]，2）= 2'（第二小元素）等等。是吗？如果是这样，我不认为上述算法是正确的。甚至没有任何递归。 – chris 2013-03-23 03:58:49

当然，如果没有递归，终止是微不足道的。如果你有递归，你的论点不能保证终止（假设你的意思是整数，而不是自然数），因为减少一个负整数可以继续（理论上）永远不会触及基本情况。 – chris 2013-03-23 04:07:49

您的代码不正确。

考虑以下输入：

x = [0,1] 
y = [2] 
z = 3

你再q = 2，并且在if条款后面，访问y[z-q+1]，即y[2]英寸这是一个数组边界违规。

来源

2013-05-01 13:51:51

如何证明以下算法的正确性？

回答

相关问题