Знання недостатньо – ми повинні застосовувати його.
Бажання недостатньо – ми повинні діяти.
Сьогодні ми вивчимо:
1. Розв’язок д/з минулого уроку.
2. Лінійний пошук.
3. Сортування бульбашкою.
4. Сортування вибором.
5. Сортування включенням.
6. Завдання для закріплення матеріалу.
Розв’язок д/з минулого уроку
1. Написати шаблон функцій для пошуку середнього арифметичного значень масиву.
#include <iostream>
#include <conio.h>
using namespace std;
template <typename T> double Average(T n[], int len);
int main()
{
const int size = 5;
double arr_int[size];
double arr_double[size];
cout << " -->arr_int input [5 elements] :" << endl;
for (int i = 0; i <size; ++i)
cin>>arr_int[i];
cout<< " -->arr_double input [5 elements] :" <<endl;
for (int i = 0; i <size; ++i)
cin>>arr_double[i];
cout<< "\n</>done</>" <<endl;
cout<< "\nAverage [arr_int] = " <<Average(arr_int, size) <<endl;
cout<< "Average [arr_double] = " <<Average(arr_double, size) <<endl;
cout<< "\nDone, pushanykeytoexit" <<endl;
_getch();
return 0;
}
template <typename T> double Average(T n[], int len)
{
T sum = 0;
for (int i = 0; i <len; ++i)
sum += n[i];
return sum / len;
}
2. Написати функцію, яка здійснює округлення певного числа з заданою точністю.
#include <iostream>
#include <conio.h>
#include <cmath>
using namespace std;
template <typename t> t round(t x, int y);
int main()
{
setlocale(LC_CTYPE, "ukr");
double x;
int y;
cout<< "\n" << "Введiть число --> ";
cin>> x;
cout<< "\n" << "Кiлькiсть знаків пiсля коми --> ";
cin>> y;
cout<< "Результат: " <<round(x, y) <<endl;
_getch();
return 0;
}
template <typename t> tround(t x, int y)
{
int q = x * pow(10, y+1);
if (q % 10 >= 5)
{
q /= 10;
q++;
return (double)(q / pow(10, y));
}
else
return (double)(q / pow(10, y + 1));
}
3. Написати перевантажені шаблони функцій для пошуку коренів лінійного ax+b=0 та квадратного ax^2+bx+c=0 рівнянь. У функцію передавати коефіцієнти.
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
template <typename T, typename T2> double res (T q, T2 w);
template <typename T, typename T2, typename T3> double res (T a, T2 b, T3 c);
int main ()
{
setlocale (LC_CTYPE, "ukr");
double x, y;
cout<< "Лiнiйне рівняння ax + b = 0" <<endl;
cout<< "Введiть коефiцiенти [a, b] --> ";
cin>> x >> y;
double a,b,c;
cout<< "\n" << "Квадратне рівняння ax^2 + bx + c = 0" <<endl;
cout<< "Введiть коефiцiенти [a, b, c] --> ";
cin>> a >> b >> c;
cout<< "\n\n</>=-=-=-=-=-=-=-=-=- done -=-=-=-=-=-=-=-=-=-=" <<endl;
cout<< "Розв'язок лінійного рiвняння: ";
cout<<res(x,y) <<endl;
cout<< "\nРозв'язок квадратного рiвняння: ";
cout<<res(a,b,c) <<endl;
_getch();
return 0;
}
template <typename T, typename T2> double res (T q, T2 w)
{
if (!q)
{
cout<< "error \t Не можна дiлити на 0" <<endl;
return -1;
}
else
return -w/q;
}
template <typename T, typename T2, typename T3> double res (T a, T2 b, T3 c)
{
T D;
D = (b*b )- 4 * a*c;
if (D < 0){
cout<< "Дискримiнант менший вiд 0, розв'язки вiдсутнi" <<endl;
return -1;
}
elseif (D == 0)
return (-b + sqrt(D)) / 2 * a;
else {
cout<< (-b - sqrt(D)) / (2 * a) << " \t ";
return (-b + sqrt(D)) / (2 * a);
}
}
Лінійний пошук
Кожний програміст у своїй роботі зустрічає моменти коли потрібно працювати в відсортованими елементами або ж пошуку певного елементу. Зараз ми познайомимося з найпростішим алгоритмом пошуку. Зразу ж варто відзначити, що даний алгоритм ефективно працює тільки на невеликих масивах. Полягає він у тому, що ми будемо перевіряти кожен елемент масиву доки не знайдемо шуканий (ключ). Спробуйте самі його скласти, він надзвичайно простий. У мене получилася така блок-схема.
Тепер приклад програми:
#include <iostream>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
using namespace std;
int main ()
{
srand(time(NULL));
const short int size = 25;
int a[size];
cout<< "\n" << "First array: " <<endl;
for (int i=0; i<size; ++i)
{
a[i] = rand()%50;
cout<< a[i] << "\t";
}
int key;
cout<< "\n" << "Enterkey --> ";
cin>>key;
bool temp = false;
for (int i=0; i<size; ++i)
{
if (key == a[i]){
cout<< "Resultis - " << i <<endl;
temp = true;
break;
}
}
if (!temp)
cout<< "Notfound :( " <<endl;
_getch();
return 0;
}
Ще варто знати, коли вам доведеться здійснювати пошук неодноразово, то простіше і звісно ж швидше спершу відсортувати масив, а потім користуватися дещо кращим алгоритмом.
Найбільший плюс лінійного пошуку – не потрібно сортувати масив. Але це впливає на його найбільший мінус – час виконання.
Сортування бульбашкою
Алгоритм полягає у сортуванні двох сусідніх елементів, в залежності від критерію вони міняються місцями. Є багато швидших алгоритмів, але це один із найпростіших.
Давайте подивимося приклад такого сортування.
#include <iostream>
#include <algorithm>
#include <vector>
#include <time.h>
#include <stdlib.h>
using namespace std;
int main()
{
srand(time(NULL));
system("color A");
const short int size = 15;
int a[size];
//Заповнення
cout<< "\n" << "First array: " <<endl;
for (int i = 0; i<size; ++i)
{
a[i] = rand() % 1000;
cout<< a[i] << "\t";
}
cout<<endl;
// Сортування
int count = 0; // К-сть проходів
for (int i = 0; i<size - 1; ++i)
{
for (int j = 0; j<size - i - 1; ++j)
{
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
count++;
}
}
}
// Вивід
cout<< "\n" << "Result: " <<endl;
for (int i = 0; i <size; ++i)
cout<< a[i] << "\t";
cout<<endl;
cout<< "\n" << "counter = " <<count<<endl;
system("pause");
return 0;
}
Перший цикл після коментаря //сортування рахує кількість потрібних проходів по масиву. Наступний – порівнює і міняє місцями елементи.
Сортування вибором
В цілому менш ефективний за сортування включенням. І неефективний при роботі з великими масивами. Плюсом цього методу є це, що ліва частина повністю відсортована, а права – ні.
Полягає метод у пошуку мінімального значення і міняє його місцями з першими елементами списку.
Давайте спробуємо відсортувати масив з п’яти елементів:
Тепер код:
// Selection sort
#include <iostream>
#include <algorithm>
#include <vector>
#include <time.h>
#include <stdlib.h>
using namespace std;
int main()
{
srand(time(NULL));
system("color A");
const short int size = 20;
int a[size];
// Заповнення
cout<< "\n" << "Firstarray: " <<endl;
for (int i = 0; i<size; ++i)
{
a[i] = rand() % 100;
cout<< a[i] << "\t";
}
cout<<endl;
// Сортування вибором
int Min = 999, index = -1, count = 0;
for (int i = 0; i <size - 1; ++i)
{
for (int j = i; j<size; ++j)
{
if (Min> a[j]) {
Min = a[j];
index = j;
}
}
swap(a[i], a[index]);
count++;
Min = 999;
}
// Вивід результату
cout<< "\n" << "Aftersort: " <<endl;
for (int i = 0; i<size; ++i)
cout<< a[i] << "\t";
cout<<endl;
cout<< "\n" << "Counter = " <<count<<endl;
system("pause");
return 0;
}
Зауваження: не запам’ятовуйте код, вам достатньо зрозуміти як працює алгоритм. Дані два алгоритми достатньо прості і їх достатньо просто зрозуміти.
Сортування включенням
Перевагами цього методу є те, що він стабільний, швидший за два попередні, ефективний на малих масивах.
На кожному кроці ми вибираємо елемент і вставляємо його на потрібне місце у відсортованому масиві. Це все ми повторюємо до закінчення вхідних даних.
Код для самоперевірки:
#include <iostream>
#include <algorithm>
#include <vector>
#include <time.h>
#include <stdlib.h>
using namespace std;
int main ()
{
srand(time(NULL));
system("color A");
setlocale (LC_CTYPE, "ukr");
const short int size = 20;
int a[size];
// Заповнення
cout<< "\n" << "First array: " <<endl;
for (int i=0; i<size; ++i)
{
a[i] = rand() % 100;
cout<< a[i] << "\t";
}
// Insertion sort
for (int i=0; i<size; ++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;
}
// Вивід
cout<< "After sort: " <<endl;
for (int i=0; i<size; ++i)
cout<< a[i] << "\t";
cout<<endl;
system("pause");
return 0;
}
Яким з цим методів сортування користуєтесь ви сортуючи колоду карт?
Завдання для закріплення матеріалу
1. Дано масив випадкових чисел в діапазоні від -35 до 35. Ваше завдання: знайти позиції крайніх від’ємних елементів і відсортувати масив в цьому проміжку.
2. Написати функцію, яка сортує масив. Останній параметр функції вказує на вид сортування (по зростанню(a->z) або спаданню (z->a).
3. З масивом випадкових чисел, від 0 до 50, виконати такі дії:
a) Функцію, яка розкидає елементи, тобто перетворити масив на несортований. b) Виберіть за допомогою функції rand випадкове число і знайти його позицію. c) Елементи ліворуч від даної позиції сортувати по зростанню, праворуч – спадання.
Схожі статті:
Новіші матеріали:
Старіші матеріали:
|