Urganch davlat universiteti axborot texnologiyalari kafedrasi

Masalani yechish. Barcha masalalarda ketma –ketliklar uchraydi, ular qandaydir joydan boshlab 

o‘nlik  bo‘lib qoladilar.  Ularning  sikllanishini  yunon  har    (ro)  ko‘rinishida  tasvirlash  mumkin: 

chiziqning boshlanishi bor, oxiri esa  yo‘q hisobi-chiziq ovalcha aylanadi  va siklik takrorlanadi. 

Bunday  ketma-ketliklarda  takrorlanishishlarni  va  sikllarni  izlash  uchun    -  algaritm  deyiluvchi 

algaritmdan foydalanadilar. 

  -algoritm  manosi  quyidagicha.  Faraz  qilaylik,  a

1

,a

2

,  ….  (rekurent  jarayon  holatlari)  ketma-

ketlik  elementlarining  qiymatlari  yakuniy  to‘plamgamansub  bo‘lib,  rekurent  munosabat 

yordamida  hisoblanadi  va  qandaydir  tartib  raqamidan  boshlab  sikilni  hosil  qiladi.  Rekurent 

munosabat  yordamida  algoritm 

va  shu  kabi  qiymatlar  juftligini 

shakllantitadi.  Juft  sikllardagi  elementlar  orasidagi  “masofa”  hamma  vaqt ortib boradi,  shuning 

uchun  ertami  yo  kech  boshlanayotgan  skilning  uzunligiga  muqarrar  karrali  bo‘lib  qoladi,  ya’ni 

qandaydir  I  ga 

ning  qiymatlari  mos  tushadilar.  Shunday  qilib 

 

ning  tengligi  sikl 

namoyon  bo‘lganligini  bildiradi,  bu  sikl  esa  I  –inchi  elementda  kech  bo‘lmagan  holda 

boshlanadigan va I dan katta bo‘lmagan uzunlikga ega. 

Bunday  formulirovkada    -  algoritmni  va  elementlarining  qiymatlari  umuman  o‘zgarishdan 

to‘xtaydigan  qandaydir  odimdan  boshlagan  xolni  ham  sikl  deb  ataydilar.  Biroq,  bir  tomondan 

buni  tekshirish  qiyinmas,  boshqa  tomondan  esa  ushbu  masaladagidek  ko‘pincha  ushbu  xolni 

ajratib ko‘rsatish kerak emas. 

---

Agar rekkurent jarayonning navbatdagi holati faqatgina oldingisi bilan to‘liqligicha aniqlansa   -

algaritm to‘g‘riligi aniqdir. Masalan, agar ketma-ketlik qiymati oldingi ikkitasiga bog‘liq bo‘lsa, 

u holda “holat” deb ikkita ketma-ket keluvchi elementlarining qiymatlarini hisoblash kerak. 

 

  algoritmning  asosiy  afzalligi  –  juda kam  xotira  yo‘qotib  sikl  haqida bilish  imkoniyati 

mavjud: Faqatgina ikki – uch holat saqlanadi. Asosiy kamchiligi – u sikl uzunligi va boshlanishi 

haqida  aniq  axborot  bermaydi.  Ushbu  kattaliklarning  juda  ham  muvaffaqiyatsiz  nisbatida  u 

ancha uzoq vaqat boshlangan siklni “sezmasligi” mumkin. 

To‘g‘ri  kasrni  o‘nlik  taqdim  qilinishini  tuzish  uchun    algoritmni  ishlatamiz.  Avvalo  r

i

=r

2i

 

bo‘lgandagi  I  ni  topamiz.  Keyin  esa  so‘nngi  tartib  raqam  last  topiladi,  bunda  r

lost

  =r

2i

.  Davr 

uzunligi  periotLength  r

2i

  -  r

lost

  bo‘ladi.  Keyingi  etapda  davr  boshini  topish  uchun  r

1

,r

2

,…  va 

r

1+period length

, r

2+period length

,…, qoldiqlar ketma ketligidan hamda d

1

, d

2

,… va d

1+period length

, d

2+period 

length

  raqamlardan  foydalanamiz.  “Kech  qolayotgan”  ketma-ketlikning  raqamlarini  davrdan 

oldingisi  singari chiqaramiz.  d

i

= d

1+period  length

 va r

i

= r

1+period  length

  tengliklar davr boshlanganligi 

haqida dalolat beradi. Keyin esa davrni  yoki u  o‘ta uzun bo‘lsa uning boshlanishini chiqaramiz 

(4.6-listing). 

4.6-listing. To‘g‘ri kasirning o‘nlik taqdim qilinishi.