Приклади розвʼязку задач на рекурсію на мові програмування Java

Приклади розвʼязку задач на рекурсію на мові програмування Java


Зміст


1. Обчислення площі трикутника

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

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

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

static 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

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

Розв’язок.

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


 

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

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

Розв’язок.

// кількість комбінацій з n по m
static 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);
}

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

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

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

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

де

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

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

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

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

// визначення, чи рядок s є ідентифікатором
static boolean IsIdentifier(String s, int pos) {
    char c;
    if (pos==0) {
        c = s.charAt(pos); // взяти символ в позиції pos
        if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z'))
            return IsIdentifier(s,pos+1);
        else
            return false;
    }
    else
        if (pos<s.length()) {
            c = s.charAt(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;
}

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

boolean b;
String s = "Alkjlkjlkj445l25k3j1";
b = IsIdentifier(s,0); // b = true

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

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

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

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

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

static int A(int n, 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));
}

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

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
res = A(3,2); // res = 29
res = A(3,3); // res = 61

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

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

де

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

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

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

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

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

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

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

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

// Рекурсивна функція-аналізатор виразу
static boolean IsExpression(String s, int pos, boolean IsOp) {
  char c;
  c = s.charAt(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() в іншому методі:

boolean res;
res = IsExpression("a+b",0,false); // res = true
res = IsExpression("+a+b",0,false); // res = false
res = IsExpression("ABCsdl-Sdl+Dfjls",0,false); // res = true
res = IsExpression("a+-b-c",0,false); // res = false
res = IsExpression("a+b;",0,false); // res = false
res = IsExpression("alsd+bsldk-",0,false); // res = false
res = IsExpression("AbcDEf",0,false); // res = 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().

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

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

// ціле число
static boolean IsDigit(char c) {
  if ((c>='0') && (c<='9'))
    return true;
  else
    return false;
}

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

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

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

boolean 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
b = IsSum("4564+2+"); // b = false

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

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

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

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

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

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

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

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

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

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

String res;
res = Convert10to2(19,""); // res = 10011
res = Convert10to2(119,""); // res = 1110111
res = Convert10to2(250,""); // res = 11111010

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

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

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

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

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

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

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

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

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


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