Информатика • 10 класс

Целочисленные алгоритмы (Python)

Алгоритм Евклида (вычисление НОД через НОД)	НОД (a, b) = НОД (a mod b, b) = НОД (a, b mod a) Функция NOD (x, y)
Решето Эратосфена (поиск простых чисел)	Записать числа от 2 до N. Начать с k = 2. Считая с позиции 2k, через шаг k «выколоть» все числа. Перейти к следующему «невыколотому». Если k · k ≤ N, то перейти к шагу 2
Длинные числа	Длинные числа хранятся как массив [А] := 1 Число хранится по группах из шести цифр, а именно в системе счисления 1000000
Целочисленная оптимизация (задача «бродячий торговец»)	Найти кратчайший путь, при котором торговец, выйдя из п. 1 и посетив все n города по одному разу, снова придет в п. 1. Решение. Необходимо выполнить перебор всех (n – 1)! возможных комбинаций пунктов назначения и найти кратчайший путь L_min (на основе матрицы расстояний)

Алгоритм Евклида (вычисление НОД через НОД)

НОД (a, b) = НОД (a mod b, b) = НОД (a, b mod a)
Функция NOD (x, y)

Решето Эратосфена (поиск простых чисел)

Записать числа от 2 до N.
Начать с k = 2.
Считая с позиции 2k, через шаг k «выколоть» все числа.
Перейти к следующему «невыколотому».
Если k · k ≤ N, то перейти к шагу 2

Длинные числа

Длинные числа хранятся как массив [А] := 1

Число хранится по группах из шести цифр, а именно в системе счисления 1000000

Целочисленная оптимизация (задача «бродячий торговец»)

Найти кратчайший путь, при котором торговец, выйдя из п. 1 и посетив все n города по одному разу, снова придет в п. 1.

Решение. Необходимо выполнить перебор всех (n – 1)! возможных комбинаций пунктов назначения и найти кратчайший путь L_min (на основе матрицы расстояний)

Было полезно?