Что такое инвариант цикла для суммирования алгоритма кубов?

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, но я не совсем уверен, как определить их как циклические инварианты.

Можно ли определить инварианты, если бы у меня было 3 отдельных тотальных переменных в каждом из течений цикла while, которые были добавлены к основному тотальному праву перед 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 

(если ваши расчетные суммы правильно).