Д. Кнут - Искусство программирования том 1 (1119450), страница 27
Текст из файла (страница 27)
[МЯ5] Эламентарнал симметричная функция определяется по формуле а, = ~ хл, хз 1<з!« з <» (Это то же самое, что н Ьм нз (ЗЗ), только прн суммировании не допускается равенство индексов ) Найдите производящую функцию для последовательности а и выразите а через 5„, определяемые формулой (34) Выпишите формулы длк ап аз, аз и а» ь 11. [МЯ5] Соотношение (39) можно также использовать для того, чтобы выразить 5з через Ьь находим 5~ = Из, Яз = 25г — йм 5з = Зйз — Зй~йз+ й~з и т д Чему равен з коэффициентприйз'Ь~~з й" в таком представлении 5, если)гз+2йз+ +пзгз = шо ь 12.
[МЯО] Пустьунасестьпоследовательностьсдвумя индексамиа, где т,п = 0,1, Покажите, что эту последовательность можно представить с помощью одной производящей функции двух переменных, и найдите производящую функцию для последовательности ат» —— („") 13. [НМЯЯ] Преобразоеание и Данзаса функции 1 (х) называется зрункция Ь1(з) = е 1(г) гЫ к зо Пусть ао,а1,а2,... — бесконечная последовательность, производящая функция которой сходится, и пусть /(х) — ступенчатая функция 2 „аь [О < /4 < х].
Выразите преобразование Лапласа функции /(т) через производящую функцию С заданной последовательностя. 14. [НМ21] Докажите соотношение (13). 15. [М26] РассмотРим фУнкцию Н(ю) = ~„йо С„(в) ю". Найдите замкнутую фоРму дла производящей функции С (х) = ~ ( „)в = ~ ~( „)(-х) 16. [м33] найдите простую формулу для производящей функции с,(в) = Яэ а2ь,э, где а 4, — КОЛИЧество спосОбов выбора к объектов из и при условии, что каждый объект можно выбрать максимум г раз. (При г = 1 получаем (",) способов, а при г > !4 — число сочетаний с повторениями, как в упр 1 2 6 — 60.) 17.
[М95] Найдите коэффициенты в разложении функции 1/(1 — х) в двойной степенной ряд по с и ю ь 18. [М86] Для заданных положительных целых чисел п и г найдите простые формулы для следующих сумм. (а) 2 1<М<4,« „„/4142 ./4„, (Ь) 2 1<1 <4 « 4 <„91/42 . й (Например, для п = 3 и г = 2 эти суммы соответственно равны 1 2+ 1 3+ 2 3 и 1 1+1 2+1 3+2.2+2 3+3 3) 19.
[НМ38] (К Ф Гаусс (С Р Сапээ), 1812 ) Хороша известны суммы следующих бесконечных рядов: 1 1 1 1 1 1 л 1 — — + — — -+" =!пг; 1 — — + — — — +. 2 3 4 ' 3 5 7 4 1 1 1 л4/3 1 1 +- — +..— — +-!п2 4 7 10 9 3 С помощью определения Н, = ~ ~-' — — '), >1 данного в ответе к упр. 1.2.7 — 24, эти ряды можно переписать следующим образом соответственно 1 2 1 1 3 1 1 1 — -Н1/2, '— — — Н1/4 + -НЗ/4, — — -Н1/э + — Н2/2.
2 ' 3 4 4 ' 4 6 6 Докажите, что в общем случае значение Н,/, равно Ч 'г р грй — — — со! -л — )п2Ч+ 2 ~ соэ — 11 !пьбп -1г 2 р Ч 2<4<4/2 где р и Ч вЂ” целые числа и 0 < р < Ч [1/кованое. По теореме Абеля эта сумма равна 1 — 2~" (и и + р/Ч) С помощью соотношения (13) выразите этот степенной ряд таким образом, чтобы можно было вычислить предел ] 20. [м31] Для каких коэффициентов с 1 справедливо равенство и в =~~ с ьэ/(1 — х) ? >о 4=О 21.
[НМЗО] Найдите производящую функцию для последовательности (и!) и исследуйте свойства этой функции. 22. (М211 Найдите производящую функцию С(з), для которой 23. [Муз] (Л. Карлитц (Ь. Сагйсз),) (а) Докажите, что для всех целых чисел т > 1 существуют многочлены 1,„(щ,..., з„,) и д„,(щ,...,с,„), такие, что формула =1 (щ, .,в ) О (щ,...,г ) превращается в тождество для всех целых чисел и > г > О. (Ь) Обобщая упр. 15, найдите замкнутую форму для суммы ' ' - =, ~..(."'.,)(."'..)- (.':.,)" '-' выразив ее через функции 1 я а из и, (а).
(с) Найдите простое выражение для о„(вп...,з ), если щ = = с = ю 24. [Мвв] Докажите, что для любой производящей функции С(г) Е(„)[ -']С()"=['](1+ ())- Вычислите обе части этого тождества, если С(с) равна. (а) 1/(1 — с); (Ь) (е' — 1)/а ь 23. [МОЮ] Вычислите сумму Яь ("„) (~„"~ )( — 2)~, упростив эквивалентную формулу [„с](1 2ш)а [са-с](1+я)~ < ы 26. [М40] Найдите обобщение обозначения (31), согласно которому можно, например, записать [с~ — 2з~] С(с) = ас — 2ас, где С(г) задается формулой (1), 1.2.10. Анализ алгоритма Пришло время применить некоторые методы, рассмотренные в предыдущих разделах, к изучению типичного алгоритма. Алгоритм М (Нахождение максимума).
Для заданных п элементов Х [1], Х [2],..., Х[п] необходимо найти ~акис величины т и у, что т = Х[у] = шахг<,<„Х[(], где у — наибольший индекс, удовлетворяющий этому соотношению. М1. [Инициализация.] Положим у с — и, /с +- п — 1, т с — Х[п]. (Во время выполнения алгоритма будем иметь т = Х[у] = шахе«,„Х[1].) М2. [Все провереноу] Если 1с = О, то работа алгоритма заканчивается. МЗ. [Сравнение.] Если Х[(с] < т, перейти к шагу М5. М4. [Замена т.] Положим у с — )с, т +- Х[(с].
(Это значение т является новым текущим максимумом.) Мб. [Уменьшение (с.] Уменьшим lс на единицу и вернемся к шагу М2. ! Может показаться, что данный алгоритм настолько тривиален, что его вообще не стоит подробно анализировать. Но на самом деле это хороший пример, показывающий, как можно исследовать более сложные алгоритмы. Анализ алгоритмов имеет Рнс. 9. Алгоритм М Подписи к стрелкам показывают, сколько рьз осуществляется проход каждого лутн Заметьте, что должен выполняться первый закон Кнрхгофа, который в данном случае выглядит так: число входов в каждый узел должно равняться числу выходов нз него.
очень большое значение в программировании, потому что, как правило, существует несколько алгоритмов решения конкретной задачи и необходимо знать, какой нз них наилучший. Для алгоритма М требуется фиксированный объем памяти, поэтому будем анализировать только время, необходимое для его выполнения. Для этого подсчитаем, сколько раз выполняется каждый шаг (рис. 9). Количество выполнений 1 гг п — 1 Л и — 1 Номер шага М1 М2 МЗ М4 М5 Зная, сколько раз выполняется каждый шаг, можно определить время работы алгоритма на конкретном компьютере. В приведенной выше таблице неизвестна только величина А, которая определяет, сколько раз необходимо изменить значение текущего максимума. Чтобы довести анализ до конца, исследуем эту любопытную величину А. Этот анализ обычно заключается в нахождении минимального (для оптимистов), максимального [для пессимистов), среднего [для специалистов по теории вероятностей) значения А и его среднего квадратичного отпклоненил (данная характеристика показывает, насколько близким к среднему может оказаться значение).
Минимальное значение А равно нулю; зто будет в случае, если Х[п] = шах Х[/с]. 1<я<а Максимальное значение А равно п — 1; это будет в случае, если Л [1] > Х[2] » ... Х[тт]. Таким образом, среднее значение лежит между 0 и и — 1. Будет ли это -,'и? Или тттп? Чтобы ответить на поставленный вопрос, нужно выяснить, что понимается под средним. А чтобы правильно определить среднее, сделаем некоторые предположения., касающиеся характеристик входных данных Л [1], Х[2]...., Х[п].
Будегт считать, что Х[Ц вЂ” различные значения и что все и! перестановок этих значений равновероятны. (В большинстве случаев это разумное допущение, но, как вы увидите из упражнений к данному разделу, анализ можно проводить также, исходя из других предположений.) Производительность алгоритма М не зависит от самих величин Х[к); имеет значение только относительный порядок их расположения.
Например, если и = 3, предполагается, что следующие шесть возможностей равновероятны. Ситуация Значение А Ситуация Значение А Х[Ц < Х[2) < Х[3] 0 Л [2] < Х[3] < Х[Ц 1 л [ц < х[з] < х[г] л [з] < х[ц < х[г] Х[2) < Х[Ц < Х[3] 0 Х[3) < Х[2) < Х[Ц 2 Среднее значение А при и = 3 равно (О + 1 + 0+ 1+ 1+ 2)/6 = 5/6. Очевидно, что можно считать Х[Ц,Х[2],..., Х[и] числами 1,2,..., и, расположенными в определенном порядке.
Согласно нашим предположениям все и. 'перестановок равновероятны. Веролтикостиь того, что А имеет значение й, равна рпь = (число перестановок и объектов, для которых А = к)/и!. (1) Для нашего примера (см, таблицу выше) рзо = з, рзт = — рзг = „-,. Средкее значение (или просто среднее) определяется, как обычно, по формуле Ап = ~ ~1српы (2) ь Дисперсия $'п определяется как среднее значение величины (А — Ап)г, поэтому У = ~~~ (й Ап) Рпь = ~~т lс~Рпз 2 Ап ~ тйРпь + Аг ~~~ Рпь ь ь ь *я~р„з — 2 АпАп + Аг = „"игр„ь — Аг. (3) ь ь И наконец, сРедкее квадРатиичкое отиклокские оп опРеделаетсЯ как зттУп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
