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

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

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

Четвертый тест, который мы будем проводить, называется "сбор купонов" (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;

Оглавление книги