Размещено на http://www.allbest.ru/

Зміст

• Вступ
• Розділ 1. Теоритична частина. Пошук та сортування одновимірних масивів
• 1.1 Пошук елемента в одновимірному масиві
• 1.2 Сортування одновимірних масивів
• 1.2.1 Сортування включенням
• 1.2.2 Сортування вибором
• 1.2.3 Обмінне сортування
• 1.2.4 Сортування злиттям
• 1.2.5 Швидке сортування
• Розділ 2. Практична частина
• 2.1 Розробка лінійних алгоритмів та програм
• 2.2 Розробка розгалужених алгоритмів та програм
• 2.3 Розробка циклічних алгоритмів та програм
• 2.4 Розробка ітераційних алгоритмів та програм
• 2.5 Розробка алгоритмів та програм обробки одновимірного масиву
• 2.6 Розробка алгоритмів та програм обробки двовимірного масиву
• 2.7 Розробка програм обробки стрічок
• 2.8 Розробка програм для роботи зі структурами
• 2.9 Розробка програм для роботи з файлами
• 2.10 Розробка програм для графічного режиму
• 2.11 Розробка програм для роботи з класами та об'єктами
• Висновки
• Список використаних джерел
• Додатки
• Вступ
• В наш час нові інформаційні технології посідають дуже важливе місце не лише в спеціалізованих, але й в повсякденних сферах життя. Комп'ютери застосовуються в бізнесі, менеджменті, торгівлі, навчанні та багатьох інших сферах діяльності людини.
• Комп'ютерні технології дуже зручні для виконання різноманітних операцій, але в різних сферах застосування ці операції різні. Тому, кожна окрема галузь, яка використовує специфічні технічні засоби, потребує своїх власних програм, які забезпечують роботу комп'ютерів.
• Розробкою програмного забезпечення займається така галузь науки, як програмування. Вона набуває все більшого й більшого значення останнім часом, адже з кожним днем комп'ютер стає все більш необхідним, все більш повсякденним явищем нашого життя. Адже обчислювальна техніка минулих років вже майже повністю вичерпала себе і не задовольняє тим потребам, що постають перед людством.
• У практиці програмування дуже часто виникає необхідність у впорядкуванні елементів використовуваних структур даних за якою-небудь ознакою, або, як іноді кажуть, за яким-небудь „ключем”. Програмісти кажуть в цьому випадку, що необхідно відсортувати множину елементів, використовуючи задане відношення порядку.
• Сортування варто розуміти, як процес перегрупування заданої множини об'єктів в деякому конкретному порядку. Мета сортування - полегшити наступний пошук елементів в такій відсортованій множині.
• Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв'язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам'яті.
• Інший клас дуже важливих та часто використовуваних алгоритмів складають алгоритми, що реалізують різні методи пошуку заданого елемента серед множини компонент визначеної структури даних.
• Найбільш відомі та часто використовувані методи пошуку та сортування ми розглянемо у цій роботі.

сортування масив алгоритм

• Розділ 1. Теоритична частина. Пошук та сортування одновимірних масивів

1.1 Пошук елемента в одновимірному масиві

Пошук є однією з найбільш поширених у програмуванні дій. У подальшому розгляді ми будемо виходити з принципового допущення, що група даних, в якій треба шукати заданий елемент, є фіксованою. Будемо вважати, що множина з n елементів задана у вигляді масиву a типу , де масив a та тип описано наступним чином:

тип = масив [1..n] із t;

змін a: ;

де для типу елементів масиву t визначені стандартні відношення: {=, <>, <, >, >=, <=}.

Якщо немає додаткової інформації про розташування елементів масиву, то очевидний вихід - послідовний перебір значень елементів масиву до знайдення шуканого елемента або до вичерпання елементів.

Виникає питання: чи можна знайти у масиві потрібний елемент за меншу кількість кроків? Відповідь є ствердною в тому випадку, коли елементи масиву впорядковані. Без обмеження загальності можна вважати, що елементи впорядковані за зростанням, тобто a[1] <= a[2] <= ... <= a[n]. Ідея методу пошуку, який називають бінарним, полягає у наступному:

На кожному кроці алгоритму шукаємо x серед елементів масиву від нижньої до верхньої границі. Спочатку нижня границя індексів - 1, а верхня - n.

На кожному кроці коло елементів, серед яких шукаємо x, зменшуємо вдвічі. Робиться це порівнянням x з середнім елементом частини масиву від нижньої до верхньої границі та зміною значення нижньої або верхньої границі індекса.

Ось приклад функції, яка здійснює такий пошук.

int binary_search(int a[], int low, int high, int target) {

while (low <= high) {

int middle = low + (high - low)/2;

if (target < a[middle])

high = middle - 1;

else if (target > a[middle])

low = middle + 1;

else

return middle;

}

return -1;}

1.2 Сортування одновимірних масивів

Сортуванням називають впорядкування елементів деякої структури даних, на якій визначено відношення порядку, по ключах (тобто за якою-небудь ознакою). В залежності від того, чи знаходяться елементи структур даних у внутрішній (оперативній) пам'яті або у зовнішній пам'яті (на зовнішніх пристроях), розрізняють внутрішнє та зовнішнє сортування.

