Rekursiya va rekursiv funksiyalarga oid algoritmlar

Информация о документе

Цена	12000UZS
Размер	1.2MB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Информатика и ИТ

Rekursiya va rekursiv funksiyalarga oid algoritmlar

Купить

KIRISH
Rekursiya
Rekursiya — Funksiya o ziga o zi to g ridan-to g ri yoki qandaydir vosita orqali ʻ ʻ ʻ ʻ ʻ ʻ
murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv funksiya
deb ataladi[1]. Rekursiv funksiya o zini — o zi chaqirgani uchun dasturchilar
ʻ ʻ
orasida quyi oldin rekursiya nimagligini tushunish kerak“ — Stephen Hawking[2].
Rekursiya funksional dasturlashning asosiy elementlaridan hisoblanadi. Rekursiya
deyarli hamma joyda ishlatiladi. Ba zi masalalarning iterativ yechimi juda ham
ʼ
uzun bo lib ketishi mumkin. Rekursiya esa kodni bir necha barobar qisqartirib
ʻ
berishi mumkin. Aksariyat tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib
bo lmaydi
ʻ
Tree, Graph, Heap, Quick Sort, Merge Sort
Bu ro'yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar
bo lgan Tree va Graphlarda rekursiya har qadamda uchraydi.
ʻ
Rekursiya har doim xotiradan qo shimcha joy talab qiladi.
ʻ
Rekursiv yechimda xato qilish ehtimoli yuqori, chunki rekursiya juda ham
chalg ituvchi.
ʻ
Rekursiv yechimni xatosini topish qiyin.
Murakkab algoritmni hisoblash qiyin
Algoritmi
Qutilar ichma-ich ixtiyoriy joylashtirilgan, qaysidir quti ichida kalit bor. Siz kalitni
topish algoritmini tuzishingiz kerak
Rekursiyaga qo yish uchun ushbu ikki shartni yozib olamiz
ʻ
Ishlash sharti: Quti ichida ichki quti chiqsa, uni ochib ko r. Agar ichki qutidan kalit
ʻ
chiqmasa tashqi qutining kelgan joyidan davom et.
To xtash sharti: Quti ichidan kalit topilsa to xta.
ʻ ʻ
Dasturi

Fibonachchi ketma ketligining n — hadini rekursiya qism dastur orqali hisoblovchi
dastur
#include <iostream.h>
int fib(int);
int main()
{
int n;
cout << "n="; cin >> n;
cout << fib(n) << endl;
return 0;
}
int fib(int k)
{
if (k == 0 || k == 1) return 1;
else return fib(k - 1) + fib(k - 2);
}
Rekursiyaga oid dastur
#include <bits/stdc++.h>
using namespace std;
void tower(int n, char sourcePole, char destinationPole, char auxiliaryPole)
{
if(0 == n)
return;
tower(n - 1, sourcePole, auxiliaryPole, destinationPole);
cout << "Diskni ko'chiring "<< n << " dan " << sourcePole <<" ga "<<
destinationPole << endl;
tower(n - 1, auxiliaryPole, destinationPole,

sourcePole);
}
int main()
{
tower(3, 'S', 'D', 'A');
return 0;
}
Rekursiv funksiyaning to xtash chegarasi bo lmasa, amallar cheksiz bajarilaveradi,ʻ ʻ
oqibatda dastur xatolik keltirib chiqaradi.
II.Rekursiv algoritm va funksiyalar.

Rekursiya matematika, informatika va dasturlash fanlaridagi asosiy tushunchadir.
Dasturlash tillarida rekursiv dastur o’z-o'ziga murojaat qiluvchi dasturdir (xuddi
matematikada rekursiv funktsiya funksiyaning o'zi bilan aniqlangani kabi).
Keling, bilimning turli sohalaridagi rekursiyalarga misollarni ko'rib chiqaylik.
Matematika uchun faktorialning rekursiv ta'rifi allaqachon ko'rib chiqilgan.
Shuningdek, Fibonachchi raqamlarini rekursiv aniqlash:
Rekursiv algoritm - bu algoritmni aniqlashda o'ziga bevosita yoki bilbosita murojat
etishi. Ko'pincha bunday algoritm qandaydir tushunchaning rekursiv ta'rifiga

