Algoritmlarni loyihalash va tahlil qilish

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

811.19140625 KB

Ko'chirib olish

Algoritmlarni loyihalash va tahlil qilish
MUNDARIJA
KIRISH ………………………………………………………………………3
1-BOB. Rekurent nisbatlar (munosabatlar) ning nazariy asoslari ………..4
1.1. Rekurent nisbat haqida umumiy tushunchalar ………………….4
1.2. Rekurent nisbatlarni sozlash ……………………………………..8
2-BOB. Rekurent algoritmlarni ishlab chiqish …………………………...10
2.1. Rekurent algoritmlarni loyihalash ……………………………...10
2.2. Rekerent nisbatlarga misollar …………………………………..13
XULOSA …………………………………………………………………...16
FOYDALANILGAN ADABIYOTLAR RO‘YXATI …………………….17
ILOVALAR ………………………………………………………………..18
1

KIRISH
Barcha algoritmik tillarda rekurent nisbatlar va proseduralarni –
qismdasturlar ko'rinishida rasmiylashtirilgan operator bloklarini dasturlash
imkoniyati mavjud. Rekurent nisbatlar tilning muhim konstruksiyalariga taalluqli
bo'lib, uchta muhim masalani yechishga imkon beradi:
 dastur matnida o'xshash fragmentlarni ko'p martalab takrorlash
zaruratidan qutqaradi;
 dastur tuzilishini yaxshilab, uni tushinishni osonlashtiradi;
 dasturlash xatolariga va dasturlarni takomillashtirishda kutilmagan
oqibatlarga chidamlilikni oshiradi.
Kurs ishi mantiqiy va algebraik tafakkur malakalarini rivojlantirishga va
Pascal tilida dasturlarni yozishda rekurent nisbatlardan foydalanish imkoniyatlarini
o'rganishga yordam beradi. Bu til dasturlash asoslarini o'rgatish uchun bejiz
tanlanmagan, chunki Pascal – dastur tuzilishi bevosita masala tuzilishini aks
ettirish lozim bo'lgan ko'rinishda “strukturalashgan” dasturlarni yasashga yordam
beradigan dasturlash tillaridan biridir. Pascal tilining bu xususiyati hamda uning
konstruksiyalarining intuitiv tushunarliligidan uning yetarlicha oddiyligi, bu tilga
dasturlash tillari orasida mustaqil o'rinni egallashga imkon beradi. Dasturlashning
hozirgi davrdagi yurug'i strukturalashgan dasturlar afzalliklarini tan olinganligidir.
Shuning uchun Pascal muhandislar va ilmiy xodimlar tomonidan keng
foydalanilmoqda, informatika bo'yicha xalqaro olimpiadalar tili hisoblanadi.
Hozirgi paytda bu tilning yetarlicha ko'p talqinlari mavjud. Eng ko'p
tarqalgan talqini 1992 yilda Borland International (Borland Pascal 7.0 va Turbo
Pascal 7.0) firmasi tomonidan ishlab chiqqan talqini hisoblanadi. Faqat MS DOS
oddiy rejimda ishlashga imkon beruvchi Turbo Pascal 7.0 dan farqli Borland
Pascal 7.0 uchta ish rejimini o'z ichiga oladi: MS DOS oddiy rejimi, MS DOS
himoyalangan rejimi va Windows muhitida.
Kurs ishi kirish, ikkita bob, xulosa, foydalanilgan adabiyotlar ro'yxati va
ilovalardan iborat.
2

