Виртуальный кабинет учителя информатики

​

Алгоритмы над целыми числами

 

1. Делимость

2. Первая модификация алгоритма Евклида (с вычитанием)

 

      Задачи, которые необходимо разобрать при изучении данной темы:

• Определить, являются ли несколько чисел взаимно простыми

• Сократить дробь (числитель и знаменатель дроби вводятся)

• Написать программу «Калькулятор» в простых дробях
  
  Вторая модификация алгоритма Евклида, использующая деление с остатком где r – остаток от деления большего числа на меньшее. Таким образом, уменьшая числа, получим наибольший общий делитель как последний не равный нулю остаток.Задача для решения: прямоугольник с длинами сторон a и b, где a и b – натуральные числа, разрезать на квадраты максимальной площади. Определить размер квадратов и их общее количество.
  
  Диофантовы уравнения
  Используя утверждение о представлении наибольшего общего делителя двух чисел в виде линейной комбинации этих чисел, приходим к утверждению о разрешимости в целых числах уравнения вида ax + by = c (диофантово уравнение).
  Задачи, которые необходимо разобрать при изучении данной темы:

• Задачи на размен денег монетами определенного достоинства.

• Задачи на переливание.
   
  Простые числа
  С простыми числами связано множество олимпиадных задач разных уровней. Классический метод для нахождения простых чисел - решето Эратосфена. С этим алгоритмом связаны решения следующих задач:

• Числа-близнецы;

• Совершенные числа;

• Скатерть Улама;

• Дружественные числа и т.п.
  
  «Длинная» арифметика
  Задачи на «длинную» арифметику возникают тогда, когда в стандартных типах данных (целые или длинные целые) не представляется возможным хранить результат, настолько он велик. В этом случае используется прием хранения длинных чисел в виде массива цифр, а чтобы выполнять арифметические действия с такими числами, необходимо написать специальные процедуры сложения, умножения, деления длинных чисел.
  Типовые задачи: найти число N! (N-факториал), определить период дроби.
  
  Рекурсия
  Почти в любой книге по программированию касаются рекурсии и рекурсивных процедур и функций. Но очень мало книг, где тема рекурсии разбиралась бы подробно.
  Это следующие задачи: факториал числа, N-я степень числа, НОД(a,b), функция Аккермана, числа Фибоначчи, перевод чисел из 10-й системы счисления в 2-ю, нахождение максимума и минимума в массиве. Многие задачи, оказывается, можно делать с помощью рекурсии. Главное, что появляется видение рекурсии в задачах, ранее решенных не рекурсивно. С целью новизны, например, в задаче о разрезании прямоугольника на квадраты максимальной площади предлагается сделать наглядное графическое сопровождение с помощью рекурсии. И уж совсем «плохо» без рекурсии при решении таких задач, как «Ханойская башня». В данном случае осознать это и на практике освоить рекурсивный алгоритм решения данной задачи помогает демонстрационно-обучающая программа «Ханойская башня».
  
  Сортировка
  Без знаний алгоритмов сортировки никак нельзя спокойно чувствовать себя на олимпиадах различного уровня. Задачи могут формулироваться как явно с упоминанием алгоритма сортировки, так и подразумевая внутри решения использование алгоритма сортировки. Два простейших алгоритма, которые необходимо знать, - это «пузырек» и сортировка обменом (с помощью поиска последовательных минимумов). При небольших объемах данных вполне хватает этих двух методов, но при работе с данными, измеряемыми десятками и сотнями Кбайт, необходимо знание какой-нибудь из быстрых сортировок. Предпочтение можно отдать быстрой сортировке Хоара, которая реализуется рекурсивно. Необходимо также знать некоторые приемы при упорядочивании данных в больших файлах. Весь файл разбивается на некоторое количество кусков, которые можно отсортировать с помощью QSORT, а затем произвести слияние отсортированных файлов уже без программы сортировки (кстати, это очень полезная с технической точки зрения задача, требующая аккуратности и хорошей техники программирования).
  
  Перебор вариантов
  Задачи перебора составляют огромный класс олимпиадных задач. Начинается перебор с простейшего поиска минимума и максимума в одномерном массиве или поиска элемента с заданными свойствами. Далее идет перебор пар элементов, использующий вложенный цикл, затем перебор троек элементов, использующий тройной цикл (как, например, в задаче о поиске трех точек на плоскости среди заданных N точек, которые образуют треугольник с максимальной площадью). А если перебирать сочетания из 4, 5, 6 и т.д. элементов? Сколько же необходимо циклов? Оказывается, существуют алгоритмы, существенно сокращающие перебор.
  Довольно длинный по времени выполнения, но один из самых универсальных алгоритмов перебора, - перебор с возвратом или «бектрекинг». Программируется рекурсивно. Лучше всего объясняется на следующих задачах:

• Ходом коня обойти шахматную доску N*M;

• Расставить 8 ферзей на шахматной доске размера 8*8 так, чтобы они не угрожали друг другу;

• Найти выход из лабиринта и т.п.
  Необходимо также объяснять учащимся, что в случае слишком долгого времени выполнения программы, необходимо ограничивать «бектрекинг». Например, в задаче про шахматы при размере доски 8*8 выполняется программа уже довольно долго. Можно и даже нужно применять симметрию, зеркальное отображение, выполняя задание для половины или четверти шахматной доски.
  Классической задачей на «бектрекинг» является задача о «рюкзаке», затем можно рассматривать производные от этой задачи:

• Разбить N чисел на два подмножества, наиболее близких по сумме;

• Из заданного множества слов выбрать максимальную подпоследовательность слов в словарном порядке.
  С перебором связаны и комбинаторные задачи. Следует освоить алгоритмы создания лексикографического упорядочения.
  
  Задачи на геометрию
  Обязательный минимум, который необходимо знать при решении задач на геометрию, включает в себя следующее:

• Уметь привести уравнение прямой, проходящей через две точки к виду Ax + By + C = 0;

• Уметь определить, принадлежит ли точка прямой или отрезку;

• Уметь определить, пересекаются ли две прямые, и, если пересекаются, то определить их точку пересечения (для этого вычислять определитель 2-го порядка);

• Уметь написать уравнение перпендикулярной прямой или определить, перпендикулярна ли одна прямая другой (использование свойства о равенстве нулю скалярного произведения перпендикулярных векторов);

• Уметь вычислять расстояние от точки до прямой.
  В дополнение к этому для решения задач областного и Всероссийского уровня необходимы знания начального курса аналитической геометрии: скалярное и векторное произведение векторов, выражение их через координаты. Скалярное произведение используется для нахождения угла (или косинуса угла) при построении, например, выпуклой оболочки заданных точек. Векторное произведение двух векторов используется, во-первых, для вычисления площадей многоугольников, а во-вторых, для определения направления в соответствующих задачах. Эти знания необходимы также для того, чтобы решать такую классическую олимпиадную задачу, как содержится ли точка внутри произвольного многоугольника.
  Необходимо обратить внимание учащихся на многозначность понятий, которые можно использовать в различных задачах.
  
  Численные методы
  Метод дихотомии
  Для поиска данных в упорядоченном множестве используется метод дихотомии (или деления пополам) с последующей проверкой искомых свойств. Этот метод, который более привычен для нахождения приближенных значений корней нелинейных уравнений, можно использовать для поиска среди «огромного» количества данных. В этом случае более употребим термин «бинарный поиск».
  Типовая задача – найти заданное слово в словаре.
  В общем случае, данный метод является оптимальным.
  Решение систем линейных уравнений: метод Крамера, метод Гаусса.
  Классические методы. Обычно в задачах число уравнений не более трех. Но знание общего случая, вероятно, пригодится.
  Задача с областной олимпиады 94 года.
  Вводится в виде строчки уравнение химической реакции: необходимо уравнять, т.е. расставить коэффициенты.
  
  Статистическое моделирование (метод Монте-Карло).
  Очень полезным является знание данного метода:

• для моделирования игровых вероятностных ситуаций (бросание монеты, кубика, блуждания). Именно «игровая» или связанная с чем-то знакомым (известным, «бытовым») формулировка задачи помогает в понимании метода, понятия вероятности. Можно предложить учащимся интересные задачи:

• чего больше, сократимых или несократимых дробей? (Математическая формулировка: оценить вероятность того, что наудачу взятая дробь несократима);

• лучшее пари для простаков («Квант» №5,1987);

• комбинаторные задачи.

• Для определения площадей фигур, когда затруднены аналитические решения.
  
  Так, в задаче (областная олимпиада 99 года) по нахождению площади пересечения трех окружностей метод Монте-Карло можно использовать в качестве альтернативного прямому аналитическому методу, так как очень трудно вывести решение, используя тригонометрические соотношения. Наилучший путь - это «использовать геометрию» для анализа частных случаев (когда нет пересечения, когда пересечение в одной точке, одна окружность внутри другой), а метод Монте-Карло для общего случая.
  
  Динамическое программирование.
  Бывают случаи, когда невозможно решить задачу полным перебором вариантов из-за их огромного количества. Но если на каждом шаге задачу можно разбить на более простые и найти оптимальное решение для них, не рассматривая всех решений общей задачи, а затем найденные решения применить для следующих шагов, то это и означает, что в данном случае применим принцип динамического программирования.
  Данный принцип легче всего воспринимается на конкретных задачах. Но объяснение его можно начать с занимательной истории про золотую лестницу Фараона (изложенную в журнале «Квант» №10, 1991 г.), а затем перейти к следующим задачам:

• Классическая задача о нахождении такого кратчайшего пути в числовой матрице A размерности NхN из A(1,1) в A(n,n), в котором сумма цифр в клетках была минимальной или максимальной.

• Нахождение общей подстроки максимальной длины (задача, возникшая из современной реальной задачи молекулярной биологии об общей генетической информации в молекулах ДНК).
  
  
  Графы и деревья.
  Очень важная тема. Практически ни одна олимпиада не обходится без использования какого-либо алгоритма на графах. Необходимо ввести понятие графа через вершины и ребра, понятие ориентированных или неориентированных графов, разобрать методы представления графов в виде матрицы, смежности, матрицы инциденций, списка связей.
  Разобрать основные алгоритмы на графах:

• поиск в глубину (иными словами “бектрекинг” или перебор с возвратом);

• поиск в ширину (или метод заливки);

• Алгоритм Дейкстра для поиска кратчайших путей в графе из заданной вершины во все остальные;

• Алгоритм Флойда для поиска кратчайших путей в графе между всеми парами вершин.
  
  Текстовые преобразования
  Задачи, в которых необходимо проводить разбор строки, порой дополнительно предполагают работу с файлами, графическими построениями (подобие команд текстового или графического редактора) или использование каких-либо приемов программирования (например, представление “стека” в виде символьной строки в задаче о правильном скобочном выражении для нескольких типов скобок).
  Представлен широкий, но далеко не полный набор тем, охватываемых олимпиадными задачами. Во многом это зависит от пристрастий организаторов олимпиад различных уровней (теоретические туры, задачи с использованием игровых стратегий, прикладного «офисного» характера).
  
  Что можно посоветовать при решении задач на олимпиаде?
  Предполагая, что теория алгоритмов «проштудирована» и основы программирования освоены, участнику соревнования можно посоветовать следующее:
  1.Оцените и распределите свои силы, знания и время в соответствии со сложностью предлагаемых задач.
  2.Обеспечьте «про запас» определенный «гарантированный» (по вашему мнению) набор баллов на простых задачах. Это не означает, что сложные задачи оставлять на последний момент. При обдумывании их решения может быть найден «хороший» алгоритм, и успехом послужит соответственно большая доля баллов.
  3.Если задача трудна для вас или дефицит времени для решения, запрограммируйте простые частные случаи (авось некоторые тесты пройдут), либо используйте какой-нибудь неоптимальный, например, переборный алгоритм.
  4.Если для задачи указано ограничение по времени решения, а ваш переборный алгоритм не укладывается в это время, то вставьте в алгоритм таймер, который при приближении к критическому времени заканчивает задачу и выводит наилучший найденный переборный вариант (возможно, он будет правильным).
  5.Немаловажен выбор алгоритмического языка, например, в Basic-программе легче работать с графикой, а у Pascal-программы - преимущество быстродействия.
  6.Строго соблюдайте указанные в условии задачи форматы ввода-вывода: «автотестировщик» может неправильно воспринять лишний пробел, или исходные тесты содержат запятую там, где вы предусматривали во вводе своей задачи пробел (особенности операторов ввода Pascal и Basic).
  7.В основном, любая программа имеет структуру:

• Ввод данных

• Расчетный блок

• Вывод результата
  1.Оформите и убедитесь, что ввод-вывод правильный (с возможным анализом ошибочных данных) прежде, чем программировать расчетный блок.
  2.Поставьте ключи компилятора для обработки всевозможных ошибок (полезно при отладке), а перед сдачей задачи отключите эти опции (для игнорирования компилятором возможных ошибок тестирования, которые не сказываются на решении).
  3.Проверьте задачу для заданных максимальных ограничений (например, если дано n £ 1000, проверьте для n = 1000). Следите за типом объявляемых переменных (предпочтительно для описания целочисленных переменных использовать тип «длинное целое»).
  4.Разумно используйте апелляцию. Возможна двусмысленность понимания задачи. В жюри тоже люди, и вы можете отстоять свою позицию, убедить их добавить вам желанные баллы.
  5.В крайнем случае, если вы «cool hacker» (крутой специалист по системной части), запустите программу «соседа», как свою (небось, никто не заметит).