问裁剪杆的循环不变实现CLRS
EN

Stack Overflow用户

提问于 2022-11-13 15:09:03

回答 1查看 28关注 0票数 -1

我想知道这个代码第4-6行中的循环不变量是什么，以及如何在初始化、处理和终止过程中证明它。

def cut_rod(p, n):
    if n == 0:
        return 0
    q = -inf
    for i = 1 to n:
        q = max(q, p[i] + cut_rod(p, n-i))
    return q

我真的不知道从哪里开始，所以一些洞察力会很好:)

发布于 2022-11-13 17:08:50

我想说的是，每次迭代后，q=最小杆的价格与连n切割，其中至少包含1片连<= i。

这是可以归纳证明的。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/74422150

复制

相似问题

问裁剪杆的循环不变实现CLRSEN