Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2012_2013/8mat_1213/spec/13-bottles-aux.pdf Дата изменения: Sat Feb 9 20:08:39 2013 Дата индексирования: Mon Feb 25 14:26:36 2013 Кодировка: Windows-1251 Поисковые слова: изучение луны

Гимназия 1543, математический спецкурс, 8 В

Постановка задачи
объ?мами сосудов

Занятие 13: переливания двумя в?драми (дополнение)

Вы, наверняка, на математических кружках, уроках информатики или где-то ещ? сталкивались с задачами на переливания. Стандартная задача такого типа устроена очень просто: есть сосуды

a и b литров (a > b > 0, x < a литров.

оба числа целые) и озеро. Требуется отмерить при помощи этих

Такую задачу очень просто решить: надо заполнить большой сосуд, затем выч?рпывать из него воду маленьким сосудом до тех пор, пока можем. Остаток нужно перелить в маленький сосуд, далее наполнить большой до кра?в, долить из него маленький до упора, затем повторить всю вышеописанную последовательность действий. Практика показывает, что рано или поздно мы прид?м к успеху.1 Теория сравнений позволяет просто и элегантно доказать результативность привед?нного алгоритма.

Очевидные соображения
Если

x

не кратно НОД(a,

b)

, то

x

литров получить нельзя. Если же НОД

мерять объ?мы не в литрах, а в ?псевдолитрах? таких, что 1 ?псевдолитр? образом задача сводится к случаю взаимно простых

(a, b) | x есть x

, то можно излитров. Таким

a

и b.

По этой причине далее без ограничения общности считаем

Формализация алгоритма
после

a

и

b

взаимно простыми.

Распишем поэтапно количество воды в сосудах. Пусть

b

n литров находится в маленьком сосуде

n

-й итерации алгоритма; b0

= 0. a + bn - b
литров, в маленьком

1) В большом сосуде

a

литров, в маленьком bn литров.

2) Доливаем маленький сосуд до кра?в. В большом сосуде в маленьком 0 литров.

3) Выч?рпываем маленьким сосудом большой. В большом сосуде станет 4) Переливаем остаток в маленький сосуд. В маленьком теперь bn+1

b (a + bn - b) mod b

литров. литров,

Арифметика остатков спешит на помощь
b0 0; b
n+1

= (a + bn - b) mod b

литров.

Рассмотрим рекуррентное соотношение для bn по модулю b. Получим

bn + a.

bn na. Поскольку a и b взаимно просты, то мы можем получить значение bn из любого класса (номер n нужной итерации будет представителем частного при делении bn на a по модулю b). А так как 0 bn < b, то мы можем получить любое значение bn пут?м нескольких итераций (в целочисленном диапазоне [0, b) есть ровно по одному представителю каждого класса). Осталось заметить, что если x b, то мы его получим в большом сосуде на той же итерации алгоритима, что и bn x - a.
Нетрудно видеть, что

1

Есть также аналогичный алгоритм, заключающийся в наполнении большого сосуда при помощи маленького. Он

тоже работает.