1-BOB. Rekurent nisbatlar (munosabatlar) ning nazariy asoslari
1.1. Rekurent nisbat haqida umumiy tushunchalar
Qismdastur tanasida dasturdagi tavsiflangan barcha obyektlarga, shu
jumladan qismdasturning o'zining nomiga kirish mumkin. O'z-o'zini chaqirishni
foydalanuvchi protsedura va funksiyalar rekurent protsedura va funksiyalar deb
ataladi (to'g'ri rekurent).
Rekurent – bu hisoblash jarayonini shunday tashkil etish usuliga aytiladiki,
bunda uni tashkil etuvchi operatorlarni bajarish jarayonida o'z-o'ziga aylanadi.
Tipik rekurent protsedura quyidagi ko'rinishga ega:
procedure Rec (n:Integer);
begin
<rekursiyaga kirish amala>
if <shrtni tekshirish> then Rec(n-1);
<rekursiyadan chiqish amali>
end;xn
, bu yerda x – butun son, n – butun nomanfiy son, ni hisoblash rekurent
funksiyasiga misolni qaraymiz.
Ma'lum faktdan foydalanamiz:
x
n
= ¿{ 1,m= 0da ,¿¿¿¿
function Deg(x, n: integer) :longint;
begin
if n = 0 then Deg:=1
3

else Deg:=Deg(x, n-1)*x;
end;
1.1-rasmda rekurent nisbatlarning to'g'ri va teskari yo'li ko'rsatilgan. Bu
holda а o'zgaruvchiga 2 4
qiymat beriladi. Ixtiyoriy rekurent qismdastur norekurent
bo'lmagan tarmoq bo'lishi lozim, bizning holda – bu
if n = 0 then Deg:=1;
Rekurent qismdasturga murojaat ixtiyoriy boshqa qismdasturni chaqirishdan
hech qanday farq qilmaydi. Rekurent qismdasturlarni bajarishda «qaytish steki»
deb ataluvchi maxsus xotira sohasidan foydalaniladi.
Har bir yangi rekurent murojaatda xotirada barcha lokal o'zgaruvchilarga ega
qismdastur nusxasi yaratiladi. Bu nusxalar chegaraviy shartga chiqqunga hosil
bo'laveradi (norekurent tarmoq). Ravshanki, chegaraviy shart bo'lmagan holda
bunday nusxalar sonini chegaralanmagan o'sishi stekning to'lishi hisobiga
dasturning favqulotda to'xtatilishiga olib keladi.
Rekurent qismdasturning barcha yangi nusxalarining xosil bo'lishi
chegaraviy shartga chiqquncha hosil bo'lishi rekursiyaning to'g'ri yo'li (rekurent
pasayishi) deb ataladi. Kompyuter xotirasida bir vaqtda joylashishi mumkin
bo'lgan rekurent qismdasturlar nusxalari maksimal soni rekursiya chuqurligi deb
ataladi. Rekurent chaqiriqlar bilan hosil qilingan rekurent qismdasturlarning eng
birinchisigacha ishining tugatilishi rekursiyaning teskari yo'li (rekurent ko'tarilish)
deb ataladi.
Har bir rekurent protsedura yoki funksiyaning boshida daastur to'xtab
qolganda undan kompyuter qayta yuklashsiz ixtiyoriy tugmani oddiy bosish bilan
chiqishga imkon beruvchi if KeyPressed then Halt; satrni joylashtirish
mumkin. Keypressed funksiya true natijani qaytaradi, agar klaviaturada
simvolni hosil qiluvchi tugma bosilsa, va false – aks holda. Masalan , repeat
4

until Keypressed; operator bo'sh operatorni o'z ichiga oladi va dasturni
bajarish paytida tugma bosilguncha tanaffusni ta'minlaydi.
1.1 – rasm. Rekurent nisbatlarning to'g'ri va teskari yo'li
5

Rekurent nisbatni – biror shart qanoatlantirmaguncha ba'zi amallar takror
bajariluvchi – iteratsiya bilan aralashtirmaslik lozim. Algoritmni tashkil etishning
rekurent shaklidan foydalanish odatda iteratsiyadan qulayroq ko'rinishda va
dasturning kompakt matnini beradi, lekin dasturchining kompyuterni qayta
yuklanishini bajarishga majbur qiluvchi rekurent dasturlashda ehtimoli katta.
Bundan tashqari, agar rekursiyaning chuqurligi juda katta bo'lsa, u holda
translirlangan dastur bajarilish paytida ko'p xotira talab etiladi, bu esa stek to'lib
ketishiga olib kelishi mumkin.
Rekurent nisbatlarga bir nechta misollar keltiramiz.
1. Natural sonning ikkilik tasvirini chop etishning rekurent protsedurasi.
procedure Rec(n: integer);
begin
if n > 1 then Rec(n div 2)
Write(n mod 2);
end;
2. Natural sonning faktorialini hisoblashning rekurent funksiyasi.
Faktarial – bu birdan qandaydir berilgan n natural songacha natural
sonlarning ko'paytmasi, ya'ni 1·2·…·( n -1)· n , n ! deb belgilanadi.
function Factorial(n: integer):longint;
begin
if n = 1 then Factorial := 1
else Factorial := n*Factorial(n-1);
end;
3. x butun sonni butun nomanfiy n darajaga ko'tarish rekurent funksiya
quyidagi ko'rinishga ega:
6

function Deg(x, n: integer):longint;
begin
if n = 0 then Deg:=1
else
if n mod 2=0 then
Deg:=Deg(x*x, n div 2)*x
else
Deg:=Deg(x, n-1)*x;
end;
Rekurent chaqirish bilvosita (bilvosita rekurent) bo'lishi mumkin. Bu holda
qismdastur o'ziga bilvosita boshqa qismdasturni chaqirish yo'li bilan aylanadi,
unda birinchisiga murojaat mavjud. Bilvosita rekurentdan foydalanishga misol
bo'lib, forward buyrug'idan foydalanishni tushuntirish uchun yuqorida
keltirilgan misol hisoblanadi. Berilgan misolda A nomli protsedura B nomli
protsedurani chaqiradi, B protsedura o'z navbatida A protsedurani chaqiradi.
1.2. Rekurent nisbatlarni sozlash
Rekurent qismdasturlarni o'z ichiga olgan dasturlarni sozlashda chaqirilgan
qismdasturlar steki mazmunini nazorat qilish zaruriyati paydo bo'ladi. Turbo
Pascal hozirgi paytda chaqirilgan qismdasturlar stekini qarashni tashkil etishga
imkon beradi. Bu vertical menyu Debug ( Ctrl+F3 tugmasi) Callstack buyrug'i
yordamida bajariladi. Bu buyruq bo'yicha Call stack maxsus oynasi ochiladi, unda
stek tartibda bu momentda bajariladigan qismdasturlar ro'yxati va ularning
parametrlari qiymatlari (stek uchi – yuqorida) beriladi. Bu oynani Enter tugmasini
bosib ochish mumkin. Call stack oynasi chaqirilgandan so'ng Window vertical
menyuning Cascade buyrug'ini bajarish maqsadga muvofiq. Bu holda ikkala oyna
7

kaskad bo'lib turadi va asosiy oyna dastur matni bilan Call stack oynani butunlay
qoplamaydi.
1.2 – rasmda yuqorida keltirilgan Deg rekurent funksiya yordamida ikki
sonining to'rtinchi darajasini hisoblashda chaqirishlar stekini qarab chiqish
namoyish qilinadi. Nazorat nuqta funksiya tanasining yopuvchi end qavsida
o'rnatilgan. Run buyrug'i bilan dasturni ishga tushirish nazorat nuqta bilan birinchi
uchrashguncha bajarilishga olib keladi. Bu 2 0
ni hisoblashda funksiyani eng oxirgi
chaqiruvidan chiqishda ro'y beradi. Agar endi bajarilishni davom ettirsak, u holda
stek sekin-asta ozod bo'la boshlaydi. Undan dastlab Deg(2, 1), keyin Deg(2, 2) va
h.k.lar chiqarib tashlanadi.
1.2 – rasm. Berilgan momentda chaqirilgan qismdasturlar ro'yxatini qarab chiqish
Qismdastur parametrlari orasida dastur tanasida hisoblanuvchi chiqish
parametrlari bo'lishi mumkin. Bunday parametrlarni kuzatishda Turbo Pascal
qismdastur lokal o'zgaruvchilari initsializatsiyalanmaydi va yaratishda ba'zi
«tasodifiy» qiymatlarni oladi. Chiquvchi parametrlarni boshlang'ich qiymatlari
juda kutilmagan ko'rinishda bo'lishga tayyor bo'lish lozim.
8

