Urganch davlat universiteti axborot texnologiyalari kafedrasi

procedure fraction(numerator,denumerator:

longint

); 

  last:

longint

; 

  i,i2:

longint

; 

  r,r2:

longint

; 

  d,d2:

longint

; 

  periodLength,outputLength:

longint

; 

begin 

  r:=numerator; 

  i:=

1

;i2:=

2

; 

  r:=

10

*r 

mod denumerator; 

  r2:=

10

*r 

mod denumerator; 

 

while r<>r2 do begin 

  r:=

10

*r 

mod denumerator; 

  r2:=

10

*(

10

*r2 

mod denumerator) mod denumerator; 

  inc(i);inc(i2,

2

); 

 

end; 

 last:=i; 

 

while (i

1

) 

do begin 

  r:=

10

*r 

mod denumerator; 

  inc(i); 

  

if r=r2 then last:=i; 

 

end; 

 periodLength:=i2-last; 

 d:=

10

*numerator 

div denumerator; 

 r:=

10

*numerator 

mod denumerator; 

 r2:=r; 

 

for i:=

1 

to periodLength do begin 

  d2:=

10

*r2 

div denumerator; 

  r2:=

10

*r2 

mod denumerator; 

 

end; 

 write(

'0,'

); 

 

while (r<>r2) or (d<>d2) do begin 

  write(d); 

---

  d:=

10

*r 

div denumerator; 

  r:=

10

*r 

mod denumerator; 

  d2:=

10

*r2 

div denumerator; 

  r2:=

10

*r2 

mod denumerator; 

 

end; 

 write(

'('

,d); 

 

if periodLength<=

100 

then 

  outputLength:=periodLength 

 

else outputLength:=

100

; 

 

for i:=

1 

to outputLength-

1 

do begin 

  d:=

10

*r 

div denumerator; 

  r:=

10

*r 

mod denumerator; 

  write(d); 

 

end; 

 

if outputLength<>periodLength then write(

'...'

); 

 write(

')'

); 

 

if outputLength<>periodLength then write(

'('

,periodLength,

')'

); 

 readln; 

 

end;

 

Yechimning taxlili. Keltirilgan prosedura bo‘yicha amallarning umumiy miqdorini baholaymiz. 

Birinchidan  tashqari  barcha  sikllar  shak-shubhasiz  (m)  murakkablik  bahosiga  ega.  Birinchi 

siklni aniq baholash juda ham oddiy emas, biroq xaqiqada u ham  (m) ga teng. Bu yerda yechim 

murakkabligi  –  (m),  bunda  hamma  vaqt  gap  (m)  haqida  emas:  aynan  (m)  haqida  boryapti, 

amallar miqdori o‘ta murakkab K va m juftlar uchun m atrofida, biroq ko‘plab juftlar uchun esa – 

juda kam bo‘ladi. 

K va m lar – kiruvchi sonlar qiymatlari (ularning  ikkilik sistemadagi uzunliklari emas) bo‘lgani 

uchun qarab chiqilgan algoritm psevdo polinominal hisoblanadi. 

4.4.2. Fibonachchi sonlarini bo‘lishdagi qoldiqlar. 

4.7-masala.  Fibonachchi  sonlari  deyiluvchi  ma’lum  bo‘lgan  rekurent  ketma-ketlikda  har  bir 

element  (ikkita  boshlang‘ichlari-dan  tashqari)  oldingi  ikkitasining  summasi  hisoblanadi:  F

0

=0, 

F

1

=1,  F

n

=  F

n-1

+  F

n-2

  n 2  ga  n-inchi  Fibonachchi  sonining    natural  songa  bo‘lishdan  qolgan 

qoldiq topilsin. 

Cheklovlar. 

, 

. 

Misollar. 

N                P                       Natija 

0 

7  

 

0 

6 

16 

 

 

8 

12 

10 

 

 

4 

