В мартовском номере "КвШ" я предложил вам попробовать доказать известную формулу 12+22+32+42+…+m2=(m(m+1)(2m+1))/6.
Напомню, что в результате долгого путешествия мы оказались лицом к лицу с теми формулами, которые называются в математике рекуррентными.
И вот…
Задача 13.
Напишите программу вычисления числа f(s,k), формула (2) для которого получена в предыдущей задаче. Придумайте несколько алгоритмов вычисления числа f(s,k). Сравните порядки операций и объемы памяти, необходимые для работы этих алгоритмов.
Посмотрим на формулу (2) с точки зрения эффективности алгоритма. Эта формула и рассуждение, которое ей предшествует, позволяют сформулировать следующий алгоритм.
АЛГ(n,k)
Дано: n монет, среди которых одна фальшивая (более легкая), и число k – количество взвешиваний каждой монеты.
Шаг 1. В столбце k определяем число s такое, что f(s-1,k)
Шаг 2. На чаши весов кладем по f(s-1,k-1) монет, а оставшиеся m монет оставляем на столе (формула (2) гарантирует нам, что на столе осталось не более f(s-1,k) монет).
Шаг 3. Если чаши находятся в равновесии, то
m=1, фальшивая монета на столе.
Если m>1, то переходим к АЛГ(m, k).
В случае, когда чаши не в равновесии:
Если в легкой чашке f(s-1,k-1)=1 монет, то эта монета фальшивая.
Если f(s-1,k-1)>1, то переходим к алгоритму АЛГ(f(s-1,k-1),k-1).
Итак, рекуррентная формула дает рекурсивный алгоритм.
Задача 14.
Запрограммируйте АЛГ(n,k). Продумайте интерфейс и "картинки". Например, можно рассмотреть возможность, при которой посторонний "наблюдатель" задает числа n, k и щелчком мыши выбирает фальшивую монету, а "машина" демонстрирует, как она эту монету находит.
Решения задач
Задача 11.
Ответ приведен в табл. 3.
Из таблицы видно, что ответом в задаче А является число 7.
Задача 12.
f(s,3)=(4/3) s3 - 2s2 + (8/3)s +1
А теперь приведем несколько решений задачи 13, ведь ее решение составляет фактически первый шаг алгоритма АЛГ (n,k). Решая предыдущие задачи, мы оценивали число операций в полученных алгоритмах через число взвешиваний. И это вполне естественно, ведь взвешивание в этих алгоритмах – самая трудоемкая операция.
Теперь мы будем рассматривать задачу, связанную с вычислениями. В таких задачах есть два подхода к оценке числа операций. Можно к элементарным операциям отнести любые арифметические операции (например, сложение и умножение – к операциям, одинаковым по сложности), а можно все операции переводить в операции над битами. Мы будем придерживаться первой точки зрения. Кроме того, в начале будем считать, что s намного больше k.
Решение 1 (хакерское). Запрограммируем формулу "в лоб".
Фрагмент рекурсивного алгоритма, вычисляющего f(s,k), выглядит примерно так:
Function F(s: integer; k: integer): integer;
{s>=0,k>=0}
begin
if (s=0) or (k=0) then
begin
F=1;
end
else
begin {s>=1,k>=1}
F:= 2*F(s-1,k-1)+F(s-1,k);
end;
end
Попробуем оценить время работы и объем памяти, необходимый для выполнения программы. Время работы растет экспоненциально (т. е. как функция 2s). Действительно, вычисление F(s,k) сводится к двум вызовам – F(s-1,k-1) и F(s-1,k); вычисление этих двух функций – к четырем вызовам F(s-2,k-2) F(s-1,k-1) F(s-1,k-1) F(s-2,k) затем к восьми и т. д. Заметьте, что уже на втором шаге мы будем дважды вычислять одну и ту же функцию F(s-1,k-1), т. е. проделывать лишнюю работу. То же происходит и с памятью. Если у вас рекурсия запрограммирована с помощью стека, то в стеке отложенных заданий число элементов будет расти экспоненциально, и в стеке будут появляться те же одинаковые элементы. Если вы запрограммировали рекурсию, используя ссылки, то число ссылок растет экспоненциально.
Конечно, если s и k не очень велики, то на современных компьютерах вы даже не заметите, как работает эта программа – нажали на кнопку, и результат уже на экране. Но при больших объемах вычислений это стоит учесть.
Решение 2 (программистское). Посмотрим в нашей таблице, какие значения нужно знать, чтобы вычислить f(s,k). На рис. 1 заштрихован "прямоугольник зависимости", т. е. место, где расположены значения f(x,y), принимающие участие в вычислении f(s,k).
Ясно, что компьютер априори не знает "начальных" значений f(s,0) и f(0,k). Мы можем изменить эти значения, но алгоритм должен работать.
Априори и коэффициенты 2 и 1 в формуле (2) могли бы быть другими. Все это означает, что, используя формулу (2) при построении алгоритма, нам придется хотя бы один раз вычислить каждое значение f(x,y) из "прямоугольника зависимости".
Поэтому можно просто завести массив размера sk и вычислить все его элементы. Эта программа потребует и памяти порядка sk, равно как и время ее работы будет порядка sk.
Задача 15.
Напишите программу, реализующую этот алгоритм.
Эта программа уже не экспоненциальная, а полиномиальная. Ресурсы (память и время), необходимые для ее работы, растут как степень от объема начальных данных (в данном случае – от s и k).
Но если k
… Если вам не надоела эта задача, то попробуйте обобщить ее, рассмотрев, например, не одну фальшивую монету, а две, три и т. д.
Похожую задачу о сортировке железнодорожных составов (тоже традиционная тема задачников для младших школьников) можно найти в статье [1]. Тем из вас, кто действительно заинтересовался алгоритмами, можно посоветовать заглянуть в замечательную книжку [2].
Следующие задачи взяты из [3].
Задачи для обобщения
Задача 1.
Среди 12 монет одна фальшивая, отличная по весу от остальных. Неизвестно, легче она или тяжелее. За три взвешивания найти фальшивую монету и установить, легче она остальных или тяжелее. ([4])
Задача 2.
Дано по паре красных, синих и зеленых гирь, причем в каждой паре одна гиря тяжелее другой. Все тяжелые гири имеют один и тот же вес; все легкие – тоже. Требуется за два взвешивания выделить все тяжелые гири.
Задача 3.
Из четырех монет две – легкие (одного веса) и две – тяжелые (тоже одного веса). За сколько взвешиваний их можно разделить?
Задача 4.
Даны четыре монеты, две одного веса, третья тяжелее, а четвертая - легче первых двух, причем общий вес первой и второй монет равен общему весу третьей и четвертой. Сколько взвешиваний понадобится для того, чтобы выделить тяжелую и легкую монеты?
Литература [1] Кулаков А.Г. Сортировки, числа Фибоначчи, системы счисления и контекстно-свободные грамматики. Квант, № 3, 1997. |