Mavzu: Algoritmlarning matematika bilan bog’liqligi (8 soat) Reja

5. Tipik masalalar: Saralash va izlash masalalari uchun algoritmlar va ularning murakkabligi.

Funksiya ancha qisqa va balkim ozroq tushunarsiz. Xo’sh, unda farq nimada? Qisqalik va soddalikning sababi biz belgilardan tashkil topgan satr yoki massivni teskarisiga o’zgartirmoqchi bo’lganimizda ekanligini yodingizda saqlang.

Bu shuni anglatadiki, strlen() va getline() ga o’xshagan funksiyalardan C++ standard kutubxonasidan foydalanishimiz mumkin. Agar bizda bunaqa funksiyalar mavjud bo’lmasa, unda bizning iterative funksiyamiz boshqacharoq bajarilishi lozim:
void iterativeReverse() {
char stack[80];
register int top = 0;
cin.get(stack[top]);
while(stack[top]!='\n')
cin.get(stack[++top]);
for (top -= 2; top >= 0; cout.put(stack[top--]));
}
While ga tegishli getline() va yuqori qiymatlarning avtoinkrementi strlen() o’rnida kelgan. For esa odatdagidek xilda. Bu tahlil albatta, aniq teoretik emas, chunki butun sonlarni o’z ichiga oluvchi kiritish qatorini teskarisiga aylantirish stekning ma’lumotlar tipini char dan int ga o’zgartirgandan keyin iterativeReverse() dek bir xil bajariladi.
Massiv uchun stekda foydalanilgan o’zgaruvchi nomi tasodifiy emasligini yodda tuting. Biz, shunchaki, Sistema tomonidan shubhasiz bajarilganlarni oydinlashtiramiz. Bizning stek amalga oshirish vaqti stekidan ko’proq vaqt talab etadi. Bu muhim, chunki birgina oddiy murojaatlar bunda dumli rekursiyada yetarli bo’lganidek yetarli emas. Rekersiv versiyadagi put() ham bunda hisobga olinishi zarur. iterativeReverse() funksiyasi uchun stek o’zgaruvchisi lokal ekanliginiham yodda saqlang. Shunday bo’lsada, agar global tarzda st obyekti yaratilishi talab etilsa, unda buning amalda qo’llanilishini quyidagicha yozish mumkin bo’ladi:
void nonRecursiveReverse() {
int ch;
cin.get(ch);
while (ch != '\n') {
st.push(ch);
cin.get(ch);
}
while (!st.empty())
cout.put(st.pop());
}
stek st ning funksiyadan tashqardagi e’loni bilan. iterativeReverse() ni nonRecursiveReverse()ga taqqoslagandan keyin , biz shunday xulosa qilishimiz mumkinki, birinchi versiya yaxshiroq, chunki, u tezroq ishlaydi va hech qanaqa funksiya murojaatlari yo’q va funksiya o’z-o’zini qoniqtiradi, lekin nonRecursiveReverse() esa har bir iteratsiyada kamida bitta murojaatdan foydalanadi, dastur ishlashi ham sekin. Funksiya rekursiv likdan iteraktivversiyaga o’zgartirilganda , dastur aniqligiga zarar yetishi mumkin va dastur kodining qisqaligi yo’qolishi mumkin. C++dagi rekursiv funksiyalarning iteraktiv versiyalari boshqa dasturlash tillaridagi kabi uzun emas, shu sababli dastur qisqaligi ahamiyatga molik bo’lmasligi mumkin.
Xulosa o’rnida, von Kochning qor uchquni qurilishini ko’rib chiqamiz. Egri chiziqlarga1904da shved matematigi Helge von Koch tomonidan ishlab chiqilgan noaniq uzunlik va atrofini qurshab olgan aniq maydonga ega bo’lgan davomiy hamda differensiallanuvchi funksiyani misol qilishimiz mumkin. Bunday egri chiziqlarga qor uchqunlarning noaniq ketma-ketligiligining limiti sifatida qarash mumkin, bularning birinchi uchtasi 3.4-rasmda namoyish etilgan. Haqiqiy qor uchqunlarida bo’lganidek, bularning ikkitasi oltita gultojbargli naqshlarga ega, lekin uning algoritmini yengillashtiradigan bo’lsak, u uchta oddiy egri chiziqning birlashmasi sifatida qaraladi. Shunday egri chiziqlarning bittasi quyidagicha chiziladi:
1. Interval qismini uchta bir xil bo’laklarga bo’ling.
2. Tomonning uchdan bir qismini burchak bo’yicha harakatlantiring.
3. O’ngga 60°ga buring (yoki –60°) va tomonning uchdan bir qismini yo’naltiring.
4. Chapga 120°ga buring va qolgan uch qismida ham davom ettiring.
5. O’ngga 60°ga buring va tomon bo’ylab yana chiziq chizing.
Bu besh qadamlarning natijasi 3.5-rasmda birlashtirilgan. Kompyuter grafikasi bizni juda uzoq masofalarga cho’zilishga aslo hojat qoldirmaydi, chunki agar chiziqlar piksellarning diametridan kichikroq bo’lsa, biz ekranda faqatgina bir nuqta sifatida ko’ramiz, xolos.

6. Rekursiv hisoblashlar masalasi uchun algoritmlar va ularning murakkabligini aniqlash

Oʻrta asrlarda oʻnli sanoq tizimi boʻyicha toʻrt arifmetik amal bajariladigan qoidani Algaritm deb atashgan. "Bu qoidalarni matematikaga 9-asrda al-Xorazmiy tomonidan kiritilgan. Yevropada bunday qoidalar uning tug'ilgan yurtiga nisbatan lotinchalashtirilgan (Algoritmus yoki Algorithmus shaklida "algorizm" deyilgan), keyinchalik "algoritm"ga aylangan" (akademik A. N. Kolmogorov). Fanga "Yevklid algoritmi", "Gʻiyosiddin Koshiy algoritmi", "Laure algoritmi", "Markov algoritmi" deb ataluvchi algoritmlar maʼlum.
Algoritm tushunchasi tobora kengayib borib, kibernetikaning nazariy va mantiqiy asosi hisoblangan algoritmlar nazariyasi paydo boʻldi. Oʻzbekiston Respublikasida bir necha ilmiy tadqiqot muassasalari va hisoblash markazlarida Algoritmdan foydalanish sohasida samarali ishlar olib borilmoqda. Masalan Oʻzbekiston Fanlar akademiyasi "Kibernetika" ilmiy ishlab chiqarish birlashmasida, Oʻzbekistondagi barcha universitetlarda, Toshkent davlat texnika universitetida, Oʻzbekiston Respublikasi Makroiqtisod va statistika vazirligi qoshidagi Hisoblash markazi va boshqa muassasalarda olib borilayotgan ishlar bunga misol boʻla oladi