求和立方体算法的循环不变量是多少？

我不是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，但我不完全知道如何将它们定义为循环不变量。

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

感谢您提供任何帮助。

来源

2012-02-11 Michael Schilling

我觉得你可以如下定义它们：

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

（如果你的计算量是正确的）。

来源

2012-02-11 07:31:29

谢谢！昨天晚上我正在研究这个问题，但是我发现了一些类似的问题，但我不完全确定如何定义它。谢谢您的帮助。对于LI2和LI3，是不是所有的'i'都会变成'（i-1）'？ – 2012-02-11 21:06:18

@MichaelSchilling，在循环执行期间以及循环执行完成后，循环不变应该为真，所以我认为我说的是真的。（也许我错了）。 – 2012-02-12 12:08:46

求和立方体算法的循环不变量是多少？

回答

相关问题