2-BOB. Rekurent algoritmlarni ishlab chiqish
2.1. Rekurent algoritmlarni loyihalash
Rekurent algoritmlarni loyihalashda asosan quyidagilar hosil bo’ladi.
Serpenskiy salfetkasi (2.1-rasm), Olti uchli qorcha (2.2-rasm), Simmetrik
bo'lmagan shoxcha (2.3-rasm), Turli radiusli aylanalardan iborat rasm (2.4-rasm),
Simmetrik shoxcha va h.k.
Serpinaskiy salfetkasi quyidagicha chiziladi: uchburchak chiziladi va unda
o'rta chiziqlar o'tkaziladi; berilgan uchburchak burchaklarida hosil bo'lgan yangi
uchburchaklarda yana o'rta chiziqlar chiziladi; jarayon ichma-ich joylashishini
berilgan tartibigacha takrorlanadi.
2.1 – rasm. Serpinskiy salfetkasi
Qorchani displey ekranida chizish uchun uchlarida kichik o'lchamdagi
qorchalar joylashgan olti uchli qorcha rasmida, ularning ham uchlarida o'z
navbatida shunga o'xshash kichik qorchalar joylashgan.
9

2.2 – rasm. Olti uchli qorcha.
2.3-rasmda tasvirlanganga o'xshash displey ekranida shoxni chizadi.
2.3 – rasm. Simmetrik bo'lmagan shoxcha
2.4-rasmda tasvirlangan turli radiusli aylanalardan iborat oddiy rasmni
chizadi.
10

2.4 – rasm. Turli radiusli aylanalardan iborat rasm.
2.5-rasmda tasvirlanganiga o'xshash shoxcha displey ekraniga chiziladi.
2.5 – rasm. Simmetrik shoxcha
11

2.2. Rekerent nisbatlarga misollar
2.1 – Misol.
Ikkita butun son eng katta umumiy bo'luvchisini hisoblash uchun rekurent
funksiyadan foydalanishni ko'rsatuvchi misol.
Ikkita butun sonning EKUBini topish dasturini yozish talab etiladi.
Kiruvchi ma'lumotlar: a va b butun sonlar.
Chiquvchi ma'lumotlar: a va b sonlar EKUBi – EKUB( a,b ).
Kiruvchi va chiquvchi ma'lumotlarga misollar:
Kiruvchi ma'lumotlar Chiquvchi ma'lumotlar
a = 36, b = 27 EKUB( a,b ) = 9
a = 39, b = 65 EKUB( a,b ) = 13
Yechish
EKUB( a,b ) ni topish uchun ayirishli Evklid algoritmidan foydalanilsa
sonlarning eng kattasini kichigi miqdoriga – ularning biri nolga teng bo'lmaguncha
kamaytirib boramiz. EKUB( a,b ) ni hisoblash uchun rekurent funksiyadan
foydalanamiz. Dasturning berilgan matni 1 – ilovada keltirilgan.
2.2 – Misol.
Murakkab simmetrikrasmni yaratish uchun rekurent algoritmdan
foydalanishni ko'rsatuvchi misol.
12

2.6 – rasm. Qor uchquni
2.6 – rasmda ko'rsatilgan qor uchqunini chizuvchi dasturini yozish talab
etiladi.
Kiruvchi ma'lumotlar: Kiruvchi ma'lumotlar yo'q.
Chiquvchi ma'lumotlar: qor uchqunining rasmi.
Yechish
Rasm o'nta uchli qorchadan iborat, har bir uchi, o'z navbatida, markazga
yo'nalish bo'yicha o'lchamda kamayuvchi o'xshash o'nuchli qorchalar to'plamidan
iborat.
Bunday qorchani rekurent protsedura uchta parametrga bog'liq
(tavsiflanuvchi figurani bir qiymatli xarakterlovchi uchta son); markaz
koordinatalari x , y va r radius.r≤1
radiusli qor uchquni monitor ekranida misoldan farq qilmaydi, bundan
rekurent protseduradan chiqish sharti: agar
r≤1 bo'lsa, u holda ( x,y )
koordinatalarga ega faqat bitta nuqta yasaladi va protsedura tugallanadi.
13