Методи сортування масивів класифікують за часом їх роботи, який залежить від числа необхідних порівнянь ключів та числа пересилок елементів. У найбільш простих методах сортування потрібно порядку O(n2) операцій, а у найкращих - порядку O(n*log2n).

1.2.1 Сортування включенням

Сортування включенням -- простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:

· простота у реалізації;

· ефективний (зазвичай) на маленьких масивах;

· ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d -- кількість інверсій;

· на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною;

· є стабільним алгоритмом.

Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням.

На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку до тих пір, доки набір вхідних даних не буде вичерпано. Метод вибору чергового елементу з початкового масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються за порядком їх появи у вхідному масиві.

void insertSort(int* a, int length){

for (int i = 1; i < length; ++i)

{

int value = a[i];

int j = i - 1;

for ( ;j >= 0 && a[j] > value; --j)

{

a[j + 1] = a[j];

}

a[j + 1] = value;

}}

Розглянемо тепер порядок сортування масива по кроках (табл. 1.1):

1.2.2 Сортування вибором

При сортуванні вибором на кожному кроці, для i від 1 до (n-1), знаходимо найменший елемент серед a[i], a[i+1], ..., a[n] з номером k, після чого міняемо місцями елементи a[i] та a[k].

void selection(int* array, int length){

for(int i=0;i<length;i++)

{

int minIndex=i;

for(int j=i;j<length;j++)

{

if(array[minIndex]>array[j])

{

//Finds smallest number

minIndex=j;

}

}

int swapVal=array[i];

array[i]=array[minIndex];

array[minIndex]=swapVal;

} }

Послідовність сортування масива по кроках:

Якщо розглянути необхідну кількість дій, то вона має порядок O(n2). Дійсно, зовнішній цикл виконується (n-1) раз, а на кожному його кроці внутрішній цикл виконується, в середньому, n div 2 раз.

1.2.3 Обмінне сортування

Алгоритм засновано на порівнянні пар сусідніх елементів масиву. При необхідності елементи у парі міняються місцями. Так продовжується до впорядкування всіх елементів. Цей метод також відомий як „бульбашкове” сортування, оскільки за один крок зовнішнього циклу найменший („найлегший”) елемент серед розглянутих елементів масива переміщується до початку масива (немов би „спливає” нагору).

#include <algorithm>

void bubbleSort(int* array, int size)

{

//для швидшого сортування посортованих

bool wasSwapped = true;

for (int i = 1; (i <= size) && wasSwapped; ++i)

{

wasSwapped = false;

for (int j = 0; j < (size - i); ++j)

{

if (array[j] > array[j + 1])

{

std::swap(array[j], array[j + 1]);

wasSwapped = true;

}

}

}

}

Якщо розглянути необхідну кількість дій, то вона має порядок O(n2). Зовнішній цикл виконується (n-1) раз, а на кожному його кроці внутрішній цикл виконується, в середньому, n div 2 раз. Взагалі, „бульбашкове” сортування відноситься до найменш ефективних методів. Дещо покращати його можна, чергуючи порядок проходу масива та зупиняючись, коли всі елементи відсортовано (дійсно, на кроках 6, 7 та 8 обмінного сортування наш масив вже відсортований та не змінюється). Такий модифікований алгоритм дістав назву „шейкерного” сортування.

Хоча шейкерне сортування дещо ефективніше за “бульбашкове”, воно відноситься до простих методів сортування та вимагає порядку O(n2) операцій.

Розглянемо тепер швидкі методи сортування.

1.2.4 Сортування злиттям

Сортування злиттям -- алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй».

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається -- тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

Приклад реалізації на С++

#include <algorithm>

#include <vector>

using namespace std;

template <typename T>

void merge_sort(T* elems, //original array

T* tmp_elems, //temp array to hold intermediate results, should be same size as array "elems"

size_t size)

{

if (size <= 1) {return;} //nothing to sort

const size_t left_size = size / 2;

const size_t right_size = size - left_size;

merge_sort(elems, tmp_elems, left_size);

merge_sort(elems + left_size, tmp_elems + left_size, right_size);

T* leftIt = elems; // pointer to walk through left part

T* const pivot = elems + left_size; //end of left part, start of right part

T* rightIt = pivot; // pointer to walk through right part

T*const end = elems + size;

T* outputIt = tmp_elems; //pointer to where to write when merging left and right subparts

while (true)

{

if (*leftIt < *rightIt)

{

*outputIt++ = *leftIt++;

if (leftIt == pivot)

{

// copy the rest of right part that has not been copied yet

copy(rightIt,

end,

outputIt);

break;

}

}

else

{

*outputIt++ = *rightIt++;

if (rightIt == end)

{

// copy the rest of left part that has not been copied yet

copy(leftIt,

pivot,

outputIt);

break;

}

}

}

copy(tmp_elems,

tmp_elems + size,

elems);

}

1.2.5 Швидке сортування

Перш ніж розглядати сортування, розглянемо процес поділу масива. Вибрають деякий елемент масива x та знаходять ліворуч від нього елемент a[i]>x, а праворуч - a[j]<x. Далі продовжують перегляд та обмін значень елементів, поки нарешті у лівій частині масива опиняться всі елементи, менші за x, а у правій частині - більші за x.

