Yechish g'oyasi. Yuqoridagi masalani k ta elementli massiv
yordamida yechish ko‘pchilikning nazarida oson usulga o ‘xshaydi.
Lekin bu to‘g ‘ri emas. Chunki, k yetarlicha katta son b o ‘lsa, k ta
elementli m assiv kom pyuter xotirasiga sig‘m ay qolishi mumkin. Qola-
versa, siqqan taqdirda ham, bu elementlaming hammasidan foyda-
lanilmaydi. M asalan, k= 1000 bo‘lganda bu masalani yechish uchun
massivning 1000 ta elementidan k o ‘pi bilan 11 tasi kerak b o ‘ladi
(nima uchunligini o ‘ylab k o ‘ring), qolganlari esa kompyuter xotirasini
befoyda band qiladi. Bunda xotiradan n o ‘orin foydalanish holati yuz
beradi va u keyinchalik salbiy oqibatlarga olib kelishi mum kin.
Shuning uchun qo‘yilgan masalani massivdan foydalanmay yechish
eng yaxshi usul hisoblanadi. Bu usulning mohiyati rekursiya
mexanizmini qo ‘llashdan iborat.
Zarur b o ‘lgan rekkurent munosabat va boshlang‘ich holatlam ing
masala shartida keltirilganligi ishni yanada osonlashtiradi.
# include
int fun(int m)
{ '
int f;
i f (m ==0) f = l ; else
{
int h=m/2;
i f (m % 2 = = 0 ) f=fun(h); else f=fun(h)+1 ;
i
/
return f;
}
void main()
{
i l l
in t n;
cout «
’’Butun sonni kiriting”;
cin » n ;
cout « ”f ( “« n « ”) = ”«fiun (n);
return;
x
/
Bu dastumi k = l 1 b o ‘lgan hoi uchun bajargan EHM
/ ( H ) = 4
natijani ekranga chiqaradi.
Yuqoridagi m a’lumotlardan k o ‘rinib turibdiki, rekursiya oddiy
protsedura yoki funksiyaga nisbatan murakkabroq tushuncha, lekin u
m ohir dasturchi q o ‘lida juda ham yaxshi vositaga aylanishi mumkin.
Do'stlaringiz bilan baham: |