Приклади розвʼязку задач на рекурсію в C++

Приклади розвʼязку задач на рекурсію в C++


Зміст



1. Знаходження площі трикутника

Задача. Задано трикутник розміром m×n, де m, n – цілі числа і m>0, n>0. Розробити рекурсивну функцію, яка обчислює площу трикутника на основі залежності:

Розв’язок. Якщо відома залежність, то реалізація функції не представляє особливих проблем. Припинення рекурсивного процесу буде здійснюватись при виконанні умови n=m=1.

Програмний код функції S() наступний:

int S(int n, int m)
{
    if ((n==1)&&(m==1)) return 1;
    else
        if (n>1)
            return S(n-1, m)+m;
        else
            return S(n, m-1)+1;
}

2. Обчислити значення квадрата числа на основі залежності

Задача. Обчислити значення квадрата цілого додатного числа n, якщо відома залежність

n2 = (n-1)2 + 2·(n-1) + 1

З цієї залежності виникає формула рекурсії:

Розв’язок.

// обчислення квадрату числа
int f(int n)
{
    if (n==1)
        return 1;
    else
        return f(n-1)+2*n-1;
}

Використання функції в іншому програмному коді

int k;
k = f(9); // k = 81

3. Комбінаторна задача

Задача. Обчислити кількість комбінацій з n різних елементів по m. Кількість комбінацій визначається формулою

Розвʼязок.

// кількість комбінацій з n по m
int C(int n, int m)
{
    if ((m==0)&&(n>0) || (m==n)&&(n>0))
        return 1;
    else
        if ((m>n)&&(n>=0))
            return 0;
        else
            return C(n-1,m-1) + C(n-1,m);
}

Використання функції C() в іншому програмному коді

int k;
k = C(6,4); // k = 15
k = C(4,3); // k = 4

4. Синтаксичний аналізатор для поняття “ідентифікатор”

Задача. Розробити рекурсивну функцію, яка реалізує синтаксичний аналізатор для поняття ідентифікатор. Як відомо, у мові програмування C++ ідентифікатор підпорядковується таким правилам:

  • першим символом ідентифікатора обовʼязково є літера латинського алфавіту;
  • другий, третій і т.д. символ ідентифікатора може бути літерою або цифрою.

Загальна формула ідентифікатора наступна:

де

  • identifier – деякий ідентифікатор;
  • letter – деяка літера латинського алфавіту (від ‘a’ до ‘z’ або від ‘A’ до ‘Z’);
  • digit – цифра від ‘0’ до ‘9’.

Розв’язок. У даному випадку реалізується рекурсивна функція з іменем IsIdentifier(). Оскільки, функція аналізує поняття “іденитфікатор”, то результатом повернення з функції є значення типу bool. Якщо функція повертає true, то ім’я ідентифікатора згідно з умовою задачі вірне. Якщо функція повертає false, то в імені ідентифікатора є помилка.

Вхідним параметром рекурсивної функції IsIdentifier() є рядок типу string. Цей рядок містить назву ідентифікатора. Перегляд ідентифікатора здійснюється з кінця до початку. Умовою закінчення рекурсивного процесу є досягнення першого символу ідентифікатора.

Текст методу IsIdentifier() наступний

// метод, що визначає, чи коректне ім'я ідентифікатора
bool IsIdentifier(string s, unsigned int pos)
{
  if (pos==0) // якщо перший символ
  {
    char c;
    c = s[pos];

    // перевірка, чи перший символ літера
    if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z'))
      return IsIdentifier(s,pos+1); // перехід до перевірки наступного символу
    else
      return false;
  }
  else
    if (pos<s.length()) // якщо не останній символ
    {
      char c = s[pos];
      // перевірка, чи символ є літерою або цифрою
      if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z') || (c>='0')&&(c<='9'))
        return IsIdentifier(s,pos+1);
      else
        return false;
    }
    else
      return true;
}

Використання функції IsIdentifier() в іншому програмному коді

bool b;
b = IsIdentifier("Aa13209", 0); // b = true
b = IsIdentifier("5A", 0); // b = false

5. Значення функції Аккермана

Задача. Обчислити значення функції Аккермана для двох невідʼємних цілих чисел n та m, де:

Розв’язок. Якщо відомі залежності, то реалізація функції не є важкою. Згідно з умовою задачі функція отримує два параметри. Це є невід’ємні цілі числа n та m. Повертає функція також ціле невід’ємне число.

При великих значеннях n та m може виникнути переповнення стеку, тому що функція Аккермана є двічі рекурсивною: один з аргументів функції є таж рекурсивна функція.

Реалізація функції наступна:

// функція Аккермана
unsigned int A(unsigned int n, unsigned int m)
{
    if (n==0)
        return m+1;
    else
        if ((n!=0) && (m==0))
            return A(n-1,1);
        else
            return A(n-1,A(n,m-1));
}

Використання функції для малих n та m:

unsigned int res;

res = A(1,2); // res = 4
res = A(0,1); // res = 2
res = A(0,0); // res = 1
res = A(2,2); // res = 7

6. Синтаксичний аналізатор для поняття “простий вираз”

Задача. Скласти програму, що реалізує синтаксичний аналізатор для поняття “expression”

де

  • Expression – деякий простий вираз;
  • simple_identifier – деякий простий ідентифікатор;
  • letter – буква латинського алфавіту від ‘a’ до ‘z’ або від ‘A’ до ‘Z’;
  • operation – знак операції ‘+’, ‘–’ або ‘*’.

Розв’язок. Для розв’язку даної задачі потрібно реалізувати три функції:

  • функцію IsIdentifier(), яка визначає чи простий ідентифікатор є літерою;
  • функцію IsOperation(), яка визначає чи є операція синтаксично вірною згідно з умовою задачі;
  • рекурсивну функцію IsExpression(), яка визначає чи є простий вираз синтаксично правильним згідно з умовою задачі.

Рекурсивна функція IsExpression() отримує 3 параметри:

  • рядок s, який обробляється;
  • позиція pos поточного символу в рядку s;
  • прапорець IsOp, який визначає чи попередній символ був знаком операції.

Реалізація функцій IsIdentifier(), IsOperation() та IsExpression() наступна:

// простий ідентифікатор
bool IsIdentifier(char c)
{
  // перевірка, чи ідентифікатор літера
  if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z'))
    return true;
  else
    return false;
}

// знак операції
bool IsOperation(char c)
{
  if ((c=='-') || (c=='+') || (c=='*'))
    return true;
  else
    return false;
}

// Рекурсивна функція-аналізатор виразу,
bool IsExpression(string s, unsigned int pos, bool IsOp)
{
  char c;
  c = s[pos];
  if (pos==0) // перший символ
  {
    if (IsIdentifier(c)) // перевірка чи перший символ літера
      return IsExpression(s, pos+1, false);
    else
      return false;
  }
  else
    if (pos<s.length()-1) // не перший символ (другий, третій і т.д.) і не останній
    {
      if (IsIdentifier(c)) // якщо ідентифікатор, то перейти далі на наступний символ
        return IsExpression(s,pos+1,false);
      else
      {
        if (IsOperation(c) && !IsOp) // після операції слідує простий вираз
          return IsExpression(s,pos+1,true); // вказати на наступному рівні, що була операція
        else
          return false;
      }
    }
    else // інакше, обробити останній символ
    {
      if (IsOperation(c)) // якщо останній символ операція, то вираз помилковий
        return false;
      else
        return IsIdentifier(c); // перевірити чи останній символ ідентифікатор
    }
}

Демонстрація використання функції IsExpression() в іншому методі:

bool b;
b = IsExpression("a+b",0,false); // b = true
b = IsExpression("+a+b",0,false); // b = false
b = IsExpression("Adsdl-Bdslf-FDF",0,false); // b = true
b = IsExpression("a+-b-c",0,false); // b = false
b = IsExpression("a+b;",0,false); // b = false
b = IsExpression("alsd+bsldk-",0,false); // b = false
b = IsExpression("AbcDEf",0,false); // b = true

За подібним зразком можна створити декілька рекурсивних функцій, які будуть аналізувати складні вирази або їх фрагменти. Важливо для кожної функції визначити правильні залежності (алгоритм).

7. Синтаксичний аналізатор для поняття “сума”

Задача. Скласти програму, яка реалізує синтаксичний аналізатор для поняття “сума”

де

  • Sum – функція, що аналізує загальну суму;
  • Integer – функція, що аналізує ціле число;
  • Digit – функція, що аналізує цифру;
  • Operation – функція, що реалізує знак операції. Знаком операції може бути ‘+’ або ‘–’.

Вираз, взятий у фігурні дужки { } може повторюватись.

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

Для розв’язку даної задачі розроблено 4 функції:

  • функцію IsSignOp(), яка визначає чи символ c є знаком операції. Символ c передається у функцію як вхідний параметер. Функція повертає логічне значення true або false;
  • функцію IsDigit(), яка визначає, чи вхідний символ c є цілим числом. Символ c є параметром функції;
  • рекурсивну функцію IsInteger(), яка аналізує увесь вираз. Функція отримує 3 параметри. Перший параметр є рядком, який аналізується. Другий параметр pos є позицією поточного символу в рядку s, який аналізується. Третій, допоміжний параметр IsOp вказує, чи був попередній символ знаком операції. Третій параметр IsOp необхідний, щоб уникнути повторення двох знаків операцій, наприклад, “++”;
  • функцію IsSum(), яка викликає рекурсивну функцію IsInteger(). Функція IsSum() здійснює просте перенаправлення на виконання функції IsInteger().

Реалізація функцій наступна:

