Алгоритм повторения формулы

Question

Я читаю Алгоритмы на С ++ Роберта Седжвика. В разделе «Основные рекурсии» было упомянуто как «Это рекуррентность возникает для рекурсивной программы, которая перебирает ввод для исключения одного элемента». Cn = cn-1 + N, для N> = 2 с C1 = 1.

Cn - это Nsquare / 2. Оценка суммы 1 + 2 + ... + N является элементарной. в дополнение к этому упоминается следующее утверждение. «Этот результат - вдвое больше искомого значения - состоит из N слагаемых, каждое из которых суммируется с N + 1

Мне нужна помощь в понимании вышеизложенного утверждения, каковы здесь N терминов и как каждый из них суммирует N +1, а также то, что означает «вдвое больше искомого значения».

Спасибо за вашу помощь

Answer 1

Я думаю, что он обращается к этой основной математической уловке, чтобы вычислить эту сумму.Хотя из такого короткого отрывка, на который вы ссылались, сложно что-то сделать.

Предположим, N = 100.Например, сумма равна 1 + 2 + 3 + .. + 99 + 100.
Теперь давайте сгруппируем пары элементов с суммой 101: 1 + 100, 2 + 99, 3 + 98, ..., 50 + 51.Это дает нам 50 (N/2) пар с суммой 101 (N + 1) в каждой: таким образом, общая сумма составляет 50*101.

В любом случае, не могли бы вы предоставить немного больше контекстаэта цитата?

Answer 2

Формула повторения означает:

C1 = 1
C2 = C1 + 2 = 1 + 2 = 3
C3 = C2 + 3 = 3 + 3 = 6
C4 = C3 + 4 = 6 + 4 = 10
C5 = C4 + 5 = 10 + 5 = 15
etc.

Но вы также можете написать это напрямую: C5 = 1 + 2 + 3 + 4 + 5 = 15

А затем используйте старый трюк:

  1 +   2 +   3 + ... + N
+ N + N-1 + N-2 + ... + 1
-------------------------
 (N+1) ...             (N+1)

= (N + 1) * N

Оттуда получаем: 1 + 2 + ... N = N * (N + 1) / 2

Для анекдота приведенная выше формула была найдена великим математиком Карлом Фридрихом Гауссом, когда он учился в школе.

Отсюда можно вывести рекурсивный алгоритм O (N квадрат), и это, вероятно,что делает Роберт Седжвик.