Masalaning taxlili va yechimi. Buneking 

---

 

 formulasi n- Fibonachchi sonini to‘g‘ridan-to‘g‘ri 

uning  tartib  raqami  bo‘yicha  imkon  beradi.  Biroq  dasturlash  uchun  undan  foyda  yo‘q  –  real 

kompyuterlarda  iratsional  sonlar  bilan  aniq  amallarni  bajarish  mumkin  emas,  taxminiy 

hisoblashlar esa bo‘lishdan qolgan qoldiqni topishga imkon bermaydi.  

Fibonachchi  sonlarini  hisoblashning  “oddiy”  algoritmini  va  (4.6)  formulani  yodga  olamiz 

(ularsiz  hech  nima  qilib  bo‘lmaydi  –  F

2000000000

>10

400000000

,  ya’ni  hatto  “uzun  arifmetika” 

ishlatilganida ham massivlar o‘lchamlari juda katta, ishlash vaqti esa – astranomik bo‘ladi). 

 

f0:=

0

;f1:=

1

; 

for i:=

1 

to n do begin 

  f2:=(f0+f1) mod p; 

  f0:=f1;f1:=f2; 

end;

 

Masala  deyarli  yechildi.  Biroq  hozircha  siklni  ikki  marta  bajarish  yaxshi  emas.  Bundan 

qutulishning uchta uslubini qarab chiqamiz. 

Birinchi  uslub.    modul  (bu  yeda 

)  bo‘yicha  hisoblashlarga  o‘tganimizda  f0,  f1,  f2 

o‘zgaruvchilarning  ehtimoliy  qiymatlarining  to‘plamini  yetarlicha  katta  qilmaymiz.  Sikl 

yetarlicha  uzoq  vaqt  ishlaganida  oldin  hisoblangan  Fibonachchi  sonining  qoldig‘i  muqarrar 

paydo  bo‘ladi.  Buning  ustiga  qachonlardir  oldin  ham  aynan  ketma-ket  keluvchi  sonlarni  yana 

ketma-ket  kelishini  olamiz.  Biroq  shunda  barcha  ketma-ketlikning  aniq  siklik  takrorlanishlari 

so‘zsiz boshlanadi. Chunki agar ushbu ikki son oldin qanday bo‘lsa, shunday bo‘lsa, u holda (F

i-

1

+F

i-2

)  mod  p  kabi  aniqlanuvchi  navbatdagi  sonlar  ham  xuddi  shunday  bo‘lar  ekan  va  shu 

kabilar. 

Biroq  qandaydir  (noma’lum  nechanchi)  i-  qadamda  c  uzunlikdagi  qandaydir  sikl  boshlanishi 

faktida  foyda  kam.  Shuning  uchun  Fibonachchining  (n-1)-ga  va  n-sonlaridan  nafaqat  (n+1), 

balki (n-2)- sonlarini topish mumkunligiga e’tibor qaratamiz: F

n-2

=F

n

-F

n-1

. Hisoblashlar   modul 

bo‘yicha olib borilganligi tufayli F

n-2

 ni   

F

n-2

 mod   =( +F

n

 mod   - F

n-1

 mod  ) mod   

Munosabatdan foydalanib topamiz. Bu yerda  

F

i

 mod   = F

i+c

 mod        => F

i-2

 mod   = F

i-2+c

 mod   

F

i-1

 mod   = F

i-1+c

 mod   

Kelib  chiqadi.  Ushbu usulni  i-2  marta qo‘llab,  F

0

  mod    = F

c

  mod    ni  olamiz.  Shunday  qilib 

ushbu  masalada  sikl  boshlang‘ich  qiymatlarning  so‘zsiz  takrorlanishidan  boshlanadi.  Bu 

quyidagi fragment (n>0 uchun) bilan dasturni yozishga imkon beradi. 

Aylanishlarni hisobga olgan holda qisqarishlarni o‘tkazuvchi dastur fragmenti. 

 