// синтаксичний аналізатор для поняття "сума"
// знак операції
bool IsSignOp(char c)
{
  if ((c=='+') || (c=='-'))
    return true;
  else
    return false;
}

// цифра
bool IsDigit(char c)
{
  if ((c>='0') && (c<='9'))
    return true;
  else
    return false;
}

// рекурсивна функція IsInteger(), реалізує перевірку всього виразу,
// pos - поточна позиція символу з рядка s, який перевіряється
// IsOp=true, якщо попередній символ на верхньому рівні був знак операції
bool IsInteger(string s, int pos, bool IsOp)
{
  char c;
  c = s[pos]; // взяти символ для обробки

  if (pos==0) // початок виразу
  {
    // першим має йти ціле число
    if (IsDigit(c))
      return IsInteger(s, pos+1, false);
    else
      return false;
  }
  else
    if (pos<s.length()-1) // середина виразу
    {
      if (IsDigit(c)) // якщо число, то перейти далі
        return IsInteger(s, pos+1, false);
      else
      {
        // якщо не число
        if (IsSignOp(c)) // чи знак операції?
        {
          // якщо знак операції, то подивитися попередній символ у змінній IsOp
          if (!IsOp)
            return IsInteger(s,pos+1,true); // якщо попередній символ не знак операції, то продовжити далі
          else
            return false; // якщо попередній символ знак операції, то є помилка: два знаки операції не можуть йти піряд
        }
        else
          return false; // якщо не число і не знак операції, то у виразі помилка - присутній недопустимий символ
      }
    }
    else // кінець виразу
      return IsDigit(c); // останній символ виразу обов'язково має бути число (цифра)
}

// функція IsSum(), яка викликає рекурсивну функцію IsInteger()
bool IsSum(string s)
{
  // викликати рекурсивну функцію IsInteger()
  return IsInteger(s,0,false);
}

Використання функції IsSum() в іншому методі

bool b;
b = IsSum("253+23"); // b = true
b = IsSum("2345w-18"); // b = false
b = IsSum("750-450+200"); // b = true
b = IsSum("-200"); // b = false
b = IsSum("2019"); // b = true
b = IsSum("210+-5"); // b = false
b = IsSum("300-"); // b = false

8. Перевід з однієї системи числення в іншу

Задача. Написати рекурсивну функцію переводу з десяткової системи числення у двійкову.

Розв’язок. Алгоритм переводу класичний. Потрібно вхідний параметр num ділити на 2 до тих пір, поки num>2. При кожному поділі потрібно виділяти остачу з допомогою виразу num%2. Операція % призначена для виділення остачі від ділення двох чисел.

Функція Convert10to2() отримує два аргументи:

  • аргумент беззнакового цілого типу, якому відповідає параметр з іменем num. Це є задане число в десятковій системі числення.
  • тимчасовий аргумент, що служить для запам’ятовування поточного результату у двійковій системі числення. Це є рядок res типу string.

Результатом функції є обернений до рядка res рядок типу string. Оскільки, при поділі, результуюче значення формується у зворотньому порядку.

Функція має наступну реалізацію:

// перевід натурального числа з 10-ї системи в двійкову
string Convert10to2(unsigned int num, string res)
{
  if (num<2)
  {
    if (num==0)
      res.append("0");
    else
      res.append("1");

    // реверсування рядка res і повернення результату
    string res2="";
    for (int i=res.length()-1; i>=0; i--)
      res2.push_back(res[i]);
    return res2;
  }
  else
  {
    if (num%2 == 0)
      res.append("0");
    else
      res.append("1");
    return Convert10to2((unsigned int)num/2, res); // перейти на наступний крок
  }
}

Використання функції в іншому програмному коді

string result;
string s="";
result = Convert10to2(255,s); // res = 11111111
result = Convert10to2(83,s); // res = 1010011
result = Convert10to2(23,s); // res = 10111
result = Convert10to2(0,s); // res = 0

9. Задачі для повторення

Задача 1. Розробити рекурсивну функцію Min() пошуку мінімального значення в масиві A, який містить n чисел типу double (n>0).

Розв’язок на мові C++ можна переглянути тут.

Задача 2. Розробити рекурсивну функцію ConvertAny() переводу числа з системи числення з основою m у систему числення з основою n. Функція повинна отримувати наступні параметри:

  • число num, яке потрібно перевести з системи числення m в систему числення n: num(m) ⇒ num(n);
  • цілочисельне беззнакове число m, що задає номінал системи числення з основою m. Причому 2<m≤9;
  • цілочисельне беззнакове число n, що задає номінал системи числення з основою n. Причому 2<n≤9.

Функція повинна повертати рядок типу string, який є результатом.

Розв’язок на мові C++ можна переглянути тут.

Задача 3. Розробити рекурсивну функцію, яка визначає, чи являється задане натуральне число N простим. Просте число, це число N>1 яке не має інших дільників крім 1 та самого себе.

Розв’язок на мові C++ можна переглянути тут.


Зв’язані теми