Структуры данных и алгоритмы (1021739), страница 72
Текст из файла (страница 72)
Один из вариантов метода декомпозиции применительно к умножению целых чисел заключается в разбиении каждого изчисел X и Y на два целых числа по га/2 битов в каждом, как показано на рис. 10.2.(Для простоты в данном случае предполагается, что га является бтепенью числа 2.)JY:=X = А2"/2 + ВY = С2п/г + DРис. 10.2. Разбиение п-битовых целых чисел на п/2-битовые составляющие1Чтобы прояснить идею алгоритма, опишем еще один шаг решения головоломки. После тогокак п - 1 дисков перемещены на стержень С, а наибольший диск помещен на стержень В, п - 2наименьших диска со стержня С перемещаются на стержень А и (л — 1)-й диск переносится надиск2 В. Далее решается задача с п - 2 дисками, находящимися на диске А.
— Прим. ред.В случае "Ханойских башен" алгоритм декомпозиции на самом деле ничем не отличаетсяот того алгоритма, который был описан вначале.10.1. АЛГОРИТМЫ "РАЗДЕЛЯЙ И ВЛАСТВУЙ"277Теперь произведение чисел X и Y можно записать в видеXY = АС2" + (AD + ВС)2"'2 + BD .(10.1)Если будем вычислять произведение XY этим способом, нам придется выполнитьчетыре умножения (л/2)-битовых целых чисел (AC, AD, ЕС и BD), три сложения целых чисел, содержащих не более 2л битов, и два сдвига (умножение на 2" и 2Л/2).Поскольку сложения и сдвиги требуют О(п) шагов, можно составить следующее рекуррентное соотношение для Т(п) — общего количества операций с битами, требующегося для умножения л-битных целых чисел по формуле (10.1):=1,Т(п) = 4Т(п / 2) + сп .(10.2)Используя рассуждения, подобные приведенным в примере 9.4, можно обосноватьв (10.2) значение константы с, равное 1.
Тогда управляющая функция d(n) просторавняется п, и однородное и частное решения имеют порядок О(л ).Если формула (10.1) используется для умножения целых чисел, асимптотическаяэффективность будет, таким образом, не больше, чем при использовании метода, которому обучают в средней школе. Не следует, однако, забывать, что для уравненийтипа (10.2) мы получаем асимптотическое улучшение в случае, если сокращается количество подзадач. Рассмотрим другую формулу для умножения чисел X и У:XT = AC2" + [(А - B)(D - С) + АС + BD]2"'2 + BD .(10.3)Несмотря на то что формула (10.3) выглядит сложнее, чем (10.1), она требуетлишь трех умножений (л/2)-битовых целых чисел (AC, BD и (A-B)(D-C)), шестисложений или вычитаний и двух сдвигов.
Поскольку все эти операции, кроме умножений, выполняются за О(л) шагов, время Т(п) для умножения л-битовых целых чисел в соответствии с (10.3) задается соотношениямиТ(1) = 1 ,Г(л) = ЗГ(л/2) + сл.Их решением является Т(п) = О(п]°"3) = Ofa1'59) .В листинге 10.3 приведен полный код алгоритма, предусматривающий умножение как отрицательных, так и положительных целых чисел.
Обратите внимание, чтостроки (8) - (11) выполняются путем копирования битов, а умножение на 2" и 2Л/2 встроке (16) — путем сдвига. Отметим также, что в строке (16) результату придаетсянужный знак.Листинг 10.1 . Алгоритмумножения целых чисел методом декомпозицииЯ': . ,vг' . я & ..•.-•", •• .
; , . .,.".. П ,*.чй;, ••:••. ^• .•;.: function mult ( X, Y, n: integer ) : integer;{ X и Y — целые числа со знаком < 2". л — степень числа 2.Функция возвращает значение произведения XY }var(1)(2)(3)(4)(5)(6)s: integer; { содержит знак произведения XY }ml, m2, m3: integer; { содержат три произведения }А, В, С, D: integer; {содержат левые и правые половины X и Y)begins:= sign(X) * sign(y);X:= abs(X);Y: = abs(Y); { теперь Хи Y— положительные числа }if л = 1 thenif (X = 1) and (Y = 1) thenreturn (s)else)278ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВ(7)return (0)else begin(8)A:= левые п/2 биты числа Х;(9)(10)B:= правые п/2 биты числа X;С:= левые л/2 биты числа Y;(11)(13)(14)(15)D:= правые л/2 биты числа У;ml:- mult(А, С, п/2);л2:= mult(A-B, D-C, п/2);m3: = mult(В, D, п/2);(16)лreturn (s * (лй*2 + (ml + m2 + тЗ) * 2endend; { mult }П/2+ тЗ) )Обратите внимание, что алгоритм, разработанный по методу декомпозиции(листинг 10.1), оказывается асимптотически быстрее, чем метод, которому.обучают в1-5в2средней школе (требует только О(п ) шагов вместо О(п )).
Таким образом, возникает закономерный вопрос: если этот алгоритм настолько лучше, почему именно его неизучают в средней школе? На этот вопрос можно дать два ответа. Прежде всего, этоталгоритм удобен для реализации на компьютере; если бы мы попытались излагатьего в средней школе, учащиеся так и не научились бы умножать целые числа. Болеетого, мы игнорировали константы пропорциональности.
В то время как процедураmult асимптотически превосходит обычный метод, константы таковы, что в случаенебольших задач (реально — до 500 бит) метод, излагаемый в средней школе, оказывается лучше.Составление графика проведения теннисного турнираМетод декомпозиции получил широкое применение не только при разработкеалгоритмов, но и в проектировании электронных схем, построении математическихдоказательств и в других сферах. В качестве иллюстрации приведем лишь одинпример. Рассмотрим составление расписания проведения теннисного турнира покруговой схеме для п = 2* игроков. Каждый игрок должен сыграть со всеми другими игроками, при этом каждый игрок должен играть по одному матчу в день втечение п — 1 дней — минимального количества дней, необходимых для проведения всего турнира.Расписание проведения турнира, таким образом, представляет собой таблицу, состоящую из л строк и п — 1 столбцов; элементом на пересечении строки i и столбца jявляется номер игрока, с которым игрок i должен провести матч в у'-й день.Метод декомпозиции позволяет составить расписание для половины игроков.
Эторасписание составляется на основе рекурсивного применения данного алгоритма дляполовины этой половины игроков и т.д. Когда количество игроков будет сокращенодо двух, возникнет "базовая ситуация", в которой мы просто устанавливаем порядокпроведения встреч между ними.Допустим, в турнире участвуют восемь игроков. Расписание для игроков 1 - 4 заполняет верхний левый угол (4 строкихЗ столбца) составляемого расписания.
Нижний левый угол (4 строкихЗ столбца) этого расписания должен свести между собойигроков с более высокими номерами (5 - 8). Эта часть расписания получается путемприбавления числа 4 к каждому элементу в верхнем левом углу.Итак, нам удалось упростить задачу. Теперь остается свести между собой игроковс низкими и более высокими номерами.
Сделать это нетрудно: надо на 4-й день свести в пары игроков, имеющих номера 1 - 4, с игроками 5 - 8 соответственно, а в последующие дни просто циклически переставлять номера 5 - 8. Этот процесс показанна рис. 10.3. Надеемся, теперь читатель сможет обобщить описанный алгоритм и составить расписание для 2* игроков при любом значении k.10.1. АЛГОРИТМЫ "РАЗДЕЛЯЙ И ВЛАСТВУЙ"2791- 03456781 2 3 4 5 6 721436587341278564321876556781234678541237856341285672341Рис. 10.3.
Организация кругового турнира для восьми игроковБаланс подзадачПри проектировании алгоритмов приходится идти на различные компромиссы. Очевидно, что по мере возможности необходимо сбалансировать вычислительные затраты на выполнение различных частей алгоритма. Например, в главе 5 было показано, что 2-3 дерево позволяет сбалансировать затраты на поискэлементов с затратами на их вставку, в то время как более прямолинейные методы требуют выполнения О(п) шагов как для каждого поиска, так и для каждойвставки (несмотря на то что другие операции можно выполнить за постоянноечисло шагов).Аналогично, при использовании алгоритмов декомпозиции желательно, чтобыподзадачи были примерно одинакового размера.
Например, сортировку вставками можно рассматривать как разбиение задачи на две подзадачи — одна размером 1, а другая — п - 1, причем максимальные затраты на выполнение слиянияравняются п шагам. В результате приходим к рекуррентному соотношениюТ(п) = Т(\) + Т(п - 1) + п , которое имеет решение О(л2). В то же время сортировкаслиянием разбивает задачу на две подзадачи, каждая размером л/2, а ее эффективность равняется О(п logn). Складывается впечатление, что разбиение задачина равные (или примерно равные) подзадачи является важным фактором обеспечения высокой эффективности алгоритмов.10.2. Динамическое программированиеНередко не удается разбить задачу на небольшое число подзадач, объединениерешений которых позволяет получить решение исходной задачи. В таких случаяхмы можем попытаться разделить задачу на столько подзадач, сколько необходимо,затем каждую подзадачу разделить на еще более мелкие подзадачи и т.д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