f0:=

0

;f1:=

1

;c:=

0

; 

repeat 

  f2:=(f0+f1) mod p; 

  f0:=f1;f1:=f2; 

  c:=c+

1

; 

until (c>=N) or (f0=

0

) 

and (f1=

1

); 

  

if cthen begin 

    N:=N mod c; 

---

    

for i:=

1 

to N do begin 

      f2:=(f0+f1) mod p; 

      f0:=f1;f1:=f2 

    

end 

   end; 

 writeln(f0); 

 

Yechim taxlili. Taqdim qilingan yechimda amallar miqdorini baholash ancha murakkab: 

u  min{N,2c}  ga proporsional ekanligi ayon, biroq  c  siklning uzunligini qanday baholash kerak? 

Nazariy  jixatdan c-p

2

, biroq p

2

 – bu juda ko‘p. Shunday bo‘lsada xaqiqatda  min{N,2c}  nisbatan 

katta emas (p dagi ko‘rsatilgan cheklovlarda u deyarli hamma vaqt 10

5

 dan katta emas). 

Ikkinchi uslub. Quyidagicha ishonish qiyinmas: 

,                            bu yerda 

,  va  shu  kabi 

ya’ni  

. 

Agar  ushbu  tenglikda  F

k 

va  F

k-1

  o‘rniga  F

1

  =0  va  F

0

=0,  n  ning  o‘rniga  esa  n-1  ni  qo‘ysak, 

quyidagini  olamiz: 

.  Shunday  qilib,  bizning  masalada  F

n

  mod  p  ni 

hisoblash  uchun  arifmetikadagi  barcha  amallarni  p  modul  bo‘yicha  bajarib,  ko‘rsatilgan 

matritsani n-1 darajaga ko‘tarish yetarli. Buning uchun murakkablik bahosi O(log n) bo‘lgan 3.2-

bo‘limdagi algaritm asosida matritsalarni 2*2 darajaga ko‘tarishni amalga oshirish kerak. 

Uchinchi  uslub.  Fibonachchi  sonlari  uchun  F

n

=  F

k+1

*  F

n-k

+  F

k

*  F

n-k-1

  ayniyat  o‘rinlidir.  k=n 

mod 2 deb olib,  o‘zgarmas  amallar  miqdori  hisobiga  Fibonachchi  sonining  tartib  raqamini  ikki 

marta oshirish mumkin. Biroq bu  yerda  F

n

  ni taxminan  ikki marta tartib raqami kichik bo‘lgan 

bitta  Fibonachchi  soni  orqali  ifodalab  bo‘lmaydi.  Shuning  uchun  ma’lumotlarnining  sezgir 

strukturasini  ishlatib  eslab qoladigan  reversiyani  (tafsilotlari  13 bobga)  yozishga  to‘g‘ri  keladi. 

Shunday  ekan  bunday  uslubni  matritsa  darajaga  ko‘tarishga  qaraganda  o‘ylab  topish  osonroq 

bo‘lsada uni amalga oshirish o‘ta murakkab. 

Fibonachchi  sonini  hisoblashni  “tezkor”  metodlari  hamma  vaqt  ham  bunday  bo‘lavermasligini 

takidlaymiz.  Istalgan  arifmetikaning  bahosi 

  ni  tashkil  qiladi  deb  taxmin  qilinganida 

matritsani darajaga ko‘tarish uchun O(log n) baho va “maktab” metodi O(m) baho olingan. 

Agarda  Fibonachchi  sonlarining  aniq  qiymatlari  4.1-bo‘limdagi  uzun  arifmetika  yordamida 

hisoblansa,  vaziyat  umuman  boshqacha  bo‘ladi.  Matritsa  darajaga  ko‘tarib,  uzun  sonlarning  

O(log  n)  ko‘paytirishlarini  bajarishga  to‘g‘ri  keladi.  Binyo  formulasiga  binoan  k-  Fibonachchi 

