В.А.Петров, С.Н. Поздняков
В № 33/99 мы опубликовали объявление о приеме школьников в Заочную школу современного программирования, которую организует журнал “Компьютерные инструменты в образовании”. Надеемся, что материалы этой школы, которые мы планируем публиковать, будут интересны и нашим читателям.
С
первого класса учителя “программируют” своих
учеников на выполнение алгоритмов с целыми
числами. Сначала это алгоритмы “поразрядного”
сложения и вычитания, потом алгоритмы умножения
“столбиком” и деления “уголком”, потом
алгоритмы перевода дробей в десятичную запись и
обратно. (Были даже времена, когда ученики
выполняли алгоритм извлечения квадратного
корня.)
Алгоритмы, которые люди знают с детства, вполне удовлетворяют их при решении бытовых задач, например, определения стоимости покупки или подсчета квартплаты. В то же время вряд ли человек справится с делением 100-значного числа на 50-значное: не очевидно также, что привычный способ записи чисел является лучшим для всех возникающих задач. Тем не менее знания вышеперечисленных алгоритмов уже достаточно, чтобы объяснить несколько важных идей компьютерной математики, которые используются при программировании операций с целыми числами.
ДЕЛИМОСТЬРаспространенной задачей является такая: определить, делится ли одно число на другое без остатка. Например, делим число 73 963 на 1999. Применяем алгоритм деления “уголком”:
Получаем частное 37 и остаток 0. Делаем заключение о делимости. Если требуется проверка результата, то умножаем частное 37 на делитель 1999 (используя алгоритм умножения “столбиком”) и убеждаемся, что результат равен делимому 73 963.
Теперь
нетрудно понять, почему делимость определяется
через операцию умножения.
Определение. Говорят, что число а делится на число b (или что а кратно b), если можно подобрать такое число с, чтобы выполнялось равенство а = bс (а, b, с — целые, b № 0).
Одна из часто встречающихся задач состоит в том, чтобы узнать, имеет ли данный набор чисел общий делитель, отличный от 1 (как говорят, нетривиальный делитель, так как 1 является делителем любого набора чисел). Числа, которые не имеют нетривиального общего делителя, называются взаимно простыми.
Обычно
сразу ищут наибольший общий делитель (НОД),
который делится на все остальные делители и,
таким образом, содержит их “в себе”.
Например, набор чисел 72, 84, 132, 144 имеет общие делители 2, 3, 4, 6, 12. Наибольший общий делитель равен 12 (пишется НОД=12). Он делится на все общие делители.
Некоторые из вас скажут: “Мы решали
эту задачу в школе, мы знаем, что делать: нужно
разложить каждое из чисел на простые
множители”. Но
представьте, что число достаточно большое, ну
хотя бы больше миллиарда, тогда для разложения
его на простые множители вам понадобится таблица
первых сотен или тысяч простых чисел, а
построение этой таблицы — задача более
трудоемкая, чем исходная.
Мы познакомим вас с очень простым и эффективным методом нахождения наибольшего общего делителя.
АЛГОРИТМ ЕВКЛИДА С ВЫЧИТАНИЕМ
Идея метода проста. Из набора выбираются любые два ненулевых числа, и большее из них (или любое, если числа равны) заменяется разностью этих чисел. Этот процесс повторяется до тех пор, пока не останется одно ненулевое число. Это число и будет наибольшим общим делителем исходного набора, состоящего из натуральных чисел.
В таблице 1 как пример представлен протокол работы одного из возможных алгоритмов, основанных на методе вычитания, для чисел 72, 84, 132, 144.
Замечание.
Когда мы употребляем слово “алгоритм”, мы
подразумеваем, что все выполняемые операции
определяются однозначно и для любых допустимых
входных данных за конечное время порождается
результат (выходные данные). Интересно, что,
формулируя метод вычитаний, можно было бы
сказать “выберем два случайных положительных
числа набора”, и тогда благодаря наличию
датчиков псевдослучайных чисел в программном
обеспечении компьютера метод вычитаний
превращается в алгоритм.
Номер шага |
1-е число | 2-е число | 3-е число | 4-е число | Сумма чисел |
Шаг 1 |
72 | 84 | 132 | 144 | 432 |
| Шаг 2 | 72 | 84 | 60 | 144 | 360 |
| Шаг 3 | 72 | 12 | 60 | 144 | 288 |
| Шаг 4 | 72 | 12 | 60 | 132 | 276 |
| Шаг 5 | 72 | 12 | 60 | 72 | 216 |
| Шаг 6 | 72 | 12 | 60 | 0 | 144 |
| Шаг 7 | 12 | 12 | 60 | 0 | 84 |
| Шаг 8 | 12 | 0 | 60 | 0 | 72 |
| Шаг 9 | 12 | 0 | 48 | 0 | 60 |
| Шаг 10 | 12 | 0 | 36 | 0 | 48 |
| Шаг 11 | 12 | 0 | 24 | 0 | 36 |
| Шаг 12 | 12 | 0 | 12 | 0 | 24 |
| Шаг 13 | 12 | 0 | 0 | 0 | 12 |
Выбирая для вычитания различные пары, можно получить разные алгоритмы. Все эти алгоритмы будут решать поставленную задачу. Для того чтобы в этом убедиться, необходимо обосновать корректность алгоритмов, то есть доказать, что каждый такой алгоритм обязательно закончит свою работу, что полученный в результате работы алгоритма набор будет содержать только одно ненулевое число и что это число будет наибольшим общим делителем исходного набора.
Обоснование корректности алгоритма — очень важный этап для программирования.
Доказать корректность изложенного метода несложно.
Доказательство
1 и а2 делятся на b, то и их разность делится на b.1. Для доказательства заметим, что если числа а
Следовательно, указанная операция над набором чисел сохраняет общие делители набора. Аналогично можно доказать, что эта операция не добавляет новых общих делителей. Мы доказали, что на каждом шаге алгоритма множество общих делителей не меняется.
2. Далее заметим, что при указанных преобразованиях числа набора остаются неотрицательными. Действительно, вычитая из положительного числа меньшее (или равное ему), мы получим неотрицательное число. Поэтому операцию вычитания можно осуществлять до тех пор, пока в наборе есть хотя бы два положительных числа.
3. Наконец, процесс изменения набора обязательно закончится, так как после каждого вычитания сумма чисел набора уменьшается. В то же время эта сумма всегда есть положительное целое число, следовательно, процесс не может длиться бесконечно (очевидно, что число шагов не превышает суммы чисел исходного набора).
ДЕЛЕНИЕ С ОСТАТКОМРассмотрим такой алгоритм для двух положительных целых чисел а и b:
ПОКА а — b
і 0Например, для чисел а = 37 и b = 11 результат этого алгоритма а = 4 (последовательные значения a: 37, 26, 15, 4).
Вы наверняка знакомы с другим алгоритмом, дающим такой же результат: алгоритмом деления целых чисел с остатком. Результат работы этого алгоритма можно проверить так: умножить частное на делитель и прибавить остаток. Должно получиться делимое.
Ј r < bУтверждение. Для натуральных а и b (делимого и делителя) единственным образом находятся числа q и r (частное и остаток), обладающие следующими свойствами:
a = bq + r, 0
В популярных языках программирования имеются операции для нахождения частного и остатка от деления целых чисел. Например, в языке Паскаль эти операции записываются так:
q:=a div b, r:=a mod b.
В дальнейшем мы будем использовать
a div b и a mod b для обозначения частного и остатка при делении a на b.Условие 0
Ј r < b говорит о том, что остаток всегда неотрицателен и меньше делителя. При r = 0 получается определение делимости чисел. АЛГОРИТМ ЕВКЛИДА С ДЕЛЕНИЕМРассмотрим снова задачу о нахождении наибольшего общего делителя набора натуральных чисел. Преобразование набора будем осуществлять по новому правилу: возьмем два ненулевых числа из набора и большее из них (или любое в случае равенства) заменим остатком от деления на меньшее. Далее будем действовать так же, как и в методе вычитаний. Оказывается, с помощью этого метода тоже можно получить НОД исходного набора чисел.
Если чисел в наборе два, то альтернативы выбора пар нет. Тогда оба метода (вычитаний и делений с остатком) однозначно определяют все действия, какими бы ни были исходные положительные целые числа, поэтому для набора из двух чисел эти методы являются алгоритмами.
Интересный смысл имеют частные с
0, с1, ..., сn, которые получаются в процессе применения алгоритма Евклида к числам а и b. Они являются членами представления числа a/b в форме так называемой цепной дроби:
| Число 1 | Число 2 | Частное |
| a | b | c0 |
| b | r | c1 |
| ... | ... | ... |
| ... | ... | cn |
Например,
Алгоритм Евклида относится к числу “быстрых” алгоритмов.
На каждом шаге этого алгоритма большее число уменьшается более чем вдвое (например, для чисел {1999; 1000} после первого шага число 1999 будет заменено на 999 (то есть 1999 уменьшится более чем вдвое), если же взять пары {1999; 1001} или {1999, 999}, то после первого шага получим соответственно 998 для первой пары и 1 для второй; как видно, вариации второго числа только уменьшают остаток).
Долгое время алгоритм Евклида был самым
эффективным способом отыскания наибольшего
общего делителя, однако с появлением
электронно-вычислительных машин ситуация
изменилась (алгоритм Евклида, как нетрудно
понять, появился задолго до вычислительных
машин). Учет специфических особенностей
выполнения арифметических операций компьютером
позволил построить более эффективную (для
программной реализации) версию алгоритма
Евклида. Действительно, для оценки трудоемкости
алгоритма правильно не просто считать общее
число операций, но и учитывать время, которое
требуется для выполнения этих операций. Так,
например, операция умножения включает в качестве
промежуточных операций несколько сложений, а
операция деления — несколько умножений и
вычитаний.
В вычислительных машинах реализована так называемая двоичная арифметика (о ней будет рассказано в следующей статье этой серии). В этой арифметике очень легко умножать и делить числа на 2. Это достигается простым сдвигом цифр (в обычной арифметике простым добавлением и удалением нуля осуществляется умножение и деление на 10).
Предлагаем вам проверить и обосновать корректность следующего алгоритма нахождения наибольшего общего делителя, который благодаря своим особенностям допускает более эффективную реализацию на компьютере, нежели описанные выше алгоритмы.
Алгоритм. Пусть а и b — натуральные числа.
ПОЛОЖИТЬ НОД=1;
ПОКА оба числа а и b четные
ДЕЛАТЬ поделить каждое из них на 2
и умножить НОД на 2;
ВСЕ-ПОКА
ПОКА оба числа а и b отличны от нуля
ДЕЛАТЬ
ЕСЛИ одно из чисел a, b четное
ТО поделить его на 2
ИНАЧЕ заменить большее из чисел а, b их разностью;
{Комментарий: в процессе выполнения последнего цикла
одно из чисел а, b обязательно будет нечетным}
ВСЕ-ПОКА
выбрать из получившихся чисел а, b ненулевое и домножить на него НОД
В ряде задач бывает нужно представить некоторое целое число в виде суммы чисел, кратных заданным. Понятно, что для решения этой задачи необходимо, чтобы это число делилось на наибольший общий делитель заданных чисел (так как каждое слагаемое такого представления делится на него). Оказывается, это условие является также и достаточным, то есть любое число, делящееся на наибольший общий делитель, можно представить в таком виде!
Утверждение. Наибольший общий делитель набора чисел можно представить в виде суммы чисел, кратных числам набора.
Алгоритм Евклида (использующий деление с остатком) позволяет явным образом найти это представление. А именно, каждый раз при замене числа а на его остаток по модулю b нужно записать равенство r = a — bq. В конце мы получим такое равенство для наибольшего общего делителя. А теперь только осталось подставить эти равенства друг в друга, начиная с последнего!
Пример нахождения такого представления для чисел 30, 42 и 280 показан в таблице 2. Наибольший общий делитель набора чисел, равный 2, представлен в виде суммы чисел 30•1 + 280•(–1) + 42•6, кратных числам набора 30, 280, 42 соответственно.
| Номер шага | 1-е число | 2-у число | 3-е число | Соотношение |
| Шаг 1 | 30 | 42 | 280 | |
| Шаг 2 | 30 | 42 | 28 | 28=280-42*6 |
| Шаг 3 | 2 | 42 | 28 | 2=30-28*1 |
| Шаг 4 | 2 | 0 | 28 | |
| Шаг 5 | 2 | 0 | 0 | НОД=2 |
В итоге получаем 2 = 30 – 28•1 = 30 – (280 –– 42 • 6)
• 1 = 30 • 1 – 280 • 1 + 42 • 6. АРИФМЕТИКА ОСТАТКОВПредставим себе, что нас интересуют не сами числа, а их остатки от деления на некоторое число т (говорят — “остатки по модулю т”). Такая ситуация встречается довольно часто.
Пример. Игра “в камушки”.
Из кучки камней двое играющих по очереди берут 1, 2 или 3 камня. Проигрывает тот, кто берет последний камень. Как играть второму, чтобы выиграть, если в кучке 17 камней?
Выигрышная стратегия второго игрока:
Второй должен брать всегда столько,
чтобы вместе со своим противником взять 4 камня.
Так как остаток от деления 17 на 4 равен 1,
последний камень достанется первому игроку.
Если нам известны остатки r
1 и r2 чисел а и b по модулю т, то, даже не зная самих чисел, можно определить остатки суммы а + b или произведения аb по модулю т. Для этого надо сложить или перемножить заданные остатки и затем найти остатки от деленияТеперь забудем о самих числах и будем работать только с их остатками от деления на т. Получается замечательная арифметика — в ней всего т чисел:
0, 1, 2, 3, ..., m – 1.
Мы можем построить таблицы сложения и умножения, которых будет достаточно для перемножения любых чисел этой замечательной арифметики. Нам не понадобятся ни алгоритмы “поразрядного” сложения, ни умножения “столбиком”! Такую арифметику мы будем называть модульной, а число т — ее модулем.
Пример таблиц сложения и умножения для m = 5 приведен ниже.
| + | 0 | 1 | 2 | 3 |
4 |
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
| * | 0 | 1 | 2 | 3 |
4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
Особенно интересна модульная арифметика для простого числа р. Так, в ней можно определить деление остатков. А именно, если а и b — остатки по модулю р, b № 0, то существует такой остаток с, что а = bс; естественно его обозначить через а/b. Таким образом, остатки по модулю р “так же хороши”, как и рациональные числа: для них можно определить действия сложения, вычитания, умножения и деления, причем они обладают привычными свойствами (говоря математическим языком, они образуют поле).
Важность модульной арифметики для вычислений определяется следующей теоремой.
Китайская теорема об остатках
Если заданы натуральные попарно взаимно простые числа m1, m2, …, mn и целые числа k1, k2, ..., kn такие, что при любом i 0 Ј ki< mi, то существует единственное число k < m1, m2, ..., mn такое, что для всех i остаток от деления k на тi равен ki.
Смысл этой теоремы в том, что натуральные числа однозначно представляются своими остатками по некоторой системе модулей.
Как говорят в таких случаях, имеет место взаимно-однозначное соответствие между числами, меньшими т1, т2, ..., тn, и наборами их остатков по модулям чисел тi. Если учесть, что это соответствие сохраняется при арифметических действиях, мы получаем мощное средство для быстрых вычислений с большими числами!
На практике в качестве тi обычно берут несколько первых простых чисел.
ЗАДАЧИ
Задача 1
Уровень 1. Рассмотрим алгоритм нахождения НОД, построенный на основе метода вычитаний с таким уточнением: “На каждом шаге алгоритма из наибольшего числа набора вычитается следующее по величине или равное”.
а) Примените этот алгоритм к набору из примера: {72; 84; 132; 144}.
б) Приведите пример набора из четырех различных чисел, для которого этот алгоритм является лучшим из всех алгоритмов, основанных на методе вычитаний.
в) Приведите пример набора из четырех различных чисел, для которого этот алгоритм не является лучшим.
Задача 2
Предложите алгоритм выбора пар для вычитания, обеспечивающий возможно меньшее число шагов в обсуждаемом методе нахождения НОД.
Уровень 1. Опишите алгоритм. Продемонстрируйте его работу для набора чисел из пункта в задачи 1.
Уровень 2. Напишите программу, которая по заданному набору из n чисел определяет последовательность выбора пар, приводящую к результату за возможно меньшее число шагов.
Формат ввода:
Количество чисел n Ј 10
1-е число набора
2-е число набора
...
n-е число набора
Формат вывода:
Количество операций т
Номер 1-го уменьшаемого Номер 1-го вычитаемого
Номер 2-го уменьшаемого Номер 2-го вычитаемого
...
Номер m-го уменьшаемого Номер m-гo
вычитаемого
Пример:
| Ввод | Вывод |
| 3 | 5 |
| 10 | 1 3 |
| 6 | 1 2 |
| 4 | 2 3 |
Задача 3
Уровень 1. Ваш знакомый живет в стандартном двенадцатиэтажном доме в квартире 87. На каком этаже может располагаться его квартира? (На лестничной площадке одно и то же число квартир.) Вообще, как быстро определить, может ли квартира с данным номером находиться на данном этаже?
Задача 4
Уровень 1. Язык племени
мумбу-юмбу состоит из шестибуквенных слов,
составленных из букв {А, Б, В, Г, Д, Е, Ж, З, И, К}. В
Оксфорде 
издан
полный словарь слов этого языка (упорядоченных
по алфавиту):
АААААА,
АААААБ,
АААААВ
…
КККККИ,
КККККК.
На каждой странице словаря помещается 15 слов.
На каких страницах и в каких строках находятся слова ДЕКАДА и ЗАБАВА?
Задача 5
Найдите цифру с номером n в последовательности
01234567891011121314151617181920... записанных подряд натуральных чисел.
Уровень 1. Опишите алгоритм. Найдите цифру с номером 1999.
Уровень 2. Напишите программу.
Формат ввода:
Число п < 1 000 000
Формат вывода:
Цифра с номером n
Пример
Ввод: 31
Вывод: 2
Задача 6Для любого натурального числа алгоритм совершает следующие операции: отделяет от числа первую цифру и прибавляет ее к числу из оставшихся цифр. Процесс оканчивается тогда, когда в числе остается одна цифра. Например:
123456
® 23457 ® 3459 ® 462 ® 66 ® 12 ® 3.Уровень 1. Определить результат работы алгоритма для чисел вида при различных значениях n.
Уровень 2. Напишите программу, которая выдает все промежуточные результаты для чисел из не более чем 50 цифр.
Формат ввода:
Количество цифр заданного числа
1-я цифра
2-я цифра
…
п-я цифра.
Формат вывода:
Первый промежуточный результат
Второй промежуточный результат
…
Итоговая цифра.
Известно, что любую дробь , где а и b — натуральные числа, можно представить в виде цепной дроби.
Уровень 1. Опишите алгоритм. Представьте в виде цепной дроби .
Уровень 2. Напишите программу, которая по данным числам a и b представляет дробь в виде цепной дроби (a, b < 1 000 000).
Формат ввода:
Число а
Число b
Формат вывода:
Количество числителей п
Число с0
Число с1
…
Число сn
Пример
Ввод:
5 9Вывод: 3 0 1 1 4
Задача 8Уровень 1. Пусть большее из чисел набора {а, b} равно 1999. Какое максимальное число шагов может сделать алгоритм Евклида с делением для такого набора в худшем случае? Каким при этом будет второе число набора? Приведите пример такого числа. Сколько таких чисел?
Уровень 2. Придумайте алгоритм для нахождения по числу а (а < 1 000 000) всех чисел b, меньших а и таких, для которых алгоритм Евклида делает максимальное число шагов.
Формат ввода:
Число а
Формат вывода:
Число шагов
Количество п различных значений b
1-е значение b
2-е значение b
…
п-е значение b
Уровень 1. Обобщить алгоритм Евклида с делением на 2 и вычитанием для наборов из более чем двух чисел. Применить обобщенный алгоритм к набору {72; 84; 132; 144}.
Уровень 2. Доказать, что если одно из чисел а, b четное, а другое нечетное, то следующее преобразование сохраняет множество общих делителей а и b:
ТО поделить его на 2ЕСЛИ ровно одно из чисел а, b четное
Задача 10
Есть несколько ведер с различными емкостями. Разрешается этими ведрами добавлять или вычерпывать воду из бочки. Сначала бочка пуста.
Уровень 1. Необходимо налить в бочку 1 литр воды, имея в распоряжении ведра емкостью 17, 32 и 45 литров. Как это сделать поскорее (за возможно меньшее количество переливаний)? Сколько при этом будет перелито воды? Можно ли выполнить эту работу, чтобы общее количество перелитой воды было еще меньше?
Уровень 2. Написать программу, которая выдает последовательность действий для наливания в бочку а (a
< 1 000 000) литров воды.Формат ввода:
Число ведер п
Ј 10Формат вывода:
НЕЛЬЗЯ
или
Число операций т
1-я операция
2-я операция
…
m-я операция
Каждая операция представляет собой
+ номер ведра (долить в бочку)
или
— номер ведра (вычерпать из бочки)
Пример
| Ввод | Вывод |
| 2 | 3 |
| 3 | +1 |
| 5 | +1 |
| 1 | -2 |
Уровень 1. Из кучки камней двое играющих по очереди берут 1, 2 или 3 камня. Проигрывает тот, кто берет последний камень. Предположим, что всего камней N. Кто из игроков имеет выигрышную стратегию? Опишите ее. А если выигрывает взявший последний камень?
Задача 12
Уровень
1. Алиса, попав в cтрану чудес, забыла
таблицу умножения. Она говорит: “семью семь
будет ... пятнадцать, девятью девять будет ...
тринадцать”.
Определите, в какой модульной арифметике такие правила умножения справедливы. Сколько всего таких арифметик?
Уровень 2. Напишите программу, которая по введенным примерам таблицы умножения определяет, существует ли модульная арифметика, в которых эти примеры имеют место. Чем больше таких модулей найдет ваша программа и чем быстрее она это сделает, тем лучше.
Формат ввода:
Число равенств п
Ј 10Каждое равенство имеет вид
число1
* число2 = число3Формат вывода:
Число найденных модулей т
1-й модуль
2-й модуль
…
n-й модуль
Пример
| Ввод | Вывод |
| 1 | 2 |
| 3*5 | 6 |
| 12 |
По заданным остаткам а, b по простому модулю р найти а/b (в решении этой задачи пригодится представление наибольшего общего делителя суммой чисел, кратных числам набора).
Уровень 1. Опишите алгоритм. Найдите 17/23 по модулю 239.
Уровень 2. Напишите программу вычисления частного а/b (а, b, р < 1 000 000).
Формат ввода:
Модуль р
Число а
Число b
Формат вывода:
Число a/b (по модулю p)
Пример
| Ввод: | Вывод: |
| 5 | 4 |
| 2 | |
| 3 | |
| 4 |
Уровень 2. Напишите программу, которая по заданным не более чем 25-значным числам а, b, с и d проверяет, верно ли, что ab = cd.
Указание. Проверьте равенство для остатков от деления чисел а, b, с и d на все простые числа до 100. (Так как произведение всех простых чисел до 100 более чем 25-значное, по китайской теореме об остатках этого достаточно, чтобы обосновать исходное утверждение.)
Формат ввода:
Число а
Число b
Число с
Число d
Формат вывода:
Да или Нет
Пример
Ввод:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 0
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
2 4 6 8 2 4 6 8 2 4 6 8 2 4 6 8 2 4 6 8 2 4 6 8
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 0
Вывод:
Да
ЖЕЛАЕМ УСПЕХОВ В РЕШЕНИИ ЗАДАЧ!