东昌府大烟囱 2019-02-18 03:20 采纳率: 0%
浏览 455
已结题

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

下边是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中的功能。
不知道我这样理解对不对,求大佬解答

  • 写回答

0条回答

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 MATLAB动图问题
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名