sonini uzunligi O(k) ni tashkil etadi. Demak, faqat bitta ko‘paytma 

 ni “tashkil” etadi. Shu 

bilan  birgalikda  olingan  barcha  ko‘paytma 

  emas,  balki 

  turishiga  ishonish 

qiyin emas. 

Birinchi safar shunday ko‘ringanidek, keyin esa “maktab” varianti xuddi shunday 

 bahoga 

ega. Chunki u 

summator baholi 

 qo‘shiluvchilarni talab etadi. 

Demak maktab “varianti” o‘zining  oddiyligi tufayli g‘alaba qiladi. 

Chunonchi 4.3 mashqdagi elementlarni ko‘paytirish algoritmidan foydalanib matritsani darajaga 

ko‘tarish  mumkin.  Shunda baho 

  bo‘ladi va  fibonachchining  juda  kata 

sonlari (taxminan F

50000

>10

10450

 dan boshlab) “maktab” algoritmi bo‘yicha  hisoblagandan  ko‘ra 

tezroq hisoblanadi. 

4.5. Faktorial oxiridagi nollar. 

---

4.8-masala.  Natural  N  va  p  (har  ikkalasi  ham  2  dan  10

9

  gacha  diapazonda)  sonlar  berilgan.  p 

asosli hisoblash sistemasida yozilgan N! (faktorial) sonining nollar miqdori topilsin. 

Misol.  

Kirish: 7 10.  

Chiqish: 1 (7!  O‘nlik sistemada 5040 kabi  yoziladi. Ushbu yoziladi, ushbu  yozuv  oxirida bitta 

nollar). 

Masalaning  tahlili.  N!  soni  nafaqat  odatdagi  butun  tiplarga  sig‘masligi,  balki  uzun  arifmetika 

ishlatilganda  xotiraning mantiqqiy hajmiga ham sig‘masligini faxmlamoq qiyin emas. Masalada 

taxminiy ham modulyar arifmetikadan xam xech qanday foydasi yo‘qligi ham o‘z-o‘zidan ayon. 

Shunday  ekan  aynan  shu    masala  uchun    harakterli  bo‘lgan    qandaydir    qonunyatni  izlashga 

to‘g‘ri keladi . 

1  dan  10  gacha  bo‘gan  son  1  faktariallarining    qiymatlarini  jadvallarga  yozamiz.  Ustunlarning 

birinchi juftiga N va uning ko‘paytiruvchilariga  yoyilishini, ikkinchi juftga ikkilik sistemada N! 

va ushbu yozuvdagi nollar (qavslarga); uchinchi va to‘rtinchi juftlarga esa - xuddi 

shuning o‘zi 

o‘nlik va o‘n ikkilik sistemalarda ko‘rsatamiz. 

 

 

Ikkilik  bo`lmagan,  qarab  chiqamiz.  Avvalo  nollar  umuman  bo`lmagan,  2  ga 

ko`paytirilganida 1 ta no`l, 4=22 ga ko`paytirilganida 2 ta no`l, 6=2*3 ga ko`paytirilganida  – 1 

ta, 8=23 ga ko`paytirilganida – 3 ta no`l, 10=2*5 ga ko`paytirilganida esa – 1 ta no`l qo`shildi.  

2  ko`paytuvchisi  bo`lmagan  songa  ko`paytirilganida  ikkilik  yozuvning  oxiridagi  no`llar 

miqdori  o`zgarmasligini,  2k  ega  sonlarga  ko`paytuvchilarga  esa  nollar  miqdori  k  ga  ortib 

borishini ko‘ramiz. Bu qonuniyatni qat’iy isbot qilish qiyinmas.  

Ushbu kuzatish asosida masalan p=2 ga ega oladigan dastur fragmetini yozish qiyinmas: 

 

k:=

2

; NF_2:=

0

; 

