Задание 16

В этом задании задана рекуррентная функция, проще всего написать её на удобном вам языке программирования, тогда ответ на задачу вычисляется довольно несложно.

Также может быть приведён код, о котором необхоимо сказать, как он работает. Я приведу его на трёх самых популярных языках,

Пример 1

tip

Алгоритм вычисления функции F(n) задан следующими соотношениями:

F(n) = 1 при n = 1

F(n) = n + 2 + F(n–1), если n чётно,

F(n) = 2* F(n–2), если n нечётно.

Чему равно значение функции F(24)? Для выполнения задания можно также написать программу или воспользоваться редактором электронных таблиц.

Java

public class Example1 {
    // функция
    static int F(int n) {
        if (n == 1)
            return 1;
        if (n % 2 == 0)
            return n + 2 + F(n - 1);
        return 2 * F(n - 2);
    }

    public static void main(String[] args) {
        // выводим F(24)
        System.out.println(F(24));
    }
}

C++

#include <iostream>

// функция
int F(int n) {
    if (n == 1)
        return 1;
    if (n % 2 == 0)
        return n + 2 + F(n - 1);
    return 2 * F(n - 2);
}


// главный метод программы
int main() {
    std::cout << F(24) << std::endl;
    return 0;
}

Python

def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + 2 + F(n - 1)
    return 2 * F(n - 2)


print(F(24))

Вывод программы:

2074

Ответ: 2074

Пример 2

Задача

Определите, сколько символов * выведет эта процедура при вызове F(22):

Java

void F( int n )
{
  System.out.print('*');
  if( n >= 1 ) {
    System.out.print('*');
    F(n-1);
    F(n-2);
    F(n-3);
  }
}

C++

void F( int n )
{
  cout << '*';
  if( n >= 1 ) {
    cout << '*';
    F(n-1);
    F(n-2);
    F(n-3);
    }
}

Python

def F( n ):
  print('*')
  if n >= 1:
    print('*')
    F(n-1)
    F(n-2)
    F(n-3)

Для выполнения задания можно также написать программу или воспользоваться редактором электронных таблиц.

Чтобы посчитать, сколько звёздочек будет выведено, проще всего заменить их вывод на увеличение глобальной переменнойи после вызова функции просто вывести его количество

Java

public class Example2 {
    // кол-во звёздочек
    static int cnt = 0;

    // функция
    static void F( int n )
    {
        cnt++;
        if( n >= 1 ) {
            cnt++;
            F(n-1);
            F(n-2);
            F(n-3);
        }
    }

    public static void main(String[] args) {
        // запускае F(22)
        F(22);
        // выводим кол-во звёздочек
        System.out.println(cnt);
    }
}

C++

#include <iostream>

// кол-во звёздочек
int cnt = 0;

// функция
void F(int n) {
    cnt++;
    if (n >= 1) {
        cnt++;
        F(n - 1);
        F(n - 2);
        F(n - 3);
    }
}

// главный метод программы
int main() {
    std::cout << cnt << std::endl;
    return 0;
}

Python

# кол-во звёздочек
cnt = 0


def F(n):
    global cnt
    cnt = cnt + 1
    if n >= 1:
        cnt = cnt + 1
        F(n - 1)
        F(n - 2)
        F(n - 3)


F(22)
print(cnt)

Вывод программы:

1957585

Ответ: 1957585

Задания для самостоятельного выполнения