asoslanadi. Masalan, N faktoriali haqida quyidagilarni aytish mumkin: agar N > 0
bo’lsa, N! = N*(N – 1)! ifoda o’rinlidir va
N = 0 bo‘lsa, N!= 1 ifoda o’rinlidir . Bu rekursiv ta'rifdir.
1 Rekursiv algoritmlar va ularning tahlili
Deklar. Ustida amal bajarish.
Deklar
chetga ega navbat degan ma noni bildiradi. Dekning o„ziga xos xususiyati shuki,‟
unga elementlar har ikkala tomondan – chapdan va o„ng tomondan kiritilishi
Dek ustida bajariladigan amallar:
Chapdan element kiritish.
O„ngdan element kiritish.
Chapdan element chiqarish.
O„ngdan element chiqarish.
Dek bo„shligini tekshirish.
Dek to„laligini tekshirish.
C++ tilida dekni statik ko„rinishda, ya’ni bir o„lchamli massiv ko'rinishida

amalga oshirishga misol: Berilayotgan butun sonlar ketma-ketligining 1- yarmini
dekning chap tomonidan, qolgan yarmini dekning o'ng tomonidan kiriting.
Dekning elementlarini bir safar chapdan, bir safar o'ngdan juftlikka tekshirib, toq
elementlari o'chirilsin.
Algoritm :
1) Dekka nechta element kiritilishi aniqlanadi – n, i=0.
2) 4-qadamga o„tiladi.
3) A bo'lsa, dekning o'ng tomonidan kiritiladi, 2-qadamga o'tish.
4) Agar dek bo'sh bo'lmasa, chapdan element chiqarib olamiz. Agar element juft
bo'lsa, bu massivga joylaymiz. 5-qadamga o'tiladi. Agar dek bo'sh bo'lsa, 6-
qadamga o'tish.
5) Agar dek bo'sh bo'lmasa, o'ngdan element chiqarib olamiz. Agar element juft
bo'lsa, bu massivga joylaymiz.5-qadamga o'tiladi Agar dek bo'sh bo'lsa, 6-
qadamga o'tish.
6) bu massiv elementlarini dekka o„ng tomondan kiritamiz.
7) Dek tarkibini ekranga chiqaramiz.
_ M u h a m m a d a l - X o r a z m i y
Yarimstatik berilganlar
tuzilmalari
Yarimstatik ma'lumotlar tuzilmasi. Dek, xossalari.1.Yarimstatik ma’lumotlar
tuzilmasiYarimstatik ma’lumotlar tuzilmasini quyidagicha tavsiflash mumkin:-
o‘zgaruvchan uzunlikka ega va uni o‘zgartiruvchi oddiy funksiyalariga ega;-

