Что является доказательством (N – 1) + (N – 2) + (N – 3) +… + 1 = N * (N – 1) / 2 [закрыто]

При компиляции шаблоны должны быть созданы экземплярами , прежде чем их компилировать в объектный код. Это создание может быть достигнуто только в том случае, если известны аргументы шаблона. Теперь представьте сценарий, в котором функция шаблона объявлена ​​в a.h, определенная в a.cpp и используемая в b.cpp. Когда компилируется a.cpp, не обязательно известно, что для предстоящей компиляции b.cpp потребуется экземпляр шаблона, не говоря уже о том, какой конкретный экземпляр это будет.

Можно утверждать, что компиляторы можно сделать умнее, чтобы «смотреть вперед» для всех применений шаблона, но я уверен, что это было бы нелегко создавать рекурсивные или другие сложные сценарии. AFAIK, компиляторы этого не делают. Как заметил Антон, некоторые компиляторы поддерживают явные декларации экспорта экземпляров шаблонов, но не все компиляторы поддерживают его (пока?).

22
задан Andrew Medico 20 March 2010 в 18:47
поделиться

9 ответов

7
ответ дан 29 November 2019 в 03:49
поделиться

Предположим, что n = 2. Тогда у нас 2-1 = 1 с левой стороны и 2 * 1/2 = 1 с правой стороны.

Обозначим f (n) = (n-1) + (n-2) + (n-3) + ... + 1

Теперь предположим, что мы проверили до n = k. Затем мы должны проверить, что n = k + 1.

в левой части у нас есть k + (k-1) + (k-2) + ... + 1, так что это f (k) + k

Тогда в правой части имеем (k + 1 ) * k / 2 = (k ^ 2 + k) / 2 = (k ^ 2 + 2k - k) / 2 = k + (k-1) k / 2 = k f (k)

. Таким образом, это должно выполняться для любого k, и это завершает доказательство.

1
ответ дан 29 November 2019 в 03:49
поделиться

Начнем с треугольника ...

    *
   **
  ***
 ****

, представляющего пока что 1 + 2 + 3 + 4. Разрежьте треугольник пополам по одному измерению ...

     *
    **
  * **
 ** **

Поверните меньшую часть на 180 градусов и приклейте ее поверх большей части ...

    **
    * 

     *
    **
    **
    **

Закройте зазор, чтобы получить прямоугольник.

На первый взгляд, это работает, только если основание прямоугольника имеет четную длину - но если у него нечетная длина, вы просто разрезаете средний столбец пополам - это все равно работает с половиной ширины в два раза больше. -tall (все еще целая область) полоса на одной стороне вашего прямоугольника.

Каким бы ни был основание треугольника, ширина вашего прямоугольника составляет (основание / 2) , а высота составляет (основание + 1) , что дает ((основание + 1) * база) / 2 .

Однако моя база - это ваш n-1 , поскольку пузырьковая сортировка сравнивает пару элементов за раз и, следовательно, выполняет итерацию только (n-1) позиций для первая петля.

21
ответ дан 29 November 2019 в 03:49
поделиться

(N-1) + (N-2) + ... + 2 + 1 - это сумма N-1 элементов. Теперь измените порядок элементов так, чтобы после первого шел последний, затем второй, а затем второй до последнего, то есть (N-1) + 1 + (N-2) + 2 + .. . Теперь, когда элементы упорядочены, вы можете видеть, что каждая из этих пар равна N (N-1 + 1 - N, N-2 + 2 - N). Так как элементов N-1, таких пар (N-1) / 2. Итак, вы добавляете N (N-1) / 2 раза, поэтому итоговое значение будет N * (N-1) / 2 .

16
ответ дан 29 November 2019 в 03:49
поделиться

Попробуйте составить пары чисел из набора. Первое + последнее; второе + позапрошлое. Это означает n-1 + 1; n-2 + 2. Результат всегда равен n. А так как вы складываете два числа, то из (n-1)/2 пар можно составить только (n-1) пар.

Так что это похоже на (N-1)/2 * N.

8
ответ дан 29 November 2019 в 03:49
поделиться

Я знаю, что мы (n-1) * (n раз), но зачем деление на 2?

Это только (n - 1) * n, если вы используете наивный баблсорт. Вы можете получить значительную экономию, если обратите внимание на следующее:

  • После каждого сравнения и замены самый большой элемент, с которым вы столкнулись, будет находиться на последнем месте, на котором вы были.

  • После первого прохода самый большой элемент будет находиться в последней позиции; после k-го прохода k самый большой элемент будет находиться в k последней позиции.

Таким образом, вам не нужно каждый раз сортировать весь массив: вам нужно отсортировать только n - 2 элемента во второй раз, n - 3 элемента в третий раз и так далее. Это означает, что общее количество сравнений/обменов, которые вам нужно сделать, составляет (n - 1) + (n - 2) + ... . Это арифметический ряд, и уравнение для общего количества раз равно (n - 1)*n / 2.

Пример: если размер списка N = 5, то вы делаете 4 + 3 + 2 + 1 = 10 обменов - и заметьте, что 10 - это то же самое, что 4 * 5 / 2.

4
ответ дан 29 November 2019 в 03:49
поделиться

Это довольно распространенное доказательство. Один из способов доказать это - использовать математическую индукцию. Вот ссылка: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

2
ответ дан 29 November 2019 в 03:49
поделиться

Сумма арифметической прогрессии

(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2

1
ответ дан 29 November 2019 в 03:49
поделиться

Вот доказательство по индукции, рассматривающее N терминов, но это то же самое для N - 1:

Для N = 0 формула очевидно верна.

Предположим, что 1 + 2 + 3 + ... + N = N(N + 1) / 2 истинно для некоторого натурального N.

Докажем, что 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2 также истинно, используя наше предыдущее предположение:

1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1) = (N + 1)((N / 2) + 1) = (N + 1)(N + 2) / 2.

Таким образом, формула справедлива для всех N.

1
ответ дан 29 November 2019 в 03:49
поделиться
Другие вопросы по тегам:

Похожие вопросы: