Standart algoritmlar - Tiplarni dinamik tarzda

|
Tiplarni dinamik tarzda
|
bet | 41/131 | Sana | 24.01.2024 | Hajmi | 1,92 Mb. | | #144844 |
Bog'liq Tiplarni dinamik tarzdaStandart algoritmlar. Yangi dasturlashni boshlanuvchilar odatda saralash, qidirish yoki qator elementlarini sanash kabi nisbatan oddiy vazifalarni bajarish uchun maxsus takrorlanishga asoslangan usullarni yozish uchun juda ko‘p vaqt sarflashadi. Bu usullar ularda xato qilish qanchalik osonligi jihatidan ham, umumiy ishonchlilik va mavjudlik nuqtai nazaridan ham muammoli bo‘lishi mumkin, chunki bu usullar tushunish qiyin bo‘lishi mumkin.
Qidiruv, sanash va saralash dasturlashda juda keng tarqalgan amallar bo‘lganligi sababli, C++ standart kutubxonasi dastlab bu vazifalarni bir necha qator kodda bajaradigan katta funksiyalar to‘plamini o‘z ichiga olgan. Bundan tashqari, bu xususiyatlar oldindan sinovdan o‘tgan, samarali va turli xil konteynerlarni qo‘llab-quvvatlaydi. Bu xususiyatlarni ham paralel qo‘llab – quvvatlash tezroq uni bajarish uchun bir xil masala uchun bir necha MP (markaziy protsessor) oqimlarini ajratish qobiliyati ega.
Algoritm kutubxonasi tomonidan taqdim etiladigan funksiyalar odatda uch toifadan biriga kiradi:
Inspektorlar (nazoratchilar) - konteynerdagi maʻlumotlarni (masalan, qidirish yoki elementlarni soni hisoblash amallari) ko‘rish uchun ishlatiladi.
Mutatorlar - konteynerdagi maʻlumotlarni o‘zgartirish uchun ishlatiladi (masalan, saralash yoki elementlarni qayta tartibga solish amallari).
Fasilitatorlar (koordinatorlar) - elementlarining qiymatlari asosida natija hosil qilish uchun ishlatiladi (masalan, qiymatlarni ko‘paytiruvchi obʻyektlar yoki elementlarning qaysi tartib juftliklarida tartiblanishi kerakligini aniqlovchi obʻyektlar).
Bu algoritmlar algoritm kutubxonasida (sarlavha faylida) joylashgan. Oldingi biladigan va eng ko‘p tarqalgan algoritmlardan baʻzilarini imkoniyatlarini chuquroq ko‘rib chiqamiz va bu algoritmlarning barchasi iteratorlardan foydalanadi.
find() algoritmi – berilgan qiymat bo‘yicha elementlarni qidirish algoritmi. Berilgan qiymatni birinchi topgunicha ishlaydi. Argument sifatida 3 ta paramertni oladi.
ketma-ketlikda boshlang‘ich element uchun iterator; ketma-ketlikda oxirgi element uchun iterator; qidirishning qiymati.
Qidirish natijada qidirilayotgan qiymatli elementga (agar u topilsa) yoki iteratorning oxiriga (agar bunday element topilmasa) ishora qiluvchi iterator qaytadi.
5.1-dastur. Find () funksiyasidan foydalanish.
// Created by MBBahodir #include "stdafx.h"
#include #include #include
using namespace std;
|
int main(){
array arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
cout << "Qidirish va oʻzgartirish uchun son kirit: ";
int search;int replace; cin >> search >> replace;
// array::iterator found;
auto found = find(arr.begin(), arr.end(), search); if (found == arr.end())
{cout << search << " topilmadi. " << endl;}
else{*found = replace;}
for (int i : arr){cout << i << ' ';}
cout << endl; system("pause"); return 0;}
|
5.1-dastur.Output
|
Birinchi sinov
|
Qidirish va oʻzgartirish uchun son kirit: 19 21
1 3 5 7 9 11 13 15 17 21
|
Ikkinchi sinov
|
Qidirish va oʻzgartirish uchun son kirit: 10
25
|
10 topilmadi.
1 3 5 7 9 11 13 15 17 19
|
find_if() algoritmi - shart orqali elementni izlash. Juda ko‘p hollarda konteynerda mavjud elementlar orasida maʻlum bir qiymat saqlaydigan element bormi degan masala duch kelamiz. Masalan, konteynerda satrli elementlar berilgan bo‘lsa, biror bir satr qismi bormikan degan masala bo‘lsin. Mana shunday masalalarni yechishda find_if() algoritmi eng mos va qulay hisoblanadi. Bu algoritm find() algoritmi bilan analog sifatida ishlaydi ammo, qidirish uchun qiymat o‘rniga funksiya ko‘rsatgichlariga moslangan element qiymatida o‘xshashlik bor bo‘lgan obʻyekt chaqiriladi. find_if() funksiyasi buning uchun har bir elementni chaqiradi va to shunday elementni topilmaguncha yoki konteynerda elementlar tugaguncha.
Maʻlum bir berilgan satr bo‘yicha, berilgan konteynerda shu satrni o‘zida qism satr qilib saqlovchi elemeni bor ki yo‘qligini aniqlovchi dasturni tuzish kerak bo‘lsin.
5.2-dastur. find_if() funksiyasidan foydalanish.
// Created by MBBahodir #include "stdafx.h" #include #include #include #include
using namespace std;
bool containsNut(string str)
{return (str.find("oro") != string::npos);}
int main()
{array arr = { "Toshkent", "Buxoro", "Samarqand", "Navoiy" };
|
auto found = find_if(arr.begin(), arr.end(), containsNut);
if (found == arr.end())
{
cout << " Topilmadi" << endl;
}
else
{
cout << " Topildi: " << *found << endl;
}
system("pause"); return 0;
}
|
Agar odatdagi standart tarzdagidek muammoni hal qilshganimizda, kamida ikki takrorlanish kerak edi (birinchi takrorlanish elementlarni saralash uchun va ikkinchisi satr qismini solishtirish uchun). Standart C++ kutubxonasining vazifalari bir nechta fragment satrlarida ham shunday qilish imkonini beradi.
count() va count_if() algoritmlari – konteynerdan berilgan elementlarini sanash vazifasini bajaradi. Berilgan mezon (shart) bo‘yicha barcha elementlarni tekshirib, sanaydi. Berilgan konteynerda nechta element berilgan satr qismi borligini sanash dasturini keltiramiz.
5.3-dastur. count() va count_if() algoritmlaridan foydalanish.
// Created by MBBahodir #include "stdafx.h" #include #include #include #include #include using namespace std;
bool containsNut(string str)
{
return (str.find("daryo") != string::npos);
}
bool counter(string str){ return true;
}
|
int main()
{
array arr = { "Sirdaryo", "Amudaryo", "Qashadaryo", "Suxondaryo", "Zarafshon", "Qashadaryo" };
auto countWithIf = count_if(arr.begin(), arr.end(), containsNut); int countofArr = count(arr.begin(), arr.end(), "Qashadaryo");
cout << "daryo satr qismi borlarining soni: " << countWithIf << endl; cout << " elementlar soni: " << countofArr << endl;
system("pause"); return 0;
}
|
5.3-dastur. Output
|
daryo satr qismi borlarining soni: 5
elementlar soni: 2
|
sort() algoritmi – foydalanuvchining saralash funksiyasini qurish uchun ishlatiladi. Oldinlari sort() funksiyasi bilan massivlarni saralagan bo‘lshingiz mumkin, ammo sort() funksiya bu bilan chegaralanib qolmaydi. Bu funksiya yordamchi bir funksiya oladi va bu argument asosida foydalanuvchi o‘zining saralash uslubini amalga oshirishi mumkin. Funksiya esa taqqoslash uchun paramert ikkita parametr oladi. Agar birinchi element ikkinchisidan oldin bo‘lishi kerak bo‘lsa, ikkinchi paramert true qiymat qaytarishi kerak. Odatda sort() funksiyasi o‘sish tartibida saralaydi. Berilgan massivni kamayish tartibida saralash dasturini tuzaylik.
5.4-dastur. sort() funksiyasidan foydalanish.
#include "stdafx.h" #include #include #include
using namespace std;
bool greater(int a, int b)
{
|
return (a > b);
}
bool d_greater(int a, int b)
{
return (b > a);
}
int main()
{array arr = { 28, 18, 16, 25, 25 }, arr_one;
arr_one = arr; sort(arr.begin(), arr.end(), greater); sort(arr_one.begin(), arr_one.end(),d_greater );
for (int i : arr) {cout << i << ' ';}
cout << endl;
for (int i : arr_one ) { cout << i << ' ';
} cout << endl;
system("pause"); return 0;
}
|
5.4-dastur. Output
|
28 25 25 18 16
16 18 25 25 28
|
Dasturdan ko‘rinadiki, o‘zimiz saralash algoritmini boshidan yozishimiz shart emas ekan, buning uchun bir qator fragment yetarli bo‘ldi. Ammo C++ tili, juda ko‘p saralashning kamayish tartibda foydalanganligi uchun greater{} tipli funksiyasi bo‘lishi mumkin ( kutubxonasida bor). Biz o‘zimizning greater funksiyasidan foydalanish uchun sort(arr.begin(), arr.end(), greater); dastur fragmentini yozdik, ammo kutubxonanikini chaqirish uchun sort(arr.begin(), arr.end(), std::greater{}); kabi fragment yozishimiz kerak. Eʻtibor bering,
greater{} funksiyasi figurali qavsga muxtoj, shuning uchun uni funksiya deb atalmaydi, maʻlumot tipi deb yuritiladi va undan foydalanish uchun nusxasini yaratishimiz kerak. Figurali qavslar anonim obʻyektlarni yaratish uchun xizmat qiladi.
for_each() algortmi – konteynerning barcha elementlari o‘tish. Bu for_each() funksiyasi kiruvchi maʻlumot sifatida to‘plamni qabul qiladi va foydalanuvchining funksiyasini joriy to‘plamdagi har bir element uchun qabul qiladi. Buning qulaylik tomoni shundaki, agar bir amalni to‘plamning barcha elementlari bo‘yicha bajarish kerak bo‘lsa, for_each() funksiyasi as qotadi. Berilgan massivning barcha elementlarini chiqarish uchun for_each() funksiyasidan foydalanishni dasturini keltiraylik.
5.5-dastur. for_each() funksiyasidan foydalanish.
#include "stdafx.h"
#include #include #include
using namespace std;
void doubleNumber(int &i){ i = i;
}
int main(){
array arr = { 1, 2, 3, 4 }; for_each(arr.begin(), arr.end(), doubleNumber);
for (int i : arr){ cout << i << ' ';
}
cout << endl; system("pause"); return 0;
}
|
Yosh dasturchilar uchun bu takrorlanish jarayonini oddiy for operatoriga aniq parametrlarni qo‘yib ishlatish maquldir. for_each() funksiyasining yutuqlari shandan iboratki, takrorlanish tanasidan qayta foydalanish va paralellashtirish, katta proektlarda katta maʻlumotlar, turli tiplari har xil maʻlumotlar tuzilmasi bilan ishlgandan eng yaxshi isntrument bo‘lib xizmat qiladi.
|
| |