Задание №11.
Умение исполнить рекурсивный алгоритм. Уровень сложности задания - базовый, максимальный балл за выполнение - 1, примерное время выполнения задания - 5 минут.
Знать: индуктивное определение объектов.
Уметь: строить информационные модели объектов, систем и процессов  в виде алгоритмов.

Задание относится к базовому уровню сложности и обычно не вызывает у учащихся особых хлопот, но бывают задания более сложные и, из-за невнимательности, можно потерять драгоценные баллы.

Особых методик решения таких заданий я не встречал. Все просто, как дважды два. Выполняем алгоритм шаг за шагом и приходим к результату.

Пример задания. Дан рекурсивный алгоритм F. Приведите последовательность чисел (без пробелов и разделите­лей), которые будут напечатаны на экране при выполнении вызова F(4).

procedure F(n: integer);
begin
  write (n);
  if n > 1 then
  begin
     F(n - 1) ;
     F(n - 2)
  end
end;

Разбор задания. Конечно, это не самое сложное из того, что может быть на экзамене, но чтобы понять, как решаются задания такого типа, этого вполне достаточно. Выполнять алгоритм будем построчно и записывать ход решения тоже будем построчно (можно записывать ход решения в виде дерева, но я делаю так).

1. Начинаем с функции, которая стоит у нас в условии - F(4) и прогоняем весь наш алгоритм от первой до последней строчки.


F(4) выводит на экран 4, затем проверяется условие  n > 1, так как оно истинно вызывается F(3), вызывается F(2). Мы не знаем, что выведет на экран F(3) и F(2), следовательно их тоже прогоним через алгоритм.

F(3) выводит на экран 3, затем проверяется условие  n > 1, так как оно истинно вызывается F(2), вызывается F(1).
F(2) выводит на экран 2, затем проверяется условие  n > 1, так как оно истинно вызывается F(1), вызывается F(0). Мы ещё не знаем, что выводят F(1) и F(0), так что продолжаем.

F(1) выводит на экран 1, затем проверяется условие  n > 1, но 1 не больше 1 и это условие ложно, на этом шаге процедура заканчивает свою работу.
F(0) выводит на экран 0, затем проверяется условие  n > 1, но 0 не больше 1 и это условие ложно, на этом шаге процедура заканчивает свою работу.

Теперь мы все делаем в обратном порядке, записывая полученные результаты, пока не дойдем до процедуры F(4).

F(0) выводит на экран 0
F(1) выводит на экран 1
F(2) выводит на экран 210
F(3) выводит на экран 32101
F(4) выводит на экран 432101210

Ответ: 432101210.

 

Пример задания. (задания взяты с сайта К.Ю. Полякова http://kpolyakov.spb.ru)

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

F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно.

Чему равно значение функции F(26)?

Решение. Такого типа задания довольно легко решаются вручную на бумаге, но это сделать довольно просто, если мы ищем значение функции F от небольшого значения переменной n. А если нас попросят найти значение функции F(100), что тогда? На бумаге и вручную будет затрачено довольно много времени. Выход есть, даже два! Можно решить задание с помощью процессора электронных таблиц, например Microsoft Excel, а ещё можно написать программу и программа эта не так уж и сложна. Мы разберём второй вариант.

Сначала опишем функцию:
function F(n:integer):integer;

begin
  if
n = 1 then
   
F := 1
  else if n mod 2 = 0 then
   
F:= n + F(n-1)
  else
   
F:= 2 * F(n-2);
end;

Теперь нам просто надо вызвать функцию F(n) с нужным нам параметром.

begin 
   writeln(F(26));
end.

Полный текст программы:

function F(n:integer):integer;

begin
  if
n = 1 then
   
F := 1
  else if n mod 2 = 0 then
   
F:= n + F(n-1)
  else
   
F:= 2 * F(n-2);
end;

begin 
   writeln(F(26));
end.

Ответ: 4122.

 

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

F(1) = G(1) = 1
F(n) = 3·F(n–1) + G(n–1) – n + 5, если n > 1
G(n) = F(n–1) + 3·G(n–1) – 3·n, если n > 1

Чему равно значение F(14) + G(14)?

 

Решение. Особых отличий в написании программы для этого примера нет. Просто тут у нас две функции – F(n) и G(n).

Сначала опишем функцию F(n):

function F(n:integer):integer;
begin
  if
n = 1 then
   
F := 1
  else if n > 1 then
   
F:= 3*F(n-1) + G(n-1) - n + 5;
end;

 

Теперь опишем функцию G(n):

function G(n:integer):integer;
begin
  if
n = 1 then
   
G := 1
  else if n > 1 then
   
G:= F(n-1) + 3*G(n-1) - 3 * n;
end;

 

Напишем саму программу

begin
   writeln(F(14) + G(14));
end.

Запускаем и видим, что программа не «пошла». А вся причина в том, что функции «друг друга не видят». Для исправления данной ошибки в самом начале программы добавим несколько строк кода:

function F(n:integer):integer;
forward;
function G(n:integer):integer;
forward;

forward это процедурная директива (предописание), другие процедуры и функции могут вызывать предописанную подпрограмму, делая возможной взаимную рекурсию.

Полный текст программы:

function F(n:integer):integer;
forward;
function G(n:integer):integer;
forward;

function F(n:integer):integer;
begin
  if
n = 1 then
   
F := 1
  else if n > 1 then
   
F:= 3*F(n-1) + G(n-1) - n + 5;
end;

function G(n:integer):integer;
begin
  if
n = 1 then
   
G := 1
  else if n > 1 then
   
G:= F(n-1) + 3*G(n-1) - 3 * n;
  end;

begin
  writeln(F(14) + G(14));
end.

Ответ: 37282721.

Добавить комментарий


Защитный код
Обновить

© 2019 Информатика и ИКТ. Все права защищены

^ Наверх