Təsadüfi Gəzinti

Maymunların Pul Atma Ordusu (ACM) təsadüfi ədədlər yaratmaqla məşğuldur. Təsadüfi ədədlər kriptoqrafiya, onlayn qumar, təsadüfi alqoritmlər və proqramlaşdırma yarışmalarında son dəqiqə həlləri kimi bir çox sahədə vacibdir.

Son vaxtlar, ən yaxşı maymunlardan biri təqaüdə çıxdı. Lakin, getməzdən əvvəl, o, pul atan maymunların yaratdığı təsadüfiliyi birbaşa istifadə etməkdən daha ucuz bir üsul icad etdi. Bu metod, 2^n düyünləri $0$, $1$, $\dots$, 2^n - 1 ilə işarələnmiş istiqamətsiz qrafı götürməklə başlayır. $k$ təsadüfi $n$-bit ədədləri yaratmaq üçün, maymunlar qrafda haradan başlayacaqlarını qərar vermək üçün $n$ sikkə atacaqlar. Bu düyün nömrəsi ilk çıxış ədədi olacaq. Sonra maymunlar bu düyündən təsadüfi bir kənar seçəcək və bu kənarın bağlandığı düyünə keçəcəklər. Bu yeni düyün ikinci təsadüfi ədəd çıxışı olacaq. Sonra bu düyündən təsadüfi bir kənar seçəcəklər (mümkün ki, son addımda gəldikləri düyünə geri), onu izləyəcəklər və endikləri düyünün nömrəsini çıxış edəcəklər. Bu gəzinti $k$ ədəd çıxış edilənə qədər davam edəcək.

Eksperimentlər zamanı ACM fərqli qrafların fərqli çıxış paylanmaları verdiyini müşahidə edib, bəziləri çox da təsadüfi deyil. Buna görə də, təsadüfiliyin satılacaq qədər keyfiyyətli olub-olmadığını yoxlamaq üçün qrafların test edilməsində köməyinizə ehtiyac duyurlar.

Onlar qrafı yaxşı hesab edirlər əgər, yaradılan hər $k$ ədədin hər $n$ bitində, bu bitin $1$ olaraq çıxış edilmə ehtimalı $25\%$-dən böyük və $75\%$-dən kiçikdirsə.