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

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

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

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

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

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

Начать с k = 2.

Считая с позиции 2k, через шаг k «выколоть» все числа.

Перейти к следующему «невыколотому».

Если k·kN, то перейти к шагу 2.

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»