Urganch davlat universiteti axborot texnologiyalari kafedrasi

 

function power(a:extended; N:

longint

):extended; 

  

var res:extended; 

begin 

  if odd(N) then res:=a else res:=

1.0

; 

  

while N>

1  

do begin 

    N:=N div 

2

; 

    a:=a*a; 

    

if odd(N) then res:=res*a; 

   

end; 

  power:=res; 

end; 

 

Rekursiv  variantining  asosiy  ustunligi  dasturning  xaqiqiy  (real)  tilda  formuladan  dasturga 

o‘tishini oddiyligida bo‘lib, yanada samarali ishlash uchun iteratsiya afzal. 

Masalaning tahlili. Iterativ algoritimning tushunish oson agar uning iteratsiyasida barcha 

ko‘rsatkichlarni ikkilik sistemaga yozilsa. N=50 dagi iteratsiyasi misol quydagi jadvalda taqdim 

qilingan.  a o‘zgaruvchining qiymatlarida daraja ko‘rsatkichi N  ning  kamayishi bilan mos holda 

o‘sadi; N toq bo‘lganda res zarur qiymatga ko‘paytirishda, qaysiki bu vaqtda a ga saqlanadi. 

 

(3.1)  formulalarni  ko‘pincha  a

n

=(a

ndiv2

)

2

*a

nmod2

, a

0

=1 ko‘rinishida  yozadilar va darajaga 

ko‘tarishning quyidagicha algoritmi deyishadi (ushbu algoritmni qadimiy Xindlarga ham ma’lum 

bo‘lgan).  

Mulohaza 3.2 listingda rekursiv chaqiruvlarni  sqr(power(a,n div 2)) biroq power(a*a, n 

div  2)  power(a,n  div  2)*  power(a,n  div  2)  bu  ifoda  bilan  almashtirilsa,  u  holda  funksiya  juda 

sekin  ishlaydi.  Buning  sababi  shundaki  rekursiyaga  bag‘ishlangan  chuqurlikning  ortishi  bilan 

power funksiyasini chaqiruvlar miqdori geometrik progressiyada o‘sadi (3.13 bo‘limiga qarang). 

Jumladan, power(a,0) chaqiruv taxminan 2

logn

=n marta bajariladi 

C/C++  ishqibozlari  uchun  topshiriq.  Yuqorida  ko‘rsatilgan  3.2  listiningda  rekursiv 

chaqiruvlar  samaradorligini  yo‘qotmasdan  sqr(power  a,n  div  2)  va  a*(power  a,n  div  2)  kabi 

---

yozish  mumkin.  Analogik  chaqiruvlarning  C/C++  tilida  yozsa  nima  bo‘ladi,  bunda  sqr 

quyidagicha amalga oshiriladi. 

a)Double sqr (double x) {return x*x} 

b)Makrotarif # define srq(x) ((x)*(x))? 

Ko‘rsatma:  Funksiya  (п.a)  alohida  oqibatlarga  olib  kelmaydi,  biroq  makro  ta’rif  (b  punkt) 

samaradorligini  juda  ko‘p  isrofiga  olib  keladi.  Agar  siz  ham  tushunmagan  bo‘lsangiz  so‘nggi 

izohli  (C/C++  bo‘yicha  kitobda  ham)  va  makro  ta’riflarda  qanday  ishlashi  to‘grisida 

ma’lumotlarni qayta o‘qing.