Швидке сортування полягає у застосуванні поділу спочатку до всього масива, потім до лівої та правої частин масива, потім для частин цих частин і так далі, поки кожна з частин не буде складатись тільки з одного елемента (отже буде відсортованою). Цей процес описується з використанням рекурсії підпрограмою:

int n, a[n];

void qs(int* s_arr, int first, int last)

{ int i = first, j = last, x = s_arr[(first + last) / 2];

do

{

while (s_arr[i] < x) i++;

while (s_arr[j] > x) j--;

if(i <= j)

{

if (s_arr[i] > s_arr[j]) swap(&s_arr[i], &s_arr[j]);

i++;

j--;

}

}

while (i <= j);

if (i < last) qs(s_arr, i, last);

if (first < j) qs(s_arr, first, j);

}

Кількість дій, необхідна для сортування, має порядок O(nlog2n). Дійсно, цикл кількість рекурсивних викликів процедури має порядок O(n), а середня довжина частини масиву при сортуванні - log2n. Цей алгоритм, як і сортування злиттям, вимагає додаткової пам'яті порядку n за рахунок рекурсивних викликів процедури Sort.

• Розділ 2. Практична частина

2.1 Розробка лінійних алгоритмів та програм

/************************************************************/

/* */

/* Підпрограми-функції з параметрами-значеннями */

/* засобами мови С. */

/* Дано:координати точок М1(x1;y1;z1) та М2 (x2;y2;z2) */

/* Обчислити та вивести на друк: */

/* координати точки М0(x0;y0;z0), яка ділить відрізок */

/* М1М2 у відношенні к */

/* Для обчислення скласти */

/* підпрограми-функції з параметрами-значеннями */

/* */

/************************************************************/

#include <iostream>

#include <math.h>

#define pi 3.14159

//Прототип функції:

float x0 (float x1, float x2, float k);

float y0 (float y1, float y2, float k);

float z0 (float z1, float z2, float k);

using namespace std;

