Александр Кулаков
Поговорим об алгоритмах. Вам уже рассказывали на уроке информатики, что алгоритм - это последовательность действий, направленная на достижение какой-то цели. Одним из самых простых является, наверное, инструкция мамы, как сварить борщ.
Но компьютеры имеют дело не с шедеврами кулинарии, а с двоичными
символами - битами, наборы которых похожи на числа. А как связаны математика
и алгоритмы и бывают ли алгоритмы в математике?
Вы, конечно, ответите "да" и приведете пример, который разобрали
на уроке математики или информатики - алгоритм Евклида. Напомню его.
Даны два числа m и n. Найти наибольший общий делитель чисел
- НОД (m, n).
На первый взгляд, решение кажется очевидным.
АЛГ-1.
Шаг 1. Найти все делители числа m.
Шаг 2. Найдем все делители числа n.
Шаг 3. Найдем все общие делители m и n.
Шаг 4. Выберем из последнего множества наибольшее число,
оно и будет НОД (m, n).
И если Вы придумали этот алгоритм, когда впервые узнали о рассмотренной Евклидом задаче, то дело обстоит просто замечательно. Потому что без него невозможно понять, как Евклид пришел к своему алгоритму.
Для небольших чисел этот алгоритм работает замечательно.
Задача 1. Проделайте алгоритм АЛГ1 для пары чисел 24 и 54. Вы довольны быстротой, с которой получен результат?..
Но для чисел побольше на его выполнение уйдет существенно
больше времени.
Задача 2. Проделайте алгоритм АЛГ1 для пары чисел
m = 2^5*3^2*5*1^1, n = 2^2*3^3*5^2*1^3
Я думаю, что мало кто в состоянии проделать действия, предписываемые
АЛГ1, и не ошибиться: ведь числа m и n имеют по 72 различных делителя.
Основная трудоемкость здесь состоит в выписывании всех делителей
чисел m и n. К тому же побольшей части эти делители для нахождения НОД (m, n)
вовсе и не нужны.
Задача 3. Число m разложено на простые множители m=p1^m1*p2^m2*...*pk^mk. Сколько различных делителей у числа m?
"Чего же здесь сложного?", скажете Вы. - "Напишем одно под
другим числа
m = 2^5*3^2*5*1^1*13^0
n = 2^2*3^3*5^2*11^0*13
и выберем среди степеней каждого простого делителя, на которые
делятся m и n, минимальную степень. Произведение простых делителей, возведенных
в эти степени, и будет НОД (m, n)"
m = 2^5*3^2*5*1^1*13^0
n = 2^2*3^3*5^2*11^0*13
НОД (m, n) = 2^2*3^2*5*11^0*13^0 = 2^2*3^2*5
Таким образом Вы сформулировали другой алгоритм.
АЛГ-2.
Шаг 1. Разложим m на простые множители (математики
записывают это так, как это сделано в задаче 3)
m = p1^m1*p2^m2*...*pk^mk
Шаг 2. Разложим n на простые множители
n = p1^n1*p2^n2*...*pk^nk
(Заметьте - если простой множитель встречается только в одном
из чисел, то в другом мы будем писать его в степени 0)
Шаг 3.
НОД (m, n) = p1^min(m1, n1)*p2^min(m2, n2)*...
Значком min (a, b) обозначается минимальное из чисел a и b.
А теперь попробуйте решить еще одну задачу
Задача 4. Найти НОД (27563, 4773). АЛГ-Е. (алгоритм Евклида) Задача 5. Попробуйте ответить на такой вопрос: "Как оценить по числам m и n, за какое число операций закончит работу АЛГ-Е (т.е., например, сколько раз нужно будет выполнять Шаг 1)?" От редакции: Уважаемые читатели! Советуем не дожидаться продолжения статьи, а взяться за дело и продемонстировать изящный стиль программирования с учетом рекомендаций автора. Направляйте ваши решения задачи о монете в редакцию или по электронной почте: giglavy@lit.msu.ru
Заметьте, Вы очень долго выполняли шаги 1 и 2 (даже если действовали
с калькулятором, не говоря уже о вычислениях на бумаге).
Действительно, разложение больших чисел на простые множители
- это трудная задача, по сложности вычислений более трудоемкая, чем алгоритм
нахождения НОД (m, n). Как же Евклид пришел к своему алгоритму?
Евклид знал (вряд ли он был первым, кто заметил этот факт),
что
Лемма Числа m и n делятся на k, то и их разность (m - n) тоже
делится на число k (впрочем, сумма (m + n) тоже делится на число k (мы считаем,
что n ( m).
Задача 4. Попробуйте аккуратно алгебраически доказать
эту лемму.
Как же рассуждал дальше Евклид? Лемма верна для любого общего
делителя k чисел m и n. Следовательно, множество общих делителей чисел m и n
совпадает с множеством общих делителей чисел m и m-n.
Сами множества делителей n и делителей m-n могут сильно различаться,
но их "общая часть" - общие делители m и n и общие делители m и m-n совпадают!
Следовательно, и наибольшее из чисел в этих множествах - одно и то же.
Ничего не стоит теперь вычитать число n из m до тех пор, пока
не получится 0 или число меньшее, чем n. Если получился 0, это означает, что
m делится на n и НОД (m, n) = n. Если же получится число n1, меньшее, чем n,
а это число есть остаток от деления m на n (математики записывают это так: m
= sn + n1, 0(n1
Дана пара (m, n).
Шаг 1. Поделить m на n с остатком n1
Шаг 2. Если n1 = 0, то НОД (m, n) : = n
Если n1 (0, то перейти к шагу 1 с парой (n, n1)
Сделаем теперь несколько замечаний.
Во-первых, работа АЛГ-3 и АЛГ-Е когда-то закончится - ведь
сумма чисел в АЛГ-Е, с которой имеет дело Шаг 1 этого алгоритма, каждый раз
уменьшается.
Во-вторых, АЛГ3 и АЛГ-Е - рекуррентные алгоритмы. Как Вы знаете,
это означает, что в процессе работы они обращаются сами к себе.
Мы так долго и подробно разбирали хорошо Вам знакомый алгоритм
Евклида, чтобы еще раз обратить Ваше внимание на то, что учет одного-единственного
простого математического факта (мы имеем в виду лемму Евклида) позволил придумать
алгоритм, в котором резко сокращается объем вычислений для нахождения НОД (m,
n).
Искусство создавать алгоритмы как раз и состоит в умении посмотреть
на математический факт, формулу или теорему с точки зрения вопроса: "А нельзя
ли из этого факта (формулы, теоремы) извлечь что-нибудь полезное для решения
задачи - посчитать, найти, определить?". Потом требуется сформулировать алгоритм
и оценить число выполняемых в нем операций. Для этого в процессе построения
алгоритма приходится решать новые задачи, доказывать теоремы.
Попробуем теперь наш "алгоритм" построения алгоритмов применить
на практике.
На Х-ой Московской математической олимпиаде в 8-ом классе
была такая
Банкир узнал, что среди одинаковых монет одна - фальшивая
(более легкая). Он попросил эксперта определить эту монету с помощью чашечных
весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях
не более двух раз. За какое наименьшее число взвешиваний эксперт всегда может
найти фальшивую?
Это вполне реальная ситуация. Ведь вместо слова "взвешивание"
может стоять слово "сравнение", и может быть, что каждое сравнение
разрушает - пусть даже частично - объекты, которые мы сравниваем. Мы же хотим,
чтобы после работы эксперта мы не только узнали, что фальшивой была, к примеру,
монета с номером 57, но и получили саму эту монету (для нас она может быть бесценна...)