O’ZBEKISTОN RESPUBLIKASI

ОLIY VA O’RTA MAXSUS TA`LIM VAZIRLIGI

 

NAMANGAN VILOYATI XALQ TA’LIMI XODIMLARINI QAYTA TAYYORLASH VA ULARNING MALAKASINI OSHIRISH HUDUDIY MARKAZI

 

“ANIQ VA TABIIY FANLAR METODIKASI”

KAFEDRASI

 

“Algoritmlash va dasturlash tillari” fan modullaridan informatika o’qitish huquqini berish bo’yicha kasbiy qayta tayyorlash kursiga laboratoriya mashg’ulotlarini bajarishi bo’yicha

 

USLUBIY KO’RSATMA

 

 

NAMANGAN – 2019 YIL

Ushbu uslubiy ko’rsatma “Informatika o‘qitish huquqini berish bo‘yicha kasbiy qayta tayyorlash kursi” o’qituvchilarining ta’lim оlishi uchun mo’ljallangan bo’lib “Algoritmlash va dasturlash tillari” fanidan laboratoriya mashg’ulotlarini bajarish bo’yicha barcha yo’riqnomalarni o’z ichiga olgan.

 

 

                                        

 

 

 

 

 

Tuzuvchilar                             o’qituvchi: F.Uzоqоv

                   19u-17-gurux talabasi Abduolimova Xaticha

 

Taqrizchi:                                NamDU  dotsenti

                                                    f-m. f-n., A.Imonov

 

 

 

 

 

 

 

 

Ushbu ko’rsatma Namamangan viloyati huzuridagi xalq ta’limi xodimlarini qayta tayyorlash va ularning malakasini oshirish hududiy markazi ilmiy uslubiy kengashi tоmоnidan 2019 yil ______________ da   tasdiqlangan.                                    

 

"Aniq va tabiiy fanlar metodikasi" kafedrasi   yig’ilishida muxоkama qilingan. "_____"__________ 2019 yil.

 

 

3-Laboratoriya ishi. Rekursiya va rekursiv funktsiyalar. Matematik induktsiya. Rekursiv va iteratsion algoritmlarni qiyoslash

 

Ishning maqsadi: Rekursiya va rekursiv funktsiyalar. Matematik induktsiya. Rekursiv va iteratsion algoritmlarni qiyoslash va o’rganish.

 

 

Qisqacha nazariy ma’lumot.

Rekursiv algoritm va rekursiv ma’lumotlar tuzilmalarini ko‘rib chiqaylik.

Rekursiya – shunday jarayonki, bunda jarayonni borishi o‘ziga murojaat qilish bilan bog‘liq bo‘ladi..

Rekursiv ma’lumotlar tuzilmasiga misol qilib shunday tuzilmalarni olish mumkinki, ushbu tuzilmalarning elementlarining o‘zi xam xuddi shunday tuzilma bo‘ladi (qarang, chizma).

Daraxtlar

         Daraxt – bu chiziqsiz bog‘langan ma’lumotlar tuzilmasidir
(qarang, chizma).

Daraxt o‘zining quyidagi belgilari bilan tasniflanadi:

 - daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo‘q. Mazkur elementga daraxt ildizi deyiladi;

 - daraxtda ixtiyoriy elementga chekli sondagi ko‘rsatkichlar yordamida murojaat qilish mumkin;

 - daraxtning har bir elementi faqatgina o‘zidan oldingi kelgan bitta element bilan bog‘langan. Daraxtning har bir tuguni oraliq yoki terminal (barg) bo‘lishi mumkin. YUqoridagi chizmada M1, M2 - oraliq, A, B, C, D, E - barglardir. Terminal tugunning o‘ziga xos tasnifi uning shoxlari yo‘qligidir.

Balandlik – bu daraxt bosqichi soni. YUqoridagi chizmadagi daraxt balandligi ikkiga teng.

Daraxt tugunlaridan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi (Keltirilgan chizmada M1 uchun chiqish darajasi 2, M2 uchun esa 3 ga teng). Daraxtlar chiqish darajasi bo‘yicha sinflarga ajratiladi:

1) agar maksimal chiqish darajasi m bo‘lsa, u holda bunday daraxt m-chi tartibli daraxt deyiladi;

2) agar chiqish darajasi 0 yoki m bo‘lsa, u holda to‘liq m-chi tartibli daraxt bo‘ladi;      

3) agar maksimal chiqish darajasi 2 bo‘lsa, u holda bunday daraxt binar daraxt deyiladi;

4) agar chiqish darajasi 0 yoki 2 bo‘lsa, u holda to‘liq binar daraxt deyiladi.

ugunlar orasidagi bog‘liqlikni tavsiflash uchun yana quyidagicha termindan foydalaniladi: M1 – A va V elementlar uchun “ota” . A va V – esa M1 tugun “o‘g‘illari”.

 

Daraxtlarni tasvirlash

Daraxtni grafik shakldagi va uning chiziqsiz ro‘yxat shaklidagi ifodalanishi

 

EXM xotirasida daraxtni ifodalashaning eng qulay usuli bu uni bog‘langan ro‘yxatlar ko‘rinishida ifodalashdir. Ro‘yxat elementi tugun qiymati va chiqish darajasini o‘z ichiga oluvchi informatsion maydonga xamda chiqish darajasiga teng bo‘lgan ko‘rsatkichlar maydoniga ega bo‘lishi lozim (yuqoridai chizma), ya’ni elementning har bir ko‘rsatkichi ushbu elementni tugun o‘g‘illari bo‘lgan tugunlarga yo‘nalishini aniqlaydi.

Binar daraxtlar

Binar daraxtlar eng ko‘p foydalaniladigan daraxtlar turi xisoblanadi.

Daraxtlarni EXM xotirasida tasvirlanishiga ko‘ra xar bir element to‘rtta maydonga ega yozuv xisoblanadi. Mazkur maydonlar qiymati mos ravishda yozuv kaliti bo‘lib, boshqa elementlarga murojaatni ifodalaydi, ya’ni chapga-pastga, o‘nga-pastga va yozuv matniga.

SHuni esda tutish lozimki, daraxt xosil qilinayotganda, otaga nisbatan chap tomondagi o‘g‘il qiymati kichik kalitga, o‘ng tomondagi o‘g‘il esa katta qiymatli kalitga ega bo‘ladi. Masalan, quyidagi elementlardan binar daraxt quramiz: 50, 46, 61, 48, 29, 55, 79. U quyidagi ko‘rinishga ega bo‘ladi:

Natijada, o‘ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt xosil qildik. Agar daraxtning o‘ng va chap qism daraxtlari bosqichlari farqi birdan kichik bo‘lsa, bunday daraxt ideal muvozanatlangan daraxt deyiladi. YUqorida xosil qilgan binar daraxtimiz ideal muvozanatlangan daraxtga misol bo‘ladi.

Binar daraxtni xosil qilish uchun EXM xotirasida elementlar quyidagi turda bo‘lishi lozim:

V = MakeTree(Key, Rec) amali ikkita ko‘rsatkichli (kalit) va ikkita maydonli (informatsion) element yaratadi (daraxt tuguni)

MakeTree protsedursi ko‘rinishi:

Paskal

New(p);

p^.r := rec;

p^.k := key;

v := p;

p^.left := nil;

p^.right := nil;

Boshida kalit birinchi qiymati kiritiladi. Undan so‘ng elementni o‘zini maketree protsedurasi orqali hosil qilamiz. Keyin esa ko‘rsatkich bo‘sh qiymatni ko‘rsatguncha siklni davom ettiramiz.

READ(key,rec)

tree=maketree(key,rec)

WHILE not eof DO

  READ(key,rec)

  V=maketree(key,rec)

  WHILE P<>nil DO

     Q=P

     IF key=k(P)

       THEN P=left(P)

       ELSE P=right(P)

    END IF

 END WHILE

 IF P=nil

  THEN WRITELN(' Bu ildiz');

  tree=V

  ELSE IF key<k(q)

           THEN left(P)=V

           ELSE right(P)=V

          END IF

   END IF

END WHILE

 

 

TОPSHIRIQNI BAJARISH UCHUN  NA’MUNA:

     

Quyidagi berilgan yig‘indini hisoblash algoritm blok sxemasi va Pascal tilidagi dasturini tuzing. Natijani ekranda chop qiling.

 

               

 

 

 

 Dastur matni

 

Uses crt;

var r:integer;

s:real;

begin

s:=0;

for r:=1 to 15 do

s:=s+sqr(100-R)/(ln(R)/ln(10)+

+1/power(5,r));

writeln('Yig`indi=',s:3:5);

end.

 

 

 

                           Tоpshiriq variantlari.

Quyidagi berilgan yig‘indini hisoblash algoritm blok sxemasi va Pascal tilidagi dasturini tuzing. Natijani ekranda chop qiling.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Скачано с www.znanio.ru