Кездейсоқ тізбектердің периоды мен апериодтылығының ұзындылығын сынақ арқылы анықтау

Жоғарыда келтірілген деректерден анық көрінетін бір ерекшелікті қарастырайық. Ол ерекшеліктің мәіні мынада. Кездейсоқ сандар тудыратын әдістердің бәрі де, оларды компьютерде қолданғанда, периодикалық тізбек тудырады. Шынында, кез-келген компьютердің кодында [0;1] арадығында жататын әр түрлі сандардың тек шекті мөлшерін ғана жазуға болады, сондықтан ерте ме, кеш пе z_L санының мәні алдындағы сандардың мәндерінің біреуімен, мысалы -мен, сәйкес келеді. Онда келесі теңдік тура болады:

(1.10)

...

ι

...

L-1

L

i

L

P

Сурет

L - (1.10) шартын қанағаттандыратын, ең кіші сан болсын. Сонда сандар жиыны кездейсоқ тізбектің апериодты кесіндісі деп аталады (1.3-сурет). Ал, L апериодтылық кесіндінің ұзындығы, (L-1) мәні периодқа тең екені 1.3-суреттен айкын көрінеді, яғни P=L-l. Сонымен, тізбек тек кездейсоқ сандардан тұруы үшін оның ұзындығы апериодтық кесіндінің ұзындығынан аспауы тиіс. Сондықтан L мен р-ң нақты мәндерін таба білу керек. L мен P-ң мәнін сынақ арқылы анықтаудың бір әдісіне тоқтайық [9, 10].

{ }- жоғарыда көрсетілген алторитмдердің біреуінің көмегімен алынған кездейсоқ сандар тізбегі болсын. Осы тізбектің индексі l-p айырымынан біраз үлкен мүшесіи жадымызда сақтап қаламыз (1.4.-сурет). Сонан соң -ді - сандарының біреуімен сәйкес келгенше салыстырамыз. Ерте ме, кеш пе, осы салыстырудың нәтижесінде мына тендікке жетеміз:

z_N = z_k (k> N).

P

P

P

N

Kcc

Lcc

P

P

K

N

Lcc

Сурет

Демек, k-N=р тізбек периодының ұзындығы. Содан соң, берілтен алгоритммен мынандай екі кездейсоқ тізбекті қатар генерациялаймыз:

және осы тізбектердін, қатар алынған мүшелерін, олар бір-біріне

теңелгенше, яғни мына теңдеу:

орындалғанша салыстырамыз. Сонда (1.12) тізбегінің сәйкес келген мүшесінің номері апериодтылығының ұзындығын анықтайды. Айтылғандарды мынадай алгоритм түрінде келтірейік:

1-қадам. i= 1, R = о деп аламыз, мұндағы R - тізбек периодының ұзындығы әлі табылмағандығының белгісі.

2-қадам. Кездейсоқ тізбектің кезекті мүшесін генерациялау.

3-кадам. i = i +1 болсын.

4-қадам. R = о шартын тексеру. Бұл шарт орындалмаса 7-қадамды орындау керек.

5-қадам. i = N+1 шартын тексеріп, ол орындалмаған жағдайда 2- қадамға көшу керек.

6-қадам. Y= және r = r +1 деп алып, 2 -қадамға көшу керек.

7-қадам. = ү шартын тексеріп, ол орындалмаған жағдайда 2-қадамға қайту керек.

8-қадам. Периодтың ұзындығын мына өрнектен P= і - N анықтап алып, і -ді бірге теңеу керек: і = 1.

9-қадам. Зерттеліп отырған кездейсоқ тізбектің және мүшелерінің мәндерін қайтадан табу керек.

10-қадам. = , шартын тексеріп, ол орындалған жағдайда, 12-қадамға көшу.

11-қадам. і = і + 1 деп алып, 9-қадамға қайтып бару.

12-қадам. Апериодтық кесіндінің ұзындығын мына өрнектен L = P + і айқындау.

13-қадам. р мен L –дің мағынасын компьютердің мониторына әлде принтерге шығару.