Алгоритмы обработки целых чисел (C++)

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

1) Записать числа от 2 до N.

2) Выбрать шаг k.

3) Считая с позиции k, через шаг k «выколоть» числа от 2k до N, которые кратны k (2k, 3k, … ).

4) Выбрать ближайшее незачёркнутое число p, которое больше, чем k.

5) Выполнить шаги 2–3 при k = p.

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

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

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

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

1) необходимо записать перестановку 2, 3, 4, ..., N и найти длину пути;

2) случайно переставить два города и найти длину маршрута;

3) запомнить перестановку, если длина пути короче предыдущего;

4) повторить цикл до тех пор, пока не будут перебраны все пути.