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

Question

Я не уверен на 100%, что такое инвариант тройного степенного суммирования.

Примечание: значение n всегда неотрицательноеэто то, что я должен делать (в основном для практики анализа алгоритмов).

Я должен предложить три инварианта цикла;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

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