AOP_Tom3 (1021738), страница 213
Текст из файла (страница 213)
(Л) Постройте 4 строк из каждой строки (13) путем замещения каждого символа»»" символами»»»»»", каждого нуля — любой из первых четырех строк н каждой единицы— любой из последних четырех строк (подобное построение создает АВП(гиги', ии') нз любых АВП(т, и) и АВП(т', и')), (е) Пусть дано АВП(16, 9). Можно в каждой строке заключить в кружок один символ » ° » таким образом, чтобы в каждом столбце было равное число заключенных в кружки символов» ° ". Затем можно разбить каждую строку на две строки, заменяя заключенные в кружки элементы нулями и единицами.
Для того чтобы показать, что такая процедура заключения символов "»" в кружки возможна, заметим, что символы "»" в каждом столбце могут быть произвольно разделены на 32 группы по 7 в каждой; тогда 512 строк содержат символы "»» из 7 различных групп каждая и каждая из 32 х 8 = 512 групп появляется в 7 различных строках, Теорема 7.5.1Е (" теорема о свадьбе' ) гарантирует существование идеального соответствия одного зацикленного элемента в каждой строке и в каждой группе. Лигпература. К. Ь. Н[гезс, ЫСОМР 5 (1976), 19-50; А.
Е. Вгони ег, СошЫпасотии, ег[1«е«[ [эу На)па) апд Вбэ, Со!1оСь МаИ. Яос. Лепт Во[уи 18 (1978), 173-184. Брувер доказывает, что АВВ(2и, и) существует для всех и > 32. Метод из и. (д) дает нам также АВВ(32, 15) путем комбинирования (13) и (15). 19. Согласно упр. 8 среднее количество при 8-5 определенных битах равно 2«з/е «(8, 8)/ /(«) со значениями соответственно (32,22, +, "— ~, г,, эз, Я, — '~,1) (32,22, 14.9,9.9,6.4,4.1, 2.6, 1.6, 1) дли 8 > 1» > О.
Эти значения лишь несущественно больше значений 32«7» (32, 20.7, 13.5,8.7, 5.7,3.7,2.4, 1.5, 1). Значения дпя наихудшего случая равны (32,22, 18, 15, П, 8,4, 2, 1) (примерами "наихудших запросов" могут служить»»»»»»»», О»»»»»»», »0»»»»О», »»0»»0»1, »»0»00»1, *0»»0100, 0001»»10, 000000»0, 00000000). 20. В работе 3. А. 1,а Ров«ге, 111ес.
Май. 58 (1986), 205-208, показано, что АВВ(п«, и) не может существовать при т > (") и и > 3; следовательно, АВ[1(16,6) не существует. В работе 1 а Ров«ге апд тап Ь[пц Ь'01. Ма«5. 31 (1987), 219-225, доказано, что не су1пествует АВВ(10,5). АВВ(8,6) получаем из АВВ(8,5) или АВВ(4, 3), используя метод нз упр. 18. Таким образом получается несколько неизоморфных решений, и могут существовать и другие примеры АВВ(8, 6).
Единственные остающиеся возможности (кроме тривиальных АВ11(5, 5) и АВХ1(6,6)) — АВ11(8,5), отличное от (15), и, возможно, одно или нескояько АВЩ12, 6). Ладно, я очень рад, что мы до этого сами додумались, как полагается сыщикам; эа всякий другой способ я гроша ломаного не дам. — тОаа сОЙеР (1684) [марк твен, приключения Гекльберри о«инна) Таблица 2 ВЕЛИЧИНЫ, ЧАСТО ИСПОЛЬЗУЕМЫЕ В СТАНДАРТНЫХ ПОДПРОГРАММАХ И ПРИ АНАЛИЗЕ КОМПЬЮТЕРНЫХ ПРОГРАММ (45 ВОСЬМЕРИЧНЫХ ЗНАКОВ) Величины, расположенные слева от знака "=", заданы в деситичной системе счисления 0.1 = 0.01 = 0.001 = 0.0001 = 0.00001 = 0.000001 = 043000001 = 0.00000001 = ОВ00000001 = 0.0000000001 = т/2 = т/3 = /5= ,/ГО = Уг= Гз= Я= 1п2 = !п3 = !п10 = 1/!п2 = 1/1п 10 = 1' = т/180 = 1/а = ,/т = Г(1/2) = Г(1/3) = Г(2/3) = 1/е = е г !пи ф ет /4 ып1 соа 1 — ~'(2) И) !пф 1/!пф — 1и 1п2 0.063Ц БЯЦб ЯЦ63 14631 463Ц бЗЦб ЯЦ63 ЦБЭ1 46315— 0.00507 53412 17270 24365 60507 53412 17270 24365 60510— 0.00040 611!5 6457Р 65176 76Я55 44264 16254 02030 44672+ 0.00003 21556 135ЯО 70414 54512 75170 ЯЗР21 15002 35223- 0.00000 24761 32610 70664 36041 06077 17401 56063 34417— 0.00000 02061 57364 055Яб 66151 55323 07746 44470 26033+ 0.00000 ОО!5Э 27745 15274 53644 12741 72312 20Я54 02151+ 0.00000 000И 57143 56106 04303 47Я74 7734! 01512 63327+ 0.00000 00001 04560 27640 46655 12262 71426 40!24 21742+ 0.00000 00000 06676 33766 35367 55653 Э7265 34642 01627- 1.Щ04 7463! 7716746220 42627 661!5 46725 12575 1743Э+ 1.56663 65641 30231 2516Э 54453 50265 60361 3407Я 42223- 2, 17067 36Я34 57722 47602 57471 63003 0056Э 55620 32021— 3.12305 40726 64555 22444 02242 57! 01 4Цбб Я3775 22532+ 1.20505 05746 15345 05Я42 10756 65334 25574 22415 ОЗЩ+ 1.3423Э 50Ц4 22!75 73134 67363 761ЯЯ 05Щ 31Ц7 60!й!— 1.!4067 74050 61556 12455 72152 644ЭО 60271 02755 7Э136+ 0.54271 02775 75071 73632 571! 7 07316 30007 7!Збб 53640+ 1.06237 24752 55006 05227 32440 63065 25012 35574 55337+ 2.2327Я 06735 ВВЩ 25405 56512 66542 56026 46050 50705+ 1.34252 16624 53405 77027 Э5750 Э7766 40644 35175 04Э53+ 0.3362Б 75425 1!562 416Ц 52325 УЯ525 27655 Ц756 06220— 3.1!037 55242 10264 302!5 Ц230 63050 56006 70163 21И2+ 0.0107Я 72152 11224 72344 25603 54276 бЭЯ51 22056 11544+ 0.2(276 30!55 62344 20251 23760 47257 50765 15156 70067- 11.
67517 14467 62135 7! Яйй 25561 15466 Я0021 40654 341 03в 1.61337 61106 64736 65247 470Э5 40510 1527Э ЯЦ 70 17762— 2.53347 35234 5!Р!3 6!316 73106 47Б44 54653 00106 66046— 1.2652Я 57!12 !4154 74312 54572 37655 60! 26 232Я1 02452+ 2.55760 52130 50535 5Щб 52773 42542 00471 7236Э б!661+ 0.27426 53066 И167 4676! 52726 754ЯБ 02440 52Э71 03355+ 7.30714 45615 23355 33460 63507 35040 Э2664 25356 5021 7+ Р.Ц742 Ц770 67666 06!72 232!5 74376 Рибй 5!3!3 2552!— 1.11206 40443 4750Я 364!Я 65374 52661 524И 375!! 46057+ 1.4743Я 57156 27751 23701 27634 71401 40271 66710 150!О-1- 1.61772 13452 бЦБВ 6576! 22477 36553 53327 17554 21260+ 2. Ц275 Я1512 16162 52370 Я5530 11342 53525 44307 021 7!— 0,65665 2ЦЭб 04414 73402 03067 2Э644 116И 07474 !4505- 0.42450 50037 ЩОБ 427!1 07022 Цббб 27320 70675 И321+ 0.74001 45144 5325Я 42Ябй 42107 23Я50 50074 46100 27706+ 1.14735 00023 60014 20470 1561Я 42561 Я!7!5 10177 066Ц+ 0.36630 26256 61213 01145 13700 41004 52264 30700 40646+ 2.04776 бР111 Г7144 41512 1ЦЯБ 16575 ООЭ55 436ЯО 4065!+ 0.27351 7!2ЯЭ 67265 63650 17401 56637 26334 ЭЦ55 57005— Несколько интересных констант без общего названия возникли в связи с анализом алгоритмов сортировки и выбора.
Эти константы вычислены с 40 десятичными ~каками в 5.2.3-119) и 6.5-16) и в ответах к упр. 5.2.3-27, 5.2.4-13, 5.2.4-23, 6.2.2-49, 5.2.3-7, 6.2.3-8, 6.3-26 и 6.3-27. ч ЗНАЧЕНИЯ ГАРМОНИЧЕСКИХ ЧИСЕЛ, ЧИСЕЛ БЕРНУЛЛИ И ЧИСЕЛ ФИБОНАЧЧИ ДЛЯ МАЛЫХ ЗНА'1ЕНИЙ е п 0 1 2 3 5 б 7 В 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Н О 1 3/2 11/б 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/!5519504 18858053/5173168 19093197/5173168 444316699/118982864 1347822955/356948592 34052522467/89237!4800 34395742267/8923714800 312536252003/80313433200 315404588903/80313433200 9227046511387/2329089562800 9304682830147/2329089562800 В 1 -1/2 1/б 0 -1/30 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 О -236364091/2730 0 8553103/б 0 -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 6 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 1 Пусть для любого х Н, = г ~ — — 1.
Тогда .. И 11+Х/ ь>1 Н1/г = 2 — 21п2, -'г/ь/3 — -' 1п 3, — Уь/3 — — !и 3, 27Г 31п23 -1я — 3 !и 2, 1 яфз/г 5- 1/4 а ф — з/25 — 1/4 — ь 1п5 + 1 Я!пф, 1яф з/25 1/4 — ь 1п5+ -1ь/5!пф, гяф~/ 5 '/4 — ь!п5 — -'ь/5!пф, -'л ь/3 — 2 !и 2 — з 1п 3, $яЛ вЂ” 21п2 — з 1п3 Н1/з = 3— з Н2/З г + Н1/4 = 4— 4 Нз/4 з + н1/ь = 5— Нг/ь = 5— ь Нз/ь = з+ ь Н4/ь 4 + ь Н1/в = 6— Н/в = ь+ в я а общем случае, когда 0 < р с д (см.
упр. 1.2.9-19), Д 7Г т 2ри п Н / —— — — — сов-т — !п29+ 2 ~ сов — я 1пв!и-я. Р/4— р я 2 1< /, Я Д ПРИЛОЖЕНИЕ Б ОСНОВНЫЕ ОБОЗНАЧЕНИЯ Буквы у„й Б,Т а,д Раздел Обозначение Значение Присвоить переменной г' значение выражения Е Значения переменных У и Ъ' поменять местами А„или А[п) А~„нлн А[та, и[ и-й элемент линейного множества А Элемент, стоящий в строке т и столбце и прямоугольной таблицы (матрицы) А Узел (грувпа переменных, каждая нз которых характеризуется именем своего поля), адресом которой является Р; предполагается, что РфЛ Переменная в МООЕ(Р) в поле с именем Р МООЕ(Р) 2.1 Р(Р) Содержимое слова компьютера, адрес кото- рого — Р СОМТЕМТЯ(Р) 2.1 2.2.3 Адрес переменной Ч в компьютере Присвоить указателю Р адрес нового узла ЬОС(Ч) Р ~.= АЧаП.
АЧАХЬ с= Р Возвратить МОРЕ(Р) на хранение; все его поля теряют наименования 2.2.3 2.2.1 Сор(Я) Узел вершины непустого стека Я в формулах, если дополнительно не оговорено, имеют следующий смысл. Арифметическое выражение, значением которого является целое число Арифметическое выражение, значением которого является неотрицательное целое число Арифметическое выражение, принимаюшее действительное значение Арифметическое выражение, принимающее комплексное значение Функция, принимающая действительное или комплексное значение Выражение, значение которого — указатель (либо Л, либо адрес компьютера) Множество или мультнмножество Строка символов Значение Раздел Обозначение Хс Я 2.2.1 2.2.1 (В =~ Е; Е') [В] 1.2.3 1.2.3 1.2.9 1.2,3 1.2.3 1.2.3 шах Дй) й)ь) 1.2.3 1.2.4 ясй0, й) 1.).
й Ат 1.2.4 1.2.3 1.2.2 х в степени й 1.2.2 бь [ "[9( ) Кю й(ь) Пю й(ь) ппп у(й) й)ь) Взято из Я в Х: присвоить Х е- сор(Я) и затем удалить Сор(Я) из непустого стека Я Поместить Х в Я: вставить значение Х в качестве нового входного значения в вершину стека Я Условное выражение: означает Е, если В истинно, и Е', если В ложно Характеристическая функция условия В; (В=ь1; 0) Символ Кронекера: [у = й! Коэффициент при г" в степенном ряду 9(г) Сумма всех у(й), таких, что значение й— целое и выполняется соотношение Е(й) Произведение всех Дй), таких, что значение й — целое и выполняется соотношение В(й) Минимальное значение из всех Дй), таких, что значение й — целое и выполняется соот- ношение В(й) Максимальное значение из всех 1(й), таких, что значение й — целое и выполняется соот- ношение тС(й) у делит й: й шос) у = 0 и 1' > 0 Разность множеств: (п [ а принадлежит В и о не принадлежит Т) Наибольший общий делитель )' и й; у' = й = 0 =ь О; шах А1 (==; ) ' э~бэ~ь / у взаимно простое с й: ясб()', й) = 1 Транспонированная прямоугольная таблица (матрица) А: Аз [у,й[ = А[й,Я Левый обратный к а элемент х в степени )) (когда х — положительное числа) < — П* 'ь') о<1<ь Обозначение Раздел Значение 1.2.5 х!/(х — Й)! = 1.2.5 1.2.5 © с и йг йт ...
айги П 1.2.6 к! к2 ° ° йм- м г<вг<ег«" <ь — йггг (а ~ Л(а)) (ам..., а„) 1.2.1 1.2 1.2.2 1.2.2 1.2.2 1.2.2 1.2.4 1.2.4 1.2.4 хшог) р [а..Ь) (а .. Ь) (а .. Ь) (а..Ь) Ф! (х) !о) (х) Г(х+ Й)/Г(х) = < Пь гг л* гг) й факториал: Г(й + 1) = и —" Биномиальный коэффициент: (Ь < О ~ О; хй/к!) Полиномиальный коэффициент (определеи только тогда, когда й = йг + йг + + й„,) Число Стирлинга первого рода: о<а,<ь,«<ь„<м Число Стирлинга второго рода: Множество всех а, таких, что выполняется соотношение гг(а) Множество или мультимножество (аь ~ 1 < й < й) Дробная часть (используется, когдах — дей- ствительное число, а не множество): х — (х) Замкнутый интервал: (х )а < х < Ь) Открытый интервал; (х ( а < х < Ь) Полузамкнутый интервал: (х ! а < х < Ь) Полуоткрытый интервал: (х ~ а < х < Ь) Число элементов множества Я Абсолютная величина х: (х > О =о х; — х) Длина а Наибольшее целое число, не превосходящее х: шаха<* Й Наименьгцее целое число > х: пппь>, Ь х по модулю Ьс (у = О ~ х; х — у (х/у) ) Раздел Значение Обозначение х ь х' (по модулю у) 1.2.4 1.2.11.1 1.2,11.11 1.2.1 1.1 1.2.11.1 0(/(и)) О(/(в)) П(/(и)) О(/(и)) !оя~ х 1.2.2 1.2.2 1,2.2 1.2.2 !их !их ехр х (Х„) 1.2.9 1.2.9 1.2.10 / (х) ув( ') /ОО (х) 1.2.11.2 НОО л 1.2.7 Гармоническое число: Н~ О! Число Фибоиаччн: (и < 1 =ь и; Е„, + Е;, т) 1.2.7 1.2.8 Число Бернулли: и! [х"] х/(е' — 1) Определитель квадратной матрицы А Знак х: [х > О] — [х < О] Дзета-функция: !пп„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
