AOP_Tom1 (1021736), страница 152
Текст из файла (страница 152)
(Такая пара называется инверсией (»птегв»оп); сл». раздел 5.1.1.) Следовательно, количество таких пар и является количеством необходимых перемещений. Теперь представим все п записанных действий и для каждой из ( ) пар (1, й) с» < й подсчитаем количество пар, для которых а» > аы Очевидно, что оно равно (",), т. е. количеству вариантов выбора а, и ал, умноженному на п~ ~, или количеству способов заполнения остальных мест. Значит, общее количество перемещений равно ( )(")и . Для получения среднего количества перемещений, т. е. форл»улы (14), эту величину нужно разделить на пм 10. Используя такой же л»етод подсчета, как в упр, 9, получим (,) ~:;"=-,'(™,)(( + +..)'-(.',+ +..')) с<»<л<п )(1-(р»+" +р-)) 2л2! В данной модели эта величина абсолю»пно нс зависит от относительного расположения списков! (Поразмыслив, можно понять, почему это так: если рассмотреть все возможные перестановки заданной последовательности ас,..., а, можно обнаружить, что общее количество перемещений для всех перестановок зависит только от количества пар различных элементов а ф ал.) 11.
Вычисляя среднее количество перемещений, как и прежде, получим п" (2) ~Х-~ ~(т) о<с< Вс Здесь э представляет » — 1 в обозначениях из предыдущего ответа,а т — количество элементов последовательности ас, аж..., а„которое равно а . Эту формулу можно упрощать с помощью ее производящих функций до тех пор, пока 1 Е (Й вЂ” 1+1)( — й — Й)( 1)" ' >О Существует ли более простой способ решения этой задачи? По-видимому, нет, поскольку производящая функция для заданных и и 1 выглядит так. и — 1 х / х 2п (1 в)з ~, (и 1)в) ' 12.
Если гп = 2Й, среднее значение равно 2, умноженному на -2й С0)2Й+(1)(2Й-1)+ +С )Й+(Й )(Й+1)+ +( Й)2Й. И эта сумма равна (')а '(( ')гу ( ')е)=(")Г ч -' г" '. Аналогичный аргумент можно использовать для т = 2Й+ 1. Ответ в этом случае будет таким: т гп /т — 11 2 2 ( (гп/2)! ' 13. А. Ч Яо доказал, что Егпах(Ймйз) = -т+(2х(1 — 2р)) ~/щ+О(гп О (1обт) ) 2 для больших т при р < -'. (ЯСОЫР 10 (1931), 398-403.) А Ф. П. М. Флажоле расширил этот анализ, в частности показав, что среднее количество асимптотически стремится к от при р = —, где 1 1 т эш(пт/2) соей(пх/2) а = — +8~ 2 из хе эшй пл >1 Более того, при р > — окончательное распределение величины Й~ стремится к равномерно- 1 му при гп -+ оо, так что Е щах(Йы Йе) ж 1гп.
(См. Ъесепге Новее (л Сошр. Бс? 233 (\98б), 325 †3.) 14. Пусть Йз = и/гп + ~/йх,. (Эта идея принадлежит Н. Е де Брейну.) По формуле Стирлинга получим пй и,, шах(Йм..., Й„) 1- =(Ля)' и""( — + щ ( „...,х„)) х ехр (--(т~~+ . +х„)) (~/т) (1+О~ — //, где Й~+. +Й, = гп и значения т равномерно ограничены Их сумма по всем неотрицательным значениям Йы..., Й„, которые удовлетворяют этим условиям., является приближением интеграла Римана. А ее асимптотическое приближение будет равно а (гп/и)+с ~/т+О(1), где а„= (Лт) и"~~ ехр ( — -(х~+ +хэ)) Пхе...Пхь, ./*~ е „=е 2 с = (~/2яя) "и"~~/ шах(хы...,х„)ехр(- — (х,+..
+х„)) г/хе .Ихь, зхг~м +* =е так как »южно показать, что соответствующие суммы находятся в е-окрестности величин а и с для любого е. Известно, что а„= )4 так как соответствующая сумма может быть оценена явно. Интеграл в выражении для с„равен п12, где 1! = / х4ехр (- †(х! + .. + х»)! 4Х2...4х». П 2 2 *, 4--4 =О 2 »4>»2,...,» Сделав подстановку 1 Х! = (У2+'''+У»), Х2 =Х! — У2, ХЗ=Х! — УЗ, ... Х» Х! У и можно найти 1! = 12/и, где 12 = / (Уз+ . +У )ехР( — — ) 4/Уг ..!(У, Г ЯЪ 22...2 >а (-2/ н 4»З = '2(уз + ' ' ' + у ) — (уз + + у») . Теперь из соображений симметрии получим, что интеграл 12 равен умноженному на (и — 1) тому же интегралу, в котором вместо (Уз+ .+У») выполнена подстановка значений Уз.
Следовательно, 12 = (и — 1)1з, где 1з = / (пуз — (Уг + + У„)) ехр( — — ) !/уг 4У Г Ят 22...2 >О ехр~- — ) 4уз !(У». !чэ т „2.„>о 2 Здесь Сэ равно Я, где уз заменены нулями. (Если п = 2, то 1з = 1.) Теперь допустим, что з! = ъ/пу! — (Уз+ . + У»)/(!/2+ ч4й), 3 < 1 < пь Тогда Оо = зз + + 22, и можно вывести, что 12 = 14/и!™2 /2, где зз+ ' +з 1,=/ схр ( — ") !Гзз... с/з» 422,-,2 >О 2 зз+''' ! Х»2 2 г 5 = 4!.
//ехР (- ' " ) 422...!/з„= о»(2/2я) 2 Здесь о» вЂ” это отношение "телесного угла" в (и — 2)-мерном пространстве, натянутом на векторы (и+»/2п, О,...,О) — (1,1,...,1), ..., (0,0,...,и+>/2пн) — (1,1,...,1), к полному телесному углу всего этого пространства. Следовательно, (и — 1),„/и с„= аю 2!/я Получим пз = 1, пз = -', п4 = л ' агсзап 2/2 .304 и 1 3 1 аз = — + — агссап — = .20б.
8 4п !/3 (Хотя решение этой задачи получено для сз (НоЬегС М. Козе)йа, Аппа(з оГ Ма!5. Яса!. 27 (195б), 507 — 512), для более высоких значений и оно, по-видимому, еще не опубликовано.) 18. Нет, если только на очереди не накладываются такие ограничения, при которых для них можно применить примитивный метод на основе правил (4) и (5).
17. Сначала следУет показать, что всегда ВАЗЕ(Яэ < ВАЗЕ(1З!. Затем можно заметить, что каждое переполнение стека ! в последовательности зо(п), которое необязательно является переполнением в последовательности з2(п),происходит тогда, когда стек ! становится больше, чем когда. либо ранее, однако его новый размер не меньше, чем исходный размер, выделенный для стека л в последовательности «1(а).
13. Допустим, что затраты времени на выполнение одной операции вставки равны а плюс 6)Ч + сп, если при этом необходимо выполнить переупаковку памяти, где Ю вЂ” количество занятых ячеек. А затраты на одну операцию удаления равны М. Предположилб что после переупаковки памяти, в результате хоторой )Ч ячеек остаются занятыми и Я = М вЂ” )Ч свободными, для хвждой операции вставки до следующего перераспределения потребуется а+ 6+ 10с+ 10(6+ с)п)Ч/Я = О(1+ па/(1 — а)), где а = )Ч/М. Если р операций вставки и Ч операций удаления происходят до переупаковки палляти, то предполагаемые затраты равны р(а+Ь+10с+10(Ь+с)п?Ч/Я) +дд, тогда как реальные затраты составляют ра+6/Ч'+сп+дй < ра+ РЬ+ 6)Ч+ оп+ Чс(. Они лленьше предполагаемых затрат, потому что р > .1Я/и.
Наше предположение о толь что М > п~ означает, что сб/и+ (6+ с) л«' > ЬЛ( + са. 19. Можно было бы просто уменьшить все индексы на единипу, но приведенное ниже решение выглядит несколько элегантнее. В исходном состоянии Т = Р = Н = О. Протолкнуть Ч в стек Х: если Т = М, то ОЧЕНР1.09; Х[Т) +- Ч; Т +- Т + 1. Вытолкнуть Ч из стека Х: если Т = О, то ОМОЕНН.ОМ; Т +- Т вЂ” 1; Ч «- Х[Т].
Вставить Ч в очередь Х: Х[Н) +- Ч; Н+- (Н+ 1) плоб М; если Н = Р, то ОЧЕНР1.ОЫ. Удалить Ч из очереди Х: если Г = Н, то ОМОЕНРЬОМ; Т +- Х [Р); Р +- (Р+ 1) шоб М. Как и прежде, Т вЂ” это количество элементов е стеке, а (Н-Р) шоб М вЂ” количество элементов в очереди. Но самым верхним элементом стека теперь является Х [Т вЂ” П, а не Х [Т) . Хотя специалистам в теории информатики почти всегда удобнее начинать отсчет с нуля, весь остальной мир вряд ли когда-нибудь перейдет к использованию нуль-индексирования. Что тут говорить, если даже Эдсгер Дейкстра при игре иа фортепиано использует считалку "1 — 2 — 3-4 ) 1 — 2-3-4"! 9Е 3.
ОЕЬЕТЕ БТ) !Р БТЗ 9Р 1.02 «(О:2) 603 0,2 )32 9Р Х01 0.3(61МК) БТ! 0,2 ХОА 0,3(1МРО) 602 АЧА16 БТ2 0,3(61МК) 1Е РАЗДЕЛ 2.2.3 1. Событие ОЧЕНРЬОМ неявно 2. 1МБЕНТ БТЗ 1Р БТ) 9Р Ы! АЧА11. 1!Х ОЧЕНРЬОН 603 0,1(1.1МК) БТЗ АЧА16 БТА 0.,1(1МРО) !Е 603 «(О:2) Е02 0,3 БТ2 О, 1 0 1МК) БТ1 0,3 ЗМР обрабатывается операцией Р ~ АЧА16. Сохранить позицию МОР Т, Сохранить адрес выхода. г11 «'.= АЧА11.. 1МРО(г11) < — Ч.
г[З+- ).ОС(Т). г12 «- Т. 61МК(г11) +- Т. Т «- г11. ! Сохранить позицию МОР Т. Сохранить адрес выхода. г12 «- ЬОС(Т). г13 «- Т. Верно ли, что Т = Л? г11 ~- 61МК(Т). т+- гП. гА +- 1МРО (гП ) . АЧА16 ~ г13. БТЗ АЧА10 Еитз г 9Н ЗМР л,З Приготовиться ко второму выходу. 1 Сохранить значение регистра гд. Сохранить значение гП. Увеличить РООЬИАХ 4.
ОЧЕНРЕОН БТЗ 9Р БТ1 БР(0:2) Ь01 РООЕМАХ БТ1 АЧА1Ь Установить для АЧА11 новый адрес. 1МС1 с БТ1 РООЬМАХ СМР1 БЕОМ1И 30 ТООВАО Не исчерпан ли объем памятиг БТК -с,1(ЫМК) Установить ЫМК(АЧА1Ы»- Л. 9Н ЕИТ1 л Извлечь значение г1. ОЕС1 2 Отнять 2. БТ1 э+2(0»2) Сохранить адрес выхода. 8Н ЕМТ1 л Восстановить г11. 1МР Возврат. А 5. Вставка с начала очереди очень похожа на основную операцию вставки (8) с допол- нительной проверкой опустошения очереди; Р »и АЧА11, 1МРО(Р) +- Ч, ЫМК(Р) » — Р, если Р = Л, то Н +- Р; Р»- Р.
Для удаления элел»ента с конца очереди люжно было бы найти узел, который связан с ИООЕ(Н), но данный метод крайне неэффективен, поскольку потребуется проследить весь путь от Р. Это можно было бы выполнить так, а) Если Р = й, то ОМОЕНРЕОМ, в противном случае установить Р» — ЕОС(Р) . Ь) Если ЫМК(Р) ~ Н, то установить Р +- 1.1МК(Р) и повторять этот этап до тех пор, пока 1.1ИК(Р) станет равным Н. с) Установить Ч+- 1МРО(Н), АЧА10 ~ Н, Н +- Р, 1.1ИК(Р)» — Л. 8. Операцию 1.1МК(Р) +- й можно было бы удалить из (14), если удалить команды Р +- ~1ИК(Р) и "если Р = й, то Н +- АОС(Р)" из (17), а вместо последней из них вставить "если Р = Н, то Р +- Л и Н +- (ОС(Р), в противном случае установить Р +- 11ИК(Р)". В результате таких изменений поле ЫМК конечного узла очереди будет содержать бесполезную информацию, которая никогда не будет использована программой Благодаря подобной уловке можно сократить время выполнения программы, что очень полезно на практике.
Однако при этом нарушаются основные допущения, принятые для сборки мусора (ель раздел 2.3.5), и ее нельзя использовать в таких алгоритмах. 7. (Убедитесзч что в вашем решении учитывается возможность опустошения списка ) 11. Установить Р +- Р1НБТ, 0 +- Л, 12. Если РРЛ, установить Н» — О, О+-Р, Р+-ЫМК(0), ЫМК(0) +-Н и повторить этот шаг. 13.
Установить Р1НБТ < — О. 3 По сути, все узлы сначала удаляются (вытвлкиваются) из одного стека, а затем вставля- ются (проталкиваются) в другой стек. 8. 001 РТНБТ 1 11. Р гв гП +- Р1НБТ. ЕИТ2 0 1 (1 = г12+- Л. 112 2Р 1 12. Если список пуст, выполнить переход. 1Н БИТА 0,2 и Н эв гй» вЂ” О. ЕМТ2 0,1 и О-Р. 101 0,2(ЫМК)»» Р+- 01ИК(0). БТА 0,2(11МК) и ЫМК(0) +- Н. 3192 1В 2Н БТ2 Р1НЯТ п РфЛ? 13. РТННТ г- 9. 1 Время выполнения равно (7п + б)и, но его можно сократить до (5п + сопэгапс)н (см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
