Программалау оқулық Алматы, 012 Қазақстан Республикасы Білім жəне ғылым министрлігінің «Оқулық»

399

a:    

2 5 7 9

b:     

1 5 9

isect:   5 9 

Union:   1 2 5 7 9 

dif:     2 7 

symdif:  1 2 7 

a b-ны қамтымайды. 

Union b-ны қамтиды.

make_heap

make_heap

 алгоритмі кездейс 

оқ қол жеткізу мүмкіндігі бар тізбекті 

пирамидаға түрлендіреді:

template

 

void make_heap(Ran fi rst, Ran last); 

template

 

void make_heap(Ran fi rst, Ran last, Compare comp);

pop_heap

pop_heap

 алгоритмі тізбектің  бірінші элементін өшіреді, содан кейін ба-

рып пирамидалылық шартын орындайды:

template

 

void pop_heap(Ran fi rst, Ran last); 

template

 

void pop_heap(Ran fi rst, Ran last, Compare comp); 

Пирамидадан шығарылып алынатын элементтің мəнін алуды əдеттегі 

тəсілмен орындау талап етіледі. Мысалы, жоғарыда көрсетілген 

а

 жиымы 

үшін келесідей түрде жазуға болады: 

x = *a; pop_heap(a, a + m);

push_heap

push_heap

 алгоритмі тізбекк 

е соңғы элементті қосқаннан кейін оны 

пирамидаға түрлендіруді жүзеге асырады:

template

 

void push_heap(Ran fi rst, Ran last); 

template

 

void push_heap(Ran fi rst, Ran last, Compare comp); 

push_heap

 алгоритмін шақыруға дейін элементті контейнер типіне сəйкес 

тəсілмен тізбекке қосу керектігіне көңіл аударыңыз, мысалы:

v.push_back(x); push_heap(v.begin(), v.end());

400

sort_heap

sort_heap

 алгоритмі пирамид аны өсуі бойынша сұрыпталған тізбеккке 

түрлендіреді:

template

 

void sort_heap(Ran fi rst, Ran last); 

template

 

void sort_heap(Ran fi rst, Ran last, Compare comp); 

Бұл алгоритм пирамиданың қасиеттерін қолданатын болғандықтан, ол 

қарапайым сұрыптаудан гөрі жылдам жұмыс істейді. Сұрыптау кілттері бірдей 

элементтердің салыстырмалы орналасу реттілігін сақтамайды.

401

15-ТАРАУ

Сандық есептеулерге арналған   құралдар 

Жалпыланған сандық алгоритмдер

Санды қ алгоритмдерді қолдану үшін 

 тақырыптық файлын 

қосу қажет. 

15-кесте. 

Жалпыланған сандық алгоритмдер

Алгоритм

Орындалатын функция

accumulate

Жинақтау

inner

_product

Скалярлық көбейту

partial_sum

Жинақтай отырып, қосындыны есептеу

adjacent_difference

Іргелес элементтер арасындағы айырманы есептеу

accumulate

accumulate

 алгоритмінің бірінші формасы 

 

fi rst

 жəне 

last

 

итера-

торларымен берілген тізбек элементтерінің қосындысын жинақтау үшін 

қолданылады. Қосындының бастапқы мəні (əдетте бұл 0) үшінші параметр 

арқылы беріледі. Бұл параметрдің типі нəтиженің типін анықтайды (функция 

есептелген қосындыны қайтарады):

template

 

T accumulate(In fi rst, In last, T init);

accumulate 

алгоритмінің екінші формасы үшінші параметрге жəне 

тізбектің кезекті элементіне берілген операцияны қолдануға мүмкіндік береді:

template t

 

T accumulate(In fi rst, In last, T init, BinOp binary_op);

Төменде көрсетілген мысалда жиым элементтерінің қосындысы, 

көбейтіндісі жəне элементтер квадраттарының қосындысы есептеледі:

#include  

#include  

#include  

using namespace std;

int sumkv( int s, int x){ return s + x * x;} 

int main(){

 

const int m = 5;

 

int a[m] = {3, 2, 5, 1, 6}, sum = 0, mul = 1, sum2 = 0; 

402

 

cout << accumulated, a + m, sum) << endl; 

 

cout << accumulate(a, a + m, mul, multiplies()) 

        << endl; 

 

cout << accumulate(a, a + m, sum2, sumkv) << endl;

 return 

0;

}

inner_product

inner_product

 алгоритмінің бірінші ф ормасы екі тізбектің скалярлық 

көбейтіндісін есептеу үшін қолданылады (

а

 жəне 

b

 тізбектерінің скалярлық 

көбейтіндісі  ∑a

i

*b

i

 өрнегі болып табылады). Көбейтіндінің бастапқы мəні 

төртінші параметр арқылы беріледі. Осы параметрдің типі нəтиженің типін 

анықтайды (функция есептелген көбейтіндіні қайтарады):

template t

 

T inner_product(In1 fi rst1, In1 last1, In2 fi rst2, T init);

inner_product

 алгоритмінің екінші формасы екі функцияның немесе 

функционалдық объектінің көмегімен берілген əрекеттерді екі тізбекпен орын-

дау үшін қолданылады. Бірінші функционалдық объект қосу операциясының 

орнына, ал екіншісі көбейтудің орнына пайдаланылады:

template t

   class BinOp1, class BinOp2> 

 

   T inner_product(In1 fi rst1, In1 last1, In2 fi rst2, 

 

 

T init, BinOp1 binary_op1, BinOp2 binary_op2);

Төмендегі шақыру а жəне 

b

 тізбектерінің сəйкес элементтерінің 

қосындыларының көбейтіндісін есептейді:

cout << inner_product(a, a + m, b, mul, 

                      multiplies(), plus());

жүктеу/скачать 3,66 Mb.

Достарыңызбен бөлісу: