оказалась последовательность 91 23 7 1 (5ave w 11865), однако в довольно широком диапазоне значений смещений результаты получаются примерно одинаковые.

30. Число точек с целыми координатами в треугольной области

{zln2--yln3<lniV, z>0, г/>0} равно i(log2iV)(log3iV)-I-0(logiV).

Во время /г-сортировки массив уже 2h- и 3/г-упорядочен (см. теорему К); следовательно, можно использовать результат упр. 25.

01 START ENT3 Т 1

02 1Н LD4 Н,3 Г

03 ENN2 -INPUT-N,4 Г

04 ST2 6F(0:2) Г

05 ST2 7F(0:2) Г

06 ST2 4F(0:2) Г

07 ENT2 0,4 Г

08 JMP 9F Г

09 2Н LDA INPUT+N, 1 NT - S - В + А

10 4Н СМРА INPUT+N-H. 1 NT - S - В + А

11 JGE 8F NT-S-B + A

12 6Н LDX INPUT+N-H,1 В

13 STX INPUT+N,1 В

14 7Н STA INPUT+N-H,1 В

15 INC1 0,4 В

16 8Н INC1 0,4 NT-В + А

17 J1NP 2В NT-В + А

18 DEC2 1 S

19 9Н ENT1 -N,2 T + S

20 J2P 8В T + S

21 DEC3 1 Г

22 J3P IB Г I

Здесь А - число правосторонних максимумов, как А в программе D - число левосторонних минимумов; обе величины статистически ведут себя одинаково. В результате упрощения внутреннего цикла время выполнения сократилось до 7ЛТ + 7A - 2S+\ + 15Г машинных циклов и, как ни странно, оно не зависит от В!

При N = 8 смещениями будут 6, 4, 3, 2, 1, и имеем Aave = 3.892, Save = 6.762; суммарное время работы в среднем составляет 276.24и (ср. с табл. 5). Обе величины - А я В - достигают максимума на перестановке 7384516 2. При 7V = 1000 имеется последовательность из 40 смещений: 972, 864, 768, 729,..., 8,6, 4, 3, 2,1; эмпирические тесты, подобные тем, которые приведены в табл. 6, дают А и 875, В яг 4250 и общее время выполнения - около 268000и (примерно вдвое больше, чем для программы D с последовательностью смещений из упр. 28).

Вместо того чтобы хранить значения смещений во вспомогательной таблице, удобно генерировать их на двоичной машине следующим образом.

Р1. Присвоить т <- 2*8наибольшая степень двойки, меньшая N. Р2. Присвоить h <- т.

РЗ. Использовать h в качестве смещения на очередном проходе сортировки. Р4. Если h четное, присвоить h h + /г/2; затем, если h < N, вернуться к РЗ. Р5. Присвоить т [m/2J и, если m > 1, возвратиться к Р2.

Хотя смещения для сортировки генерируются не в порядке убывания, сформированная последовательность значений обеспечивает правильную работу алгоритма.

32. 4 12 11 13 2 О 8 5 10 14 1 6 3 9 16 7 15.

33. Улучшить программу можно двумя разными способами. Во-первых, полагая, что искусственный ключ Ко равен оо, можно опустить проверку условия р > 0. (Эта идея применялась, например, в алгоритме 2.2.4А.) Во-вторых, можно использовать стандартный прием оптимизации: продублировать внутренний цикл, поменяв местами присвоенные регистрам значения р и д; в результате удастся избежать присвоения g <- р. (Эта идея использовалась в упр. 1.1-3.)

Таким образом, предполагается, что в поле (0:3) по адресу INPUT содержится наибольшее возможное значение и нужно заменить в программе L строки, начиная с 07,

р <- (Здесь р = г13, g = г12.)

Перейти к шагу L4 с g <-V р, если К > Кр. Lq <- j. Lj <r- p.

Переход на уменьшение j. р Lq. (Здесь р = г12, g = rI3.)

Перейти к шагу L4 с g <-V р, если К > Кр. Lq <-j.

Lj <- p.

g <- 0. К <Kj. N>j>l. 1

= Л-l, так что суммарное время выполнения сортировки равно 5В + 14N + N - 3 машинных циклов. Поскольку 7V равно числу элементов, справа от которых имеется нечетное число меньших элементов, величина Л имеет следующие статистические характеристики:

(min О, ave iiV+ Н/} - Ялг, max Л - 1).

Трюк с присвоением значения оо дает аналогичное ускорение и программы S. Приведенный ниже текст программы предложен Дж. X. Гальпериным (J. Н. Haiperin), который использовал эту идею и команду MOVE для сокращения времени выполнения до {6B + 11N - Щи, полагая, что по адресу INPUt+N+1 уже находится наибольшее возможное однословное число.

Дублирование внутреннего цикла сохранит дополнительно Б/2 или около того машинных циклов.

34. Существует () последовательностей из N выборов, в которых данный список выбирается п раз; вероятность появления каждой такой последовательности равна (1/М)"(1 - l/M)"", так как каждый список выбирается с вероятностью 1/М.

Замечание. Если программа М была модифицирована таким образом, чтобы отслеживать текущий конец каждого списка, то, поместив команду "ST1 END,4" между строками 19 и 20, можно сберечь время путем объединения списков так же, как и в алгоритме 5.2.5Н.

36. Программа L: Л = 3, Б = 41, N = 16, время = 496и. Программа М: А = 2 + 1-1-1+3 = 7, Б = 2-)-0-)-3-)-3 = 8, iV = 16, время = 549и. (К приведенному значению времени выполнения программы М нужно добавить время 94и, необходимое для выполнения дополнительной программы из упр. 35. Это позволит осуществить корректное сравнение. Операции умножения всегда замедляют выполнение программы! Обратите внимание на то, что время выполнения программы L, усовершенствованной в упр. 33, составляет только 358и.

37. Сформулированное тождество эквивалентно тождеству

„,+...+„М=ЛГ \ П1....ПМ. J

которое доказывается, как в упр. 34. Интересно, по-видимому, будет привести таблицу некоторых из этих производящих функций, чтобы выявить тенденцию, которая наблюдается при возрастании М:

94i{z)= {216+ 6482-1-108022-1-12962*-I-10802"-)-6482+21б2)/5184, 542(2) = (945 + 19172-1-148522+ 5942*+ 1352"+ 812+ 272в)/5184, Р4з(2) = (1704 + 22642+ 8402+ 3042*+ 402"+ 242+ 82)/5184.

Если Gm{u!, z) - сформулированная двойная производящая функция, то дифференцирование по z дает

М-1 „

GMiw,z) = M(£gn{z)) YlsniK

n>0 n>0

Следовательно,

9MN{l)-r=Me [-e j =--i

JV>0

Аналогично из формулы дп{1) = §(4) + (з) следует, что

е 91.Л1) = М{М - 1)е<-2- (ie-y + Ме-- («;" + и,*) е».

Приравнивание коэффициентов приги даетр5ул(1) = ()М~\рл(1) = (() + (з))х хМ~2 и оказывается, что дисперсия равна (К) + ())