Рекурсія. Розробка рекурсивного та ітераційного алгоритмів розв’язання індивідуального завдання

ЛАБОРАТОРНА РОБОТА №6

6.1. Тема: Рекурсія.

6.2. Мета роботи: Здобути навички та практичний досвід у розробці рекурсивних програм.

6.3. Теми для попередньої роботи

6.3.1. Статичні та динамічні структури даних

6.3.2  Пошук

6.3.3. Сортування

6.3.4.  Ітераційні алгоритми

6.4. Індивідуальні завдання

            Розробити рекурсивний та ітераційний алгоритми розв’язання індивідуального завдання. Порівняти час виконання відповідних програм, зробити висновки.

1. Функція Аккермана A визначається для всіх додатних (>0) цілих аргументів m та n так:

A(0,n)=n+1;

A(m,0)=A(m-1,1)                               (m>0)

A(m,n)=A(m-1,A(m,n-1))                  (m>0, n>0)

            Обчислити значення функції A(m,n) для m і n, що вводити з клавіатури.

2. Дано масив цілих чисел. Відсортувати масив за спадом згідно з алгоритмом сортування Шелла.
3. Знайти всі n! перестановок для  n елементів a₁…a_n, та видати їх на екран. Число n та самі числа, що переставляються,  ввести з клавіатури.

4. Дано текст (ланцюжок символів). Перевірити чи є паліндромом ланцюжок символів, що починається з індекса s і закінчується індексом e.

5. Коефіцієнти, що утворюють трикутник Паскаля, визначаються так:

                  C(n,0)=1

                  C(n,n)=1                                             (n>0)

                  C(n,k)=C(n-1,k-1) + C(n-1,k)            (n>0, m>0)

      Розробити програму, що для заданого n будує трикутник Паскаля.

6. Алгоритм перетворення числа N з однієї системи обчислення в іншу (B) полягає в багаторазовому діленні N на B. Як що  N = d_n-1 d_n-2 d_n-3 … d₁ d₀, то послідовність остач від ділення в порядку d₀ ... d_n-1 дає цифри результату перетворення.

      Розробити функцію, що перетворює число N в систему обчислення B, припустити умову B<=10.

7. Створити односпрямований список. Розробити алгоритм послідовного пошуку по числовому ключу. Ключ ввести з клавіатури.

8. Розробити програму для визначення розміру платежів по ссуді у $150000 під 10% річних на 25 років.

9. Обчислити корінь рівняння  f(x)=x³ –2x² –3x +10 із заданою точністю в інтервалі a<=x<=b методом дихотомії. Метод дихотомії визначається так: як що f(a) та f(b) мають різні знаки, то між a та b корінь є. Обчислюється середня точка m=(a+b)/2. Як що f(m)=0, то корінь знайдено. В противному випадку перевіряються  інтервали a<=x<=m та m<=x<=b і подальші дії виконуються в тому інтервалі де знак функції змінюється. Процес продовжується поки інтервал не стане достатньо малим або не буде знайдено точне значення корня.

10. Дано масив цілих чисел. Відсортувати вміст масиву за зростанням бульбашковим методом із запам’ятовуванням місця останньої перестановки. 

11. Створити односпрямований список цілих чисел (числа читати з файла); видати вміст списку на екран;  знайти найбільше число.

12. Створити дві множини A та B однакового розміру n цілих, додатних чисел, що не перетинаються (масиви з різними числами) . Знайти всі пари <a, b> з n вихідних пар, таких, що a належить до A і є парним, більшим ніж 10, b належить B і є непарним, кратним 5.
13. Розробити програму, що визначає кількість n- розрядних двійкових чисел, які не мають у собі підряд двох  одиниць. (Підказка: Число починається з нуля або одиниці. Якщо – з нуля, то кількість варіантів визначається (n-1) цифрами, що лишилися. А як що з одиниці, то якою повинна бути наступна цифра?).
14. Створити динамічну чергу запитів на обслуговування, в яку запити ставити підряд, як будуть приходити.  Розробити функцію пріоритетного за min читання запитів з черги (для запитів з однаковим пріоритетом обрати процедуру обслуговування FIFO).
15. Дано текст (ланцюжок символів). Змінити послідовність ланцюжка символів, що починається з індекса s і закінчується індексом e, на зворотню послідовність.
16. Ввести масив з  n додатних (>0) цілих чисел. Визначити, чи можна з цих чисел вибрати такі, що їх сума дорівнює числу s. Як що варіант існує, результат видати на екран. Всі числа вводити з клавіатури. Наприклад, вхідні дані: 7, 5, 4, 4, 1;   s=10;

10 = 5+4+1.

17.  Ввести три масиви таких, що їх елементи впорядковані по зростанню. Розробити програму злиття трьох масивів в один масив впорядкований по зростанню.

18. Дано масив записів. Розробити алгоритм двійкового пошуку по текстовому ключу. Ключ ввести з клавіатури.

6.5 Типове завдання.

Обчислити значення функції f=xⁿ.

#include<iostream.h>

#include<stdlib.h>

int power( int x, int n);

// Предусловие: n>=0.

//  Повертає х у ступені n.

Int main()

{       

      for ( int n = 0; n< 4;  n++)

          cout << “ 3 у ступені ” << n

                  << “ дорівнює ” <<power(3, n) << endl;

      return 0;

}

// Використовує iostream.h і stdlib.h:

int power( int x, int n)

{

       if ( n <0)

           {

              cout <<” Неприпустимий аргумент функції power.\n”;  

         exit(1);

      }

  if (n >0 )

      return (power(x, n –1 )*x );

else // n == 0

       return (1);

}

6.6. Результати роботи програми(приклад):

        3 у ступені 0 дорівнює 1

        3 у ступені 1 дорівнює 3

        3 у ступені 2 дорівнює 9

        3 у ступені 3 дорівнює 27