Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 58
Текст из файла (страница 58)
Комплемеитериой системой глроек порцдка о является такое рвзмещевие 2о объектов (хг,...,х„, х!,...,х,) в тройках, при котором каждая пара объектов встречается ровио в одной тройке, за исключением комплементарных пар (хм х;), никогда пе встречающихся вместе. Например, (х! хе хз)! (х! хе хэ)! (й! хмйз)! (й! йэ,хэ) представляет собой комплементарную систему троек третьего порядка. Докажите, что комплемеитариые системы троек порядка о существуют для всех и ) О, ие имеющих вид ЗЬ + 2. 12.
(МОЮ] Продолжая упр. 11, постройте компзементарную систему четоерме порядка 7. 13. [МЙЯ Постройте систему четверок с о = 4" элементами, аналогичную системе троек из упр. 9. 14. (ОВ] Обсудите проблему удаления узлов из четревьев, Ь-б-деревьев и почтовых деревьев, подобных показанному па рис.
45. 16. ]НМОО] (П. Элиас (Р. Ейае).) Дана большая коллекция т-бятовых записей. Предположим, что необходимо найти запись, ближайшую к данному аргументу поиска в том смысле, что согласовано наибольшее количество битов. Разработайте алгоритм эффективиого решения этой задачи в предположении, что задан т-битовый код из 2" элементов, исправляющий Ф ошибок, и что как!дав запись хешируется в один из 2" списков, соответствующих ближайшему кодовому слову. э 1О.
(23] (В. Х. Кац (ет'. Н. Кваса) и Р. К. Сииглтои (Н. С. Рйлй1егол).) Покажите, что Штейнеровская система троек порядка о может использоваться для построения о(и — 1)/б о-битовых кодовых слов, таких, что никакое слово ие содержится в суперпозиции двух других. ь 1Т. (Муу] Рассмотрите следующий путь сведения (2п+1)-битовых ключей а „... ео... а к (и+ 1)-битовому блоку адресов Ьо... Ь„: Ьо +- ао; если Ь!, ! = О, то Ье +-а е, иначе Ье е-ае для 1 < Ь < и. а) Опишите ключи, появляющиеся в блоке Ьо... Ь„.
Ь) Чему равно наибольшее количество блоков, которые необходимо проверить при базовом запросе с Г определенными битами? е 18. (Муб] (Кокструироовмие ассоциотиеиоео блока.) Множество еп-элементных наборов типа (13) с ровно т — и звездочками в каждой из 2 строк пазывается АВП(т, п)е, если в каведом столбце содерлгится одно и то же количество звездочек и если каждая пара строк имеет "несоответствие" (О против 1) в некотором столбце. Каждое т-битовае бинарное число будет в таком случае соответствовать в точности одной строке.
Например, (13) является АВП(4, 3). а) Докажите, что АВП(т,п) невозможно, кроме случаев, когда т является делителем 2" 'и и пе > 2гл(1 — 2 ), Ь) Будем говорить, что строка АВП имеет иечетима варитет, если в вей содержится нечетное количество единиц. Покажите, что для любого выбора т — и столбцов в АВП(т,п) количество строк с нечетным паритетом с "е" в этих столбцах реяло количеству строк с четным паритетом. В частности, каждое возможное расположение символов "*" должно встречаться в четком количестве строк. " От А!его!як!ее,%ось Пемут.
— Прим. верее. с) Найдите АВР(4, 3), которое не может быль получено пз (13) путем перестановки и/или дополнения столбцов. д) Постройте АВР(16, 9). е) Постройте АВР(16, 10). Начните с АВР(16, 9) из п. (4) вместо АВР(8, 5) из (15). 19. (Мйй) Проанализируйте АВР(8,5) нз (15) так же, как (13) было проанализировано в (14).
Сколько из 32 позиций должно быть проверено при запросе с (в неопределенными битами в среднем и в наихудвпем случвях7 20. (М47) Найдите асе АВР(гп, и) при и = 5 или и = 6. Ф Новый раздел 6.6 в следуюшем издании книги планируется посвятить постоянным структурамданных. Этн структуры гюзволяют представить измененную информацию таким образом, что ксторня изменений может быть эффективзю восстановлена.
Иными словами, можно сделать множество вставок и удалений, но, тем не менее, оставаться способнымн выполнить поиск так, как будто обновлений после некоторого данного момента времени вовсе не было. Пока что в настоян!ее издание включены лишь ссылки на литературу по атой теме: ° 1. К. Мп(!т, Сотр. Х. 24 (1981), 367 — 373; ° М. Н. Отегтагв„1есгиге Ховав т Сотр. Яс), 166 (1983), СЪарйег 9; ° Е. %. 5!уетв, АСМ сутр. Рппс!рМв о(Ргоб. Евай. 11 (1984), 6675; ° В. СЪаве!!е, 1п(огтабоп апв! Сопмо! 63 (1985), 77-99; ° Р.
РоЫцп апг! 1. 1. Манго, Х А!йопг!пав 6 (1985), 455-465,' ° В. Со!е, 2. А!8опббтв 7 (1986), 202-220; ° Р. Р!е!д, )п(отта!!оп Ргосевипй ) еагегв 24 (1987), 95-96; ° С. %. Ртавег апб Е. ЪЧ. Муегв, АСМ Тгавв. Ргой. ),апй. апс! оуягетя 9 (1987), 277-295! и,!. В. Рпвсо!!, Н. Вагиза, Р, Р. 8!еа!ог, аад В.
Е. Тат)аа, Х Сотр. Яуж. Зс!. 38 (1989), 86 -124; ° В. В. РаппепЪегб, бойиаге Ргвспсе 4с Ехрепепсе 20 (1990), 109 — 132; ° 1. В, Рпвсо!1, Р. Р. К. 8!еагог, аш! В. Е. Таг)ап,,1АСМ 41 (1994), 943-959, таблицы инструкций (программы) будут создаваться математиками С Опытом вычИСлИтЕлЬНОй работы и, вероятно, с определенными способностями к решению головоломок. Перевод на некоторой стадии каждого известного процесса в бюрму таблиц инструкций, скорее всего, будет значительной частью такой работы.... Процесс построения таблиц инструкций должен очаровывать.
Реальной опасности стать слугой машины нет, ибо любой более или менее механический процесс можно передать самой машине. — АЛАН М. ТЬЮРИНГ (А~ АН М. Тцг!!Нб) (1946) Тпблицп 2 ВЕЛИЧИНЫ, ЧАСТО ИСПОЛЬЗУЕМЫЕ В СТАНДАРТНЫХ ПОДПРОГРАММАХ И ПРИ АНАЛИЗЕ КОМПЬЮТЕРНЫХ ПРОГРАММ (45 ВОСЬМЕРИЧНЫХ ЗНАКОВ) Величины, расположенные слева от знака "=", заданы в десятичной системе счисления О.! = ОЗН = 0.001 = 0.0001 = 0.00001 = 0,000001 = 0.9Ю0001 = 0.00000001 = 0.00000000! ~ 0.0000000001 = Л= ~/з = Л= До= ~12 = Фз= т/2 = !пз ю !пз = !п10 = 1/!из = 1/1п10 = гг = 1' = гг/180 = 1/я = тг ~/т = Г(1/2) = Г(1/3) = Г(2/3) = еы 1/е = г' !и гг ф ез л!4 е!п 1 соя 1 -<'(2) 4'(3) !пф 1/!п ф — !и!п2 0.063Ц 69Цб ЭЦБЭ Ц631 463Ц 69Ц6 Я463 Ц631 46ЯБ- 0.00507 БЯ412 17270 24365 60507 53412 17270 24965 БРИО- 0.00040 БП15 64570 65176 76МБ 44264 16М4 РРОЭО 44672+ О.ООООЭ 21МБ 1МЭО 704Ц 54512 75170 9902! 15002 35223- 0.00000 24761 ЗМ10 70664 М041 06077 17401 56063 34417- 0.00000 02061 57364 05536 661И 55323 07746 44470 26039+ 0.00000 00153 27745 15274 53644 1874! 72Я2 20М4 02!51+ 0.00000 00012 57ЦЯ 56!Об 04ЯОЭ 47974 77941 01512 63327+ 0.00000 00001 04560 87640 46655 12862 7Ц26 40Щ Я 742+ 0.00000 00000 06676 Э3766 М367 556БЗ 3726Б 94642 01627- 1.38404 746Я 77167 46МО 4М27 66115 467М Ь2575 1'ЦЗО+ 1.
56669 65641 302Я 8И6Э 54453 50265 60361 34073 42223- 2.! 7067 36334 577М 47602 57471 69003 00569 М620 32021- 3. 12305 40726 64М5 22444 02242 5710! 4Ц66 93775 22532+ 1.20505 05746 15345 05942 10756 65334 М574 2ММ 09024+ 1.34299 50444 22175 ТЯ34 67Я69 76133 05334 91 Ц'! 601Я— 1.Ц067 74050 61556 Щ55 72152 64430 60271 027М 73136+ 0.54271 02775 75071 7МЭ2 57117 07916 ЯО007 71366 53640+ 1.06М7 24752 550РБ 05227 92440 63065 25012 М574 55937+ 2.29273 067М 53524 М405 56И2 66542 56026 46050 50705+ 13ЦМ8 16624 53405 77027 М750 37766 40644 М! 75 04953+ О.М626 754М П562 416Ц 529М 99525 27655 14756 06220- Э.П097 55242!ОМ4 90215 Ц290 63050 56006 70169 Я122+ 0.01079 72152 ПМ4 72344 М6ОЯ 54276 633И 28056 П544+ 0.24276 30155 62944 20251 23760 47М7 50765 15ЬББ 70067- П.67517 Ц467 бЯМ 71922 МБ61 Щбб 30021 40654,Ц103- 1.61337 б!106 647М 65247 47035 40ИО 15273 3447Р 17762- 2.53947 95294 И013 61 316 73!06 47644 54653 001 06 66046- 1.26529 БЯ12 Ц154 'ЦЭ12 54572 37655 60!26 232Я 02452+ 2.55760 52130 505М БЩб 52773 42548 00471 72363 616И+ 0.2Ц26 БЯО66 1Я67 46761 52726 75496 02440 52371 09955+ 7.307Ц 45615 29955 39460 6М07 М040 38664 МЭ56 5021 7+ ОчЦ742 Ц770 67666 06172 2ЭЖ5 74Я76 01002 ИЯЗ 25521- 1.
П206 40443 47509 964М 65974 БМ61 52410 97511 46057+ 1.47433 57156 27751 23701 27634 7Ц01 40271 66710 15010+ 1-61772 19452 БП52 6576! 22477 96553 59927 17М4 Я260+ 2.Ц275 Я512 16162 52370 М590 П342 5ММ 44Я07 02171- О.М665 24436 044Ц 73402 03067 2ЭбЦ 11612 07474 Ц505- 0.42450 50097 32406 42711 07022 Цббб 27320 70675 12321+ 0.74001 45Ц4 БЭМЗ 42362 42107 23МО 500Ц 46100 27706+ 1Л47М 00023 БООЦ 20470 156М 42561 Я715 10177 066Ц+ 0.96690 26256 61219 ОЩ5 19700 41004 52264 90700 40646+ 2,04776 60П! 17!44 41И2! ЦМ 16575 ООЭМ 49630 406И+ 0.27951 71233 67265 6МБО 17401 56637 26394 Я1455 57005- Несколько интересных констант без общего названия возникли в связи с анализом алгоритмов сортировки и выбора. Этн константы вычислены с 40 десятичными знаками в 5.2.3-(19) и 6.5-(6) и в ответах к унр. 5.2.3-27, 5.2.4-13, 5.2,4-23, 6.2.2-49, 6.2.3-7, 6.2.3-8„6.3-26 и 6.3-27.
ч ЗНАЧЕНИЯ ГАРМОНИЧЕСКИХ ЧИСЕЛ, ЧИСЕЛ БЕРНУЛЛИ И ЧИСЕЛ ФИБСНАЧЧИ ЛЛЯ МАЛЫХ ЗНАЧЕН14й в 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Г7 18 19 20 21 22 23 24 25 26 27 28 29 ЗО Н„ 0 1 3/2 11/6 25/12 137/60 49/20 363/140 761/280 7129/2520 7381/2520 83711/27720 86021/27720 1145993/360360 1171733/360360 1195757/360360 2436559/720720 42142223/12252240 14274301/4084080 275295799/77597520 55835135/15519504 18858053/5173168 19093197/5173168 4443!6699/118982864 1347822955/356948592 34052522467/8923714800 34395742267/8923714800 312536252003/80313433200 315404588903/80313433200 9227046511387/2329089562800 9304682830147/2329089562800 Вв 1 -1/2 1/6 0 — 1/30 О 1/42 0 -1/ЗО 0 5/бб О -691/2730 О 7/б 0 -3617/510 О 43867/798 0 -174611/330 О 854513/138 0 -236364091/2730 о 8553103/б О -23749461029/870 0 8615841276005/14322 5а 0 1 1 2 3 5 8 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 30 Пусть для любого х Нг = ~~г ~- — — 1!.
Тогда й й+./ 2 — 2!п2, 3 — —,к/Я вЂ” з 1п3, з+3 «~~ з 4 — ззк — 31п 2, з+зк ~з~ 3-зУ $! 3 Д1п~ $ — -'кзз згзб ггз - -„!п 3+ ~1 Л1п Ф, $ ч гк„1-зУзб-1У4 $! б.~„г Д! $ + 1, Уз/зб-г!4 $ !и 3 1, гб ~ 6 — ~Угг~/3 — 2 1п2 — ~ 1п 3, $+ -'к43-2!п2 — У~1п3 Нзуз = Нзуз = Нзуз = Нзгз = Нзу» = Нзуз = Нз уз Нзуз ж Н~уз = Нз|е = и в общем случае, когда О < р «у 1сзс упр. 1.2.9-19), ф 7Г р 2!зп, и Н; =- — -соз-к — 1п2о+2 з соз — к-1пз!п-к, з>'з— р 2 г<з<зр ПРИЛОЖЕНИЕ Б ОСН08НЫК 0БОЗНАЧаНИя Буквы у,й Я,Т а,Ф Раздел Обозначение Присвоить переменной 1' значение выражения Е Значения переменных П и 1' поменять местами (Г++ 1г А„или А(п) А „или А(щ,п) и-й элемент линейного множества А Элемент, стоящий в строке гп и столбце и прямоугольной таблицы (матрицы) А Узел (группа переменных, каждая из кото- рых характеризуется именем своего поля), ад- ресом которой является Р; предполагается, что Р э6 А Переменная в НОРЕ(Р) в поле с именем Р Содержимое слова компьютера, адрес кото- рого — Р Адрес переменной Ч в компьютере Присвоить указателю Р адрес нового узла Возвратить НООЕ(Р) на хранение; все его поля теряют наименования НООЕ(Р) Р(Р) СОНТЕНТЕ (Р) 2,1 2.2.3 ЫС(Ч) Р ч= АЧА11 аЧАП.
~"- Р 2.2.3 2.2.1 гор(3) Узел вершины непустого стека 3 в формулах, если дополнительно не оговорено, имеют следующий смысл. АриФметическое выражение, значением которого является целое число Арифметическое выражение, значением которого является неотрицательное целое число Арифметическое выражение, принимающее действительное значение Арифметическое выражение, принимающее комплексное значение Функция, принимающая действительное или комплексное значение Выражение, значение которого — указатель (либо А, либо адрес компъютера) Множество или мультимножество Строка символов Значение Раздел Обозначение 2,2.1 (В =о Е; Е') (В) 1.2.3 1.2.3 1,2.9 1.2.3 1.2.3 1.2.4 йсб(э', х) 1,2.3 бьу ( "Ь() ~ю ЖИ Цли ЯОО пип ДЙ) лре Взято из 3 в Х: присвоить Х <- сор(3) и затем удалить Фор(3) из непустого стека 3 Поместить Х в 8: вставить значение Х в ка- честве нового входного значения в вершину стека 8 Условное выражение: означает Е, если В истинно, и Е", если В ложно Характеристическая функция условия В: (В=о 1; О) Символ Кронекера: у = и] Коэффициент при з" в степенном ряду у(х) Сумма всех Д(л), таких, что значение л-- целое и выполняется соотношение В(л) Произведение всех 1(л), таких, что значение (с — целое и выполняется соотношение В(я) Минимальное значение из всех Дл), таких, что значение и — целое и выполняется соот- ношение В(й) Максимальное значение из всех у'(л), таких, что значение Й вЂ” целое и выполняется соот- ношение В(й) т делит (с: и шос( т = О и э > О Разность множеств: (а ! а принадлежит Я и а не принадлежит Т) Наибольший общий делитель у и л: у взаимно простое с Й: йсб(у', и) = 1 Транспонированиая прямоугольная таблица (матрица) А: Ат(1 й1 з(й Я Левый обратный к о элемент з в степени у (когда л — положительное число) х в степени л: с - и * ~*-") а<у<а Раздел Обозначение Значение хнах — Ь)1 = < ЙГО Ц Ь-О; ЬД*-Чгь) о<у<о и факториал: Г(п + 1) = па Биномиальный коэффициент: (Ь < 0 =ь 0; , -'~Ь1) Полиномиальный коэффициент (определен только тогда, когда и = кч + пт + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
