Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 59
Текст из файла (страница 59)
" + а„,) 1.2,б < п1 В21 ° ° ° 1 вт й Число Стирлинга периого рода: о<о,<ь,«-.ь. « Число Стирлннга второго рода: (." о<о,<ь,й- <ь. < (. (П()) (ам..., а„) Множество всех а, таких, что выполняется соотношение В(а) Множество или мультимножество (аь ~ 1 < Ь< и) Дробная часть (используется, когда х — дей- ствительное число, а не множество): х — (х1 Замкнутый интервал: (х ~ а < х < Ь) Открытый интервал: (х ) а < х < Ь) Полузамкнутый интервал: (х ~ а < х < Ь) Полуоткрытый интервал: (х ~ а < х < Ь) Число элементов множества Я Абсолютная эеличина хч (х > 0 =о х; — х) Данна и Наибольшее целое число, не превосходящее х: шаха<, Ь Наименьшее целое число > х: пипьйь Ь х по модулю Ьс (у = 0 =ь х; х — у(х/у)) 1.2.П.2 1.2.2 1,2.2 1.2.2 1.2.2 (а..Ь) (а..Ь) (а,.Ь) (а..ь) Ф! 14 М Ф Гх) хшодр х~ Г(х + Ь)/Г(х) = Пь,,~, 1л..)-) о<1«ь Обозначение Значение х ш х' (по модулю р) 1.2.4 1.2,11.1 1.2.11А 1.2,11.1 1.2Л1.1 О(У(п)) О(/(з) ) П(/(и)) 6(/(и)) 1ойв х 1.2.2 1.2.2 1,2.2 1.2.2 1пх )бх екрх (Х,д 1,2.9 1.2.9 1.2.10 У'(х) У"(х) /(и)( .) 1.2.11.2 1.2.7 Н('1 Гармоническое число: Н( 1 (() Число Фнбоначчи: (п < 1 =о и; Е„ в + Е„ з) 1.2.7 1.2.8 Число Бернулли: и! (з") х/(е' — 1) Определитель квадратной матрицы А Знак т: (х > 0) — (х с О) Дзета-функция: Ивп, Н (когда х > 1) (ю Гамма-функция: (х — 1)! = я(х, оо) Неполная гамма-функция: / е 'И в~(( Константа Эйлера: Иш„.(̈́— 1пп) Основание натурального логарифма: 2..>е 1/п1 Отношение длины окружности к ее диаметру: 4 Е„>е(-1) "/(2п + 1) Бесконечность: больше любого числа Пустая связь (указатель без адреса) Пустая строка (строка длины нуль) 1.2.11.2 1.2.3 Н„ пес(А) з)кп(х) 1(х) Г(х) у(х, у) 1.2.7 1.2.5 1.2.11.3 1.2.7 Сравнимость (конгрузнтность) по модулю Ьс х впоб у = х' шоб у О большое от У(п) при п -+ оо О большее от У(х) при з -в 0 Омега большое от /(и) прн и -+ со Тэта большое от /(и) при и -+ сю Логарифм числа х по основанию Ь (когда х > О, Ь > О и Ь ф 1): у такое, что х = Ь" Натуральный логарифм: 1ок, х Логарифм числа х по основанию 2: (ояз х Показательная функция от х: е' Бесконечная последовательность Хе, Хы Хю ...
(здесь буква и — часть обозначения) Производная от / по х Вторая производная от / по х и-я производная от / по х: (и = О =о У(х); у'(х)), где я(х) = /(" Ы(х) Гармоническое число порядка х: ~ 1/й' в<в<ь Раздел Обозначение Значение Пустое множество (множество, не оздержащее злементов) Золотое сечение: 1»(1 + ~Л) Функция Эйлера: ~» (6,1.
и) е<»<а х приближенно равно 9 Вероятность того, что утверждение 5(Х) справедливо для случайных величин Х Математическое ожидание (среднее значение) случайной величины Х: 2, хрг(Х = х), если Х вЂ” дискретная случайная величина Рг(5(Х)) 1.2.10 ЕХ шеап(9) 1.2.10 гаг(9) 1,2.10 (ппп хм ате хз гаах хз, бег х») 1.2.10 1.2.2 1.2.2 1,2.2 (... а»аа.а » )» //х», хз,"..., х„// Соединительное произведение Сумма мультимножеств, т, е. (а, Ь) е» (а„с) и (а,а,6,с) Приращение функции: У(Ь) — /(а) Конец алгоритма„программы или доказатель- ства Один пробел Регистр А (сумматор) компьютера И11 Регистр Х (расширение) компьютера И11 1.1 1.3.1 1.3.1 1.3.1 гХ Среднее значение распределения вероятностей, которое задано производящей функцией 9: 9'(1) Дисперсия распределения вероятностей, которое задано производящей функцией 9: 9" (1) + 9'(1) 9 (1) Случайная величина с минимальным значением хм средним значением (математическим ожиданием) хю максимальным значением хз, среднеквадратичным отклонением х» Действительная часть х Мнимая часть х Комплексное число, сопряженное к: згх — » Пс Представление числа в позиционной системе счиш»ения с основанием 6: ~ »а»6 Цепная дробь: 1/(х1 + 1/(хз+ 1/( ' '+ 1/(хь) ° .
))) ОТВЕТЫ К УПРАЖНЕНИЯМ 'Гчег, довольна! — сказал возмушенный отец. — Есть граница любому теРпенью. Если пятый вопрос гы задашь наконец, Сосчитаешь ступень за ступенью(рь — льюис кзррол ((.е>)(((3 сдггргоьь), длиса е стране чудес, гл, б. (1вб2) ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ 1. Задача средней сложности для читателей с математическим уклоном, 3. См, )1(. 1.
ЬеЪецце, Тор)сз )л №лгЬег ТЛеогу 3 (Веа()>пб, Мазза А(Ымоа-)1>ее1еу, 1966), СЬаргег 3; Р. 11(ЬепЬо)ш, 13 йессигез оп ГеплагЪ |.ааг ТЛеогега (Хеи Уог1с Врг(абер-)(ег1аб, 1979)( А. %1!гл, АллаВ о( Л(агЛещаиса 141 (1995), 443-551.
РАЗДЕЛ Б 1. Пусть р(1)...р(п) и 9(1)... о(п) — лве различные перестановки, удовлетворяющие этим условиям, и пусть а — минимальный индекс, при котором р(а) аг 9(1). Тогда р(а) = (((з) при некоторых ) > а, а а(() = р(Л) при некоторых Л > 1, Поскольку Кр(,> < Кр(а> = К (;> < К о> = Кр((), имеем Кр((> — — К ((» а так как сортировка устойчива, то р(() < р(Л) = 9(а) < д(З) = р(1), чего быть не может.
2. Да, если все операции сортировки были усгаейчиеммц. (В противном случае этого утверждать нельзя.) Ясно, что Алиса н Кркс получили одинаковые результаты; то же самое получил н Билл, так как вследствие устойчивости при равных больших ключах малые ключи расположились в порядке неубывания. Формальное доказательство: пусть после сортировки по малым ключам Билл получил Вр(»... В„(н> - -В',...
К„., а после второй сортировки по большим ключам В,',(,)... В,',(н> = Вр(„(гн... Вр(а(нн. Нужно показать, что при 1 < а < Л> (Кр(аб)) Лр(а(а))) < (Кр(а((+)>) Лр(а((аг))) Если К„(,(,» )е Кр(а((ац> то К„( ((» < Кр(а((а,», если же Кр( ((» — — Кр( ( агр то К ( ) —— и тогда 9(а) < 9(а + 1). Следовательно, Л,((> < й'(,+», т. е. Лр(а(,» < Йр(,(;+и>. 3. Всегда можно собрать вместе записи с одинаковыми ключами, сохранив при этом их относительное располо)кение) тогда в последующих операциях каждая такая группа рассматривается как неделимое целое.
Следовательно, можно считать, что вге ключи различны, Пусть а < Ь < с < а; этн три ключа можно упорядочить так: аЬс, Ьса нли саЬ. Далее, если упорядочены Ф вЂ” 1 различных ключей тремя способамн, можно это сделать н для Ф ключей, поскольку прн Ка « К,ч-а > К,а либо К; а < Кл < К; для некоторого а, либо Кн < Кь а ))греаол С. Я. Маршака. 4. Сначала сравним слова„не обращая внимания на регистр символов, затем воспользуемся регистром символов для уточнении порядка. Точнее, заменим каждое слово а парой (а', а), в которой а' формируется из и подстановкой А -+ а, ..., Е -+ г; затем рассортируем сформированные пары лексикографически.
В результате получим, например, сех < Тех < ТеХ < ТЕХ с !ех!. В словарях также встречюотся слова с диатоническими знаками, префиксами, суффиксами и аббревиатуры; например, а < А < А < а- с а, < -а < А- < А. < аа < а.а. < аа < аА < АА < А.А. < ААА « -. гг < Ег. < ЕЕ < ггг < ЕЕЕ. В таком более общем случае получим а' отображением а -+ а, А -+ а и т, д,, отбрасывая знаки дефиса и точки. б. Положим р(О) = 0 и р((1а)г) = 1р(Ц)а; здесь (1а)г является обычным двоичным представлением положительного целого числа, а )а) — длиной строки а. Тогда р(1) = 10, р(2) = поо, р(3) = по1, р(4) = п10000, ..., р(1009) ппо1оопп110001, ...,, (83330) = 1 О, °, р(2 ) = 1 О " и т. д. Длина р(п) равна (р(п) $ = Л(п) + Л(Л(в)) + Л(Л(Л(п))) + " + 18 я + 1, где Л(0) = О, Л(п) = (13п) лля и > 1, а 18' и есть наименьшее целое гл > О, такое, что Л1 1(п) = О.
(Эта конструкция предложена В. И. Левенштейном, Проблемы кибернетики 20 (1968), 173-179, см, также Д, Э. Кнуте Тве Ахасьещас!св! Свгдпег, еайеа 'оу П. А. К1апнк (Вейпопц СаЫогп1а; ЧЧабзиогсв!псегпайова1, 1981), 310-325.) 6. Возможно переполнение, которое может исказить результаты сравнения. Следовало написать, например, "1ЛА А; СЕРА В" и проверить индикатор сравнения. (Невозможность сравнения чисел, занимающих целое слово, посредством вычитания — проблема, возникающая на многих моделях компьютеров; это основной довод в пользу включения операторов СНРА,..., СНРХ в систему команд компьютера Н1Х.) 7. СОНРАВЕ 311 9Р ВЕС! 1 18 РВХ А,1 11Р 13 СНРХ 8,1 98 ЮНР е 3 1НЕ 9Р 8. Решение 1, основанное на тождестве гщп(а,ь) = г(а+Ь вЂ” )а — Ь)): ЗОМ !РА Х ЗМХ 1 БМХ $ АРР АВ1 В1Ч 2" ЕНТХ 1 ЗТА А1 а = га~ +аз БХАХ 5 БТХ А2 )аг) < 1 Ноь АВ2 1ЛМ В ЗТХ АВБ (аг-Ьг) ив (а — Ь) ЗМХ 5 Ый Я2 ВХЧ «'г~ АОВ В2 ЗТА В1 Ь = 2Ь +Ьг ЗОВ АВ3 ЗТХ В2 )Ьг) < 1 ЗМХ 3 !РА А1 ВХЧ 2 БОВ 81 Переполнение невозможно АРР А1 ЗТА АВ1 а| — Ь| АРР 81 Переполнение невозможно Ыи Аг БОВ АВ1 (1: 3) ЗОВ 82 ЗТА С ЗТА АВ2 аг Ьг Рениксе Е, основанное на том, что индексирование может вызвать сложные взаимные обмены: 301.2 ХОА А БТА С БТА ТА ЬОА В БТА ТВ Теперь включите в программу приведенную виже последовательность операторов $ раз подряд, где 2Ф > 1010: ХОА ТВ ЕВАХ 3 017 а2 ЗТХ ТЕИР Ы2 ТЕМР ЗТА ТВ ХИС1 0,2 1ИС1 0,2 1ИС1 0,2 1ДИ ТИ1И,1 ЫА О,З ЗТА С ЬОА ТА ЕВАХ З ОХТ "2 ЗТХ ТБИР Ы1 ТЕИР БТА ТА (Эта программа просматривает разряды в двоичном представлении а и Ь справа налево, сохраняя знаковые разряды.) В конец текста программы поместите следующую таблицу: В.
Вероятность равна сумме ) '1 (~~ ) (-1)' (,~1)я"э~„которую получим методом вхлючеиия и исключения (упр. 1.3.3-20). Это также можно записать в виде бета-распределения (Ф) гэ 1~.-1(1 1)Ф-г (1 10. Рассортируйте содержимое ленты, а затем посчитайте. (Некоторые методы сортировки позволяют легко отбрасывать записи с повторяющимися ключами.) 11. Присвойте каждому человеку индивидуальный идентификационный номер, который должен быть указан иа всех касающихся его карточках.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
