Облако знаний. Алгоритмы обработки целых чисел. Решето Эратосфена (Python). Информатика. 11 класс

Алгоритмы обработки целых чисел. Решето Эратосфена (Python)

Алгоритм	Описание
Алгоритм Евклида	НОД (a, b) = НОД (a – b, b) = НОД (a, b – a)
Решето Эратосфена (поиск простых чисел)	Записать числа от 2 до N. Выбрать шаг k. Считая с позиции k, через шаг k «выколоть» числа от 2k до N, которые кратны k (2k, 3k, … ). Выбрать ближайшее незачёркнутое число p, которое больше, чем k. Выполнить шаги 2–3 при k = p
Целочисленная оптимизация (задача «бродячий торговец»)	Найдите кратчайший путь, при котором торговец, выйдя из п. 1 и посетив все n города по одному разу, снова придёт в п. 1. Решение. Необходимо выполнить перебор всех (n – 1)! возможных комбинаций пунктов назначения и найти кратчайший путь L_min (на основе матрицы расстояний). Реализация пути: необходимо записать перестановку 2, 3, 4, ..., N и найти длину пути; случайно переставить два города и найти длину маршрута; запомнить перестановку, если длина пути короче предыдущего; повторить цикл, пока не будут перебраны все пути

Алгоритм

Описание

Алгоритм Евклида

НОД (a, b) = НОД (a – b, b) = НОД (a, b – a)

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

Записать числа от 2 до N.
Выбрать шаг k.
Считая с позиции k, через шаг k «выколоть» числа от 2k до N, которые кратны k (2k, 3k, … ).
Выбрать ближайшее незачёркнутое число p, которое больше, чем k.
Выполнить шаги 2–3 при k = p

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

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

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

Реализация пути:

необходимо записать перестановку 2, 3, 4, ..., N и найти длину пути;
случайно переставить два города и найти длину маршрута;
запомнить перестановку, если длина пути короче предыдущего;
повторить цикл, пока не будут перебраны все пути

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