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
Rekursiv funksiya yozish uchun avvalo : 1) rekkurent munosabat; 2) shu munosabat uchun boshlang‘ich holatlar aniqlangan bo‘lishi shart. Rekkurent munosabat deganda qaralayotgan jarayonga doir muayyan bosqichlami avvalgi bosqichlar bilan bog‘lovchi munosabatlar tushuniladi. Masalan, N! =N*(N—1) formulani N! uchun rekurent munosabat deb qarash mumkin. Boshlang‘ich holat sifatida esa 1!=1 olinadi. Keltirilgan ma’lumotlami hisobga olsak, faktorialni hisoblash masalasi uchun rekkurent va boshlang‘ich munosabatlar quyidagicha bo'ladi:
𝑁!={𝑁∗(𝑁−1)! 𝑎𝑔𝑎𝑟 𝑁>11, 𝑎𝑔𝑎𝑟 𝑁=1
Ko‘rinib turibdiki, N! ni hisoblash uchun (N-1)! ma’lum bo‘lishi kerak. Lekin, (N-1)!=(N-1)*(N-2)! bo‘lgani uchun o‘z navbatida (N-2)! ni inpish talab qilinadi. (N-2)! esa (N-3)!*(N-2) ga teng va hokazo. Bu yerda N! ni hisoblash algoritmi o ‘zining ichiga o ‘zi “cho‘kib” borishi hodisasi ro‘y bermoqda. Cho‘kish jarayoni boshlang‘ich holat sodir bo‘lgunga qadar, ya’ni 1! gacha davom etadi. Shundan keyin, “cho‘- kish” jarayoni
to‘xtaydi, 1!=1 ekanligi haqida ko‘rsatma olgan kompyuter yuqoriga qarab “suzib” chiqish bosqichini boshlaydi. Ya’ni, 2!=1, 2!=l-2=2, 3 !=2!-3=6 va hokazo. Bu holat to N! hisoblanmaguncha davom etaveradi.
Yuqorida keltirilgan masala dasturi quyidagicha bo’ladi
#include
using namespace std;
long fak(int m)
{ long f;
if (m==1) f=1; else f=fak(m-1)*m;
return f;
}
int main()
{
int n;
cout<<"Butun sonni kiriting: ";
cin>>n;
cout<}
Dastur natijasi quyidaicha bo’ladi:
Faktorialni hisoblash funksiyasini takrorlash operatori yordamida ham hisoblash mumkin ammo ba’zi narsalarni rekursivlikdan boshqacha yo’ldan foydalanib hisoblab bo’lmaydi.
Masalan: f(n ) funksiyaning qiymatlari f(0 )= 1 , f(2n)= f(n) va f (2n+1)=f (n)+1 ifodalar yordamida topiladi. Berilgan k natural soni uchun f(k) ni toping.
Buni rekursiyadan foydalanmasdan bajarish imkonsiz.
Uning dasturi quyidagicha bo’ladi:
#include
using namespace std;
int fun(int m)
{
int f;
if (m==0) f=1; else
{
int h=m/2;
if (m % 2==0) f=fun(h); else f=fun(h)+1 ;
}
return f;
}
int main()
{
int n;
cout<<"Butun sonni kiriting: ";
cin>>n;
cout<<"f(n)="<}
Dastur natijasi quyidagicha bo’ladi:
Xulosa o’rnida shuni aytish joizki C++ dasturlash tili funksiyalar tili hisoblanadi.
Unda hech bo’lmaganda bitta main() funksiyasi qo’llaniladi.
Funksiyalar dasturchining ishini sezilarli darajada osonlashtiradi .
Do'stlaringiz bilan baham: |