while k<=N do begin 

  NF_2:=NF_2+N div k; 

  k:=k*

2

; 

end; 

 

Uni tushuntiramiz. Bu  yerda  N –  kiruvchi ma`lumotlardagi  N  soni,  NF_n o`zgaruvchida 

javob  ko`riladi  (nollar  soni),  K  o`zgaruvchi  yordamchi  kabi  ishlatiladi.  Nollar  miqdorini 

hisoblash  faktorialni  qadam  va  qadam  hisoblaganda  paydo  bo‘lganidek  tartibda  emas,  balki 

tartibda  yetishicha ayyorana va  yanada sollarlik usulda ro‘y beradi. Avvalo  K=2 da barcha juft 

ko`paytuvchilar lokal 1 ta nol bo‘lishini hisobga olinadi. Keyin esa K=4 da 4 ga karrali bo`lgan 

barcha  ko`paytuvchilar  laoqal  2  ta  nol berishi:  biroq ushbu  noldan 1 tasi  hisoblangan  bo`lishi, 

chunki  4  ga  karrali  son  juft  son  singari  hisobga  olindi,  shuning  uchun  NF_2  ga  4  ga  karrali 

---

bo`lgan  ko`paytuvchilar  miqdori  qo`shiladi  va  shu  kabi  jarayon  K>H  bo`lguncha  davom 

qilaveradi. Ya`ni 2 ning shunchalik katta darajalari ko`paytuvchilar orasida yo`q. Shunday ekan 

2 lik sistema bilan tushunib oldik. Biroq jadvalni qarashni davom qildirsak 10 lik sistemada holat 

birmuncha  murakkab  ekanini  ko`ramiz.  Aynan  N!  ning  oxirida  nollar  nafaqat  10  ga  karrali 

sonlarga, 5 soniga ko‘paytirilganda qanday no‘llarni paydo bo‘layotganini tushinish qiyin emas, 

10=2*5, shuning  uchun, agar ko‘paytmaning oldingi qiymatida “erkin” 2 ko‘paytuvchi bo‘lsa u 

holda  5  ga  ko‘paytirish  ko‘paytuvchilarning  ya’ni  (2;5)  juftligini  paydo  bo‘lishiga  va  demak, 

ko‘paytmaning  oxirida ya’ni 0 ning paydo bo‘lishiga olib keladi.  

Bu 

kuzatishni 

umumlashtirish 

qiyin 

emas. 

Agar 

sistemaning 

P 

asosi 

  kabi  oddiy  ko‘paytuvchilarga  yoyilsa  u  holda  oddiy  P

1

,  P

2

,...,  P

m

 

bo‘luvchilardan har biri uchun (alohida) N! dagi shunday ko‘paytuvchilar miqdorini hisoblaymiz 

4.9 fragmentdagi NF_2 bilan analogik ravishda. Son oxirida bitta 0 ning paydo bo‘lishi uchun P

1

 

ning k

1

 ko‘paytuvchilari, P

2

 ning k

