AOP_Tom1 (1021736), страница 176
Текст из файла (страница 176)
Также имеется последовательность операций, когда л кратно 16, которая приводит к заполнению,з и блоков размером 8 на -', а других —,' и блоков — на -'. Если и кратно 128, последовательные запросы на !'Зп блоков размером 8 потребуют больше чем 2.5п ячеек памяти. (Система двойников позволяет нежелательным единицам "переползти" в зп из 8-блоков, поскольку иет других свободных двоек для разделения в критический момент; алгоритм псамого левою" поддерживает все единицы ограниченными.) 42. Можно считать, что ш > 6.
Основная идея заключается в установлении шаблона занятости Н 2(Н„зН1) в начале памяти для й = О, 1, ..., где ВЗ и Е! обозначают л выделенные и свободные блоки размером у. Переход от !с к й+ 1 начинается с Н вЂ” 2(г — ЗВ1) + Вп — 2(г -ЗВ1) В -2Н -2 + Впл-2(4' — ЗВ1) гг -4В -2 -+ Кп-2(Н -ЗК) 'Н К -зКК -2 ! Впс-2(4' и-ЗН!) г!ЗВ -ЗН1 затем коммутационная последовательность Г -зВ1 Г.Н зВ1 ~ Нм-ЗВ1 В и — зВгН ! — ЗЖ -+ гг -4Н2Н -ЗВ! — Л НЗВ -зВ1ВЗВ -ЗВ1 -+ г Нп -зВ1г — ЗВ1 испол! ЗУЕтек Й Раэ До тех пор, пока не будет получено В В -ЗН1(Г~-ЗН1) -+ Ег -зВ1(Г -ЗК) -+ Н 2(г:,'и зН!), И наконец, когда !с становится достаточно большилс, наступает заверз!1 шающая фаза, которая вызывает переполнение, если только размер памяти ие превышает (и — 42л+ 11)(пг — 2).
Детальное описание можно найти в Сошр. 3. 20 (1977), 242-244. [Заметьте, что наихудший из возможных наихудших случаев, который начинается с шаблона Н -!В!У~-!В!У' 1В!..., только немногим хуже этого; к такому шаблону может привести стратегия пследующего подходящего", рассмотренная в упр. 6.) 43. Покажем, что если Р1, Вг, ... представляет собой последовательность чисел, такую, что Р1/т+ Вг/(т+1) 4- + В~/(2сл — 1) > 1 для всех сл > 1, и если С = Р1/1+ Вг/2+ + Р /ш, то слггг(п, сл) < иС . В частности, поскольку 1 1 1 1 1 1 1 > !п2, + + — 1 — -+ -!- — — — + т и!+1 2сл+1 2 22л — 3 2сл — 2 2т — 1 последовательность констант Р = 1/(и 2 удовлетворяет необходимым условиям.
Доказательство осуществляется по индукции по и!. Пусть 1121 = пС для / > 1, и предположим, что некоторый запрос на блок размером пс не может быть удовлетворен в результате выделения в дсм левых ячеек памяти. Тогда сл > 1. Для О <,2 < сл обозначим через 112! крайние справа позиции, выделенные для блоков размерами < у (либо это значение равно О, если 11111111 10101010 11110000 1Ш1111 10101010 10001000 10000000 11111111 10101010 11110000 11110000 10102-2- 10002-00 10000000 00000000 2-2-2-2- 2-110000 11110000 10102-2- 10002-00 10000000 00000000 00000000 00000000 00000000 00000000 4 — -4 —- 4 — -0000 все выделенные блоки больше /).
По индукции имеем и", < Ху. Кроме того, пусть Х' означает крайние справа занятые позиции < Х, так что У' > Ю вЂ” гп -г 1. Тогда интервал (Ж', Ж') содержит как минимум (У(Х,' — Х,',)/(тп+У вЂ” 1)) занятых ячеек, поскольку размеры свободных блоков в нем меньше гп, а размеры его зарезервированных блоков > 21 Отсюда следует, что п — т не меньше числа занятых ячеек, а последнее не меньше Я,, у(Ж' — Ф,',)/(та+/-1) = гпХ,'„/(2яг-1)-(ш — 1) ~,.:,' б/,'/(ш+у)(ш+у — 1) > тМ,„/(2ш-1)-ш — (ш — 1) ~",' дг (1/(ш+у — 1)-1/(гп.~-у)) = ~,, пР,/(т+у — 1) — т > и — тп, что приводит к противоречию. (Здесь доказано несколько больше, чем требовалось.
Если определить Р как Р,/т + + Р /(2т — 1) = 1, то последовательностью См Сг, . будет 1, 1, г з', результат может быть улучшен даже лля ш = 2, как в упр. ЗВ.) 44. ГГ-'(1/1У)1, ГГ-'(2/М)'), ..., ГГ-'(Л/Д')1. ВЕЛИЧИН!я, ЧАСТО ИСПОЛЬЗУЕМЫЕ В СТАНДАРТНЫХ ПОДПРОГРАМЛ4АХ И ПРИ АНАЛИЗЕ КОМПЬЮТЕРНЫХ ПРОГРАММ (45 ВОСЬМЕРИЧНЫХ ЗНАКОВ) Величины, расположенные слева от знака "=", заданы в десятичной систеые счисления е2 7 1п я ф ет ; !4 ып1 сое 1 -С'(2) Л(3) !пф 1/1п ф — 1п!п2 0.1 = 0.01 = 0.001 = 0.0001 = 0.00001 = 0.000001 = 0.0000001 = 0.00000001 = 0.000000001 = 0.0000000001 = т/2 = ,/3 = т/5 = Яо= ~/2 = /3 = с/2 = 1п2= 1пз = !п10 = 1/1п2 = 1/1п 10 = 1' = я/130 = 1/и = 2 ~/я = Г(1/2) = Г(1/3) = Г(2/3) = е =' 1/е = 0.06Э14 63146 3146Я 146Э1 46814 63146 ЯЦ63 Ц631 463!5— 0.00507 584!2 17270 24365 60507 58412 17270 24365 60510— О 00040 61115 64570 65176 76855 44264 16254 02030 44672-Ь О.ООООЭ 21556 1Я580 70414 54512 75!70 88021 15002 85228- 0.00000 24761 32610 70664 Э6041 06077 17401 56068 ЭД1 7— 0.00000 02061 57Э64 05586 66151 55823 07746 Д470 26033+ 0.00000 00153 27745 15274 53644 12741 728!2 20854 02151+ 0,00000 00012 57ЦЗ 56106 04808 47Я74 77841 01512 63827+ 0.00000 00001 04560 27640 46655 12262 7Ц26 40124 2!7424- 0.00000 00000 06676 83766 35367 55658 37265 34642 01627— 1.32404 74681 77167 46220 42627 66115 46725 12575 17435+ 1.56663 65641 80231 25163 5445Я 50265 60861 34078 42223- 2.17067 86384 57722 47602 57471 63003 00563 55620 32021- 8.12Я05 40726 64555 22444 02242 57101 41466 88775 225826 1.20505 05746 15345 05842 10756 65334 25574 22415 03024+ 1 84288 504Д 22175 73184 67868 76133 053Э4 Я1Ц7 60121— 1.
Ц067 74050 61556 12455 72152 ОДЯО 60271 02755 78186+ 0.54271 02775 75071 78682 571! 7 073! 6 Я0007 71 866 53640+ !. 06237 24752 55006 05227 ЗаДО 63065 25012 35574 55837+ 2,23278 06735 52524 25405 56512 66542 56026 46050 50705+ 1.34252 16624 53405 77027 Э5750 Я7766 40644 85175 04858+ 0.88626 75425 !1562 416Ц 52Э25 ЯЭ525 27655 14756 06220- Я.Ы087 55242 10264 80215 ЦЯЗО 63050 56006 70163 21122+ О. 0107Э 72152 11224 72344 25608 54276 63351 22056 11544+ 0.24276 30155 62Я44 20251 23760 47257 50765 !5156 70067- 11.67517 Ц467 62185 71322 25561 15466 Я002! 40654 3410Э- 1.61ЗЯ7 б! 106 64736 65247 47035 40510 15278 ЭД 70 1 7762— 2.58847 85284 51013 б! Э! б 73106 476Д 54653 00!06 66046— 1.2652Э 57112 14154 74Э12 54572 87655 60126 ЯЭЯЯ1 02452+ 2.55760 52!80 50585 5!246 5277Э 42542 00471 72368 61661+ 0.27426 58066 13167 46761 52726 75486 02440 52371 03355+ 7.30714 45615 ЯЯ855 33460 63507 35040 32664 25Я56 50217+ 0.44742 14770 67666 061 72 28215 74Э76 01002 513ГЭ 2552!— 1.11206 40448 47503 86413 65874 52661 52410 87511 460574- 1.47488 57156 2775! 2370! 276Э4 7Ц01 40271 66710 15010+ 1.61772 13452 61152 65761 22477 36558 53827 17554 21260+ 2.14275 81512 16162 52370 35530 11342 5Э525 44307 02171— 0.65665 Я4486 04414 78402 03067 28644 11612 07474 Ц505— 042450 50037 82406 42711 07022 Цббб 27320 70675 12321+ 0 74001 45Ц4 58253 42862 42107 28850 50074 46100 27706+ 1.Ц7Э5 0002Э 60014 20470 15613 42561 31715 10177 06614+ 0.36630 26256 6121Э 01Ц5 1Э700 41004 52264 30700 40646+ 2,04776 60111 171Д 41512 1ЦЯО !6575 00355 43630 40651+ 0.27351 71233 67265 68650 17401 56687 263Ц ЯЦ55 57005— Значения некоторых из приведенных в табл.
1 констант были вычислены с точностью до 40 знаков с помощью обычного калькулятора Джоном В. Ренчем (мл.) (Зппп Ч1. %гепсЬ, Зг.) для первого издания втой книги, Когда в 70-х годах новое программное обеспечение позволило вычислить их на компьютере, оказалось, что значения, полученные Д. Ренчем, правильны. (В ответе к упр. 1.3.3 — 23 приводится значение еще одной фукдаментапьной константы с точностью до 40 знаков.) Таблица 3 ЗНАЧЕНИЯ ГАРМОНИЧЕСКИХ ЧИСЕЛ, ЧИСЕЛ БЕРНУЛЛИ И ЧИСЕЛ ФИБОНАЧЧИ ДЛЯ МАЛЫХ ЗНАЧЕНИЙ и 0 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Н 0 1 3/2 11/б 25/12 137/60 49/20 363/140 761/280 7129/2520 7381/2520 837И/27720 86021/27720 1145993/360360 1171733/360360 1195757/360360 2436559/720720 42142223/12252240 14274301/4084080 275295799/77597520 55835135/15519504 18858053/5173168 19093197/5173168 444316699/118982864 1347822955/356948592 34052522467/8923714800 34395742267/8923714800 312536252003/80313433200 315404588903/80313433200 9227046511387/2329089562800 9304682830147/2329089562800 Н» 1 -1/2 1/6 0 -1/ЗО 0 1/42 0 -1/30 0 5/66 0 -691/2730 0 7/б 0 -3617/510 0 43867/798 0 -174611/330 0 854513/138 0 -236364091/2730 0 8553103/б 0 -23749461029/870 О 8615841276005/14322 г» 0 1 1 2 3 5 В 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 0 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ЗО « /1 1 Пуста для любого х Н, = 42 ~ — — — 1, Тогда ,~п п+х/ «)1 = 2 — 21п2, ь 2 + ь з — + ь 4 Н,/б -+ 6 ь Нь/б и в общем случае, когда Я Н„,= —— р Н1/2 Нг/з Н2/2 Н1/4 Нз/4 Н1/ь Хз/Ь Нз/ь Н4/ь -1я/за — з !п 3, ~ /3 — -!иЗ, 1 21г — 3!п2, -гг — 31п2, 1 фз/25 1/4 $!п5 — 21ь,/51пф, -' ф-'/'5-'/' — -'!и5+ -,'Л!иф, 2 ф-з/25-1/4 ь 1п5+ 1Л!пф, 4 2 фз/25-1/4 ь ! 5 ~ Д! ф зхз/3 — 2!п2 — з!пЗ, -'гг зГЗ вЂ” 2! п 2 — 22 1п 3 0 < р < г/ !см.
упр. 1.2.9 — 19), х р 4 2ри, и — со! — гг — !и 24/ + 2 42 соь — 1г ° 1и згп -гг. 2 9 Ч Ч 1<«<4/2 ПРИЛОЖЕНИЕ Б ОСНОВНЪ|Е ОБОЗНАЧЕНИЯ Буквы в у,й гп, и х,р Р В,Т Раздел Обозначение Значение Присвоить переменной 1г значение выражения Е Значения переменных с' и 1г поменять местами и-й элемент линейного множества А 1.1 1.1 1.1 П еэ 1' А„или А(п) А,„н или А(т,н) Элемент, стоящий в строке гп и столбце и прямо- угольной таблицы (матрицы) А Узел (группа переменных, каждая из которых ха- рактеризуется именем своего поля), адресом ко- торого является Р; предполагается, что Р Ф Л Переменная в ИООЕ(Р) в поле с именем Р Содержимое слова, адрес которого — Р Адрес переменной Ч в компьютере Присвоить указателю Р адрес нового узла Возвратить ИОРЕ(Р) иа хранение; все его поля теряют наименования ИОВЕ(Р) гА 2.1 2.1 2.1 2.2.3 Р (Р) СОИТЕИТЕ(Р) 1.ОС(Ч) Р ~ АЧА1Е Ача1е (= Р 2.2.3 2.2.1 Сор(Е) Х~Е Узел вершины непустого стека Б Взять из Е в Л: присвоить Л +- Сор(8); затем удалить сор(Е) из непустого стека Е Поместить Х в Ес вставить значение Л' в качестве нового входного значения в вершину стека Е Условное выражение: означает Е, если В истин- но, и Е', если В ложно 2.2.1 (В~Е: Е') формулах, если не оговорено дополнительно, имеют следующий смысл.
Арифметическое выражение, принимающее целочисленное значение Арифметическое выражение, принимающее неотрицательное целочисленное значение Арифметическое выражение, принимающее действительное значение Функция, принимающая действительное или комплексное значение Выражение, значение которого — указатель (либо Л, либо адреса компьютера) Множество или мультимножество Строка символов Раздел Обозначение Значение [В[ 1.2.3 1.2.3 1.2.9 1.2.3 1.2.3 1.2.3 шах Дй) Я(lс) 1.2.3 1.2.4 у'~й Я') Т ксо(0, й) 1.2.4 у сх 1.2.3 1.2.2 х" х 1.2.2 1.2.5 х!/(х — й)! = с й>0= и ( -у)) о<о<а 1((. — ) )=" 1.2.5 1.2.5 и! бго [х"[у(х) Ею н) ь) П )(й) н(ь) ппп Дк) я(о) Характеристическая функция условия В: (В~1; 0) Символ Кронекера: [) = к[ Коэффициент при хн в степенном ряду д(х) Сумма всех Д)о), таких, что значение )о — целое и выполняется соотношение В(й) Произведение всех Дй), таких, что значение й— целое и выполняется соотношение го(К) Минимальное значение из всех Дх), таких, что значение Й вЂ” целое и выполняется соотноше- ние В(й) Максимальное значение нз всех 1()о), таких, что значение Й вЂ” целое и выполняетсн соотноше- ние В(й) у делит й: й шоб у' = 0 и у > 0 Разность множеств: (а [ а принадлежит В и а не принадлежит Т) Наибольший общий делитель у и и; ,) = й = 0 ~ 0; шах 4 (==; 1 Уо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
