Створення програм з використанням рекурсій

Лабораторна робота №13

“Створення програм з використанням рекурсивних функцій на мові С++”

Мета: навчитися складати й реалізовувати алгоритми та програми з використанням рекурсивних функцій мовою С++.

Обладнання: ПК.
Програмне забезпечення: Середовище С++.

Завдання:

1. Запустити середовище програмування С++ Builder (див. початок роботи)
2. Набрати код програми і перевірити її роботу.

   

3. Задача: Відсортувати одномірний масив a[n] за спаданням елементів, використовуючи рекурсивну функцію швидкого сортування. Записати код програми в звіт.

#include <iostream.h>
#include <conio.h>
template <class T>
void QuickSortRecur(T* a, int Nend)
{
// исходный массив a[ ], a[Nend] — его последний элемент
  int і = 0, j = Nend;
  T rab, с;
  с = a[Nend >>1]; 
/* выбор центрального элемента с использованием операции побитового сдвига вправо */
  do
  { while (a[i] < с) i++;
    while (a[j] > с) j--;
    if i <= j) 
    { rab = a[i];
      a[i++] = a[j];
      a[j--] = rab; }
  }
  while (i <= j); 
/* рекурсивные вызовы функции QuickSortRecur(), если есть, что сортировать */
  if (j > 0) QuickSortRecur(a, j);
  if (Nend > i) QuickSortRecur(a+i, Nend-i);
}
void main()
{ int a[ ] = (2, 7, 6, 9, 45, 4, 3, 67, 104, 1, 99, 72, 43, 8, 4, 28, 100};
   int n = sizeof(a)/sizeof(int);
   QuickSortRecur(a, n-1);
   cout << "\n Result Quick-sortirovki massiva" << endl;
   for (int i = 0; i<n; i++)
   cout << a[i] <<' ';
   getch();
}

4. Зробити висновок по роботі.