Фундаментальные алгоритмы и структуры данных в Delphi

{объединить две первые категории - это будет сумма категорий "все цифры одинаковы" и "две разные цифры"}

inc(Bucket[1], Bucket[0]);

Expected := (p[0]+p[1]) * NumFives;

ChiSqVal := Sqr(Expected - Bucket[1]) / Expected;

{обработать другие категории}

for i := 2 to 4 do

begin

Expected :=p[i] * NumFives;

ChiSqVal := ChiSqVal + (Sqr (Expected - Bucket [i]) / Expected);

end;

{вернуть значения}

ChiSquare := ChiSqVal;

DegsFreedom := 3;

end;

Тест "сбор купонов"

Четвертый тест, который мы будем проводить, называется "сбор купонов" (coupon collector's test). Случайные числа считываются по одному и преобразуются в "купоны" - числа от 0 до 4. Фиксируется длина последовательности до получения полного комплекта купонов (т.е. цифр от 0 до 4). Очевидно, что получаемые длины будут от пяти и выше. После набора полного комплекта сбор купонов начинается снова. Длины последовательностей разбиваются на категории, к которым затем применяется тест по критерию хи-квадрат. Как правило, используются категории для длин от 5 до 19 и еще одна дополнительная категория для больших длин. Таким образом, мы получаем 16 категорий, а, следовательно, 15 степеней свободы. Как и в тесте "покер", вычисление вероятностей для каждой из категорий включает сложные математические выкладки, которые в этой книге не приводятся. Соответствующие подробности можно найти в [11].

Листинг 6.8. Тест "сбор купонов"

procedure CouponCollectorsTest(RandGen : TtdBasePRNG;

var ChiSquare : double;

var DegsFreedom : integer);

var

NumSeqs, LenSeq, NumVals, NewVal, i : integer;

Expected, ChiSqVal : double;

Bucket : array [5..20] of integer;

Occurs : array [0..4] of boolean;

p : array [5..20] of double;

begin

{вычислить вероятности для каждой категории событий, алгоритм Кнута}

p[20] := 1.0;

for i := 5 to 19 do

begin

p[i] := (120.0 * Stirling(i-1, 4)) / IntPower(5.0, i);

p[20] := p[20] - p[i];

end;

NumSeqs := 0;

FillChar(Bucket, sizeof(Bucket), 0);

while (NumSeqs < CouponCount) do

begin

{продолжать сбор купонов (т.е. случайных чисел) до получения полного набора из пяти купонов}

LenSeq := 0;

NumVals := 0;

FillChar (Occurs, sizeof(Occurs), 0);

repeat

inc(LenSeq);

NewVal := trune(RandGen.AsDouble * 5);

if not Occurs [NewVal] then begin

Occurs[NewVal] := true;

inc(NumVals);

end;

until (NumVals = 5);

{обновить значение для соответствующей категории в зависимости от количества собранных купонов}

if (LenSeq > 20) then

LenSeq := 20;

inc(Bucket[LenSeq]);

inc (NumSeqs);

end;

{вычислить значение xu-квадрат}

ChiSqVal := 0.0;

for i := 5 to 20 do

begin

Expected := p [ i ] * NumSeqs;

ChiSqVal := ChiSqVal + (Sqr(Expected - Bucket [i]) / Expected);

end;

{вернуть значения}

ChiSquare := ChiSqVal;

DegsFreedom := 15;

end;

Результаты выполнения тестов

В разделе сопровождающих эту книгу материалов, который расположен на Web-сайте издательства, можно найти тестовую программу, которая применяет все рассмотренные нами тесты к стандартному генератору случайных чисел Delphi и минимальному стандартному генератору случайных чисел. На рис. 6.1 приведены результаты проведения одного из тестов для генератора случайных чисел Delphi.

Рисунок. 6.1. Тестирование стандартного генератора Delphi

Как видите, данный конкретный тест свидетельствует о том, что стандартный генератор Delphi успешно прошел проверку. (под успешным прохождением теста понимается, что предложенная к тестированию последовательность случайных чисел не дает результатов, которые являются значимыми на уровне 5%.)

Окно в правой части окна программы представляет собой снимок случайных чисел, полученных на выходе генератора. Координаты точек вычисляются на основе двух случайных чисел: первого для оси х, а второго - для оси Y. После этого точки выводятся в окне, если они находятся в прямоугольнике (0.0, 0.0, 0.001, 1.0) или, другими словами, в прямоугольнике, нижний левый угол которого расположен в точке (0.0, 0.0), а верхний правый - в точке (0.001, 1.0). Чтобы распределение точек было удобнее изучать, прямоугольник растянут по оси х. Как видите, на рисунке точки случайным образом разбросаны по всему прямоугольнику. Никакой системы при этом не наблюдается.

У вас может возникнуть удивление, зачем мы так много говорим об этом окне. Посмотрите на рис. 6.2, на котором показана та же программа, но для минимального стандартного генератора случайных чисел. Как видите, и этот генератор успешно прошел все тесты, но посмотрите на распределение случайных точек. Очевидно, что генератор дает последовательность случайных чисел, которые при переносе их на график формируют определенный регулярный рисунок.