weixin_41982270
weixin_41982270
采纳率0%
2019-02-18 03:20 阅读 440

刚接触python的新手请问一个循环不变量证明循环正确的问题

5

下边是mergesort代码:
01 def head(Q):
02 return Q[0]

03 def tail(Q):
04 return Q[1:]

05 def mergesort(U):
06 if U == [] or tail(U) == []:
07 return U
08 else:
09 L = []
10 R = []
11 while U != [] and tail(U) != []:
12 L = L + [head(U)]
13 U = tail(U)
14 R = R + [head(U)]
15 U = tail(U)
16 L = L + U
17 L = mergesort(L)
18 R = mergesort(R)
19 S = []
20 while L != [] and R != []:
21 if head(L) <= head(R):
22 S = S + [head(L)]
23 L = tail(L)
24 else:
25 S = S + [head(R)]
26 R = tail(R)
27 S = S + L + R
28 return S
要找到一个循环不变量证明循环(line9-16)是正确的,这个循环不变量应该是U,循环开始之前U保持原始状态不变;每次循环迭代后U失去前两个元素分别给L和R,在下次循环开始之前U保持剩余元素不改变;循环结束的条件是U为空或只有一个元素,此时U保持判定false之前的状态依旧不变,若是剩余一个元素,语句L=L+U将其加入到L中,满足将元素依次加到L和R中的功能。
不知道我这样理解对不对,求大佬解答

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

相关推荐