Єдина Країна!

Головне меню

Наша кнопка

Українські уроки про ІТ

Друзі

Підтримка української армії


Головна Програмування - C++ Базовий курс програмування на С++. Урок 12. Сортування. Лінійний пошук

Базовий курс програмування на С++. Урок 12. Сортування. Лінійний пошук
Написав Joker   
Неділя, 11 жовтня 2015 20:02
Переглядів: 3841

Знання недостатньо – ми повинні застосовувати його.

Бажання недостатньо – ми повинні діяти.

 

Сьогодні ми вивчимо:

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) Елементи ліворуч від даної позиції сортувати по зростанню, праворуч – спадання.


( 9 Проголосувало )

Схожі статті:
Новіші матеріали:
Старіші матеріали:

Коментарі
Добавити новий
Залишити коментар
Ім`я:
e-mail:
 
Тема:
 
:angry::0:confused::cheer:B):evil::silly::dry::lol::kiss::D:pinch:
:(:shock::X:side::):P:unsure::woohoo::huh::whistle:;):s
:!::?::idea::arrow:
 
Введіть цей настирливий код
Русская редакция: www.freedom-ru.net & www.joobb.ru

3.26 Copyright (C) 2008 Compojoom.com / Copyright (C) 2007 Alain Georgette / Copyright (C) 2006 Frantisek Hliva. All rights reserved."

 

Ввійти



Підписка

Хто онлайн?

Немає
На даний момент 88 гостей на сайті

Український рейтинг
TOP.TOPUA.NET