Численные алгоритмы. Лекция №2

План:
Нахождение наибольшего общего делителя.
Возведение в степень.
Работа с простыми числами. Нахождение
простых множителей. Нахождение простых
элементов. Проверка на простоту.
Численное интегрирование. Формула
прямоугольников. Формула трапеций.

3.

Рандомизация данных.
Генерирование случайных величин
Линейный конгруэнтный генератор псевдослучайных чисел
Пример. A = 7, B = 5 и M = 11.
0, 5, 7, 10, 9, 2, 8, 6, 3, 4

4.

Рандомизация массивов
Время работы алгоритма равно O(N)

5.

Нахождение
наибольшего общего делителя
максимальное время работы
алгоритма O(log (B))

6.

Возведение в степень
73 = 7 × 7 × 7 = 343
7
102 187 291
=?
Общее время работы составляет

7.

Нахождение простых множителей
время работы алгоритма составит O(N)

8.

1. Не стоит проверять, делится ли число на любое четное, кроме 2,
поскольку четные числа уже сами по себе кратны двум. Это означает, что
нужно рассмотреть лишь делимость на 2 и на нечетные числа, вместо
того, чтобы перебирать все возможные множители. В таком случае время
работы сократится вдвое.
2. Следует проверять множители только до квадратного корня числа. Если
n = = p q, то p или q должно быть меньше либо равно sqrt (n). (Если p и q
больше sqrt (n), их произведение превысит n.) Проверив возможные
множители до sqrt (n), вы найдете наименьший среди них, а, поделив n
на такой множитель, определите еще один. Это сократит время работы
до O(sqrt (n)).
3. Всякий раз при делении числа на множитель вы можете обновить
максимальное количество потенциальных множителей, которые
необходимо проверить.

Численные алгоритмы. Лекция №2

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.