Urganch davlat universiteti axborot texnologiyalari kafedrasi

Tehnik cheklov: m 200000000. 

Misollar . 

Kirish                                

 

 

Chiqish 

3 

4 

 

 

 

 

 

0,75(0) 

1 

6 

 

 

 

 

 

0,1(6) 

---

1 

199999999 

 

 

 

0,(000000005…)(12343056) 

Masalaning tahlili: To‘g‘ri K/m kasrni   d

1

, d

2

, ... ,p-inchi taqdim qilinishining raqamlarini olish 

maqsadida qoldiqli ko‘paytirish va bo‘lish kerak: d

1

=K*p div m, r

n

=K*p mod m, d

2

 =  r

n

 *p div 

m, r

2

 =  r

n

 *p mod m va shu kabilar (d

i

 =  r

i-1

 *p div m, r

i

 =  r

i-1

 *p mod m). 

Agar  navbatdagi  qoldiq  r

i

=0  bo‘lsa,  u  holda  barcha  keyingi  raqamlar  nollar  bo‘ladi,  ya’ni 

ko‘rinish  0,  d

1

,d

2

…  d

i

(0)  ko‘rinishga  ega  bo‘ladi.  Agarda  barcha  qoldiqlar  nolga  teng 

bo‘lmasalar,  u  holda  p-inchi  ko‘rinish  cheksiz  va  davriydir  (balki,  juda boshidan  bo‘lmasa):  0, 

d

1

,d

2

…  d

i

(d

i+1

d

i+2

…  d

j

)  bu  yerda  i 0,  j-1 1.  Davr  undan  keyin  boshlanadigan  minimal  i  ni 

topish kerak. 

Masala  shartida  p=10,  m 200000000,  shuning  uchun  hisoblashlar  uchun  longint  tipidagi 

standart  arifmetika  yetarli.  O‘z-o‘zidan  kelib  chiqadigan  yechim  shundaki  navbatdagi  qoldiqni 

oldingilar  bilan  taqqoslash  hisoblanadi-birinchi  takrorlanish  davr  boshlanishi  ko‘rsadi.  r

j

-

navbatdagi qoldiq bo‘lsin. Agar qandaydir i da r

j

 = r

i

 bo‘lsa, u holda d

j

 = d

i

 da d

i

 … d

j-1

 davr 

bo‘ladi,  aks  holda  esa-  d

i+1

  …  d

j

.  Oldingi  qoldiqlarni  saqlash  uchun  longint  tipidagi  sonlar 

massivi zarur bo‘ladi.  

Qoldiqlar massivining zarur uzunligini baholaymiz. m ga bo‘lishdagi nolga teng bo‘lmagan turli 

xil qoldiqlar miqdori m-1 ga teng va ularning barchasi davrda paydo bo‘lishlari mumkin. Bundan 

tashqari va m-1 dan katta bo‘lmagan so‘ngi birinchi takrorlangan qoldiq 1 dan kichik bo‘lmadan 

tartib  raqamga  ega  bo‘lishi  mumkin.  Shunday  qilib,  massiv  o‘lchami  m-1  dan  2m-2  gacha 

oraliqda  bo‘lishi  mumkin.  Biroq  m  2*10

8

  gacha  yetishi  mumkin  va  longint  tipidagi  elementlar 

massivi umumiy o‘lchami 800 MBaytdan ko‘p emas, har bir yangi qoldiq bilan o‘tish kerak – bu 

qo‘rqinchli. 

Nazariy jihatdan bunday o‘lcham xotirasi topiladi deb taxmin qilish mumkin va 1.6-masalaning 

yechimini  yodga  olish  kerak.  Nolni  massivlarni  initsializatsiyalaymiz  va  r  indeksi  elementga  r 

qoldiq  olingan  qadamning  tartib  raqamini  o‘zlashtirib  olamiz.  Shunga  qoldiq  takrorlanishini 

tekshirish 0(1) vaqtni talab etadi, bu esa 0(m) murakkablikdagi summa baholashga yetib olishga 

imkon beradi. Biroq deyarli bularning barchasining imkoni yo‘q va asosiysi kerak emas, chunki 

umuman massivlarsiz ham uddalash mumkin.