Цитата nastr:
Можно без массива. Дано N. Найти сумму натуральный чисел, не превосходящих N, которые делятся на 3 и на 7 без остатка.
найти сумма всех чисел не превосходящих N, которые делятся на 3 без остатка. »
|
Вооот, это уже другая задача. Массив-то, как я понимаю, оказывается не просто упорядоченным, а с шагом в 1 (т.к. последовательность натуральных чисел).
Тогда алгоритм весь строится на сумме арифметической прогрессии следующим образом:
Шаг 0. Пусть N = 500 (т.е. числа 1 2 3 4... 499 500)
Шаг 1. Первый член арифметической прогрессии с шагом в 3 [An=3d] - это 3. Последний член прогрессии = mod(500 / 3) * 3 = 166 * 3 = 498 (используем целочисленное деление). Заодно мы в курсе, что последний член прогрессии имеет номер 166.
Шаг 2. Считаем сумму арифметической прогрессии по формуле (
в википедии есть) sum = (A1+An)*n/2 = (3 + 498) * 166 / 2 = 41583
Шаг 3. Теперь с семёркой. Тут немного сложнее, т.к. нам надо из суммы исключить числа, делящиеся на 3
Имеем такой ряд: 7 14 28 35 49 56... Т.е. просто An=7d нас не устраивает. Используем хитрость:
Шаг 4. Сначала считаем сумму для прогрессии An=7d. 71 член прогрессии равен 497. Сумма = (7 + 497) * 71 / 2 = 17892
Шаг 5. Теперь нужно исключить числа, делящиеся на 21. Считаем сумму прогрессии An = 21d. 23 член прогрессии равен 483. Сумма = (21 + 483) * 23 / 2 = 5796
Шаг 6. Итоговый результат = 41583 + 17892 - 5796 = 53697.
Для маленького N такой алгоритм не особо эффективен, но для большого - то, что надо. Для предела в 500 значений, в ассемблере получается 40 инструкций для этого алгоритма и около 6500 инструкций для цикла с делением.
Конечно, если у вас массив - это не последовательность натуральных чисел, а просто упорядоченные случайные целые числа больше нуля, то ничего не выйдет, используйте цикл.
