|
Ózbekstan respublikasí joqarí bilimlendiriw ilim hám innovaciyalar ministrligi
|
| Sana | 20.05.2024 | | Hajmi | 103,39 Kb. | | #244641 |
Bog'liq 2K1 Beknazarov Túwelbay
ÓZBEKSTAN RESPUBLIKASÍ JOQARÍ BILIMLENDIRIW
ILIM HÁM INNOVACIYALAR MINISTRLIGI
BERDAQ ATINDAǴI QARAQALPAQ MÁMLEKETLIK UNIVERSITETI
Algoritmlestiriw hám programmalastırıw texnologiyaları kafedrası
Algoritmler hám berilgenler strukturası páninen
ÓZBETINSHE JUMÍSÍ
Тema: Algoritm tusinigi.Rekursiv algoritm
Fakultet: Matematika
Tálim baǵdarı: “Kompyuter ilimleri hám programmalastırıw texnologiyaları”
Kursı hám toparı: 2K1 gruppa
Studenttiń F.A.Á: Beknazarov Túwelbay ____________
(imza)
Qabıllaǵan: Kalbaev Allambergen ____________ (imza)
Nókis 2024-j
Tema: Algoritm túsinigi. Rekursiv algoritmlar.
Algoritm — málim bir túrge tiyisli máselelerdi sheshiwde isletiletuǵın ámellerdiń arnawlı bir tártipte orınlanıwı haqqındaǵı anıq qaǵıyda (programma ). Kibernetika hám matematikanıń tiykarǵı túsiniklerinen biri. Orta ásirlerde sanaqtıń onlıq sisteması boyınsha tórt arifmetik ámel atqarılatuǵın qaǵıydanı algoritm dep ataǵan. "Bul qaǵıydalardı matematikaǵa IX asirde al-Xorezmiy kirgizgen. Evropada bunday qaǵıydalar onıń tugilgan jurtına salıstırǵanda latınshalastırılgan (Algoritmus yamasa Algorithmus formasında „algorizm“ delingen), keyinirek „algoritm“ga aynalǵan". Pánde „Yevklid algoritmi“, „G'iyosiddin Koshiy algoritmi“, „Laure algoritmi“, „Markov algoritmi“ dep atalıwshı algoritmlar málim. Algoritm túsinigi barǵan sayın keńeyip barıp, kibernetikanıń teoriyalıq hám logikalıq tiykarı esaplanǵan algoritmlar teoriyası payda boldı. Ózbekstanda bir neshe ilimiy izertlew mákemeleri hám esaplaw oraylarında algoritmnan paydalanıw salasında nátiyjeli jumıslar alıp barılmaqta. Mısalı, Ózbekstan Pánler Akademiyası „Kibernetika“ ilimiy islep shıǵarıw birlespesinde, Ózbekstandaǵı barlıq universitetlerde, Tashkent mámleket texnika universitetinde, Ózbekstan Respublikası Makroekonomika hám statistika ministrligi qasındaǵı Esaplaw orayı hám basqa mákemelerde alıp barılıp atırǵan jumıslar buǵan mısal bola aladı.
REKURSIYA:
Rekursiya - funkciya (procedura) nı sol funkciyanı ishinde shaqırılıwı dep qarasaq eń túsinikli kórinis boladı. Programmistler arasında sonday gáp bar: "Rekursiyani biliw ushın, aldın onı biliw kerek". Rekursiya orınlanıwı ushın eki zat bolıwı kerek.
1. Ózin shaqırıw
2. Toqtap qalıw shegarası
Hesh anańız sizge uyge kirip karobkanıń ishinen qandayda bir neni alıp shiq dep aytqanba? Siz bolsa karobkalardi qarap 1 saatta tapqansız/yamasa ulıwma tabalmaǵansız. Sebebi siz karobkanı kórip shıǵıw izbe-izligin tuwrı qoymaǵansız.
Másele: karobkalar ishpe-ish qálegenshe jaylastırılǵan, qaysı bolıp tabıladı karobka ishinde gilt bar. Sizge giltti tabıw programmasın dúziw wazıypası qoyılǵan.
Rekursiyaga qoyiw ushın bul eki shárt jazıp alamız :
1. Islew shárti: karobka ishinde karobka shıqsa, onı ashıp kor.
2. Toqtap qalıw shárti: karobka ishinen gilt shıqsa toqtatıw.
Rekursiv funksiyanıń toqtap qalıw shegarası bolmasa bolsa, ámeller sheksiz atqarılaberedi, aqıbette crash beredi, yamasa programma asılıp qaladı. Al nege?
Funksiya jumısqa túskende keyingi shaqırılıp atırǵan funksiya STACKqa qosıp barılaberedi. Rekursiv funksiya islegende ózin-ózi shaqırıwın ayttım, áyne shaqırıwshı funkciya bolsa shaqırılǵan funksiyanı nátiyjesin kútip turadı, ol bolsa ózi shaqırǵan funksiya nátiyjesine baylanıslı boladı.... hám taǵı basqa tokı toqtap qalıw noqatındaǵı funksiyaǵa barǵansha. Aqırǵı noqatdaǵı funksiya islegende bolsa, stacktan shıǵıp ketip odan aldınǵısı atqarılıp, odan aldınǵısına juwap jetip baradı... hám taǵı basqa eń birinshi shaqırılǵan funksiya eń aqırında jabıladı.
Bul stack tolıp qalsa yamasa toqtap qalıw shegarası nadurıs qoyılıwı aqıbetinde Stack Overflow error alasız. Keliń bunı printFun funkciya mısalında kóremiz:
void printFun(int test) //C++
{
if (test < 1)
return;
else
{
cout << test << " ";
printFun(test-1);
cout << test << " ";
return;
}
}
int main()
{
int test = 3;
printFun(test);
}
Tómendegi funkciyaǵa itibar beriń printFun funksiyası 3 argumenti menen shaqırilǵanda tap 1 ge barmaǵanǵa shekem 3, 2, menen shaqırılǵan funkciyalar kútip turıptı. hám aqır-aqıbetde 1 menen shaqırılǵan element , teris jabilǵannan keyin izbe-izlilikde 2, 3 menen shaqırılǵan funksiyalar da jawıldı.
Nátiyje:
3 2 1 1 2 3
Taǵı bir mısal N sanınıń Faktorialın anıqlaw :
def fact(x): #python
if x == 1:
return 1
else:
return x*fact(x-1)
Bul jerde eki shárt retinde:
1. Rekursiya shárti: ózinen kishi sandı shaqırıw.
2. Toqtatıw shárti: 1 ge barǵanda funkciyanı toqtatıw.
Islew stackı bolsa tóbedegi mısalda keltirilgen sıyaqlı fact(3) shaqırılǵanda fact(3) fact (2) ni shaqıradı hám nátiyjesin kútip jumısın toqtatpay turadı, tap sonday fact (2) fact (1) shaqıradı, fact(1) jabılǵannan keyin bolsa stack terisine bosap baradı. Bul jerde C#da san faktorialı esaplaw ushın rekursiya algoritmınıń ápiwayı úlgisi keltirilgen:
using System;
class Program
{
static void Main (string[] args)
{
int number = 5; // San faktorialın esaplaw ushın kerek bolǵan sandı kórsetemiz
int result = Factorial (number);
Console. WriteLine ($" San faktoriali {number} teń {result}");
}
static Factorial (int n)
{
if (n == 0) //Eger n 0 ge teń bolsa,1 di qaytaradı
return 1;
return n * Factorial (n - 1); // Faktorialdı esaplaw ushın rekursiv shaqırıw
}
}
Bul kod rekursiv túrde san faktoriali esaplaw ushın isletiledi.
Rekursiya islep atirǵan waqıtta dıqqatlı bolıw kerek, sebebi eger base case anıqlanbasa yamasa rekursiv shaqırıwlar sheklenbese, programmanıń islewinde mashqala júzege keliwi múmkin.
Rekursiya menen jazılǵan kod ádette ápiwayılaw hám aǵıwǵa qolaylaw boladı, biraq onıń natiyjeliligi hám yadtı kóp isletiwi múmkin. Bul bolsa kodtı jazıw hám analiz qılıw procesin ańsatlastıradı.
Rekursiyanıń bir neshe wazıypaları bar bolıp tabıladı:
1. Ápiwayı algoritmlar jazıw : Rekursiya, ápiwayı algoritmlardı jazıwda járdem beredi. Mısalı, faktorialni esaplaw, fibonachchi izbe-izligin generatsiya qılıw yamasa qosımsha matematikalıq ámellerdi orınlaw ushın rekursiv algoritmlar jazıwda paydalı boladı.
2. Járdem beriw: Rekursiya, programmalastırıwda járdem beriwdiń qolay usılı bolıp, máseleler sheshiwde yamasa maǵlıwmatlardı qayta islewde járdem beredi.
3. Programma kodın ańsatlastırıw : Rekursiya, kodtı ańsatlastırıwda hám oqılıwında qolaylıq jaratadı. Koddıń kóbirek bólegin tákirarlaw hám qayta islew talap etetuǵın wazıypalarda rekursiya isletiliwi múmkin.
4. Yad optimallastırıw : Rekursiya, programmada yad optimallastırıwǵa járdem beredi. Mısalı, programmanıń jumısqa túsiwine uqsas rekursiv shaqırıwlardı qayta isletmesten yadtı kemrek isletiw múmkin.
5. Programmanıń dúzilisi hám analizi: Rekursiya tiykarlanıp programma dúzilisi hám analizinde isletiledi. Rekursiv funkciyalar hám proceduralar, programmanıń dúzilisi hám islewin analiz etıwde járdem beredi.
Rekursiya programmalastırıwda kúshli bir qural bolıp, onıń natiyjeliligi hám qolaylıǵı zárúrli bolıp tabıladı. Biraq,diqqatli bolıw kerek, sebebi nadurıs rekursiv shaqırıwlar programmanıń toqtap qalıwına alıp keliwi múmkin.
Fibanashı sanlardıń keyingi aǵzasın tabatuǵın C# programmalastırıw tilindegi kodı:
using System;
class Program
{
static int Fib(int n)
{
if (n <= 1)
{
return n;
}
return Fib(n - 1) + Fib(n - 2);
}
static void Main()
{
Console.WriteLine("Fibonachi sanlar:");
for (int i = 0; i < 10; i++)
{
Console.WriteLine(Fib(i));
}
}
}
Paydalanılǵan ádebiyatlar
https://metanit.com/sharp/tutorial/
https://www.texnoman.uz/
https://ru.wikipedia.org/
|
| |