tuzilmaning uzunligini o‘zgartirish ma’lum bir chegarada, ya’ni qandaydirbir
maksimal qiymatdan oshmagan holda amalga oshirilishi mumkin;Agar yarimstatik
tuzilmani mantiqiy jihatdan qaraydigan bo‘lsak, u holdachiziqli ro‘yhat
munosabati bilan bog‘langan ma’lumotlar ketma-ketligitushuniladi.
Berilganlarni abstrakt toifalari
Algoritmlar haqida malumot
Ma’ lumotlarni abstrakt toifalari Umuman olganda toifalar o‘zgaruvchi yoki ifoda
qabul qilishi mumkin bo‘lgan qiymatlar to‘plami orqali tavsiflanadi. Ko‘plab
dasturlash tillarida ma’lumotlar standart va foydalanuvchi tomonidan beriladigan
toifalarga ajratiladi. Ma’lumotlarni standart toifalariga quyidagi 5 ta tur
o‘zgaruvchilari kiradi: a) butun (INT); b) haqiqiy (FLOAT) ; c) mantiqiy (BOOL);
d) belgili (simvol) (CHAR);
e) ko‘rsatkichli (*). Foydalanuvchi tomonidan aniqlanadigan toifalar esa: a)
sanaladigan; b) diapazonli (oraliqli)
Algoritm bu oldimizga qo‘yilgan masalani yechish zarur bo‘lgan amallar ketma-
ketligidir.Algoritm so‘zi va tushunchasi IX asrda yashab ijod etgan buyur alloma
Muhammad al-Xorazmiy nomi bilan uzviy bog‘liq. Algoritm so‘zi Al-Xorazmiy
nomini Yevropa olimlari tomonidan buzib talaffuz qilinishidan yuzaga kelgan. Al-
Xorazmiy birinchi bo‘lib o‘nlik sanoq sistemasining tamoyillarini va undagi to‘rtta
amallarni bajarish qoidalarini asoslab bergan. Algoritmning asosiy
xossalari.Algoritmning 5-ta asosiy xossasi bor:
1.Diskretlilik (Cheklilik)
2.Tushunarlilik
3.Aniqlik
4.Ommaviylik
5.Natijaviylik

Use this for a powerful quote or statistic
Berilganlar tuzilmasini klassifikatsiya qilish.
Hammasi shulardan iborat edi !
2-Amali ish: Fibonachchi
ketma
ketligining
n –hadini
rekursiya qism
dastur orqali
hisoblovchi dastur.
Amali ish: n! faktorialni rekursiyali funksiya orqali hisoblochi dastur tuzilsin. n!
=1*2*…*(n- 1)*n;
Thank you for your attention
Summarize what this chart is about
Back up your points with data and charts

$_ Algoritmlar va berilganlar strukturalari. Rekursiv algoritm f dasturlash tilida yozilgan. Rekursiya va rekursiv algoritmlar. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari Rekursiya - bu subroutin o'zini o'zi chaqiradigan vaziyat. Bunday algoritmik qurilishga birinchi marta duch kelganda, ko'pchilik muayyan qiyinchiliklarga duch keladi, ammo ozgina amaliyot va rekursiya sizning dasturiy arsenalingizda tushunarli va juda foydali vositaga aylanadi. 1. Rekursiya mohiyati Protsedura yoki funktsiya boshqa protseduralar yoki funktsiyalarni chaqirishni o'z ichiga olishi mumkin. Protsedurani o'z ichiga olishi mumkin. Bu erda hech qanday paradoks yo'q - kompyuter faqat dasturda uchragan buyruqlarni ketma-ket bajaradi va agar u protsedura qo'ng'irog'iga duch kelsa, shunchaki ushbu protsedurani bajarishni boshlaydi. Buni qanday buyruq berganligi muhim emas. Rekursiv protseduraga misol: Rec (a: butun) protsedurasi; agar boshlang\u003e a Agar asosiy dasturda, masalan, Rec (3) shaklida qo'ng'iroq qilinsa nima bo'lishini ko'rib chiqing. Quyida bayonlarning ketma-ketligini ko'rsatuvchi jadval. Anjir. 1. Rekursiv protseduraning blok diagrammasi. Rec protsedurasi a \u003d 3. parametri bilan chaqiriladi, unda a \u003d 2 parametrli Rec protsedurasiga qo'ng'iroq bor. Oldingi qo'ng'iroq hali tugallanmagan, shuning uchun siz boshqa protsedura yaratilayotganligini tasavvur qilishingiz mumkin va uning ishi oxiriga qadar u o'zining birinchi ishini tugatmaydi. A \u003d 0 parametridan so'ng qo'ng'iroq jarayoni tugaydi. Ayni paytda protseduraning 4 ta nusxasi bir vaqtning o'zida bajariladi. Bir vaqtning o'zida bajariladigan protseduralar soni chaqiriladi rekursiya chuqurligi. (Rec (0)) deb nomlangan to'rtinchi protsedura 0 raqamini bosib chiqaradi va o'z ishini yakunlaydi. Shundan so'ng, boshqaruv uni (Rec (1)) deb nomlangan protseduraga qaytadi va 1-raqam bosiladi va hokazo, barcha protseduralar tugaguncha. Dastlabki qo'ng'iroq natijasi to'rtta raqamni chop etadi: 0, 1, 2, 3. Nima bo'layotganining yana bir vizual tasviri sek. 2. Anjir. 2. Rec protsedurasini 3-parametr bilan bajarish, 2-parametr bilan Rec protsedurasini bajarish va 3-raqamni bosib chiqarish, o'z navbatida, 2-parametr bilan Rec protsedurasini bajarish, 1-parametr bilan Rec protsedurasini bajarish va 2-raqamni bosib chiqarish va boshqalarni o'z ichiga oladi. Mustaqil mashq sifatida Rec (4) ni chaqirganda nima bo'lishini o'ylang. Shuningdek, quyida tasvirlangan Rec2 (4) protsedurasini chaqirganda nima yuz berishi haqida o'ylang, bu erda operatorlar almashadi. Rec2 protsedurasi (a: butun); writeln (a) boshlash; agar a\ u003e 0 bo'lsa, Rec2 (a-1); oxiri; Yuqoridagi misollarda rekursiv chaqiruv shartli gapning ichida ekanligini unutmang. Bu rekursiyani to oxirigacha davom ettirish$

