求和立方體算法的循環不變量是多少？

我不是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

求和立方體算法的循環不變量是多少？

回答

相關問題