Aks holda (r>1 ) protsedurada radiusi 5 marta boshlang'ich radiusdan kichik
bo'lgan eng chetki qorchadan boshlab 36 o
qadamli burchak bo'yicha siklda qor
uchqunining 10 ta tarmog'i tasvirlanadi.
Bu qism ichida yana 8 ta o'xshash qorchadan iborat tarmog'ining o'zi
chiziladi, bunda navbatdagi qor uchquni radiusi dastlabki qor uchquni markaziga
yaqinlashishi bilan 1,5 marta kamayadi.
Butun qor uchqunini chizish uchun asosiy dasturdan bu protsedurani
parametrlar sifatida ekran markazi koordinatalari va dastlabki qor uchquni
radiusini berib bir marta chaqirish yetarli.
Dasturning dastlabki matni 2 – ilovada keltirilgan.
2.3 – misol.
Agar har bir bo'lak bir millisekundda 2 ta bo'lakka ajralsa, jismning
N
millisekund davomida bo'lish natijasida olingan bo'laklari sonini hisoblash dasturni
yozish talab etiladi.
Kirish ma'lumotlari:
N – millisekundlar soni. Butun tipli o'zgaruvchi (
N ≤ 30
).
Chiqish ma'lumotlari:
K – bo'laklar soni. Butun tipli o'zgaruvchi.
Kirish va chiqish ma'lumotlariga misollar:
Kirish ma'lumotlari Chiqish ma'lumotlari
0 1
10 1024
Yechish
Ravshanki,
N = 0 da bo'laklar soni 1 ta, har bir millisekundda bo'laklar soni
2 marta ko'payadi, oson ko'rsatish mumkinki
N >0 da bo'laklar soni 2N yoki
2⋅2(N−1)
ga teng. Ma'um N vaqt bo'yicha bo'laklar soni K ni topish uchun
funksiyadan foydalanamiz. Quyida rekursiyadan foydalanib (3.1-ilova) va
14

rekurentsiz (3.2-ilova) berilgan funksiyani qanday ishlatish mumkinligi
ko'rsatilgan.
XULOSA
Rekurent nisbatlarni ishlatish mumkin bo’lgan barcha dasturlash tillari har bir faol
proseduraga tegishli bo’lgan o’zgaruvchilarning barcha qiymatlarini saqlash uchun
faol yozuvlar steki ishlatilar ekan. Proseduralarni rekurent chaqirish ko’p
dasturlarning strukturasini qisqartiradi. Lekin ayrim dasturlash tillarida
proseduraviy chaqirishlar operatorlarning bajarilishiga nisbatan ko’p vaqt
sarflanadi, shuning uchun dasturdan rekurent nisbatlardan foydalanganda dastur tez
ishlaydi. Buni men kurs ishini bajarish davomida misollar ishlab amin bo’ldim.
Bundan keying ishlarimda ham rekurent nisbatlardan keng foydalanaman.
15