uchun zarur shartdir. Shuni ham yodda tutingki, protseduraning o'zi boshqa
parametr bilan chaqiriladi, lekin u chaqirilgandek emas. Agar protsedura global
o'zgaruvchilardan foydalanmasa, unda rekursiya cheksiz davom etmasligi kerak.
Hisoblagichning maksimal qiymatiga erishmagunimizcha protseduraning yangi
namunasi, avvalambor, boshqa misolni chaqiradi va hokazo. Shundan keyingina,
chaqirilgan protseduralarning oxirgisi uning ko'rsatmalarini bajaradi, so'ngra
oxirgi, ammo bitta ko'rsatmani bajaradi va hokazo. LoopImitatsiya2 (1, 10) ni
chaqirish natijasi tabriklarni teskari tartibda chop etadi: Salom N 10 … Salom N 1
Agar biz rekursiv deb ataladigan protseduralar zanjirini tasavvur qilsak, unda 1-
misolda biz bundan oldin chaqirilgan protseduralardan keyingilariga o'tamiz. 2-
misolda buning teskarisi keyinroq oldingisiga. Va nihoyat, ikkita ko'rsatma
bloklari orasiga rekursiv qo'ng'iroqni qo'yish mumkin. Misol uchun:
LoopImitation3 protsedurasi (i, n: butun son); begin writeln ("Salom N", i);
(Birinchi ko'rsatmalar bloki bu erda joylashgan bo'lishi mumkin), agar i Bu erda
birinchi navbatda birinchi blokdagi ko'rsatmalar ketma-ket, so'ngra teskari tartibda,
ikkinchi blokning ko'rsatmalari bajariladi. LoopImitation3 (1, 10) ni chaqirganda
biz quyidagilarga ega bo'lamiz: Salom N 1 … Salom N 10 Salom N 10 … Salom N
1 Buni takrorlashsiz bir xil qilish uchun birdaniga ikki tsikl kerak bo'ladi. Xuddi
shu protsedura qismlarining bajarilishi vaqt ichida ajratilganligini ishlatish
mumkin. Misol uchun: 3-misol: raqamni ikkilik tizimga tarjima qilish. Ikkilik