2

 ta shu kabi kerak bo‘ladi yakuniy  javob (N! ning oxiridagi 0 

lar miqdori quyidagicha aniqlanadi:  

min {N F(P

1

) div k

1

, N F(P

2

) div k

2

,..., N F(P

m

) div k

m

,   }. 

Agar ushbu formula asosida quyidagi dastur ishlaydi unda Free Pascal dasturlash sistemasining 

tili  tomonidan  ishlatiladi  Dword  va  Qword  tipining  4  va  8  baytli  belgisiz  butun  sonlaridan 

foydalanilgan. 

4.7 listing, 4.8 masalani yechish. 

 

var N,p,p_,q,k:QWord; 

  primes:

array[

1..16

] 

of record; 

    val_,num_in_p:DWord; 

    num_in_fact:QWord 

  

end; 

  i,N_prime:

integer

; 

  N_zeroes:QWord; 

  

BEGIN  

    read(N,p); 

    p_:=p; 

    N_prime:=

0

; 

    q:=

2

; 

    

while p_>

1 

do begin 

      if p_ mod q=

0 

then begin 

        inc(N_prime); 

        primes[N_prime].val_:=q; 

        primes[N_prime].num_in_p:=

0

; 

     

repeat 

      p_:=p_ div q; 

      inc(primes[N_prime].num_in_p); 

     

until p_ mod q<>

0

; 

     

end; 

      inc(q); 

        

if q*q>p_ then q:=p_; 

     

end; 

    

for i:=

1 

to N_prime do begin 

      prime[i].num_in_fact:=

0

; 

      k:=primes[i].val_; 

    

while k<=N do begin 

      inc (primes[i].num_im_fact,N div k); 

        k:=k*primes[i].val_; 

---

     

end; 

     q:=primes[i].num_in_fact 

div primes[i].num_in_p; 

     

if (i=

1

) 

or (q

      

then N_zeroes:=q; 

     

end; 

    writeln(N_zeroes); 

   

END.

 

 

Xulosaga o‘nlik sistema uchun masala tahlil qilganda natijaga kelishi (o‘ylash) mumkin bo‘lgan 

bitta  o  no‘ldan  qutqaramiz.  2<5  bo‘lgani  uchun  ketma  ket  1.2.3.....  hisoblashda  hamma  vaqt 

“erkin” 2 ko‘paytuvchilar bo‘ladi va hech qachon “erkin” 5 ko‘paytuvchilar bo‘lmaydi. Shuning  

uchun  10  lik  sistema  uchun  “kretik”  oddiy  ko‘paytuvchi  bo‘lib  5  hisoblanadi  va  P=10  da 

masalani  yechish  uchun  (4.9)  fragmentga  ikkala  kirishlarni  oddiygina  qilib  5  ga  almashtirish 

kerak.  Biroq  ehtimoliy  P  asos  uchun  aniq  (kretik)  oddiy  ko‘paytuvchini  izlash  g‘oyasi 

o‘chmaydi. Masalan  P=12 da nollar miqdori tanaffuslar bilan 2 ko‘paytuvchilar miqdori yoki 3 

ko‘paytuvchilar miqdori bilan aniqlanadi.  

Mashqlar 

4.1.  Birinchi  qatorda  A  soni  1  dan  1000  gacha,  ikkinchi  qatorda  B  soni  1  dan  10

1000

  gacha 

yozilgan B ning A ga bo‘lishdagi qoldiqini hisoblang. 

4.2.  Murakkab  strukturalarni  funksiyalar  natijalari  kabi  qaytarish  imkonini  beradigan 

komplyatotni  toping  va  arifmetik  dasturostilarni  funksiyalar    ko‘rinishida  amalga  oshiring. 

Xotira ajralganida, biroq holi bo‘lmaydi (bunda xotira tugashi  yoki tortib olish fayli juda kuchli 

kattalashishi  mumkin),  bizning  amalga  oshirganlaringiz  “xotiraning  sarflanishi”  ga  olib  kelish 

kelmasligi so‘zsiz tekshiring (eksperimenti ravishda). 

4.3 Kvadratik baholashga qaraganda asimptotik  yanada samarali  ko‘paytirish algoritmlari bizga 

ma’lum. Ularning bittasining asosiy g‘oyasi quyidagicha: agarda har biri 2k raqamlardan tashkil 

topgan A

1

  va  A

2

  sonlar bor bo‘lsa, ularni  A

i

=d

k

 *B

i

+C

i

  ko‘rinishida tasavvur qilish mumkin (d-

hisoblash  sistemasining  asosi,  B

i

  va  C

i

  –  har  bir  K  raqamlardan  tashqari  topgan  sonlar).  Unga 

. 

“Manglay”  yondashishda  K  uzunlikdagi  sonlarning  to‘rt  ko‘paytirilishini  bajarish  kerak.  Biroq 

buning  o‘rniga  B

1

+C

1

  ni,  keyin  esa  uch  ko‘paytma 

  va  (B

1

+C

1

)*(  B

2

+C

2

)  larni 

hisoblash  yetishmaydigan 

  ifodani  esa  (B

1

+C

1

)*(  B

2

+C

2

)-

  ning  farqi 

sifatida  olish  mumkin.  Rekursiv  chaqiruvlar  miqdorining  kamayishi  amallarning  umumiy 

miqdorini,  ushbu  holda  – 

  dan 

  gacha  jiddiy  ravishda 

kamaytiradi. 

4.4 Uzun sonlarning EKUB ini hisoblashni amalga oshiring. 

4.5 Sonli A

0

, A

1

, A

2

 to‘plamlar quyidagicha tarzda shakillanadi: A

0

=[0;1], A

1

-[0;1/3] va [2/3;1] 

kesimlardan,  ya’ni  birinchidan  va  A

0

  kesishning  oxirgi  uchdan  biridan,  tashkil  topgan,  A

2

- 

birinchidan  va  A

1

  dagi  har  bir  kesimning  oxirgi  uchdan  biridan  tashkil  topgan  va  shu  kabi. 

Barcha  A

0

,  A

1

,  A

2

...  to‘plamlarga  mansub  bo‘lgan  nuqtalar  A

-1

  to‘plamni  shakillantiradi.  m/n 

nuqta  A

k

  to‘plamga  mansubligi  aniqlansin,  bu  yerda  k 1  .  Maslan,  1/6.  A

1

ga  mansub,  A

2 

  va 

barcha boshqasiga mansub emas, 3/10 nuqta esa istalgan k 0 da A

k

 ga tegishli, ya’ni A

-1

 ga ham 

tegishli.  

Kirish

 uchta butun m, n, k son, bu yerda 0

8

, -1 k<10

6

.  

Chiqish, 1 yoki 0 nuqta A

k

 ga tegishli yoki yo‘q. 

4.6. Massalari 1,3,9,...,3

n-1

 bo‘lgan n  ta chira mavjud. Tarozining chap pallasiga berilgan butun 

musbat m massali buyum va chiralarning istalgan kombinatsiyasi qo‘yiladi, o‘ng pallasiga esa – 

faqat chiralar qo‘yiladi. Agar buning imkoni bo‘lsa, tarozi muvozanat holatida bo‘lganida, chap 

va o‘ng tarafidagi pallalardagi chiralar to‘plam ostini toping. 

Kirish. Mantning birinchi qatoriga – n qiralar miqdori, ikkinchi qatoriga – t soni. 

1 n 20, logint tipidagi t; 

---

1 n 300, m<10

100

.  

Chiqish.  Agar  muvozanat  mumkin  bo`lmasa,  mantiqga  -1  chiqarilsin.  Aks  holda  mantning 

birinchi  qatoriga  –t  va  gap  palladagi  giralarnimg  o‘suvchi  massalari,  ikkinchi  qatorga  –  o‘ng 

palladagi giralarning o‘suvchi massalari (barcha sonlar probil 1 orqali). 

4.7  sonli  A  to`plam  quyidagicha  tarzda  tuziladi:  uning  elementlari  bo`lib,  berilgan  turli  xil 

natural a va b  sonlar hisoblanadi; agar x va y – uning elementlari, u holda x+y+xy – ham uning 

elementi,  boshqa  sonlar  unda  yo`q.  Berilga  uzun  natural  son  c  A  to`plamga  mansubligi 

aniqlansin.  

4.8 Ahmoqlar mamlakatida butun musbat k va m sonlar quyidagicha taqqoslanadi. Avvalo k

m

 va 

m

k

  hisoblanadi.  Keyin  esa  ushbu  sonlar  raqamlarining  yakuniy  summalari  topiladi  (agar  son 

raqamlarining  summasi  10  dan  katta  yoki  teng  bo`lsa,  ushbu  raqamlar  summasining  raqamlari 

yig‘indisini topadilar va shu kabilar, raqamalar summasi 10 dan kichik bo‘lmaguncha bu davom 

etadi). K va m lardan eng katta son shu bo`ladiki, uning darajasi raqamlarning yakuniy summasi 

katta bo‘lsin. Masalan, 2<5, chunki 2

5

=32 raqamlarining yakuniy summasi 5, 5

2

=27 summasi 7. 

Anologik ravishda 4>5, 2=4. Axmoqlarga yordam bering.  

Kirish.  Birinchi  qatorga  –  restlar  miqdori,  har  bir  test  axolida  qatordagi  longint  tipidagi  sonlar 

juftligi. 

Chiqish. <, = yoki = belgilar ketma-ketligi (taqqoslashning ko`rsatilgan uslubi bo`yicha birinchi 

son ikkinchidan kichik, teng yoki katta).  

4.9 Butun N son ( 0<=N<=2147483647) berilgan. Raqamlarining ko`paytmasi N ga teng bo‘lgan 

eng kichik musbat butun son  yoki bunday son bo‘lmasa 0 chiqarilsin. Masalan,  N=0 da bu son 

10, N=5 da -5, N=21da -37, N=11 da -0. 

4.10  Berilgan  k  bo`yicha  1  va  2  raqamalardan  tashkil  topgan  109  va  qoldiqsiz  2

k

  (agar  mavzu 

bo`lsa) beriladigan qandaydir k ishorali o‘nlik son topiladi. 

