Urganch davlat universiteti axborot texnologiyalari kafedrasi

Masalani yechish: Aslida algoritmni quyidagi yozuvdagi formulada: 

  

 

 

( 3.1) 

Bo‘sh  dastur  ko‘rinishida  amalga  oshirish  qoldi.  Ikkita  amalga  oshirish  yo‘lini  keltiramiz. 

Birinchisi - ushbu formulalarning rekursiv funksiya ko‘rinishida bevosita yozilishi. 

3.2 – listing . Yarmini bo‘lishni rekursiv amalga oshirilishi  

 

function power(a:extended;N:

longint

):extended; 

begin 

  if N=

0 

then power:=

1.0 

  

else if odd(N) 

    

then power:=a*power(a*a,N div 

2

) 

   

else power:=power(a*a,N div 

2

) 

  

end; 

 

Natija  olish  uchun  res:=power(a,N)  chaqiruv  qilish  kerak.  A  ning  oraliq  darajalari  funksiya 

chaqiruvlarining  lokal  xotirasida,  aniqrog‘i  power  ismiga  mos  turuvchi  o‘zgaruvchilarda 

saqlanadi. Shunday qilib, har bir navbatdagi yopishgan chaqiruvga n argumentli qiymati oldingi 

qiymatdan maksimum ikki marta kichik bo‘ladi. n≤1 da chaqiruvdan qaytish ro‘y beradi shuning 

uchun  n  argument  qiymatini  ko‘rsatilgan  kichiklashuvi  log

2

N

  dan  katta  emas  va  n  argumentli 

chaqiruvning rekursiya chuqurligi ham log

2

N

 dan kata bo‘lmaydi.  Har bir chaqiruv bajarilganda 

---

bittadan  ko‘p  bo‘lish,  kvadratga  ko‘tarish  va  ko‘paytirish  bo‘lmaydi,  shuning  uchun  arifmetik 

operatsiyalarni  umumiy  soni  3*log

2

N 

dan  ko‘p  emas.  Takidlashimizni  qandaydir  n  larda 

keltirilgan  algoritm  n  chi  darajani  hisoblash  uchun  zarur  bo‘lgan  ko‘paytmalarini  miqdorini 

bermaydi.  Masalan  n=15  da  algaritm  bo‘yicha  6  ko‘paytirish  bajariladi,  3  ta  ko‘paytirish 

yordamida  a

5

  ni  hisoblash  mumkin  bo‘lsada  va  keyin  uni  o‘ziga  ikki  marta  ko‘paytiriladi 

(hammasi  bo‘lib  5  ko‘paytirish).  Shunday  bo‘lsa  ham  bu  nooptimallik  haqiqatdan  ham  katta 

bo‘lmaydi,  shuning  uchun  mualiflar  ushbu  oddiy  va  chiroyli  algoritmni  yaxshilashga  harakat 

qilmaydilar. 

(3.1) formulaling ikkinchi amalga oshirilishi - iterativ, yani siklikdir (3.3 –listing ). 

3.3- listing. Ikki qilib bo‘lishning iterative amalga oshirish