Foydalanilgan adabiyotlar ro’yxati
1. Алексеев, Е . Р. Турбо Паскаль 7.0 / Е.Р. Алексеев, О.В. Чеснокова. – М.:
НТ Пресс, 2005. – 314 с.: ил. – (Самоучитель). – ISBN 5-477-00003-1.
2. Вирт , Н. Алгоритмы и структуры данных / Н. Вирт. – М.: Мир, 1989.
(Зуев, Е.А. Язык программирования Turbo Pascal 6.0, 7.0 / Е.А. Зуев. –
М.: Веста: Радио и связь, 1993.)
3. Лалетин, Н.В. Практикум по решению задач на ЭВМ. Часть 1: учебное
пособие / Н.В. Лалетин; Краснояр. гос. пед. ун-т им. В.П. Астафьева. –
Красноярск, 2006. – 114 с. : ил. – ISBN 5-98997-002-1.
4. Немнюгин, С . А. Turbo Pascal. Практикум. 2-е изд. / С.А. Немнюгин. –
СПб.: Питер, 2003. – 268 с.: ил. – ISBN 5-94723-702-4.
5. Окулов, С . М. Основы программирования / С.М. Окулов. – 3-е изд. – М.:
БИНОМ. Лаборатория знаний, 2006. – 440 с.: ил. – ISBN 5-94774-538-0.
6. Павлова , М . А . Рекурсивные алгоритмы и их построение: Заочная школа
современного программирования. Занятие 7: учебное пособие / М.А.
Павлова, Н.Н. Паньгина. – СПб.: Издательство ЦПО «Информатизация
образования», 2000. – 24 с.: ил. – ISBN 5-89733-036-0.
7. Фаронов, В . В. Турбо Паскаль. В 3-х книгах. Книга 1. Основы Турбо
Паскаля / В.В. Фаронов. – М.: Учебно-инженерный центр «МВТУ-
ФЕСТО ДИДАКТИКА», 1992. – 304 с.: ил. – ISBN 5-85896-002-2.
8. Методические указания по курсу «Программирование и
вычислительная физика». Часть II. Процедуры и функции в языке
Turbo Pascal. Перечисляемые типы данных, тип диапазон и оператор
case. Массивы / сост. Т.П. Шестакова; УПЛ РГУ. – Ростов-на-Дону,
2003. – 23 с.
9. Всё о Паскале [Электронный ресурс] / редактор Злобин Евгений; Web-
мастер Злобин Евгений – Режим доступа: http://tpascal.h15.ru ,
свободный. – Загл. с экрана. – Яз. рус.
10. Турбо Паскал 7.0 [Электронный ресурс] / Режим доступа:
http://pascal.guti.ru , свободный. – Загл. с экрана. – Яз. рус.
16