Kirish. k soni, 1<=k<=1000.  

Chiqish. k- ishorasi sonli qator yoki 0 (agar son bo`lmasa). 

4.11 Kichik o`nlik N raqamini katta razryadga ko`chirganda va qolgan raqamlarni o‘nga siljitgan 

N  marta  ortadigan  eng  kichik  natural  son  topilsin  (agar  N=2,…,9  ga  bunday  sonlar  umuman 

mavjud bo`lsa). 

4.12  Rejada  bilyard  maydoni  eniga  butun  sonli  k  (gorizantal  bo`yicha)  va  uzunligiga  butunli 

sonli  M  (vertikal  bo‘yicha)  o‘lcham;  arga  ega.  Koordinatalar  maydonning  chapdagi  pastki 

(janubiy  g`arbiy)  burchagiga  joylashgan.  Maydonning  butun  sonli  koordinatalarga  ega  (x,y) 

nuqtasiga  shar  shimoliy  –  sharqiy  yo`qolishda  harakatlana  boshlaydi  (garizantalga  nisbatan  45

0

 

burchak  ostida).  O‘ng  bortlarga  bir  necha  marta  urilib  va  luvazalarga  tushmasdan  L

2

 

uzunlikdagi yo`lni bosib o`tadi. Yo`l oxiridagi shar koordinatalari hisoblanadi.  

Kirish. 1 dan 

100

 gacha diapazondagi uchta K,M,L butun sonlar. 

Chiqish. Ikki x,y butun sonlar. 

4.13  Qimmati  1,  3  yoki  5  minutli  N  ga  teng  kupyuralarni  ishlatilib  to`lanishi  mumkin  bo`lgan 

berilgan S summa aniqlansin. 

4.14  0  va  1  dan  tashkil  topgan  qatorlarning  A

0

,  A

n

,  …  ketma  ketligi  quyidagicha    tarzda 

shakillanadi:  A

0

=1; A

n+1

  esa  A

n

 dan  har   bir 1 ni 01 ga va  har bir 0 ni 10 ga almashtirish  yo‘li 

bilan olinadi. Berilgan  n  va  m  lar bo‘yicha A

n

  ning  m-inchi raqami topilsin, bu  yerda 0 n 31, 

0 m 2

n

-1.