$raqamlarning raqamlarini olish, ma'lum bo'lganingizdek, qolgan son bilan 2-son tizimining bazasida bo'lish orqali sodir bo'ladi. Agarda raqam mavjud bo'lsa, uning ikkilik ko'rinishida uning oxirgi raqami bo'ladi. 2 ga bo'linishdan butun sonni olish: biz bir xil ikkilik tasvirga ega bo'lgan sonni olamiz, ammo oxirgi raqamsiz. Shunday qilib, keyingi bo'linish maydoni 0 ga teng butun sonni olguncha yuqoridagi ikkita operatsiyani takrorlash kifoya qiladi. Repsursiz, u quyidagicha bo'ladi: X\u003e 0 boshlanganda c: \u003d x mod 2; x: \u003d x div 2; yozish (c); oxiri; Bu erda muammo shundaki, ikkilik vakillik raqamlari teskari tartibda (birinchi oxiri) hisoblab chiqiladi. Raqamni oddiy shaklda chop etish uchun siz massiv elementlaridagi barcha raqamlarni eslab, ularni alohida tsiklda ko'rsatishingiz kerak. Rekursiondan foydalanib, natijani ketma-ket va ikkinchi bosqichsiz to'g'ri tartibda olish oson. Aynan: BinaryRepresentation protsedurasi (x: butun); var c, x: butun; begin (Birinchi blok. Bu protsedurani chaqirish tartibida bajariladi) c: \u003d x mod 2; x: \u003d x div 2; (Rekursiv qo'ng'iroq) agar x\ u003e 0 bo'lsa, BinaryRepresentation (x); (Ikkinchi blok. Bu teskari tartibda bajariladi) yozish (c); oxiri; Umuman olganda, biz hech qanday foyda olmadik. Ikkilik vakillik raqamlari mahalliy o'zgaruvchilarda saqlanadi, ular rekursiv protseduraning har bir ishlaydigan holati uchun farq qiladi. Ya'ni, xotirani saqlab qolishning iloji bo'lmadi. Aksincha, biz ko'plab mahalliy o'zgaruvchilarni saqlash uchun qo'shimcha xotira sarflaymiz. Shunga qaramay, bunday echim menga juda chiroyli ko'rinadi. 4. Takroriy nisbatlar. Rekursiya va takrorlash Agar boshlang'ich vektor va keyingi vektorning oldingi holatga funktsional bog'liqligi bo'lsa, vektorlar ketma-ketligi takrorlanish munosabati bilan beriladi, deyiladi. Takrorlanish munosabatlari yordamida hisoblangan miqdorning oddiy namunasi - bu faktorial Keyingi omilni avvalgisidan hisoblash mumkin: Notation bilan tanishtirib, biz nisbatni olamiz: Formuladan (1) vektorlarni o'zgaruvchan qiymatlar to'plami sifatida talqin qilish mumkin. Keyin ketma-ketlikning kerakli elementini hisoblash ularning qiymatlarini takroriy yangilashdan iborat bo'ladi. Xususan, faktorial uchun: X: \u003d 1; for i: \u003d 2 to n do x: \u003d x * i; writeln (x); Har bir bunday yangilanish (x: \u003d x * i) chaqiriladi iteratsiya, va takrorlashni takrorlash jarayoni iteratsiya. Ammo shuni ta'kidlaymizki, munosabatlar (1) - bu ketma-ketlikning sof rekursiv ta'rifi va n-elementni hisoblash f funktsiyani o'zidan ko'p marta olishdir: Xususan, faktorial uchun siz quyidagilarni yozishingiz mumkin: Factorial funktsiyasi (n: butun son): butun; agar n\u003e 1 bo'lsa, undan keyin boshlang'ich: \u003d n * Fakultativ (n-1) else Faktor: \u003d 1; oxiri; Shuni tushunish kerakki, chaqirish funktsiyalari qo'shimcha qo'shimcha xarajatlarni talab qiladi, shuning uchun omilni hisoblashning birinchi varianti biroz tezroq bo'ladi. Umuman olganda, iterativ echimlar rekursiv echimlarga qaraganda tezroq ishlaydi. Rekursiya foydali bo'lgan holatlarga o'tishdan oldin, keling, uni ishlatmaslik kerak bo'lgan yana bir misolga e'tibor qarataylik. Takroriy munosabatlarning alohida holatini ko'rib chiqing, agar ketma-ketlikning keyingi qiymati bir biriga emas, balki darhol bir necha oldingi qiymatlarga bog'liq bo'lsa. Bunga misol sifatida taniqli Fibonachchi ketma-ketligini keltirish mumkin, bunda har bir keyingi element oldingi ikki elementning yig'indisidir: "Frontal" yondashuv bilan siz quyidagilarni yozishingiz mumkin: Fib (n: integer): butun son; agar n\u003e 1$ $bo'lsa, keyin Fib: \u003d Fib (n-1) + Fib (n-2), boshqa tolalar: \u003d 1; oxiri; Har bir Fib qo'ng'irog'i birdaniga ikkita nusxani yaratadi, ularning har biri yana ikkita nusxani yaratadi va hokazo. Operatsiyalar soni soniga qarab o'sib bormoqda n eksponent sifatida, garchi iterativ eritma etarlicha chiziqli bo'lsa ham n operatsiyalar soni. Aslida, bu misol bizga o'rgatmaydi QACHON rekursiya ishlatilmasligi kerak, lekin AS ishlatilmasligi kerak. Oxir-oqibat, agar tez iterativ (ko'chadan asoslangan) echim bo'lsa, xuddi shu pastadir rezursiv protsedura yoki funktsiyadan foydalanib amalga oshirilishi mumkin. Misol uchun: // x1, x2 - boshlang'ich shartlar (1, 1) // n - Fibonachchi funktsiyasining zarur bo'lgan soni Fib (x1, x2, n: integer): butun son; var x3: butun son; agar n\u003e 1 bo'lsa, keyin x3 ni boshlang: \u003d x2 + x1; x1: \u003d x2; x2: \u003d x3; Fib: \u003d tolasi (x1, x2, n-1); else end Fib: \u003d x2; oxiri; Hali ham iterativ echimlar afzal ko'riladi. Dastur: #include using namespace std; int a[10],R=0,n;//bu yerda n navbatga kiritilishi kerak bo'lgan elementlar soni. int kiritish(int s){ a[R]=s; R++; } int chiqarish(){ int t=a[0];$

for(int i=0;i
a[i]=a[i+1];
R--;
return t;
}
bool isEmpty(){
if(R==0) return true; else return false;
}
bool isFull(){
if(R>=10)return true;else return false;
}
int print(){
int i;
while(i
int k=chiqarish();i++;

$cout< kiritish(k);} } int main(){ int n,s; cout<<"n=";cin>>n; for(int i=0;i if(!isFull()){cin>>s; kiritish(s);} else{cout<<"navbat to'ldi"; n=i;break;} } cout<<"\nnavbat elementlari: "; print(); for(int i=0;i s=chiqarish();$ $if(s%2!=0)kiritish(s); } cout<<"\nnatijaviy navbat elementlari: "; print(); system("PAUSE"); } Dasturning bajarilishi natijasi: n=5 Adabiyotlar 1.Djangoda static filelar ni ishlatishda kelib chiqadigan muammolarga yechim 2.Introduction to the Design and Analysis of Algorithms 3.rekursiv algoritm. 4. https://uz.m.wikipedia.org/wiki/Quicksort 5. https://www.texnoman.uz/blogs/algoritm 6. https://uz.m.wikipedia.org/wiki/Insertion_sort 7. https://www.texnoman.uz/post/2-saralash-algoritmlari.html 8. https://poe.com/s/Vgku3UroXf0NDpDzNqET 9.Veb sayt VisuAlgo 10.GeeksforGeeks platforma$

Rekursiya va rekursiv funksiyalarga oid algoritmlar

Купить

Похожие документы
3d-max dasturida obektlarni yaratish
Algoritm va ma’lumotlar strukturasi
3D-MAX dasturi haqida
3D Studio MAX dasturiga kirish. 3D Studio MAX dasturi haqida tushuncha
Adobe photoshop dasturida tasvirlarda ishlov berish,taqdimot yaratish

Информация о документе

Продавец

Rekursiya va rekursiv funksiyalarga oid algoritmlar

Похожие документы