$ILOVALAR 1 – ILOVA. Ikkita butun sonning EKUBini topish program p2_1; uses crt; var a,b:integer; {EKUBni topish rekurent funksiyasi} function Ekub(a,b:integer):integer; begin if (a=0) or (b=0) then Ekub:=a+b else if a>b then Ekub:=Ekub(a-b,b) else Ekub:=Ekub(a,b-a) end; begin {Asosiy dastur} clrscr; {ekranni tozalash} writeln(‘Ikkita natural sonni kiriting’); write(‘a=’); readln(a); write(‘b=’); readln(b); writeln (‘EKUB(a,b)=’, Ekub(a,b)); readkey; end. 17$ $2 – ILOVA. Qor uchqunini chizish. program p2_2; uses G raph; const Step=Pi*0.2; var Driver, Mode:integer; procedure DrowStar(x, y, Size:Integer); {x, y – markaz koordinatalari va Size – qorcha radiusi} var i, j, NewSize, xNew, yNew:Integer; begin if Size<1 then PutPixel(x,y,white) else {Birinchi sikl – yo'naltiruvchi qorchalar soni bo'yicha} for i:=0 to 9 do begin newsize:=size; {Ikkinchi sikl – qor uchqunining 8-qism darajasini chizish} for j:=1 to 8 do begin xnew:=x+Round(newsize*cos(i*Step)); ynew:=y+Round(newsize*sin(i*Step)); DrowStar(xnew, ynew, newsize div 5); newsize:=newsize*2 div 3; end; end; end; 18$ ${Asosiy dastur} begin {grafik jihoz ko'rinishini beramiz. Drayverlar Vga VgaHi rejimda 640x480 nuqtalar ekran ochilishiga ruxsat beradi} Driver:=Vga; Mode:=VgaHi; {grafik rejimni initsializatsiyalash} InitGraph(Driver, Mode, 'C:\BP\BGI'); {rekurent protsedurani chaqirish} DrowStar(320, 240, 120); {320=GetMaxX/2; 240=GetMaxY/2} Readln; CloseGraph end. 19$ $3.1 – ILOVA. Bo'laklar sonini ma'lum vaqt bo'yicha topish (rekursiyadan foydalanamiz). program p2_3_1; uses Crt; var N:word; {rekurent funksiya} function Count(N:word):Longint; begin if (N=0) then Count:=1 {rekursiya tugashining sharti} else Count:=2*Count(N-1) end; {asosiy dastur} begin clrsrc; {ekranni tozalash} writeln('Vaqtni millisekundlarda kiriting'); write('N='); readln(N); write ('bo’laklar soni =', Count(N)); readkey; end. 20$ $3.2 – ILOVA. Bo'laklar sonini ma'lum vaqt bo'yicha topish (rekurentsiz). program p2_3_2; uses Crt; var N:word; function Count(N:word):Longint; var M:Longint; i:word; begin M:=1; for i:=1 to N do M:= 2*M; Count:=M; end; {asosiy dastur} begin clrsrc; {ekranni tozalash} writeln('Vaqtni millisekundlarda kiriting'); write('N='); readln(N); write ('bo’laklar soni =', Count(N)); readkey; End. 21$

Algoritmlarni loyihalash va tahlil qilish MUNDARIJA KIRISH ………………………………………………………………………3 1-BOB. Rekurent nisbatlar (munosabatlar) ning nazariy asoslari ………..4 1.1. Rekurent nisbat haqida umumiy tushunchalar ………………….4 1.2. Rekurent nisbatlarni sozlash ……………………………………..8 2-BOB. Rekurent algoritmlarni ishlab chiqish …………………………...10 2.1. Rekurent algoritmlarni loyihalash ……………………………...10 2.2. Rekerent nisbatlarga misollar …………………………………..13 XULOSA …………………………………………………………………...16 FOYDALANILGAN ADABIYOTLAR RO‘YXATI …………………….17 ILOVALAR ………………………………………………………………..18 1

KIRISH Barcha algoritmik tillarda rekurent nisbatlar va proseduralarni – qismdasturlar ko'rinishida rasmiylashtirilgan operator bloklarini dasturlash imkoniyati mavjud. Rekurent nisbatlar tilning muhim konstruksiyalariga taalluqli bo'lib, uchta muhim masalani yechishga imkon beradi:  dastur matnida o'xshash fragmentlarni ko'p martalab takrorlash zaruratidan qutqaradi;  dastur tuzilishini yaxshilab, uni tushinishni osonlashtiradi;  dasturlash xatolariga va dasturlarni takomillashtirishda kutilmagan oqibatlarga chidamlilikni oshiradi. Kurs ishi mantiqiy va algebraik tafakkur malakalarini rivojlantirishga va Pascal tilida dasturlarni yozishda rekurent nisbatlardan foydalanish imkoniyatlarini o'rganishga yordam beradi. Bu til dasturlash asoslarini o'rgatish uchun bejiz tanlanmagan, chunki Pascal – dastur tuzilishi bevosita masala tuzilishini aks ettirish lozim bo'lgan ko'rinishda “strukturalashgan” dasturlarni yasashga yordam beradigan dasturlash tillaridan biridir. Pascal tilining bu xususiyati hamda uning konstruksiyalarining intuitiv tushunarliligidan uning yetarlicha oddiyligi, bu tilga dasturlash tillari orasida mustaqil o'rinni egallashga imkon beradi. Dasturlashning hozirgi davrdagi yurug'i strukturalashgan dasturlar afzalliklarini tan olinganligidir. Shuning uchun Pascal muhandislar va ilmiy xodimlar tomonidan keng foydalanilmoqda, informatika bo'yicha xalqaro olimpiadalar tili hisoblanadi. Hozirgi paytda bu tilning yetarlicha ko'p talqinlari mavjud. Eng ko'p tarqalgan talqini 1992 yilda Borland International (Borland Pascal 7.0 va Turbo Pascal 7.0) firmasi tomonidan ishlab chiqqan talqini hisoblanadi. Faqat MS DOS oddiy rejimda ishlashga imkon beruvchi Turbo Pascal 7.0 dan farqli Borland Pascal 7.0 uchta ish rejimini o'z ichiga oladi: MS DOS oddiy rejimi, MS DOS himoyalangan rejimi va Windows muhitida. Kurs ishi kirish, ikkita bob, xulosa, foydalanilgan adabiyotlar ro'yxati va ilovalardan iborat. 2

1-BOB. Rekurent nisbatlar (munosabatlar) ning nazariy asoslari 1.1. Rekurent nisbat haqida umumiy tushunchalar Qismdastur tanasida dasturdagi tavsiflangan barcha obyektlarga, shu jumladan qismdasturning o'zining nomiga kirish mumkin. O'z-o'zini chaqirishni foydalanuvchi protsedura va funksiyalar rekurent protsedura va funksiyalar deb ataladi (to'g'ri rekurent). Rekurent – bu hisoblash jarayonini shunday tashkil etish usuliga aytiladiki, bunda uni tashkil etuvchi operatorlarni bajarish jarayonida o'z-o'ziga aylanadi. Tipik rekurent protsedura quyidagi ko'rinishga ega: procedure Rec (n:Integer); begin <rekursiyaga kirish amala> if <shrtni tekshirish> then Rec(n-1); <rekursiyadan chiqish amali> end;xn , bu yerda x – butun son, n – butun nomanfiy son, ni hisoblash rekurent funksiyasiga misolni qaraymiz. Ma'lum faktdan foydalanamiz: x n = ¿{ 1,m= 0da ,¿¿¿¿ function Deg(x, n: integer) :longint; begin if n = 0 then Deg:=1 3

else Deg:=Deg(x, n-1)*x; end; 1.1-rasmda rekurent nisbatlarning to'g'ri va teskari yo'li ko'rsatilgan. Bu holda а o'zgaruvchiga 2 4 qiymat beriladi. Ixtiyoriy rekurent qismdastur norekurent bo'lmagan tarmoq bo'lishi lozim, bizning holda – bu if n = 0 then Deg:=1; Rekurent qismdasturga murojaat ixtiyoriy boshqa qismdasturni chaqirishdan hech qanday farq qilmaydi. Rekurent qismdasturlarni bajarishda «qaytish steki» deb ataluvchi maxsus xotira sohasidan foydalaniladi. Har bir yangi rekurent murojaatda xotirada barcha lokal o'zgaruvchilarga ega qismdastur nusxasi yaratiladi. Bu nusxalar chegaraviy shartga chiqqunga hosil bo'laveradi (norekurent tarmoq). Ravshanki, chegaraviy shart bo'lmagan holda bunday nusxalar sonini chegaralanmagan o'sishi stekning to'lishi hisobiga dasturning favqulotda to'xtatilishiga olib keladi. Rekurent qismdasturning barcha yangi nusxalarining xosil bo'lishi chegaraviy shartga chiqquncha hosil bo'lishi rekursiyaning to'g'ri yo'li (rekurent pasayishi) deb ataladi. Kompyuter xotirasida bir vaqtda joylashishi mumkin bo'lgan rekurent qismdasturlar nusxalari maksimal soni rekursiya chuqurligi deb ataladi. Rekurent chaqiriqlar bilan hosil qilingan rekurent qismdasturlarning eng birinchisigacha ishining tugatilishi rekursiyaning teskari yo'li (rekurent ko'tarilish) deb ataladi. Har bir rekurent protsedura yoki funksiyaning boshida daastur to'xtab qolganda undan kompyuter qayta yuklashsiz ixtiyoriy tugmani oddiy bosish bilan chiqishga imkon beruvchi if KeyPressed then Halt; satrni joylashtirish mumkin. Keypressed funksiya true natijani qaytaradi, agar klaviaturada simvolni hosil qiluvchi tugma bosilsa, va false – aks holda. Masalan , repeat 4

until Keypressed; operator bo'sh operatorni o'z ichiga oladi va dasturni bajarish paytida tugma bosilguncha tanaffusni ta'minlaydi. 1.1 – rasm. Rekurent nisbatlarning to'g'ri va teskari yo'li 5

O'xshashlar

Arifmetik ifodalarni keltiriah usullari. Algoritmlarni loyihalash va tahlil qilish

Arifmetik ifodalarni keltiriah usullari.Algoritmlarni loyihalash va tahlil qilish

Algoritmlarni tahlil qilish asoslari. Turli xil ishlash baholari algoritmlar

MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish

TANLOV BO’YICHA SARALASH. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH