Программалау оқулық Алматы, 012 Қазақстан Республикасы Білім жəне ғылым министрлігінің «Оқулық»
жүктеу/скачать 3,66 Mb. Pdf көрінісі
|
pavlovskaia-jogargy-dengeili
| template Bi2 copy_backward(Bi1 fi rst, Bi1 last, Bi2 result); Тізбектер бір-бірімен қиылысуы мүмкін. Көшіру кезінде шығыс тізбектің шекараларынан шығып кетпеуін қадағалап отыру керек. Тізбектің көшірмесін алудың мысалы: #include #include using namespace std; int main(){ int b[4], a[5] = {1, 2, 3, 4, 5}, i; copy (a + 1, a + 5, b); for (i = 0; i < 4; i++) cout << b[i]; // 2 3 4 5 cout << endl; copy (a + 1, a+5, a); for (i = 0; i < 5; i++) cout << a[i]; // 2 3 4 5 5 cout << endl; copy_backward (b, b + 3, b + 4); for (i = 0; i < 4; i++) cout << b[i]; // 2 2 3 4 cout << endl; return 0; } copy алгоритмін тізбекті енгізу жəне шығару үшін де қолдануға болады. Ол үшін үшінші параметр ретінде ағымдық итератор беріледі (361 б.):
381 #include #include using namespace std; int main(){ const int N = 5; int a[N] = {1, 2, 3, 4, 5}; copy (a, a + N, ostream_iterator cout << endl; return 0; } fi ll, fi ll_n fi ll алгоритмі fi rst жəне
last итераторларының көмегімен анықталған тізбектің барлық элементтерін берілген
мəніне алмастырады. fi ll_n
алгоритмі n элементті берілген мəнге алмастыруды жүзеге асырады: template void fi ll(For fi rst, For last, const T& value); template void fi ll_n(Out fi rst, Size n, const T& value); Бүтін сандардан тұратын жиымды толтыру мысалын қарастырайық: #include #include using namespace std; int main(){ int a[5], i; fi ll (a, a + 5, 1); for (i = 0; i < 5; i++) cout << a[i]; // 1 1 1 1 1 cout << endl; fi ll_n (a + 2, 2, 0); for (i = 0; i < 5; i++) cout << a[i]; // 1 1 0 0 1 cout << endl; return 0; } Мұнда біздер тізімдер үшін fi ll (a, a + 5, 1); сияқты өрнекті қолдана алмайтынымызға назар аударыңыз, өйткені тізім итераторлары үшін қосу опе- рациясы анықталмаған. Егер толтырылатын тізбек соңына тағайындалатын итератор белгісіз болса, алгоритмнің екінші формасын қолдануға болады.
алгоритмі барлық элементтерді операция нəтижесіне алмасты- руды орындайды. Осы арқылы контейнерді бірдей мəндермен емес, үшінші параметр арқылы берілген функция арқылы немесе gen функционалдық объект көмегімен есептелген мəндермен толтыруға мүмкіндік аламыз.
382 template void generate(For fi rst, For last, Generator gen); template void generate_n(Out fi rst, Size n, Generator gen); Қарапайым мысал: #include #include using namespace std; int f(){ static int i = 1; return (++i) * 3; } int main(){ int a[5], i; generate(a, a + 5, f); for (i = 0; i<5; i++) cout << a[i] << " "; // 6 9 12 15 18 return 0; } iter_swap, s wap, swap_ranges iter_swap алгоритмі итераторлармен берілген екі элементтің орындарын өзара алмастырады:
алгоритмі екі элементтің орындарын өзара алмастырады: template Келесі
swap_ranges алгоритмі берілген екі диапазондағы элементтердің орындарын өзара алмастырады (екінші диапазонның басталатын орны ғана көрсетілген): template For2 swap_ranges(For1 fi rst1, For1 last1, For2 fi rst2); random_shuffl e random_shuffl e алгоритмі кездейсоқ бірқалыпты үлестірімге сəйкес элементтердің орындарын алмастыруды жүзеге асырады. Алгоритмнің үшінші параметрі ретінде кездейсоқ сандардың генераторын беруге бола- ды. Осылайша программаны əрбір іске қосқан кезде əртүрлі нəтижелер алу мүмкіндігіне ие боламыз. Генератор int типті
n аргументін қабылдайтын, 0 мен
аралығындағы бүтін санды қайтаратын функция немесе функционалдық объект болуы мүмкін.
383 template void random_shuffl e(Ran fi rst, Ran last); template void random_shuffl e(Ran fi rst, Ran last, RandomNumberGenerator& rand); Генератор енгізілген мысалда тақырыптық файлында жарияланған
функциясы қолданылған: #include #include #include using namespace std; struct random_gen{ random_gen(){srand((unsigned int)time(NULL)); } int operator()(int n){return rand() % n;} }; int main(){ int a[5] = {1, 2, 3, 4, 5}, i; random_shuffl e(a, a + 5, random_gen()); for (i = 0; i < 5; i++) cout << a[i] << " "; // 5 3 4 1 2 cout << endl; return 0; } remove, remove_if, remove_copy, remove_copy_if remove тектес алгоритмдер тізбектің элементтерін берілген value мəні
бойынша немесе pred предикаты бойынша тізбектің соңына жылжытады. Бұл кезде тізбектің қалған элементтері өзара орналасу реттіліктерін сақтай отырып, тізбектің бас жақ бөлігіне қарай ығыстырылады. Алгоритм олардың орналасу шекарасын қайтарады. Шекарадан кейін орналасқан элементтер өшірілмейді, тізбектің өлшемі өзгертілмейді. copy сөзі бар алгоритмнің фор- малары өңдеудің алдында тізбекті
итераторы арқылы берілген орынға көшіреді де, тізбектің көшірмесін өңдейді.
384 Мəндері екіге тең вектор элементтерін өшіру үшін remove алгоритмін қолдану мысалы:
Программа жұмысының нəтижесі: 0123401234 0134013434 01340134 Мəндері 10 жəне 50 аралығында жататын вектор элементтерін өшіру үшін remove_if алгоритмін erase əдісімен қатар қолдану мысалы: #include #include #include using namespace std; bool In_10_50 (int x) {return x > 10 && x < 50;} int main(){ vector a; int i; for (i = 1; i<10; i++) a.push_back(i*10); for (i = 0; i cout << endl; vector a.end(), In_10_50); a.erase(new_end, a.end()); for (i = 0; i cout << endl; return 0; } 385 Программаның орындалу нəтижесі: 10 20 30 40 50 60 70 80 90 10 50 60 70 80 90 replace, rep lace_if, replace_copy, replace_copy_if replace тектес алгоритмдер берілген мəні бар элементтерді немесе предикатқа сəйкес элементтерді алмастыруды орындайды. Алгоритмнің
сөзі бар формалары өңдеу алдында тізбекті Out итераторы арқылы берілген орынға көшіреді де, тізбектің көшірмесін өңдейді.
Мысал қарастырайық, мұнда а векторының мəндері 10 мен 50 аралығында жататын элементтерін 33 мəніне алмастыра отырып, оны жаңа
векторына көшіру орындалады (кірістіру итераторы қолданылады):
386 cout << endl; return 0; } Программаның жұмыс істеу нəтижесі (бірінші жолда бастапқы вектор, екінші жолда нəтижелік вектор):
алгоритмі тізбек элементтерінің орналасу реттілігін кері бағытқа өзгертеді, ал
бастапқы тізбекті кері бағытта орналасқан нəтижелік тізбекке көшіруді жүзеге асырады:
алгоритмі тізбек элементтерінің орындарын циклдік түрде біртіндеп ығыстыруды жүзеге асырады, ал
тізбекті циклдік түрде көшіреді:
Біртіндеп орын ауыстыру, яғни ығыстыру екінші параметр арқылы нұсқалған элемент тізбектегі алғашқы орынға орналасқанға дейін жүзеге асы- рылады. Бірінші жəне үшінші параметрлер өңделіп жатқан тізбектің басы мен соңын көрсетеді. Мысалы, int
бүтін сандық жиымы үшін rotate(a, a+2, a+5) функциясын шақыру элементтердің 34512 ретімен орналасуына алып келеді. Егер осыдан кейін мынадай
функциясын шақырсақ, жиым бастапқы қалпына қайтып оралады. transform tr ansform алгоритмі берілген операцияны тізбектің əрбір элементі үшін орындайды. Алгоритмнің бірінші формасы
функциясы немесе
функционалдық объектісі арқылы берілген унарлы операцияны орындайды да, нəтижені result итераторының көмегімен берілген орынға орналастырады: 387 template Out transform(In fi rst, In last, Out result, Op op); Алгоритмнің екінші формасы екі тізбектің өзара сəйкес орындарындағы элементтер жұбымен бинарлы операция орындайды да, нəтижені
ите-
раторы арқылы берілген орынға орналастырады: template class BinaryOperation> Out transform(In1 fi rst1, In1 last1, In2 fi rst2, Out result, BinaryOperation binary_op); Функционалдық объект стандартты немесе қолданушы тағайындаған болуы мүмкін. Қолданушы тағайындаған функционалдық объект
немесе binary_function функциясының (363 б. қараңыз) ұрпағы болуы тиіс. Төменде көрсетілген мысалда
алгоритмін бірінші шақыру кезінде
2 2 i i i b a a − = формуласы бойынша түрлендіру орында- лады, ал оны екінші шақыру кезінде negate стандартты функционалдық объектісінің көмегімен
жиымы элементтерінің таңбасы өзгертіледі. #include #include #include using namespace std; struct preobr: binary_function double operator()(double x, double y) const{ return x * x - y * y;} }; int main(){ const int m = 5; double a[m] = {5, 3, 2, 3, 1}, b[m] = {1, 10, -3, 2, -4}; transform(a, a + m, b, a, preobr()); transform(b, b + m, b, negate int i; for (i = 0; i cout << endl; for (i = 0; i cout << endl; return 0; } Программа орындалуының нəтижесі: 24 -91 -5 5 -15 -1 -10 3 -2 4 388 unique, uniqu e_copy unique алгоритмі тізбектен қатар тұрған өзара тең екі элементті не- месе
бинарлы предикатының көмегімен тағайындалған критерийді қанағаттандыратын көршілес екі элементті өшіруді жүзеге асырады. Мұнда тізбектің өлшемі өзгертілмейді 1 . Алгоритм итераторды мəліметтердің жаңа логикалық соңына қайтарады. template For unique(For fi rst, For last); template For unique(For fi rst, For last, BinPred pred); unique_copy алгоритмі дəл осы əрекеттерді тізбектің көшірмесімен орын- дайды:
Бұл категорияның алгоритмдері тізбектерді реттей отырып сұрыптайды, элементтерді іздеуді, тізбектерді біріктіруді, минимум мен максимумды та- буды, лексикографиялық салыстыруды, орын ауыстыруларды жəне т.б. əрекеттерді жүзеге асырады.
Сұрыптаумен байланысты алгоритмдер Алгоритм Орындалатын функция binary _search Берілген мəнді іздеу
Берілген мəні бар элементтер тізбегін табу inplace_merge Бір диапазондағы сұрыпталған тізбектерді біріктіру
Екі тізбектің ішіндегі лексикографиялық түрдегі алғашқысы
Берілген мəннің алғашқы енгізілуін анықтау max Екі мəннің ішіндегі үлкені max_element Тізбектегі ең үлкен мəн merge Сұрыпталған тізбектерді біріктіру min Екі мəннің кішісі min_element Тізбектегі ең кіші мəн next_permutation Лексикографиялық тəртіппен келесі орналастыру 1 Тізімдер үшін list əдісін қолданған жөн. 389 Алгоритм Орындалатын функция nth_element n -ші элементті берілген орынға орналастыру partial_sort Ішінара бөлігін сұрыптау partial_sort_copy Көшіре отырып, ішінара бөлігін сұрыптау partition Шартты қанағаттандыратын элементтерді алға жылжыту
Лексикографиялық тəртіппен алдыңғы орналас- тыру
Сұрыптау
stable_partition Шартты қанағаттандыратын элементтердің өзара орналасу реттілігін сақтай отырып, алға қарай жылжыту
stable_sort Бірдей элементтер үшін олардың реттілігін сақтайтын сұрыптау
Берілген мəннен үлкен алғашқы элементті табу Осы алгоритмдерді толығырақ қарастырайық. Алгоритмдердің əрқайсысы үшін екі форма бар: біреуі < операциясын, ал екіншісі қолданушы тағайындаған салыстыру функциясын қолданады. Алгоритмдердің басым бөлігіне кездейсоқ қол жеткізу итераторлары қажет екендігіне назар аударыңыз. binary_search binary_se arch алгоритмі fi rst жəне
last итераторлары арқылы берілген сұрыпталған тізбектегі
мəнін іздеуді орындайды. Ізделген мəннің табылғаны немес табылмағаны туралы ақпарат қана беріледі. Іздеудің екілік деп аталатын себебі – интервалды тізбекті түрде ортасынан екіге бөлу жолы- мен орындалады («шөлдегі арыстанды ұстау сияқты»).
алгоритмі элементтер тізбегінің шекараларын табуды жүзеге асырады, тізбектің кез келген жеріне берілген мəнді реттілікті бүлдірмей кірістіруге болады. Тізбек сұрыпталған болу керек. Функционалдық объектіні беру кезінде алгоритм
итераторының əрбір мəні үшін comp(*k, value) == false && comp(value, *k) == false шарты орындалатын аралықтың шекараларын табады.
390 template pair const T& value); template pair const T& value, Compare comp); Мысалы, 2 4 5 5 7 9 12 18 тізбегі үшін equal_range алгоритмін value = 8
мəнімен шақыру нəтижесінде 9 жəне 9 элементтеріне нұсқайтын итераторлар жұбын, ал value = 5 мəнімен шақыру 5-ке тең элементтердің алғашқысын жəне 7 мəнін қайтарады.
алгоритмі бір тізбектің сұрыпталған екі бөлігін біріктіруді жүзеге асырады. Бірінші бөліктің шеаралары алғашқы екі параметр көмегімен, ал екінші бөліктің басы үшінші параметр арқылы беріледі. template void inplace_merge(Bi fi rst, Bi middle, Bi last); template void inplace_merge(Bi fi rst, Bi middle, Bi last, Compare comp); lexicographical_compare lexicographical_compare алгоритмі < операциясын қолдану арқылы немесе
функциясының көмегімен екі тізбекті əрбір элемент бойынша салыстыруды орындайды. Егер бірінші тізбек лексикографиялық тұрғыдан алғанда, екіншісінен кіші болса (яғни, бірінші тізбектің кезекті элементі екінші тізбектің соған сəйкес элементінен кіші болып шықты),
мəні, кері жағдайда
мəні қайтарылады. Егер тізбектердің ұзындықтары бір-біріне сəйкес келмесе, жеткіліксіз элементтер басқа тізбектің сəйкес элементтерінен кіші болып саналады. template bool lexicographical_compare (In1 fi rst1, In1 last1, In2 fi rst2, In2 last2); template bool lexicographical_compare (In1 fi rst1, In1 last1, In2 fi rst2, In2 last2, Compare comp); Мысалы:
#include #include #include 391 using namespace std; int main(){ const int m = 5; double a[m] = {5, 3, 2, 3, 1}, b[m] = {5, 3, 2, 3, 2}, c[m] = {5, 3, 1, 3, 10}; cout << lexicographical_compare(a,a+m,b,b+m); // 1 cout << lexicographical_compare(a,a+m,c,c+m); // 0 cout << lexicographical_compare(a,a+m,b,b+m, greater return 0; } lower_bound, upper_boun d lower_bound алгоритмі реттілікті бұзбай берілген мəнді алдына кірістіруге болатын сұрыпталған тізбектің элементтерінің алғашқысына, ал
соңғысына деген итераторды табады. template For lower_bound(For fi rst, For last, const T& value); template For lower_bound(For fi rst, For last, const T& value, Compare comp); template For upper_bound(For fi rst, For last, const T& value); template For upper_bound(For fi rst, For last, const T& value, Compare comp); max, min Салыстырудың ө зіндік критериін немесе < операциясын қолдану арқылы max алгоритмі екі мəннің үлкенін, ал min – кішісін іздейді. template template const T& min(const T& a, const T& b, Compare comp); template template const T& max(const T& a, const T& b, Compare comp); max_element, min_elemen t max_element алгоритмі итераторды тізбектің ең үлкен мəніне, ал min_element алгоритмі оны ең кіші мəніне қайтарады. 392 template For min_element(For fi rst, For last); template For min_element(For fi rst, For last, Compare comp); template For max_element(For fi rst, For last); template For max_element(For fi rst, For last, Compare comp); merge merge алгоритмі с ұрыпталған тізбектерді біріктіруді жүзеге асырады. template Out merge(In1 fi rst1, In1 last1, In2 fi rst2, In2 last2, Out result); template Out merge(In1 fi rst1, In1 last1, In2 fi rst2, In2 last2, Out result, Compare comp); Тізімдерді біріктірудің осы аттас əдісіне қарағанда, бастапқы тізбектердегі элементтер өшірілмейді. Кілттері тең болған жағдайда, бірінші тізбектің элементтері екінші тізбек элементтерінен бұрын орналасады (бұл жағдай, кілтпен қатар, ақпараттық бөлігі болатын мəліметтер құрылымдары үшін маңызды болып саналады). Мысал:
Кез келген тізбектің элементтерін əртүрлі тəсілдермен орналастыруға болады. Ұзындығы
болып келетін тізбек үшін мұндай қайта орналастыру- 393 лар саны n! (1*2*...*n) болады.
next_permutation алгоритмі кезекті қайта орналастыруды лексикографиялық тəртіппен, ал
алгоритмі бұрынғы орналастыруды жүзеге асырады. Егер келесі орналасты- ру бар болатын болса, алгоритмдер true бульдік мəнін, кері жағдайда false
мəнін қайтарады. template bool next_permutation(Bi fi rst, Bi last); template bool next_permutation(Bi fi rst, Bi last, Compare comp); template bool prev_permutation(Bi fi rst, Bi last); template bool prev_permutation(Bi fi rst, Bi last, Compare comp); Мысал:
#include #include using namespace std; int main(){ const int m = 3; int a[m]={1, 4, 2}, b[m]; int i; copy(a, a + m, b); cout << " next_permutation(a, a + m):" << endl; while (next_permutation(a, a + m)){ for (i = 0; i < m; i++) cout << a[i] << " "; cout << endl;} cout << " prev_permutation(b, b + m):" << endl; while (prev_permutation(b, b + m)){ for (i = 0; i < m; i++) cout << b[i] << " "; cout << endl;} return 0; } Программа жұмысының нəтижесі: next_permutation(a, a + m): 2 1 4 2 4 1 4 1 2 4 2 1 prev_permutation(b, b + m): 1 2 4 26-1140
394 nth_element Алгоритм жиымды ішінара сұрыптау əрекетін орындайды. Алгоритмнің орындалуынан кейін
итераторы арқылы берілген элементтің мəні толық сұрыптаудан кейінгімен бірдей болады, яғни осы позициядан солға қарай орналасқан элементтер одан кіші, оңға қарай орналасқандары одан үлкен болады.
жүктеу/скачать 3,66 Mb. Достарыңызбен бөлісу:
|