|
Вимірювати продуктивність програмування
підрахунком рядків коду – це так само, як
оцінювати будівництво літака по його вазі
Bill Gates
Сьогодні ми вивчимо:
1. Розв’язок д/з минулого уроку.
2. Рекурсія.
3. Двійковий пошук.
4. Швидке сортування.
5. Завдання для закріплення матеріалу.
Розв’язок д/з минулого уроку
1. Дано масив випадкових чисел в діапазоні від -35 до 35. Ваше завдання: знайти позиції крайніх від’ємних елементів і відсортувати масив в цьому проміжку
#include <iostream>
#include <conio
#include <algorithm>
#include <time
#include <stdlib
#include <vector>
using namespace std;
int main ()
{
srand(time(NULL));
const short size =15;
int a[size];
cout<< "First array: " <<endl;
for (int i = 0; i<size; ++i)
{
a[i] = rand()%(35+1-(-35))+(-35);
cout<< a[i] << "\t";
}
int left, right;
for (int i=0; i<size; ++i)
{
if(a[i]<0){
left = i;
break;
}
}
for (int i=size-1; i>=0; --i)
{
if (a[i]<0){
right = i;
break;
}
}
cout<< "\nleft = " << left <<endl;
cout<< "right = " << right <<endl;
for (int i=left; i<right; ++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<< "Second array: " <<endl;
for (int i=0; i<size; ++i)
cout<< a[i] << "\t";
cout<<endl;
cout<< "\n\n" << "Sorting elements: " <<endl;
for (int i = left; i<right; ++i)
cout<< a[i] << "\t";
cout<<endl;
_getch();
return 0;
}
2. Написати функцію, яка сортує масив. Останній параметр функції вказує на вид сортування (по зростанню(a->z) або спаданню (z->a)).
#include <iostream>
#include <conio
#include <algorithm>
#include <vector>
#include <time
#include <stdlib
using namespace std;
void Sort (int n[], int len, bool flag);
int main ()
{
srand(time(NULL));
system ("color A");
setlocale (LC_CTYPE, "ukr");
const short int size = 15;
int a[size];
cout<< "Початковий масив: " <<endl;
for (int i=0; i<size; ++i)
{
a[i] = rand()%100;
cout<< a[i] << "\t";
}
bool key;
cout<< "\nВиберіть вид сортування [1/0] --> ";
cin>> key; // 1 - up 0 - down
Sort(a, size, key);
_getch();
return 0;
}
void Sort (int n[], int len, bool flag)
{
if (flag) { // up
int Min = 999;
int index = -1;
for (int i=0; i<len-1; ++i)
{
for (int j=i; j<len; ++j)
{
if (Min > n[j])
{
Min = n[j];
index = j;
}
}
swap (n[i], n[index]);
Min = 999;
}
cout<< "\n" << "Результат:" <<endl;
for (int i=0; i<len; ++i)
cout<< n[i] << "\t";
cout<<endl;
}
else { // down
int Max = -1;
int index = -1;
for (int i=0; i<len-1; ++i)
{
for (int j=i; j<len; ++j)
{
if (Max < n[j])
{
Max = n[j];
index = j;
}
}
swap (n[i], n[index]);
Max = -1;;
}
cout<< "\n" << "Результат:" <<endl;
for (int i=0; i<len; ++i)
cout<< n[i] << "\t";
cout<<endl;
}
}
3. Масивом випадкових чисел, від 0 до 50, виконати такі дії:
- Функцію, яка розкидає елементи, тобто перетворити масив на несортований.
- Виберіть за допомогою функцію функції rand випадкове число і знайти його позицію.
- Елементи ліворуч від даної позиції сортувати по зростанню, праворуч – спаданням.
#include <iostream>
#include <conio
#include <time
#include <stdlib
using namespace std;
void Change(int arr[], int n);
int main()
{
srand(time(NULL));
const short int size = 20;
int arr[size];
//Заповнення масиву / Вивід масиву на екран
cout<< "\n" << "First array: " <<endl;
for (int i = 0; i <size; ++i)
{
arr[i] = rand()%20;
cout<<arr[i] << "\t";
}
// Розкидуємо елементи
Change(arr, size);
// Створюємо випадкове число і знаходимо його позицію
int key = rand() % 20;
cout<< "\n" << "Random key = " <<key<<endl;
for (int i = 0; i <size; ++i)
{
if (key == arr[i]) {
cout<< "\n" << "Random key_index = " << i <<endl;
key = i;
}
}
// Сортування
for (int i=0; i<key; ++i) // beforekey
{
int Min = 999, index = -1;
for (int j=i; j<key; ++j)
{
if (Min>arr[j])
{
Min = arr[j];
index = j;
}
}
swap(arr[i],arr[index]);
}
for (int i=key+1; i<size; ++i)
{
int Max = -1, index = -1;
for (int j = i; j<size; ++j)
{
if (Max<arr[j])
{
Max = arr[j];
index = j;
}
}
swap(arr[i], arr[index]);
}
// Вивід масиву
cout<< "\n\n\nFinal array: " <<endl;
for (int i = 0; i <size; ++i)
cout<<arr[i] << "\t";
cout<<endl;
cout<< "\n\n" << "Final array before key: " <<endl;
for (int i = 0; i <key; ++i)
cout<<arr[i] << "\t";
cout<< "\n" << "Final array after key: " <<endl;
for (int i = key+1; i <size; ++i)
cout<<arr[i] << "\t";
cout<<endl;
_getch();
return 0;
}
void Change(int arr[], int n)
{
for (int i = 0; i < n / 2 - 1; ++i)
{
int flag2 = rand() % 20;
int flag = rand() % 10;
swap(arr[flag], arr[flag2]);
}
cout<< "\n" << "Secondarray: " <<endl;
for (int i = 0; i < n; ++i)
cout<<arr[i] << "\t";
cout<<endl;
}
Рекурсія
Ще однією «традицією» програмістів (перша – Hello world) є вивчення рекурсії на прикладі факторіалів. Спершу потрібно зрозуміти, що таке факторіал. Тут все дуже просто, факторіал – це добуток чисел від 1 до заданого числа включно. Позначається n! . Наприклад,
5! = 1 * 2 * 3 * 4 * 5 = 120
Тобто, факторіал 5 дорівнює 120. Для кращого засвоєння ось приклад програми, яка вираховує факторіал:
#include <iostream>
#include <conio
#include <algorithm>
#include <vector>
using namespace std;
int main ()
{
int n, res = 1;
cout<< "Enter n --> ";
cin>> n;
for (int i=1; i<=n; ++i)
res*=i;
cout<< "\n" << "Result = " <<res<<endl;
_getch();
return 0;
}
Рекурсія чимось схожа на цикл, вона викликає саму себе. І будь-яку рекурсивну програму можна написати без неї (за допомогою циклів). Але є випадки (достатньо багато випадків), коли простіше і зрозуміліше написати функцію для рекурсії. Хоча факторіал цього не демонструє, але він легко дасть зрозуміти як це працює.
Для написання такої програми нам потрібно знати, що 0! = 1. Now code it
#include <iostream>
#include <conio
#include <algorithm>
#include <vector>
using namespace std;
int Factorial (int a)
{
if (!a)
return 1;
else
return Factorial(a-1)*a;
}
int main ()
{
int n;
cout<< "Enter n --> ";
cin>> n;
cout<< "Result = " << Factorial(n) <<endl;
_getch();
return 0;
}
У нас є функція з одним параметром – саме число.Якщо дане число є 0, то програма повертає 1. А як тоді працює програма якщо a = 3?
Програма повторює викликати саму себе доки a буде рівне 0, тоді вона знає значення, яке повернути і повертається до попереднього виклику. Там вона вже зможе підрахувати значення функції. Нехай якась змінна res.
Res = Factorial(0)*1
Щоб дізнатися результат нам спершу потрібно порахувати чому буде дорівнювати значення Factorial(0), повернутися до виразу і помножити на 1.
Двійковий пошук
Ми трішки зачепили цю тему на попередньому уроці, а саме її переваги. І дійсно цей алгоритм кращий за лінійний пошук, якщо нам дано відсортовані дані. Ще його вигідно використовувати, коли пошук буде виконуватися достатньо часто, в такому випадку (при умові, що масив не відсортований) продуктивніше буде його посортувати, ніж користуватися лінійним пошуком (використовується для одноразових пошуків у невеликих масивах).
Спершу я розкажу його роботу, можливо ви самі напишете алгоритм. Пошук буде починатися з середнього елементу масиву. Якщо шукане число менше за середину, то ми вже продовжуємо перевірку у лівому відрізку (де всі числа менші). Продовження пошуку відбувається за тими ж правилами. Думаю, що ви зрозуміли якими повинні бути ваші дії якщо шукане число більше за значення даного середнього елемента.
Код програми:
#include <iostream>
#include <conio
#include <algorithm>
#include <vector>
#include <time
#include <stdlib
using namespace std;
template <typename T> T Binary_search (T n[], T key, int len);
int main ()
{
srand(time(NULL));
constshort int size = 100;
int a[size], key;
cout<< "First array: " <<endl;
for (int i=0; i<size; ++i)
{
a[i] = rand() % 100;
cout<< a[i] << "\t";
}
cout<< "Enter key --> ";
cin>>key;
cout<< "Result_index is " <<Binary_search (a, key, size) <<endl;
_getch();
return 0;
}
template <typename T> T Binary_search (T n[], T key, int len)
{
int B = 0, E = len-1, mid;
while (B<=E)
{
mid = (B+E)/2;
if (key == n[mid])
return mid;
elseif (key> n[mid])
B = mid+1;
else
E = mid-1;
}
return -1;
}
У функції створено 3 змінні:
- B – вказує на початок пошуку (begin)
- E – вказує на кінець пошуку (end)
- mid– середина, визначаємо за формулою mid = (begin+end)/2 .Саме з елементом n[mid] буде здійснювати порівняння
Нагадаю, що все це індекси масиву, а не їх значення. Отже, якщо ключ (шуканий елемент) більший за значення елементу з індексом mid, то ми можемо стверджувати, що ключ 100% праворуч від елементу mid. Все це здійснюється поки B не буде більшим за E, інакше такий елемент відсутній у масиві.
Швидке сортування
Сама назва повідомляє, що цей алгоритм швидший за ті, що ми досі вивчили. Суть полягає у розділенні масиву таким чином, щоб кожен елемент лівої частини не був більший за елемент правої частини (якщо ми говоримо про зростання).
Найпростішим способом реалізації цього алгоритму є рекурсія.
Є немало варіацій алгоритму, але головною їх відмінністю – це те, який елемент обрано опорним для перевірки.
Швидке сортування:
// Швидке сортування
#include <iostream>
#include <algorithm>
#include <vector>
#include <time
#include <stdlib
using namespace std;
int Quick_sort (int b[], int B, int E);
int main ()
{
srand(time(NULL));
system("color A");
constshort 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";
}
cout<<endl;
cout<<Quick_sort(a,0, size-1);
cout<< "\n" << "After sort: " <<endl;
for (int i=0; i<size; ++i)
cout<< a[i] << "\t";
cout<<endl;
system("pause");
return 0;
}
int Quick_sort (int b[], int B, int E)
{
long i = B, j = E;
int p = b[(B+E)/2];
do{
while (b[i] < p)i++;
while (b[j] > p)j--;
if (i<=j)
{
swap(b[i], b[j]);
i++;
j--;
}
}while (i<=j);
if (B<j)return Quick_sort(b,B,j);
if (i<E) return Quick_sort(b,i,E);
}
Спершу потрібно вибрати опорний елемент (початок, середина, кінець…). Далі всі елементи менші за опорний перемістити ліворуч нього, а більші – праворуч. Тепер масив складається з двох частин, де елементи лівої менші за елементи правої частини. Далі повторюємо цю ж дію для обох цих частин, доки кількість елементів у них не буде меншою за 2.
Завдання для закріплення матеріалу
Акцент буде на рекурсію.
1. За допомогою рекурсії підрахувати добуток чисел у діапазоні введеному з клавіатури.
2. Реалізуйте бота для інтелектуальної гри J (звісно ж за допомогою рекурсії). Гра: Ханойська вежа — це математична гра, головоломка. Утворена трьома стрижнями і кількома дисками різних розмірів, які можна насунути на будь-який стрижень. Початковий стан головоломки має два порожніх стрижні і всі диски на третьому в монотонно спадному порядку з низу до гори, так утворюється побудова, що нагадує вежу.
Ціллю головоломки є перенести весь стос дисків на інший стрижень, дотримуючись таких правил:
- За раз можна рухати лише один диск.
- Кожен крок полягає в перенесенні верхнього диска з одного зі стрижнів і насування його на інший зверху інших дисків, які вже можуть бути присутніми на другому стрижні.
- Диск більшого розміру не можна класти з гори меншого диска.
З трьома дисками, головоломку можна розв'язати за сім кроків.
Схожі статті:
Новіші матеріали:
Старіші матеріали:
|
Програмування 
А сортировка то не роботает
