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

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

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

Предыдущий конспект

Следующий конспект