Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 94
Текст из файла (страница 94)
Когда лифт пуст, мы всегда имеем нэ = 4, ~ ври 1 < й < и, поскольку на каждом этюке находится В человек. Количество людей, направлякнцихся с этажей (1,..., к) на этажи (8+1,..., и), должно быть равно числу людей, стремящихся переехать в обратном направлении. По определению и„= йг = О. Ясно, что лифт должен сделать, по крайней мере, (иэ/т) рейсов с этажа й на этаж й + 1 при 1 < й < и, так как только т пассажиров могут подняться за один рейс. Аналогично он должен сделать не менее (4,/т) рейсов с этажа й на этаж к — 1. Следовательно, лифту потребуется, по крайней мере, ~~~„Цнэ/т) + Гйэ/т) ) э=1 единиц времени при любом правильном графике работы.
Карп обнаружил, что эта нижняя граница действительно достижима, если им..., и„~ ненулевые. Теорема К..Если нь > О прн 1 < й < и, то существует график работы лнфэв, при котором все люди доставляются иа свои этажи за минимальное время (5). Докаэательстео. Предположим, что в здании имеется дополнительно т человек. Изначально они находятся в лифте, и этаж их назначения искусственно полагается нулевым. Лифт может функционировать в соответствии со следующим алгоритмом, начиная с я (текущий этаж), равного 1. К1. (Движение вверх.) Из 6+т людей, которые находятся в данный момент в лифте и на этаже Й, только т человек„стремящихся на самый высокий этаж, попадает в лифт. Остальные остаются на этаже к.
Пусть теперь в лифте находится и человек, стремящихся на этажи > й, и и' — на этажи < й. (Если иь < т, окажется, что и = гпш(т, нь). Следовательно, можно увозить некоторых людей от их места назначения. Это — их жертва во имя общей пользы.) уменьшить иь на и, увеличить бььг на б н затем увеличить й на 1. К2. (Продолжить движение вверх?) Если пв > О, вернуться к шагу К1.
КЗ. ~Движение вниз,) Из Ь+ гп людей, находящихся в данный момент в лифте или на этаже Ь, только га человек, стремящихся на самый низкий этаж, попадает в лифт. Остальные остаются на этаже /с. Пусть теперь в лифте находится н человек, стремящихся на этажи > Й, и д — на этажи < Ь. (Всегда оказывается, что и = О, а д = т, но алгоритм описывается здесь применительно к произвольным и и /1, чтобы сделать доказательство несколько прозрачнее.) Уменьшить /11 на /1, увеличить ив 1 на н и затем уменыпить Ь на 1.
К4. (Продолжить движение вниз?1 Если Ь > 1 и ив 1 > О, вернуться к шагу КЗ. Если Ь = 1 и и/ = О, закончить выполнение алгоритма (все люди доставлены на свои этажи, а т "дополнительных" человек снова находятся в лифте). В противном случае вернуться к шагу К2. На рис. ЗВ шжазан пример выполнения этого алгоритма для здания с девятью зтажамн, Ь = 2 и ш = 3. Заметим„что один из тех, кто стремится на шестой этаж, временно отдаляется от своего места назначения, несмотря на то что лифт проходит максимально близко к этому этажу.
Идея проверки ив / на шаге К4 является, как мы увидим, решающим моментом для правильной работы алгоритма. 9: — 6 — "— ~99 899 458 9 9: — — ~~6-6,~6 — — ~~6 899 245 778 577 Этюк 7: — 19 — — ~18 — +58 — /кбб-+77 889 124 677 556 Этаж 69 — 24 — — +24 — Ч-44 — +44 — /т 5б 7гбб 889 122 677 445 456 455 9 6: 99 1П =~6 ~~6 ~%696 778 122 266 244 9 667 122 Этаж 3: — 13 — +13 23 — 7ГЗЗ 667 112 123 122 Этаж 2: — 67 — +03— 01-З7 22— 036 011 Этаж 1: — 36 — 76-00- 11 ООО 000 l Начало Конец Рнс.
88. Оптимальный способ перераспределения людей прн поможи неболыпого медленного лифта, (Каждый человек представлен номером этажа, на который он направляется.) при 1 <1< и; при 1 < 1 < /с; если и/ = О и л < 1 < и. (б) (7) (8) и/ = 4+1 и/ = /1/+1 — /п н/+1 = О, Чтобы проверить правильность этого алгоритма, заметим, что па шагах К1 и КЗ всегда поддерживается соответствие данных в массивах н н /1 в (4) текущему состоянию, если считать людей в лифте находящимися на текущем этаже к. Теперь можно доказать по индукции, что в начале каждого шага справедливы следующие соотношения между параметрами: Кроме того, в начале шага К1 в лифте или на этаже й находится ппп (иы ш) человек, стремящихся на самые высокие этажи, среди всех людей на этажах < Й, которые хотят попасть на этажи > й.
В начале шага КЗ в лифте или на этаже й находится ппп (д», т) человек, стремящихся попасть на самые низкие этажи, среди всех людей на этажах > к, направляющихся на этажи < Й. Эти условия также можно проверить по индукции, если проследить, как мы попадаем на шаг К1 или КЗ (см. упр. 5). Из сказанного выше следует, что замечания в скобках на шагах К1 и КЗ справедливы. После каждого выполнения гнала К1, следовательно, [нь/пл) уменьшается на 1 и [с(ьлл /го~[ остается без изменений. После каждого выполнения шага КЗ [оь/ил [ уменьшается на 1 и [иа л/гл) остается неизменным.
Значит, алгоритм должен завершиться за конечное число шагов, и после этого в силу (б) и (8) каждый человек должен оказаться на своем этаже. $ Если иа = О., а иь л > О. мы имеем "несвязную" ситуацию; лифт должен подняться до этажа к+ 1, чтобы переместить людей вверх, хотя никому не нужно переезжать с этажей < )г на этажи > й+1. Не поступаясь общностью, можно считать и„-л > О. Тогда любой правильный график должен включать по крайней мере 2 л шах(1, [еа/тп[) !<л<н движений, так как мы требуем, чтобы лифт вернулся на первый этаж, График, для которого достигается эта нижняя граница, несложно построить (см. упр.
4). УПРАЖНЕНИЯ 1. [80[ В методе пузырька Р-го порядка. который проанализирован в тексте раздела, используются только прямое чтение и перемотка. Можно лн модифицировать алгоритм твк, чтобы глолучить преимущества от обращногэ чтения? 2. [М86) Найдите явные выражения в замкнутом виде для чисел Хк н 1'л, определенных в (3). [Указании Проанализируйте решение уравнения 5.2.2-(19).) 8. [у8[ Существует ли метод сортировки с двумя лентами, основщлный на сравнении ключей (а не на свойствах, представляющих этн ключи цифр), для которого в нанхзтлщем случае прн сортировке?лг запллсей перемещение лент составляет О(?л'1ой?л?)? [Прн быстрой сортировке это значение достигается в среднем, но не в наихудшем случае; в методе ХенниСтнрнза (гм.
рис. 86) оно равняется 0(Х(1ой?лл)л) [ 4. [Мйй[ В задаче о лифте предположим, что ямеются индексы р и д, причем д > р+ 2., ил > О, и > 0 и аурел — — . = ц л = О. Обьясннте, как составить график, требующий не более (9) единиц времени. 6. [Мйз) Верно лн следующее утверждение? После шага К1 алгоритма теоремы К никто в лифте не стремится попасть нв более низкий этаж, кроме тех, кто остался на этажах < Ь. 6. [МУО) (Р. М. Каро.) Обобщите задачу о лифте (см, рнс, 87) лля случаи, когда на этаже У первоначально находится Ь пассажиров и на этаж,у стремятся попасть Ь' пассажиров при 1 < у < н. Покажите, что существует график работы, рассчитанный на 21 л, лпэх(1, [вь/пл $, [лХл+л /нл) ) еднннп вреллени, причем на этаже у никогда не оказывается одновременно более лвах плах(Ь .
Ь',) пассажиров. [Указанвк Введите, если необходимо, фиктивных людей, чтобы равенство Ь, = Ь', соблюдалось прн всех /ь[ 7. [М4Р) (Р. М. Карп.) Обобцлите задачу из упр. 6, заменив лвнейный путь, который проходит лнфг, сетью дорог, по которым можно ездить на автобусе, при условии, что сеть образует любое сеоЬодное дереки Автобус имеет конечную емкость, .н желательно перевезти пассажиров к нх местам назначения так, чтобы автобус прглпел минимальное расстояние. В.
(Мзл) Пусть в задаче о лифте, рассмотренной в тексте раздела, Ь = 1. Сколько перестановок вз н человек по и этажам дадут в (4) см < 1 прн 1 < Ь < и? (Например, перестановка 3 1 4 Ь 9 2 б 8 7.) 9. (МВЬ) Найдите важную связь межлу мейлер-сортировкоуг, описанной в разделе 8.2.2 (см. рнс. 16). я числами вм иг,, и„в (4) для Ь = 1. 10. (80) Как бы вы сортировали файлы на нескольких бобинах, имея только Лва лентопротяжных устройства? е5.4.9. Диски и барабаны До сих пор ленты рассматривались как единственное средство для внешней сортировки, однако нередко в нашем распоряжении оказываются и другие типы более функционально гибких устройств внешней памяти.
Хотя существует множествз конструкций таких запоминающих устройств большого объема илн запоминающих устройств с прямым доступом, можно выделить следующие общие для них свойства. !) Получить доступ к любой заданной части хранимой информации можно довольно быстро. !!) Блоки данных. содержащие последовательные слова„могут быстро передаваться между внутренней (оперативной) и внешней памятью.
Накопители на магнитной ленте обладают свойством (й). но не (!), поскольку перемотка ленты от одного конца к другому отнимает много времени. Каждое внешнее запоминающее устройство имеет свои особенногтп, которые следует тщательно изучить, прежде чем разрабатывать для него большие программы. Однако технология меняется так быстро, что здесь не удастся сколько-нибудь подробно обсудить все существующие разновидности оборудования. Поэтому мы рассмотрим лишь некоторые типичные внешние запоминающие устройства и на иих проиллюстрируем продуктивные подходы к задаче сортировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
