Четвертый тест, который мы будем проводить, называется "сбор купонов" (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 : integers-Expected, ChiSqVal : doubles-Bucket : array [5. .20] of integers-Occurs : array [0..4] of boolean;
p : array [5. .20] of double;
begin
{вычислить вероятности для каждой категории событий, алгоритм Кнута) р[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), Ob-repeat inc(LenSeq) ;
NewVal := t rune (RandGen. As Double * 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;

Тест "покер" || Оглавление || Результаты выполнения тестов


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



Новости за месяц

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс