Mamy losowy ciąg w postaci kluczy, np. o rozmiarze: n = 10 albo 100 tys. - typowy słownik.
Pytanie: jaka jest najbardziej prawdopodobna najdłuższa już 'posortowana' seria - podciąg w takim ciągu = seria?
Posortowana seria znaczy tyle, że kolejne klucze rosną w ramach tej serii, np. taki przykład:
abba < baba < cudo < igła < kra < rasa < rosa;
długość serii = 7;
Albo inaczej: jak długi ciąg (losowy) musi być, aby zawierać w sobie serię o długości k (z prawdop. 50%)?
len_max_seria(n) = k;
Do testowania można wykorzystać prosty random, który generuje ciągi liczb o rozkładzie liniowym.
Wystarczy random 32 bitowy.
Generujemy ciąg n liczb, np. n = milion, i sprawdzamy jaką najdłuższą serię zawiera: k.