MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
TELEKOMMUNIKATSIYA TEXNOLOGIYALARI VA KASB TA’LIMI
FAKULTETI Sirtqi
mustaqil ishi
Samarqand-2024
Bajaruvchi:
habibullayv N
.
Tekshiruvchi: KAYUMOV A..
“Dasturlash 2
”
fanidan.
Mavzu. Juda katta raqamlar bilan ishlash
Reja:
1.
Juda katta raqamlar bilan ishlash.
2.
Juda katta raqamlar bilan ishlash.
3.
Xotirani taqsimlovchilar va ularga qo‘yilgan talablar.
4.
Standart bo‘yicha taqsimlovchi.
Juda katta raqamlar bilan ishlash
.
С++ tilining standart algoritmlar kutubxonasi, iteratorlar, xotirani taqsimlash
talablari, dinamik xotira ajratish va foydalanishga asosida qidirish, saralash,
taqqoslash funksiyalari, dasturlashda o‘zlarini tutishlari, iteratorlar, o‘zgarmas
iteratorlar, teskari iteratorlar bilan ishlashga mo‘ljallangan asosiy funksiyalar va
ularning dasturlashdagi ahamiyati, xotirani taqsimlovchi sniflarni yaratish va
talablari, turli tipli massivlar uchun dinamik xotirani ajratish va foydalanish
operatorlar uslublari, amallari, talablari, vazifalari va usullari keltirilgan bo‘lib,
nazariy bilimlarni asoslash uchun dasturlar tuzib ko‘rsatilgan. Bilimlarni
mustahkamlash uchun 30 ta nazariy savol va amaliy ko‘nikma va malakalarni
rivojlantrish uchun 3 ta assisment topshirig‘i va har assismentda 10(9,7) ta topshiriq,
jami 26ta topshiriq berilgan. Bu topshiriqlarni bajarish mavzuni mustahkamlash
uchun xizmat qiladi.
iterator, qidirish, saralash, o‘rin almashtirish, shablon, sinf, find(), sort(),
swap(), begin(), end(), rbegin(), rend(), crbegin(), crend(), xotira, pul, xotira bloki,
new, delete, for_each(), funksional obʻyektlar.
Bugunki kunda dasturlash juda soddalashib bormoqda, baʻzi bir mutaxassislar
dasturlash uchun matematika kerakmas deb aytsa, baʻzilari matematika
dasturlashning asosi deb aytadi. Shuning negizida nima yotibdi. Albatta algoritmlar,
isteratorlar va xotirani taqsimlovchilar va ularning talablari yotadi. Algoritmlar
tayyo bo‘lsa, faqat bu algoritmlarini joy joyiga qo‘yish bu juda osondir. Ammo
algoritmlarni yaratish va uni dasturlash joriy qilish o‘ta mushkul va mashaqqatli
masaladir. Shuning uchun bugungi kunda juda ko‘plab algoritmlarni saqlovchi
standart va no standart kutubxonalar mavjud.
Standart 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.
// 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;}
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.
. 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.
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;
}
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.
#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;
}
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.
#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.
Algoritmlarning bajarilish tartibi . Algoritm kutubxonasida eng ko‘p algoritmlar
maʻlum bir ijro tartibini kafolatlamaydi. Bunday algoritmlar uchun har qanday
belgilangan funksiyalar bajarilish tartibini o‘z zimmasiga olmasligiga ishonch hosil
qilish kerak, chunki bu funksiyalarni chaqirish tartibi ishlatiladigan kompilyatorga
qarab farq qilishi mumkin. Quyidagi algoritmlar aniq bajariladi:
for_each()
copy()
copy_backward()
move()
move_backward()
Agar parametr sifatida biror funksiya berilmagan bo‘lsa, aniqlanmagan holat
o‘tadi. Buning uchun har bir algoritmga arr.begin() va arr.end() aniq berilishi kerak.
Ammo C++20 standartida faqat massiv berilsa o‘zi aniqlanadi.
Algoritm kutubxonasining algoritmlari ro‘yxati:
Bu yerda 85 ta algoritmlar keltirilgan, ammo bularning hammasi shablon
funksiya bo‘lganligi uchun C++ dasturlash versiyalarida farqi bo‘lishi mumkin.
Shuningdek, eslab ko‘ring, bu algoritmlarning ko‘plaridan oldin mavzularimizda
foydalanganmiz.
Iteratorlar va ularning qo‘llanilishi. Iteratorlar konteynerlarning elementlariga
murojaat qilish uchun foydalaniladi. Iteratorlar bilan elementlar bilan ishlash juda
qulay hisoblanadi. Iterator iterator tipi bilan yoziladi. Har qanday konteyner uchun
iteratorlarning tiplari farq qiladi. Masalan, list tipidagi konteyner uchun list::iterator
tipi, vector tipidagi konteyner uchun esa vector::iterator tipi ishlatiladi. C++ tiladi
konteynerlardan iteratorlarni ajratib olish uchun begin() va end() funksiyalaridan
foydalaniladi. begin() funksiyasi konteynerdagi birinchi element ko‘rsatuvchi
iteratorni qaytaradi (agar konteynerda elementlar bo‘lsa). end() funksiyasi
konteynerdagi oxirgi elementdan keyingi pozitsiyani ko‘rsatuvchi iteratorni (yaʻni
konteyner oxirini) qaytaradi. Agar konteyner bo‘sh bo‘lsa, begin() va end()
funksiyalari bir xil qiymat qaytaradi. Agar begin() va end() funksiyalari o‘zaro teng
bo‘lmasa, ularning orasidan kamida bitta element bor. Bu funksiyalar aniq tipli
konteyner uchun iterator qaytaradi. Iterator yaratishga misol:
std::vector v = { 1,2,3,4 };
std::vector::iterator iter = v.begin();
Bu misolda tipiga mansub bo‘lgan vektor tipidpgi konteyner - vektor
yaratilgan. Konteyner doimiy qiymatlar bilan to‘ldirilgan. begin() funksiyasi (usuli)
bilan vektor elementini olish uchun iterator keltirilgan. Bu iterator vektor
konteynerning birinchi elementini ko‘rsatadi.
Iterator amallari:
•
*iter – iterator ko‘rsatadigann elementni olish;
- ++iter - keyingi elementga murojjat qilish uchun iteratorni harakatlantirish
o --iter - oldingi elementga murojjat qilish uchun iteratorni harakatlantirish.
forward_list konteyner iteratorlari dekrement amalini qo‘llab quvvatlamaydi.
o iter1 == iter2 - ikki iterator teng, agar ular bir xil iteratorni aniqlagan bo‘lsa.
o iter1 != iter2 ikki iterator teng emas, agar ular bir xil iteratorni aniqlagan
bo‘lsa.
Konteynerlar bilan ishlaganda, konteynerdagi elementlarni qo‘shish yoki
o‘chirish ushbu konteyner uchun barcha joriy iteratorlarni, shuningdek, uning
elementlariga havola va ko‘rsatgichlarni bekor qilishiga olib kelishi mumkin.
Iteratorlar nafaqat elementlarni olish, balki ularni o‘zgartirish imkonini beradi.
#include #include using namespace std; int main()
{vector myvector;
for (int i = 0; i < 15; i++)
{myvector.push_back(rand() % 10);}
vector::iterator iter = myvector.begin();
//auto iter = myvektor.begin(); while(iter!=myvector.end())
{*iter = (*iter) * (*iter);++iter;}
for(iter = myvector.begin(); iter!=myvector.end(); ++iter)
{cout << *iter << " | ";}
cout << endl; system("pause"); return 0;
}
Dasturda while takrorlanish operatori konteynerning elementlarini iteratorga
olib, o‘zini o‘ziga ko‘paytirib, yana shu iteratorga yozadi. Shuning uchun ekranga
konteynerdagi sonlarning kvadratlari chiqadi.
O‘zgarmas iteratorlar. Agar konteynerda o‘zgarmas qiymatli elementlar
bo‘lsa, bu holda konteyner elementlariga murojaat qilish uchun o‘zgarmas
iteratorlardan foydalanishsh kerak. Buning uchun const_iteratop tipi ishlatiladi. Bu
iteratorlar faqat elementlarni sanash imkonini beradi. O‘zgartirish mumkin emas.
vector::const_iterator iter ;
for(iter = myvector.begin(); iter!=myvector.end(); ++iter)
{cout << *iter << " | ";
//*iter = (*iter) * (*iter);
}
O‘zgarmas iteratorning qiymatlarini olish uchun cbegin() va cend() funksiyalari ham
ishlatiladi. Agar iterator o‘zgarmas deb olinmagan bo‘lsa ham, bu funksiyalar uni
o‘zgarmas qilib beradi. Shungdek, o‘zgartirish mumkin emas bo‘ladi.
// ConsoleApplication1.cpp : main project file.
#include "stdafx.h" #include #include using namespace std;
int main(){
int myints[] = {16,2,77,29,28};
const vector myvector (myints, myints + sizeof(myints) / sizeof(myints[0])
); vector myvector_one; for (int i = 0; i < 15; i++)
myvector_one.push_back(rand() % 10);
vector::const_iterator it;
for (it = myvector.begin(); it != myvector.end(); ++it) cout << ' ' << *it;
cout << endl;
for (it = myvector_one.cbegin(); it != myvector_one.cend(); ++it) cout << ' ' << *it;
cout << endl; system("pause"); return 0;
}
Teskari iteratorlar. Bu iteratorlar konteynerning elementlarini teskari olishni
amalga oshiradi. Buning uchun reverse_iterator tipi ishlatiladi. Bu tipdagi
iteratorlarga konteynerning elementlarini olish uchun rbegin() i rend()
funksiyalaridan foydalaniladi.
#include "stdafx.h" #include #include using namespace std; int main()
{
int myints[] = { 1, 2, 3, 4, 5 };
vector v (myints, myints+ sizeof(myints)/sizeof(myints[0]));
for (vector::reverse_iterator iter = v.rbegin(); iter != v.rend(); ++iter) std::cout << *iter << " | ";
cout << endl; system("pause");
return 0;
}
Agar konteynerni o‘zgartirishdan himoyaya qilish va teskarisi kerak bo‘lsa,
const_reverse_iterator tipidagi iteratordan va uning crbegin() va crend()
funksiyalaridan foydalanish maqsadga muvofiqdir. Yuqoridagi dasturga quyidagi
fragmentni yozish yetarli bo‘ladi.
for (vector::const_reverse_iterator iter = v.crbegin(); iter != v.crend();
++iter)
std::cout << *iter << " | ";
Shuningdek iteratorlari qo‘shima amallarga ham ega (list va forward_list
konteynerlaridan tashqari):
o
iter + n - n ta pozitsiya keyingi elementni ko‘rsatuvchi iteratorni qaytaradi.
o
iter – n - n ta pozitsiya oldingi elementni ko‘rsatuvchi iteratorni qaytaradi.
o
iter += n - iteratorni n - chi pozitsiyaga o‘tkazadi
o
iter -= n - iteratorni n - chi pozitsiyaga o‘tkazadi
o
iter1 - iter2 - iter1 va iter2 lar orasidagi pozitsiyalar sonini qaytaradi
o
[>], [>=], [<=] - taqqoslash amallari. Agar iterator oxiriga yaqin elementni
ko‘rsatsa boshqasidan katta.
#include "stdafx.h" #include #include using namespace std; int main()
{int myints[] = { 1, 2, 3, 4, 5 };
vector v (myints, myints+ sizeof(myints)/sizeof(myints[0])); for (auto i = v.begin(); i < v.end();
i++)
{cout << *i << " | ";}
cout << endl;
auto it1 = v.begin(); auto it2 = it1 + 2;
cout << "it1 + 2 => " << *it2 << endl; auto it3 = v.end() - 3;
cout << "it1 - 3 => " << *it3 << endl; it2 += 2 ;
cout << "it2 + 2 => " << *it2 << endl; it3 -= 2;
cout << "it3 - 2 => " << *it3 << endl;
cout << "it2 - it1 => " << it2 - it1 << endl; cout << "(it1 < it2) => " << (it1 < it2) << endl;
cout << "(it1 >= it2) => " << !(it1 < it2) << endl; cout << "(it1 != it2) => " << !(it1 == it2) <<
endl;
cout << "(it1 == it2) => " << (it1 == it2) << endl; cout << "(it1 != it2) => " << (it1 != it2) << endl;
cout << endl;
system("pause"); return 0;
}
1 | 2 | 3 | 4 | 5 |
it1 + 2 => 3
it1 - 3 => 3
it2 + 2 => 5
it3 - 2 => 1
it2 - it1 => 4 (it1 < it2) => 1 (it1 >= it2) => 0 (it1 != it2) => 1 (it1 == it2) => 0
(it1 != it2) => 1
Taqqoslash amallari uchun ko‘chirib o‘tish iteratorlari va bazaviy iteratorlar uchun
Ko‘chirib o‘tish iteratorlari uchun.
Ekvivalent bazaviy iteratorlari uchun.
move_ita == move_itb
basic_ita == basic_itb
move_ita != move_itb
!(basic_ita == basic_itb)
move_ita < move_itb
basic_ita < basic_itb
move_ita <= move_itb
!(basic_itb < basic_ita)
move_ita > move_itb
basic_itb < basic_ita
move_ita >= move_itb
!(basic_ita < basic_itb)
Xotirani taqsimlovchilar va ularga qo‘yilgan talablar. Dinamik xotira bilan
ishlashda maxsus truklarni, fragmentlardan foydalanish bo‘lmasa, ko‘pigina
algoritmlardan foydalanish samarasiz bo‘lshi mumkin. Bunga misol sifatida ikkita
holatni ko‘rib chiqamiz. new va delete operatorlarining qayta aniqlanib yuklanishida
sintaktik konstruktorlar kichikroq bo‘ladi va dastur lokalizatsiya qilish oddiy
bo‘ladi. Shuningdek protsessordagi amallar tizimida ham qayta aniqlash sodir
bo‘ladi.
Avvalo, xotirani ishlashini tezlashtirishda aqlli allocator qanchalik foydasi
borligini aniqlash lozim. Buning uchun oddiy test misollarini (C++ va S#) tillarida
ko‘rib chiqaylik ( bu xotira bilan ishlash uchun yaxshi menejer hisoblanadi va
obʻyektlarni avlodlarga ajratadi, turli o‘lchamdagi obʻyektlar uchun turli pullardan
(joylar) foydalanadi).
|
