Принцип «Разделяй и властвуй»

Тимофей: До Удотинска идти ещё минут 40.

Алла: Долго! Я уже устала.

Гоша: А мне всё нравится. Идём, обсуждаем интересные вещи! Я вот уже специалист по рекурсии!

Тимофей: Ну-ка, специалист, что такое «разделяй и властвуй»?

Гоша: Это что-то про Цезаря?

Тимофей: Вообще фраза «разделяй и властвуй!» (лат. Divide et impera!) — девиз внешней политики Древнего Рима. Но авторы того времени на этот счёт ничего не говорили. Поэт Генрих Гейне из Германии приписывает этот девиз македонскому царю Филиппу, отцу Александра Македонского.

Первым правителем, который сказал эту фразу, считают короля Франции Людовика XI. Он произнес: «Разделять, чтобы царствовать».

Этот принцип применяется не только в политике, но и в информатике.

При изучении логарифмов мы рассматривали алгоритм бинарного поиска. С его помощью мы быстро находили слово в словаре.

Когда данные отсортированы, можно выполнить задачу намного быстрее, чем если использовать последовательный поиск. Сначала смотрим слово в середине словаря. Если оно на выбранной странице, поиск окончен. Если в алфавитном порядке слово идёт раньше, выполняем те же действия для левой половины словаря, иначе — для правой половины.

Иными словами, на каждом шаге мы разделяем задачу на подзадачи и работаем с данными меньшего объёма.

Подзадачи должны быть того же типа, что и задача. Только так мы сможем решить их одним и тем же способом.

Алгоритм бинарного поиска — пример стратегии «разделяй и властвуй».

Но есть много других примеров применения этого метода.

Трешландия славится своими великолепными садами. Много специалистов ежедневно трудятся, чтобы растения радовали жителей и гостей страны.

Перед Овощеславом, главным садоводом села Верхние баги, что близ Удотинска, стоит задача разделить земельный участок размером 2400 на 820 на одинаковые части квадратной формы. Причём они должны быть наибольшего из возможных размеров.

Такие варианты не подходят:

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

Овощеслав любитель рекурсивных алгоритмов.

Как известно, рекурсивный алгоритм состоит из определённых шагов.

Овощеслав приступил к поиску решения задачи. Самый простой случай — если длина одной стороны участка кратна длине другой стороны.

Число a кратно числу b, если a можно представить в виде произведения b и с, где с — какое-то другое число.

Например, 8 кратно 4, так как 8 = 4 × 2.

А 9 не кратно 4, ведь нельзя подобрать такое число с, которое при умножении на 4 давало бы 9.

Допустим, ширина участка равна 20 м, а длина — 40 м. Если разделить такой участок пополам, получим две части размером 20 м х 20 м каждая. Это самый большой размер участка из возможных.

Так Овощеслав определил базовый случай алгоритма.

А какой в задаче рекурсивный случай?

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

Как сократить задачу?

Для начала нужно выделить самые большие участки, которые можно использовать.

В исходном садовом участке можно разместить два участка размером 820 х 820. Но ещё останется место размером 820 х 760 м, которое тоже можно разделить.

Чтобы это сделать, Овощеслав применит тот же алгоритм, что и на предыдущем шаге.

Овощеславу нужно разделить участок размером 2400 х 820 на равные квадраты. Решая задачу методом «разделяй и властвуй», он получил меньший сегмент — 820 х 760.

Чтобы понять, что произойдёт дальше, разберёмся с алгоритмом Евклида.

Алгоритм Евклида позволяет найти наибольший общий делитель двух целых чисел. То есть для чисел а и b найти такое максимальное число с, на которое бы делились а и b.

Здесь 6 — НОД чисел 12 и 18.

Ведь именно наибольший делитель сторон садового участка Овощеславу и нужно найти.

Алгоритм Евклида нахождения наибольшего общего делителя (НОД):

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

Остаётся меньший сегмент с размерами 760 х 60 м.

Получится ещё 12 участков размером 60 х 60 м. Останется меньший сегмент: 60 х 40 м.

После очередного отсечения получится квадрат размером 40 х 40 м.

После этого шага Овощеслав получит базовый случай, ведь 40 кратно 20. Если разбить этот сегмент на квадраты 20 х 20 м, ничего лишнего не останется!

Таким образом, для исходного садового участка самый большой размер подучастка равен 20 х 20 м.

Удача, что на предпоследнем шаге получились числа 40 и 20!

Гоша: Я прямо сейчас мог бы написать рекурсивную функцию нахождения НОД. Тимофей: Расскажи идею.

Гоша: Ну, взять 2 числа, вычислить их НОД, вернуть его. Вот алгоритм.

Тимофей: Эффективный и очень краткий алгоритм у тебя получился.

У нас есть два числа. Допустим, a и b. Так как мы реализуем рекурсивную функцию, определимся с базовым случаем.

Гоша: Подожди с базовым случаем. А разве не нужно выбрать из чисел максимальное, чтобы поставить его на первое место? Нам же, насколько я понял, нужно поделить первое на второе и вычислить остаток.

Тимофей: Так что менять местами числа нет необходимости. Вернёмся к алгоритму.

Алла: А давайте, может, как-нибудь потом? Смотрите, какие красивые цветы. Нужно собрать букет.

Гоша: Я как раз хочу сам написать решение, так что да, не рассказывай.

Алла: Интересно, сколько можно собрать оригинальных букетов из трёх цветков, чтобы в нём все цветы были разные?

Применим формулу вычисления количества сочетаний из n по k.

В комбинаторике сочетанием из n по k называют набор, состоящий из k элементов, которые выбраны из данного множества, если всего в множестве n различных элементов.

Подставим в формулу 10 вместо n и 3 вместо k, получим 120.

Пока Алла выбирала, из чего собрать букет, цветы одного вида закончились.

Теперь решите задачи L и M: https://contest.yandex.ru/contest/18359/problems/L/.