int main(){

setlocale(LC_ALL, "Ukrainian");

//Оголошення констант та змінних:

float x1,x2,y1,y2,z1,z2,k;

//Ввід заданих величин радіуса та висоти:

cout<<"Введіть координати М1(x;y;z) "<<endl;

cin>>x1;

cin>>y1;

cin>>z1;

cout<<"Введіть координати М2(x;y;z) "<<endl;

cin>>x2;

cin>>y2;

cin>>z2;

cout<<"Введіть коефіцієнт к: "<<endl;

cin>>k;

//Обчислення параметрів циліндра:

cout<<"x0="<<x0 (x1,x2,k)<<endl;

cout<<"y0="<<y0 (y1,y2,k)<<endl;

cout<<"z0="<<z0 (z1,z2,k)<<endl;

system ("pause");

float x0 (float x1, float x2, float k) {

return (x1+k*x2)/(1+k); }

float y0 (float y1, float y2, float k){

return (y1+k*y2)/(1+k);}

float z0 (float z1, float z2, float k){

return (z1+k*z2)/(1+k);}

Результати роботи програми:

Введ?ть координати М1(x;y;z)

2 2 2

Введ?ть координати М2(x;y;z)

4 4 4

Введ?ть коеф?ц?єнт к:

2

x0=3.33333

y0=3.33333

z0=3.33333

2.2 Розробка розгалужених алгоритмів та програм

/**********************************************************/

/* */

/* Обчислення значення складної функції */

/* засобами мови С. */

/* Обчислити значення складної функції у: */

/* y=exp(-(fabs(x-a))) , якщо x<3; */

/* y=pow(a+pow(x,1.5),0.2) , якщо 3<=x<10; */

/* y=y=log(fabs(b*x)+1)*log(fabs(b*x)+1) , якщо x>=10; */

/* не існує, в інших випадках. */

/* */

/**********************************************************/

#include <iostream>

#include<math.h>

#include <conio.h>

using namespace std;

int main(){

float y, x, a, b;

cout<<"x=";

cin>>x;

cout<<"a=";

cin>>a;

cout<<"b=";

cin>>b;

if (x < 3) y=exp(-(fabs(x-a)));

else if ((x >= 3) && (x<10)) y=pow(a+pow(x,1.5),0.2);

else if (x >= 10) y=log(fabs(b*x)+1)*log(fabs(b*x)+1);

cout<<"y="<<y;

getch();

return 0;}

Результати роботи програми:

x=2

a=3

b=4

y=0.367879

2.3 Розробка циклічних алгоритмів та програм

/************************************************************/

/* Табулювання функції на інтервілі засобами мови С++ */

/* Обчислити всі значення функції: */

/* s=s*((pow(-1,i)*(i*i+4*i))/(i*i+4*i+5)), аргумент якої змінюється */

/* на інтервалі[1;10] з кроком h=1. Циклічні процеси */

/* реалізувати командою while */

/************************************************************/

#include <iostream>

#include<conio.h>

#include<math.h>

#include<iomanip>

using namespace std;

int p (){

while (int i < 10)

{

s=s*((pow(-1,i)*(i*i+4*i))/(i*i+4*i+5));

cout<<fixed<<setprecision(2)<<"\nI i="<<i<<" I s= "<< s<<" I\n";

k++;

i++;

}

}

int main(){

setlocale (LC_ALL, "ukrainian");

float i=1, s=1,sa,k=0;

cout<<"Результати табулювання функції:\n";

p ();

cout<<"\n Обробка результатів табулювання: \n";

if(k>0)

{

sa=s/k;

cout<<"\nI К-сть значень I "<<k<<" I";

cout<<"\nI Сума значень I "<<s<<" I";

cout<<"\nI Середнє ариф I "<<sa<<" I";

}

else

printf("\n Такої функції не існує.\n",k);

getch();

}

Результати роботи програми:

Результат табулювання функцыъ :

I-------------------I------------------I

I i= 1.00 I y= -45.00 I

I-------------------I------------------I

I i= 2.00 I y= 61.11 I

I-------------------I------------------I

I i= 3.00 I y= -79.20 I

I-------------------I------------------I

I i= 4.00 I y= 99.27 I

I-------------------I------------------I

I i= 5.00 I y=-121.33 I

I-------------------I------------------I

I i= 6.00 I y= 145.38 I

I-------------------I------------------I

I i= 7.00 I y=-171.43 I

I-------------------I------------------I

I i= 8.00 I y= 199.47 I

I-------------------I------------------I

I i= 9.00 I y=-229.50 I

I-------------------I------------------I

I i=10.00 I y= 261.53 I

I-------------------I------------------I

I i=11.00 I y=-295.56 I

I-------------------I------------------I

I i=12.00 I y= 331.58 I

I-------------------I------------------I

Обробка резельтат?в табудюваня фунц?ї :

К?льк?сть значень функц?ї з ?нтервалу [1;12] k=10

Добуток значень функц?ї з ?нтервалу [1;12] S=-782786273094473350000.00

2.4 Розробка ітераційних алгоритмів та програм

/************************************************************/

/*Ітерації обчислювальні процеси : обчислення із заданою точністю корення */

/* нелінійного рівняння засобами мови С++ */

/* Обчислити із заданою точністю eps=0.001 методом дотичних */

/* і відокремити корені нелінійного рівняння f(x)=3*x*exs(x)=1 */

/* Для обчислення значення функцыъ f(x) скласти підпрограму-функції*/

/************************************************************/

#include<iomanip>

#include<math.h>

#include<iostream>

/*метод дотичних*/

using namespace std;

float fun(float x) {

return(3*x*exp(x)-1); };

float funp(float x) {

return(3*exp(x)*(x+1));};

float funp2(float x) {

return(3*exp(x)*(x+2));};

int main() {

setlocale(0,"");

float e=0.001,a,b,b1,r,x1,x0;

cout<<"Введіть початок відрізка: ";

cin>>a;

cout<<"Введіть кінец відрізка: ";

cin>>b;

do {

x1=b-fun(b)/funp(b);

if (fun(x1)>0) b=x1;

else a=x1;

r=fabs(fun(b));

cout<<setw(3)<<fixed<<setprecision(3)<<" x="<<b<<" f(b)="<<r<<endl;}

while(r >=e);

cout<<"korin="<<b<<" f(x)="<<fun(b);

system ("pause");

}

Результати роботи програми:

Введ?ть початок в?др?зка: 1

Введ?ть к?нец в?др?зка: 3

x=2.254 f(b)=63.427

x=1.572 f(b)=21.721

x=0.988 f(b)=6.959

x=0.553 f(b)=1.887

x=0.321 f(b)=0.325

x=0.261 f(b)=0.017

x=0.258 f(b)=0.000

korin=0.258 f(x)=0.000

2.5 Розробка алгоритмів та програм обробки одновимірного масиву

/************************************************************/

/* Протабулювати функцію Y=F(x), аргумент якої пробігає множину */

/*елементів одномірного масиву А, попередньо обчисливши значення*/

/* параметраS. */

/* S-ln(sqrt(exp(x) + sin2 х)), */

/* де S - кількість нульових елементів масиву А */

/************************************************************/

#include<iostream>

#include<math.h>

#include<iomanip>

using namespace std;

class Array{

public:

int Sym(int s,int a[5]);

void get_Y(float y, int s, int a[5]);

int a[5];

}

int Array::Sym(int s,int a[5])

{

s=0;

for(int i=0;i<5;i++)

{

if(Array::a[i]==0) s++;

}

};

void Array::get_Y(float y, int s, int a[5]){

cout<<"\n Результати табулювання:\n";

for(int i=0;i<5;i++) {

y=(s-log(sqrt(exp(*(a+i)) + sin(2*(*(a+i))))));

cout<<" --------------------\n";

cout<<fixed<<setprecision(2)<<"I x = "<<*(a+i)<<" I y="<<y<<" I"<<endl; }

cout<<" ----------------------\n";};

int main(){

setlocale(LC_ALL,"Ukrainian");

Array A;

A.a[0]=0;

A.a[1]=1;

A.a[2]=5;

A.a[3]=0;

A.a[4]=-2;

int s;

A.Sym(s,a);

A.get_Y(1,s,A.a);

system("pause");

return 0;}

Результати роботи програми:

Результати табулювання:

--------------------

I x = 0 I y=2.00 I

--------------------

I x = 1 I y=1.36 I

--------------------

I x = 5 I y=-0.50 I

--------------------

I x = 0 I y=2.00 I

--------------------

I x = -2 I y=2.06 I

2.6 Розробка алгоритмів та програм обробки двовимірного масиву

/************************************************************/

/* Дано двовимірний масив a[m][n], елемти якого дійсного типу */

/* необхідно знайти max елементи кожного стовчика та значення їх */

/*індексів. Доступ до елементів здійснити за допомогою вказівників*/

/************************************************************/

#include<iostream>

using namespace std;

int Vvid(float a[10][10],int m,int n){ //функція вводу

cout<<"Введіть поелементно заданий масив:\n";

for(int i = 0; i < m; i++)

{

for(int j = 0; j < n; j++)

{

cout<<" введіть a["<<i<<"]["<<j<<"]=";

cin>>*(*(a+i)+j);

}

}

}

int Druk(float a[10][10],int m,int n){

int i,j;

cout<<"\n\n Заданий масив\n";

for(i=0;i<m;i++)

{

for (j=0;j<n;j++)

cout<<" "<<*(*(a+i)+j);

cout<<"\n";

}

}

int Max(float a[10][10],int m,int n){

float min, max; //обчислення min тa max значень масиву

min=a[0][0];

int i, j;

int nomstr, nomsto;

int numstr, numsto;

max=a[0][0];

numstr=0;

numsto=0;

for(j=0;j<n;j++)

{

for( i=0;i<m;i++)

{

if (*(*(a+i)+j) > max)

{

max=*(*(a+i)+j);

numstr=i;

numsto=j;

cout<<"\nмаксимальний елемент стовчика max="<<max<<"\n";

cout<<" номер стрічки максимального елементу numstr="<<numstr<<"\n";

cout<<" номер стовпця максимального елементу numstr="<<numsto<<"\n";

}

}

}

}

int main()

{

setlocale(LC_ALL,"UKrainian");

float a[10][10];

float min, max;

int m, n;

int i, j;

int numstr, numsto;

cout<<"\n Введіть кілкість стрічок масиву:";

cin>>m;

cout<<"Введіть кілкість стовпців масиву:";

cin>>n;

Vvid(a, m, n);

Druk(a, m, n);

Max(a, m, n);

system("pause");

}

Результати роботи програми:

Введ?ть к?лк?сть стр?чок масиву:2

Введ?ть к?лк?сть стовпц?в масиву:2

Введ?ть поелементно заданий масив:

введ?ть a[0][0]=1

введ?ть a[0][1]=2

введ?ть a[1][0]=3

введ?ть a[1][1]=4

Заданий масив

1 2

3 4

максимальний елемент стовчика max=3

номер стр?чки максимального елементу numstr=1

номер стовпця максимального елементу numstr=0

максимальний елемент стовчика max=4

номер стр?чки максимального елементу numstr=1

2.7 Розробка програм обробки стрічок

/************************************************************/

/* Задано стрічку символів. Замінити всі малі букви великими */

/*****************************************************************/

#include <iostream>

#include <conio.h>

#include <stdlib.h>

#include <string.h>

#include <assert.h>

#include <ctype.h>

#include <stdio.h>

using namespace std;

int main(){

setlocale(0,"");

char s[20];

int i=0,len;

cout<<" Введіть стрічку меншу 20 символів"<<endl;

int c;

while ((c = getchar ()) != EOF) {

putchar (toupper (c)); }

assert (! ferror (stdin));

getch();

return 0;}

Результати роботи програми:

Введ?ть стр?чку меншу 20 символ?в

aabrakadabra heytn jdfv kl njnau nja ijk

AABRAKADABRA HEYTN JDFV KL NJNAU NJA IJK

2.8 Розробка програм для роботи зі структурами

/************************************************************/

/* Формування масиву структур. */

/* Структура містить такі поля: №, марка, двигун,рік випуску*/

/* пробіг, прізвище власника. Вивести на екран інформацію про*/

/* дизельні машини, випущені до 1993 року */

/* число записів - 9 */

/************************************************************/

#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <iomanip>

#include <windows.h>

#define n 1

using namespace std;

struct String{ char ch[15]; };

struct Avto{

int number;

int marka;

int engine;

int year, distance;

char name[10];

};

//int Auto_desh(struct Avtoprice *p);

void Auto_entring(struct Avto *p);

void Auto_result(struct Avto *p);

//int str(int m, int e, char *marca[],char engin[]);

int Auto_desh(struct Avto *p);

int main(){

setlocale(LC_ALL,"Ukrainian");

system("cls");

int k;

Avto a1[n];

Auto_entring(a1);

Auto_result(a1);

Auto_desh(a1);

getch();

}

int Auto_desh(struct Avto *p){

cout<<" Власники дизельних машин, випущених до 1993 року:\n";

for(int i=0;i<n;i++)

{

if(( ((p+i)->year) < 1993)&&( ((p+i)->engine)==1) )

{

cout<<(p+i)->name<<"\n";

}

}

return 0;

}

void Auto_entring(struct Avto *p){

int c;

for(int i=0;i<n;i++)

{

(p+i)->number=i+1;

cout<<endl<<" Уведіть марку машини\n 1-Ауді,\n 2-Нива,\n 3-БМВ,\n 4-Опель\n ";

cin>>(p+i)->marka;

cout<<"\n 1-дизельний,\n 2-карбюраторний\n ";

cin>>(p+i)->engine;

cout<<" Уведіть рік випуску машини ";

cin>>(p+i)->year;

cout<<" Уведіть пробіг машини в тис.км ";

cin>>(p+i)->distance;

cout<<"\n Уведіть прізвище власника ";

cin>>(p+i)->name;

}

}

void Auto_result(struct Avto *p){

cout<<"\n"<<" Машини:"<<"\n";

cout<<"№ Назва Двигун Рік Пробіг Власник "<<"\n";

for(int i=0; i<n; i++)

{

cout<<setprecision(5)<<(p+i)->number<<"\t";

if (((p+i)->marka) ==1 ) {cout<<"Ауді"; }

else if(((p+i)->marka)==2 ){cout<<"Нива";}

else if(((p+i)->marka)==3 ){cout<<"БМВ"; }

else if(((p+i)->marka)==4 ){cout<<"Опел";}

switch ((p+i)->engine){

case 1:{ cout<<"\tдизельний"; break;}

case 2:{ cout<<"\tкарбюраторний"; break;}

}

cout<<"\t"<<(p+i)->year<<"\t"<<(p+i)->distance<<"\t"<<(p+i)->name<<"\n";}}

Результати роботи програми:

Увед?ть марку машини

1-Ауд?,

2-Нива,

3-БМВ,

4-Опель

1

1-дизельний,

2-карбюраторний

1

Увед?ть р?к випуску машини 1987

Увед?ть проб?г машини в тис.км 3

Увед?ть пр?звище власника sader

Машини:

№ Назва Двигун Р?к Проб?г Власник

1 Ауд? дизельний 1987 3 sader

Власники дизельних машин, випущених до 1993 року:

sader

2.9 Розробка програм для роботи з файлами

/************************************************************/

/* Завдання створити файл паралельного доступу з такими полями: */

/* 1)№ */

/* 2) марка; */

/* 3) двигун(дизельний чи карбюраторний); */

/* 4) рік випуску */

/* 5) пробіг; */

/* 6) прізвище власника ; */

/* Повино бути число записів- 9 . */

/* Вивести на екран інформацію про */

/* дизельні машини, випущені до 1993 року */

/* Реалізацію здійснити мовою С++ . */

/************************************************************/

#include <fstream>

#include <string>

#include <iostream>

#include <conio.h>

#include <windows.h>

#include <iomanip>

#include <math.h>

using namespace std;

struct Avto{

int number;

int marka;

int engine;

int year, distance;

char name[10];};

int main() {

setlocale(LC_ALL,"Ukrainian");

system("cls");

//Відкриття файлу input.txt :

ifstream f;

f.open("input.txt");

string typocin, predmet, formzdach,formnavch;

int nomer, ocinka;

Avto p[2];

int c;

for(int i=0;i<1;i++)

{

(p+i)->number=i+1;

cout<<endl<<" Уведіть марку машини\n 1-Ауді,\n 2-Нива,\n 3-БМВ,\n 4-Опель\n ";

cin>>(p+i)->marka;

cout<<"\n 1-дизельний,\n 2-карбюраторний\n ";

cin>>(p+i)->engine;

cout<<" Уведіть рік випуску машини ";

cin>>(p+i)->year;

cout<<" Уведіть пробіг машини в тис.км ";

cin>>(p+i)->distance;

cout<<"\n Уведіть прізвище власника ";

cin>>(p+i)->name;

f>>(p+i)->number>>(p+i)->marka>>(p+i)->engine>>(p+i)->year

>>(p+i)->distance>>(p+i)->name;

}

f.close(); //Закриття файлу input.txt

//Створення файлу output.txt :

ofstream g;

g.open("output.txt");

//Відповідно до умови:

g<<" Власники дизельних машин, випущених до 1993 року:\n";

for(int i=0;i<1;i++)

{

if(( ((p+i)->year) < 1993)&&( ((p+i)->engine)==1) ){

g<<(p+i)->name<<"\n";}

}

g.close(); //Закриття створеного файлу output.txt

getch();

return 0;}

Результати роботи програми:

Увед?ть марку машини

1-Ауд?,

2-Нива,

3-БМВ,

4-Опель

1

1-дизельний,

2-карбюраторний

1

Увед?ть р?к випуску машини 1987

Увед?ть проб?г машини в тис.км 3

Увед?ть пр?звище власника sader

Машини:

№ Назва Двигун Р?к Проб?г Власник

1 Ауд? дизельний 19 3 der

Власники дизельних машин, випущених до 1993 року:

der

2.10 Розробка програм для графічного режиму

/************************************************************/

/* Побудова графіка функцій. Завдання. Побудувати графік */

/* функції y=(sin(x*a)*sin(x*a)+pow(abs(x-b),1/3))/pow(abs(x-b),3)*/

/************************************************************/

#include <graphics.h>

#include <stdlib.h>

#include <conio.h>

#include <stdio.h>

#include <math.h>

void drawAxes(void) {

int xmax,ymax,i;

char c[3];

setcolor(15);

xmax = getmaxx();

ymax = getmaxy();

line(xmax/2-400,ymax/2,xmax/2+400,ymax/2);

line(xmax/2,ymax/2-400,xmax/2,ymax/2+400);

for(i=-9;i<10;i++)

{

line(xmax/2+i*20,ymax/2,xmax/2+i*20,ymax/2-5);

line(xmax/2,ymax/2+i*20,xmax/2+5,ymax/2+i*20);

}

setcolor(12);

for(i=-9;i<10;i++)

{

itoa(i,c,10);

outtextxy(xmax/2+i*20-5,ymax/2+5,c);

if (i) outtextxy(xmax/2-15,ymax/2-i*20,c);

}}

void drawFunction(void) {

float a =0.28, b=19.3;

int xmax,ymax,i,j,i0,j0;

double x,y;

setcolor(11);

xmax = getmaxx();

ymax = getmaxy();

x=-400/20.0;

y=(sin(x*a)*sin(x*a)+pow(abs(x-b),1/3))/pow(abs(x-b),3);

j=-y*20+ymax/2;

i0=xmax/2-400;j0=j;

for(i=xmax/2-400;i<xmax/2+400;i++)

{

x=(i-xmax/2)/20.0;

if(x == 19.3)

{

y=(sin(x*a)*sin(x*a)+pow(abs(x-b),1/3))/pow(abs(x-b),3);

j=-y*20+ymax/2;

line(i0,j0,i,j);

i0=i;j0=j;

}

}}

int main(){

int graphdriver=DETECT, graphmode,errorcode;

initgraph(&graphdriver,&graphmode,"");

errorcode = graphresult();

if(errorcode != grOk)

{

printf("Graphics error: %s\n", grapherrormsg(errorcode));

printf("Press any key to halt:");

getch();

exit(1); //возврат с кодом ошибки

}

drawAxes(); //вызов процедуры черчения осей

drawFunction(); // вызов процедуры черчения графика

getch(); //задержка консоли

closegraph(); //конец работы в графическом режиме

return 0;}

Результати роботи програми:

2.11 Розробка програм для роботи з класами та об'єктами

/************************************************************/

/* */

/* Конструювання класів та об*єктів засобами мови С++ */

/* Завдання.Сформувати клас Dani з такими елементами : */

/* Клас містить такі поля: №, марка, двигун,рік випуску */

/* пробіг, прізвище власника. Вивести на екран інформацію про*/

/* дизельні машини, випущені до 1993 року */

/* число записів - 2 */

/* */

/************************************************************/

#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <iomanip>

#include <windows.h>

#define n 1

using namespace std;

class Avto{

public:

int number;

int marka;

int engine;

int year, distance;

char name[10];

void Auto_entring(int number,int marka,int engine,int year,int distance,char name[10]);

void Auto_result(int number,int marka,int engine,int year,int distance,char name[10]);

int Auto_desh(int number,int marka,int engine,int year,int distance,char name[10]);};

int main(){

setlocale(LC_ALL,"Ukrainian");

system("cls");

int k;

Avto obj;

obj.Auto_entring(obj.number, obj.marka, obj.engine, obj.year, obj.distance,obj.name);

obj.Auto_result(obj.number, obj.marka, obj.engine, obj.year, obj.distance,obj.name);

obj.Auto_desh(obj.number, obj.marka, obj.engine, obj.year, o bj.distance,obj.name);

getch();}

int Avto::Auto_desh(int number,int marka,int engine,int year,int distance,char name[10]){

cout<<" Власники дизельних машин, випущених до 1993 року:\n";

for(int i=0;i<n;i++)

{

if(( (Avto::year) < 1993)&&( (Avto::engine)==1) )

{

cout<<Avto::name<<"\n";

}

}

return 0;}

void Avto::Auto_entring(int number,int marka,int engine,int year,int distance,char name[10]){

int c;

for(int i=0;i<n;i++)

{

Avto::number=i+1;

cout<<endl<<" Уведіть марку машини\n 1-Ауді,\n 2-Нива,\n 3-БМВ,\n

4-Опель\n ";

cin>>Avto::marka;

cout<<"\n 1-дизельний,\n 2-карбюраторний\n ";

cin>>Avto::engine;

cout<<" Уведіть рік випуску машини ";

cin>>Avto::year;

cout<<" Уведіть пробіг машини в тис.км ";

cin>>Avto::distance;

cout<<"\n Уведіть прізвище власника ";

cin>>Avto::name;

}}

void Avto::Auto_result(int number,int marka,int engine,int year,int distance,char name[10]){

cout<<"\n"<<" Машини:"<<"\n";

cout<<"№ Назва Двигун Рік Пробіг Власник "<<"\n";

for(int i=0; i<n; i++)

{

cout<<setprecision(5)<<Avto::number<<"\t";

if ((Avto::marka) ==1 ) {cout<<"Ауді"; }

else if((Avto::marka)==2 ){cout<<"Нива";}

else if((Avto::marka)==3 ){cout<<"БМВ"; }

else if((Avto::marka)==4 ){cout<<"Опел";}

switch (Avto::engine){

case 1:{ cout<<"\tдизельний"; break;}

case 2:{ cout<<"\tкарбюраторний"; break;}

}

cout<<"\t"<<Avto::year<<"\t"<<Avto::distance<<"\t"<<Avto::name<<"\n";

}

}

Результати роботи програми:

Увед?ть марку машини

1-Ауд?,

2-Нива,

3-БМВ,

4-Опель

2

1-дизельний,

2-карбюраторний

1

Увед?ть р?к випуску машини 2345

Увед?ть проб?г машини в тис.км 5

Увед?ть пр?звище власника fasdi

Машини:

№ Назва Двигун Р?к Проб?г Власник

1 Нива дизельний 2345 5 fasdi

Власники дизельних машин, випущених до 1993 року:

Висновки

Виконуючи курсову роботу, ми опрацювали тематичну літературу, провели аналіз методів сортування та застосування їх у повсякденному житті.

Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.

Виконуючи дану роботу, ми прийшли до ряду висновків:

· найбільш універсальним методом, є метод швидкого сортування («QuickSort»), він показує стабільно високі результати на будь-яких розмірах масивів.

· метод вставки ефективний, за умови великого часу виконання операцій перестановки, тому що він є абсолютним лідером за кількістю перестановок, програючи при цьому за кількістю порівнянь.

· при використанні невеликих масивів даних немає великої різниці в швидкості між методами сортування, тому доцільніше застосовувати метод Бульбашки або метод вставок.

· дослідження проводилося на масивах з великим ступенем невпорядкованості. Для масивів, які вже є майже відсортованими, найбільш застосуємо метод сортування вставками.

· алгоритми прямого сортування, не є складними у розумінні, легко виконувані і прості у реалізації;

· дані алгоритми, що ми розглянули, можна використовувати для сортування даних довільного типу, тобто ці алгоритми в певній мірі є універсальні;

· сортування методами вибору і сортування вставками як при найгіршому, так і при середньому варіанті мають квадратичний час виконання.

· швидкодія прямих методів сортування невелика, але якщо впорядковуваний масив є невеликим або ж сортування проводиться не часто, то ними користуватися є більш вигідно, ніж іншими алгоритмами;

· сортування вставками дає більш відчутну перевагу, якщо вихідний масив близький до впорядкованого стану;

· Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.

Виконуючи дану курсову роботу ми не тільки детально проаналізували теоретичний матеріал по напряму "Прямі алгоритми сортування", а й реалізували їх на практиці, з використанням мови високого рівня програмування С++.

Оскільки прямі алгоритми сортування вважаються більш простими, дана курсова робота може стати у пригоді при вивченні більш складних алгоритмів сортування, наприклад в графах, списках. Її можна буде використати як початковий матеріал для сортування об'єктів класу за певним ключем.

• Список використаних джерел

1. Веблог «Штучний Інтелект», Обмінне сортування числових даних.

2. А. Б. Ставровський, «Посібник з програмування для студентів 1 курсу факультету кібернетики», Розділ 17. Пошук, Сортування та Поняття Складності

3. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1

4. Дональд Кнут. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 106-110 of section 5.2.2: Sorting by Exchanging.

5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-2, pg.38.

6. Реалізація алгоритму швидкого сортування різними мовами програмування

7. Реалізації алгоритму швидкого сортування різними мовами програмування в стилі грамотного програмування

8. Айра П. Обьектно-Ориентированное прогрпммирование на С++. М.: Санкт-Петербург, 1999. - 460 с.

9. Архангельський А.Я. С++Builder 6: Справ. Пособие. Кн.1. Язык С++. - М.: Бином, 2004. - 544 с.

10. Глушаков С.В. Программирование на Visual C++. - М.: АСТ; Х.: Фоліо, 2003. - 726 с.

11. Дейтел Х. Как программировать на С++. - М.: Бином, 2001. - 1152 с.

12. Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль. М, 1991. - 709 с.

13. Клюшин Д. А. Полный курс С++. Москва: Санкт-Петербург, 2004. - 668 с.

14. Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. - М.:Издательский дом "Вильямс", 2000. - 750 с.

15. Ковалюк Т.В. Основи програмування. Київ: Видавнича група ВНV, 2005. - 385 с.

16. Культин Н. Б. С/С++ в задачах и примерах. - М., 2002. - 288 с.

17. Кучеренко В. Язык программирования С++ для начинающих и не только. - М.: Майор, 2001. - 160 с.

18. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. Херсон, 1997.

19. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. К.: ВЕК, 2000. - 441 с.

20. Мешков А.В. Visual C++ u MFC. - М, 2003. - 1040 с.

21. Павловская Т.А. С/С++: Программирование на языке высокого уровня: Учебник для студ. ВУЗ. М, 2002. - 464 с.

22. Секунов Н.Ю. Самоучитель Visual C++. М., 2002. - 735 с.

23. Франка П. С++: Учебный курс. М., 2002. - 521 с.

24. Щедріна О.І. Алгоритмізація та програмування процедур обробки інформації. К., 2001. - 240 с.

Додаток А

Додаток Б

Додаток В

Размещено на Allbest.ru

...