立方求和算法的循环不变式是什么？

Question

我不能 100% 确定三重幂求和中的不变量是什么。

注意：n 始终为非负值。

伪代码：

triplePower(n)
    i=0
    tot=0
    while i <= n LI1
        j = 0
        while j < i LI2
            k = 0
            while k < i LI3
                tot = tot + i
                k++
            j++
        i++

我知道它很混乱，可以用更简单的方式完成，但这是我期望做的（主要用于算法分析实践）。

我要提出三个循环不变量； LI1、LI2 和 LI3。
我认为对于 LI1 来说，不变量与 tot=(i^2(i+1)^2)/4 有关（从 0 到 i 的立方和的方程）
我不知道要为 LI2 或 LI3 做什么。 LI2 处的循环使 i^3 和 LI3 处的循环使 i^2 ，但我不完全确定如何将它们定义为循环不变量。

如果我在每个 while 循环体中有 3 个单独的总计变量，并在第一个循环中的 i++ 之前添加到主总计中，那么不变量会更容易定义吗？

感谢您提供的任何帮助。

Answer 1

我认为你可以将它们定义如下：（

LI1 <= (i^2(i+1)^2)/4
LI2 <= (i+1)^3 + (i^2(i+1)^2)/4
LI3 <= (i+1)^2 + i^3 + (i^2(i+1)^2)/4

如果你计算的金额是正确的）。