Urganch davlat universiteti axborot texnologiyalari kafedrasi

3.1 listing .O‘zaro rekursiv dasturostilari 

 

program Cells; 

  

var n:

byte

; 

procedure free(n:

byte

);

forward; 

procedure fillOnly(n:

byte

); 

begin 

  if n=

1 

then write(

'+1'

) 

  

else begin  

  fillOnly(n-

1

); 

  write(

'+'

,n); 

  free(n-

1

) 

end 

end; 

procedure free(n:

byte

); 

begin 

  if n=

1 

then write(

'-1'

) 

  

else begin  

  fillOnly(n-

1

); 

  write(

'-'

,n); 

  free(n-

1

) 

end 

end; 

procedure fill(n:

byte

); 

begin 

  if n=

1 

then write(

'+1'

) 

else 

  if n=

2 

then write(

'+1+2'

) 

  

else begin  

  fillOnly(n-

1

); 

  write(

'+'

,n); 

  free(n-

2

) 

end 

end; 

begin 

  readln(n);fill(n); 

end.

 

3.2  masala.  a,  N  berilga  a

n

  hisoblangan  a  va  a

n

  sonlar  extended  tipida  taqdim  qilinishi 

mimkin, N longint tipida nomanfiy butun son. Logorifm va eksponenta ishlatish kabi chiqilgan. 

Masalaning  tahlili.  Logorifmlarni  va  ekspanentalar  esa  olingan.  Chunki  x

y

=  e

ylnx

  biroq 

ushbu  formuladan  foydalanish  mumkin  emas.  Nima  uchun?  Shunig  uchunki,  darajaga  nafaqat 

sonlar balki boshqa obyektlar,  masalan,  kvadrat matritsalar  ham  ko‘tariladi.  Yoki  butun  sonlar, 

biroq odatiy arifmetikadagi emas, balki p modul bo‘yicha halqadagi, bundan tashqari juda katta, 

masalan  1024  bitli  (bu  zamonaviy  shiferlash  metodlarida  zarur).  Bunday  situatsiyalar  e  sonni 

logorifmlash  va  darajaga  ko‘tarish  o‘rinli  emas.  Bizning  masala  ma`nosi  sonlarni  darajaga 

---

ko‘tarishni  amalga  oshirish  shunday  bo‘lsinki,  sonlarni  ko‘paytirish  operatsiyasi  mos  keluvchi 

obyektlarni  ko‘paytirish  dasturlari  bilan  almashtirib  ulari  darajaga  ko‘tarilishini  amalga 

oshirishni olish mumkin bo‘lsin. 

Qo‘shimchasiga,  imkoni  boricha,  samarali  bo‘lsin.  Avvaliga  a

n

  ni  hisoblashni  ayyon 

bo‘lgan variantlarini qarab chiqamiz. 

 

es:=

1.0

; 

for i:=

1 

to N do res:=res*a 

 

Biroq  shunday  tarzda  1.0000001

2000000000

=7.2259*10

86 

(bir  butun  o‘nliklardan  bir 

darajasida ikki milliard) ko‘taring. Masalan, AMD486-DX4-100 ga bu deyarli bir soat davomida 

hisoblangan  va  bu  -  matematik  so  prosessorning  bitta  buyrug‘iga  javob  beradigan  ko‘paytma 

mavjud bo‘lgan  ko‘chuvchi  nuqtali  sonlardir.  Agar  har  bir  ko‘paytma  murakkab  dasturostining 

bajarilishini  talab  etadimi?  Bundan  tashqari  shifrlashning  jamovi  algoritmlariga  daraja 

ko‘rsatkichi longint tipida bo‘lmasligi mimkin, yani 2*10

9

 dan ko‘p emas, masalan, butun 1024- 

bitli  yani  10

310

  atrofida  (bunda  shiferni  buzush  uchun  emas,  balki  tezkor  bo‘lish  shart  bo‘lgan 

qonuniy  shifrlash-  deshifrlash uchun).  Shunday qilib, mashqlar  yordamida  N  darajaga  ko‘tarish 

uslubi kerak, biroq ko‘paytmalar N dan yetarli darajada kam bo‘lishi kerak. 

Asosiy  g‘oya.  Faraz  qilaylik  a  qiymatli  b  o‘zgaruvchi  va  a

1000

  qiymatli  b  o‘zgaruvchi 

mavjud  bo‘lsin.  A

2000

  qiymatni  olish  uchun  qancha  ko‘paytma  kerak?  Va  qanday  qilib  a

2001

 

qiymatni olish kerak javob o‘z-o‘zidan tushunarli. 

 

Shunday qilib bir  –  ikki bilan darajani  ikki marta ortirish mumkin.  N  darajaga  ko‘tarish 

uchun  zarur  bo‘lgan  M(N)  ko‘paytmalar  soni  [log

2

N

]  dan  2[log

2

N

]  gach  a  oraliqda  bo‘lar  ekan 

yoki 2*10

9

 darjaga ko‘tarish uchun 43 ta ko‘paytirish kerak.