Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 22
Текст из файла (страница 22)
(Алгоритмы для критериев собирания купонов и монотонности подобны этому ) После реализации алгоритма О Хз-критерий применяется при й = 1+ 1 к значениям СООИТ[О], СООНТ[Ц, ..., СООйТ[1] с использованием следующих вероятностей: р =р(1-р)" для О <г < Ф вЂ” 1; 1ь. =(1 — р) .
(4) Здесь р = б-а — вероятность того, что а < У < ~3. Значения и и г выбираются, как обычно, чтобы ожидаемое значение СООИТ[г] равнялось 5 илн больше (желательно больше). Критерий интервалов часто применяется при а = 0 или ф = 1 для того, чтобы на шаге 63 обойтись без одного сравнения. Особые случаи (о, ~3) = (О, -') и ('-, 1) иногда называются "отклонение выше среднего" и "отклонение ниже среднего" соответственно. Вероятности в (4) получить легко, и мы это осщвляем читателю. Заметим, что для критерия интервалов, описанного выше, необходимо получить и интервалов определенной длины. Однако таких интервалов в количестве н может не оказаться.
Если последовательность (У„) недостаточно случайна, то алгоритм О может не закончиться. Поэтому можно предложить другой критерий интервалов, требующий фиксированное число значений У; (см. упр, 5). П. Покер-критерий (крнтернй разбиений). "Классический" покер-критерий рассматривает п ~руин по пять последовательных целых чисел (Уху, Уэу„.ыузуч.з, )э~+э,Уху+4) для О < 1 < п и проверяет, какие из следующих семи комбинаций соответствуют таким пятеркам чисел (порядок не имеет значения). Хз-критерий основан на подсчете числа пятерок в каждой категории.
Уместно рассмотреть какую-нибудь упрощенную версию этого критерия, для которой можно использовать более простые программы. Хорошим компромиссом Все числа разные: Одна пара: Две пары: Три числа одного вида: Полный набор: Четыре числа одного вида: Пять чисел одного вида: аабсИ ааЬЬс аааЬс аааЬЬ ааааЬ ааааа будет крятернй, использующий более простой подсчет р»»личных значений в мно- жестве пятерок. В этом случае можно выделить только пять категорий: 5 значений = все разные; 4 значения = одна пара; 3 значения = две пары или три числа одного вида; 2 значения = полный набор или четыре числа одного вида; 1 значение = пять чисел одного вида. При такой схеме упрощаются подсчеты н критерий остается почти таким же хорошим. В общем случае можно рассматривать н групп Й последовательных чисел и подсчитывать число групп нз й чисел с г различными числами.
Затем применяется ~э-критерий, в котором используются вероятности того, что в группе г различных чисел (Числа Стирлннга [ь) определены в разделе 1.2.6 и могут быть подсчитаны по приведенным в ием формулам.) Так как вероятности р„очень малы, когда г = 1 или 2, следует, вообще говоря, перед применением с~-критерия объединить несколько категорий, имеющих малые вероятности, в одну. Чтобы получить формулу для р„, следует подсчитать, сколько д" групп из Й чисел, расположенных между 0 и Ы вЂ” 1, имеют точно г различных элементов, и разделить это число на И".
Так как дф-1)... (д — г+1) — это число упорядоченных наборов из г элементов множества, содержащего й элементов, достаточно показать, что [ „) -- зто число способов разбиения множе»тва из и элементов на точно г частей. Ф Поэтому в упр. 1.2.6-64 завершается доказательство равенства (»). Е. Критерий собирания купонон. Следующий критерий соотносится с покер- критерием, так как критерий интервалов соотносится с критерием частот. Используется последовательность у», 1ы ° ° ° н находятся длины отрезков 11-ы ~ 1 1 ~э ~ ° ° > '1 ~.>г~ содержащие "'полный набор" целых чисел от 0 до д — 1.
Алгоритм С описывает эту процедуру. Алгоритм С (Данные длл крнпырил с»бнр»нил купонов). Если дана последовательность целых чисел 1», К~,..., таких, что 0 < уу < 6, то алгоритм подсчитывает длины и последовательных "собравших купоны" отрезков. После реализации алгоритма СООИТ[г) — это число отрезков длиной г для Ы < г < г, а СОШПЯ вЂ” это число отрезков длиной > б С1.[Инициализация.[ Присвоить г' ~- -1, г <- 0 и присвоить СОШ~Т[г[ +- О для 4<г<б С2. [Присвоить д и г значение 0.[ Присвоить д +- г <- 0 и присвоить ОССМВБ[л]»- 0 для 0 < х < И. СЗ.
[Следующее наблюдение.) Увеличить г и,у на 1. Если ОССОНЗЩ ф О, повторить этот шаг. Р1. [Инициализация.) Присвоить г ~- г, у <- О. (В этом алгоритме всегда будет выполняться неравенство О < У < 1)/г!.) Р2, [Найти максимум.[ Найти максимум ((7м...,бг,). Если У, — это максимум, присвоить ~ с- г ~+ е — 1. РЗ. [Замена.) Заменить 6', еэ сГ,. Р4. [Уменыпить г [ Уменьшить г на 1. Если и > 1, то вернуться к шагу Р2. 9 Последовательность (Ггм..., Ц) будет расположена в порядке возрастания, когда алгоритм остановит работу. Чтобы доказать, что функция у единственным образом тарактперизретпся начальным порядком ((7м..., (7г), заметим, что алгоритм Р может быть обращен.
Длит=2,3,...„г присвоить э < — у шог(г, У +- [УЯ н заменить б'„и (7,+1. у = (. (Сг-1 х ($ — 1) + с~ г) х (1 — 2) + ° ° ° + сг) х 2+ сг = (à — 1))сг 1+ (1 — 2)(сг г+ ° ° + 2! сг+ 1! см где "цифры" сг — это целые числа, удовлетворяющие неравенствам О<от<у для 1<1<6 В алгоритме Р с, ~ = е — 1, когда шаг Р2 выполнен для заданного значения г.
С. Критерий монотонности. В последовательности можно проверять распределение восходящих и нисходящих серий. Имеется в виду проверка распределений длин мемопюмммт частей заданной последовательности (отрезки возрастания или убывания), В качестве примера точного определения серии рассмотрим последовательность цифр "1298536704". Проводя вертикальные линии слева, справа, а такгке между Х и Х1~.г всякий раз, когда Х > Х +м получим [1 2 9[8[5[3 6 7[0 4[.
(9) Таким образом выделяется восхадящие серии: сначала — серия длиной 3, за; тем — две серии длиной 1, затем — снова серия длиной 3 и, наконец, серия длиной 2. В алгоритме из упр. 12 показано, как твбулировать длину восходящей серии. Мы не будем применять Хг-критерий к подсчету серий, клк в критерии витервалов и критерии собирания купонов (которые во многих других отношениях Легко видеть, что это разрушит эффект шагов Р2-Р4. с,ледовательно, не существует двух перестановок, которые могут иметь одно и то же значение у, и алгоритм Р обоснован. Главной идеей„которая лежит в основе алгоритма Р, является представление со смешанным основанием, называемым "факториальной числовой системой": каждое целое число на отрезке О < у < й может быль единственным образом записано в виде подобны этому критерию), поскольку смежные интервалы не являются независимы- ми. Длинные серии имеют тенденцию следовать за короткими и наоборот.
Такого отсутствия независимости достаточно, чтобы применение кт-критерия было непра- вомочным. Вместо этого можно подсчитать следующую статистику для случая, когда длины серий определены так, как в упр. 12: )х = — ~ (СООйтЯ вЂ” пЬ1)(ОООйт(Я вЂ” пЬ )о4, 1 (10) 1< 4<0 где и — длина последовательности н матрицы коэффициентов А = (аб)1<,1<0 и 8 = (54)1<4<0 заданы в следующем виде: 1 0 3 24 П 120 10 220 20 2040 1 4529.4 9044.9 13568 9044.9 "18097 27139 13568 27139 40721 18091 36187 54281 22615 45234 67852 27892 55789 83685 18091 22615 27892 36187 45234 55789 54281 67852 83685 72414 90470 1П580 90470 113262 139476 111580 139476 172860 040 811 = т21 = 221 = А4 = Аэ = Аэ = 220 = 220 = 210 = А20 = 1 а все оСтальные ЕО равны нулю.
В этих обозначениях ~р = ~р1 +рз+'''+ ~~ представляет собой число серий длиной ) р и (12) Лр = й' — Яр+1 (13) является числом серий, длина которых точно равна р. Наша цель — подсчитать сРеднее значение (шеап) хгр., а также коеаРиацпю (сотах) сочах(Яр, 4Ч4) = теап((х(р — шеап(14р) ) (В4 — шеап(Вд)) ), (Значения 041, приведенные здесь, только приблизительны; точные значения могут быть получены из формул, приведенных ниже.) Статистика 1' в (10) должна иметь Кз-распределение с шесгью, а не пятью, степенямн свободы, когда и большое. Значение п должно, скажем, равняться 4 000 или больше.
Тот же критерий можно применить к нисходящей серии. Значительно более простой н более практичный критерий монотонности приведен в упр. 14, так что читатель, интересующийся только проверкой генераторов случайных чисел, может пропустить несколько страниц и перейти к критерию "максимум-1" после выполнения этого упражнения. С другой стороны, с математической точки зрения поучительно увидеть, как можно изучить сложный критерий монотонности со взаимно независимыми сериями. Так что на некоторое время мы отклонимся в сторону.
ПУсть заДана. пеРестановка п элементов. ПУсть йр, = 1, если положение 1 является началом возрастающей серии длиной р или больше, н пусть Яр1 = 0 в других случаях. Например, рассмотрим перестановку (9) с и = 10. Легко видеть, что являющуюся мерой зависимости Вр и Вр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
