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

Головне меню

Наша кнопка

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

Друзі

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


Головна Програмування - C++ Базовий курс програмування на С++. Урок 13. Рекурсія, двійковий пошук. Швидке сортування

Базовий курс програмування на С++. Урок 13. Рекурсія, двійковий пошук. Швидке сортування
Написав Joker   
Неділя, 01 листопада 2015 23:46
Переглядів: 2045

Вимірювати продуктивність програмування

підрахунком рядків коду – це так само, як

оцінювати будівництво літака по його вазі

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 (звісно ж за допомогою рекурсії). Гра:  Ханойська вежа  — це математична гра, головоломка. Утворена трьома стрижнями і кількома дисками різних розмірів, які можна насунути на будь-який стрижень. Початковий стан головоломки має два порожніх стрижні і всі диски на третьому в монотонно спадному порядку з низу до гори, так утворюється побудова, що нагадує вежу.


Ціллю головоломки є перенести весь стос дисків на інший стрижень, дотримуючись таких правил:

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

З трьома дисками, головоломку можна розв'язати за сім кроків.



( 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."

 

Ввійти



Підписка

Хто онлайн?

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

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