Как проанализировать этот псевдокод

Question

У меня есть следующий псевдокод:

sum<-0
inc<-0
for i from 1-n
  for j from 1 to i
     sum<-sum+inc
     inc<-inc+1

Меня просят найти закрытую формулу. Подсказка заключается в использовании общих сумм. Независимо от того, как я на это смотрю, я не могу написать этот код в форме суммирования. Может кто-нибудь дать мне представление о том, как будут выглядеть суммы или даже рекурсивная формула?

Answer 1

Предполагая, что for i from 1-n означает:

for i from 1 to n

Закрытая формула для этого может быть получена с помощью численного анализа. Давайте проверим количество раз в цикле для пары значений n (5 и 6).

Внешний цикл всегда n раз, и внутренний цикл равен i для каждой итерации, поэтому для значений n вот количество итераций:

n    count
=    ===========================================
1    (1)                                    =  1
2    (1),(12)                               =  3
3    (1),(12),(123)                         =  6
4    (1),(12),(123),(1234)                  = 10
5    (1),(12),(123),(1234),(12345)          = 15
6    (1),(12),(123),(1234),(12345),(123456) = 21

Закрытая формула для них лучше всего иллюстрируется следующим образом:

n = 5: 5 + 4 + 3 + 2 + 1
       |   |   |   |   |
       |   |   V   |   |
       |   |   3   |   |  Formula is: (n+1)*((n-1)/2)  +  ((n+1)/2)
       |   +-> 6 <-+   |             [outer pair sets] + [inner value]
       +-----> 6 <-----+
              --
              15

Это формула для всех нечетных значений n. Для четных значений можно использовать аналогичный метод:

n = 6: 6 + 5 + 4   +   3 + 2 + 1
       |   |   |       |   |   |
       |   |   +-> 7 <-+   |   | Formula is:   (n+1)*(n/2)
       |   +-----> 7 <-----+   |            [outer pair sets]
       +---------> 7 <---------+
                  --
                  21

Здесь указывается количество итераций вложенного цикла для каждого значения n (назовем это x).

Расчет окончательного значения sum очень похож. На первой итерации вы добавляете ноль. На второй итерации вы добавляете одну. На третьей итерации вы добавляете две. Это почти то же самое, что вы должны были сделать, чтобы вычислить количество итераций, только теперь он основан на x, а не n, и 0+1+2+..., а не 1+2+3+..., то есть мы можем использовать точно так же формула, просто применяя ее к x-1, а не x.

Так что мы можем использовать:

if n is odd:
    x <- (n+1) * ((n-1)/2) + ((n+1)/2)
else:
    x <- (n+1) * (n/2)
x <- x - 1
if x is odd:
    sum <- (x+1) * ((x-1)/2) + ((x+1)/2)
else:
    sum <- (x+1) * (x/2)

Проверка этого по алгоритму для первых нескольких значений в n:

n  algorithm  formula
-  ---------  -------
0       0         0
1       0         0
2       3         3
3      15        15
4      45        45
5     105       105

Итак, идеальное совпадение, по крайней мере, в выбранном месте выборки. Вы могли бы пойти дальше и превратить это в единую формулу, основанную только на n, вместо того, чтобы вычислять промежуточное значение, но я оставлю это в качестве упражнения для читателя.

---

Подсказка: формула C, которая работает как для нечетных, так и для четных чисел:

    x <- ((n+1) * ((n-(n%2))/2)) + ((n%2) * ((n+1)/2))

(хотя все еще не проверено на отрицательные значения n - вы должны поставить проверку на это, прежде чем использовать формальную версию).

Answer 2

Внутренний цикл (давайте просто позвоним i на фиксированный номер):

inc увеличивается * в 1005 * раз.
sum имеет inc добавлено к нему i раз. (я * (я-1) / 2, верно?)

Если мы предположим, что inc и sum начнут художественное значение 0, то это верно. Если мы предположим, что они начинаются с какого-то другого значения, назовем их k и l, то мы знаем, что inc в итоге получит значение k+i. Мы знаем, что sum закончится на l+k*i + i*(i-1)/2.

Теперь само i переходит с 1 на n. Хм ... гул. Позвольте мне подумать об этом немного больше.