Рекурсивный алгоритм паскаль егэ

Ниже записаны две рекурсивные процедуры, F и G:

procedure F(n: integer); forward;

procedure G(n: integer); forward;

procedure F(n: integer);

procedure G(n: integer);

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F (11)?

Паскаль, встретив команду F(11), вызывает процедуру F и передает ей параметр n = 11:

в случае выполнения условия n > 0 выполняется следующая строка: G(n — 1), вызывающая процедуру G после уменьшения n на 1

процедура G печатает звездочку и, в случае выполнения условия n > 1, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(7)

в случае выполнения условия n > 0 выполняется следующая строка: G(n — 1), вызывающая процедуру G после уменьшения n на 1

процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(3)

в случае выполнения условия n > 0 выполняется следующая строка: G(n — 1), вызывающая процедуру G после уменьшения n на 1

процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(-1)

получив значение -1 и убедившись, что условие не выполнилось, Паскаль завершает выполнение программы.

А нам остается подсчитать, сколько раз печаталась звездочка. В нашем случае это произошло ровно 3 раз(а)

Итого, правильный ответ: 3

Внимание! Для прокрутки условия на анимации необходимо по нему произвести щелчок левой кнопкой мыши и нажать кнопку "ВНИЗ" или "ВВЕРХ"

Интерактивный тренажер 11 ЕГЭ ДЕМО 2015
на "Рекурсивные алгоритмы"

Если уловие задания видно не полностью, щелкните по нему курсором мыши и нажмите клавишу «вниз» или «вверх»

Примеры заданий и их решений, генерируемых интерактивным тренажером по задачам11 ЕГЭ 2015
Рекурсивные алгоритмы.

Задание №1. Дан рекурсивный алгоритм:

procedure F(n: integer);
begin
writeln(n);
if n = 5 процедура выводит число n и заканчивает работу без рекурсивных вызовов:
S(n) = n при n >= 5
при n = 5
S(n) = n + S(n+1) + S(n+3)

Прокручиваем цикл сшагом -1 начиная от значения меньшего 5

S(4) = 4 + S(5) + S(7) = 4 + 5 + 7 = 16
S(3) = 3 + S(4)+S(6) = 3 + 16 + 6 = 25
S(2) = 2 + S(3) +S(5) = 2 + 25 + 5 = 32
S(1) = 1 + S(2) + S(4) = 1 + 32 + 16 = 49
таким образом правильный ответ = 49

Воспользуемся данным методом и попробуем решить следующую задачу, не тратя время на комментарии

Задача 2

Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n =6

Записываем прокрутку в общем виде

S(5) = 5 + S(7) + S(15)
S(4) = 4 + S(6) + S(12)
S(3) = 3 + S(5) + S(9)
S(2) = 2 + S(4) + S(6)
S(1) = 1 + S(3) + S(3)

из последнего уравнения видим, что нам нужны третье и пятое уравнение, поэтому окончательно получаем:

S(5) = 5 + S(7) + S(15) = 5+7+15 = 27
S(3) = 3 + S(5) + S(9) = 3 + 27 + 9 = 39
S(1) = 1 + S(3) + S(3) = 1 + 39 + 39 = 79

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

РЕШЕНИЕ:

F(0) = 1, F(1) = 1
1) используя заданную рекуррентную формулу, находим, что F(2) = F(2 — 1) * F(2 — 2) = 1
2) используя заданную рекуррентную формулу, находим, что F(3) = F(3 — 1) * F(3 — 2) = 1
3) используя заданную рекуррентную формулу, находим, что F(4) = F(4 — 1) * F(4 — 2) = 1
4) используя заданную рекуррентную формулу, находим, что F(5) = F(5 — 1) * F(5 — 2) = 1
5) используя заданную рекуррентную формулу, находим, что F(6) = F(6 — 1) * F(6 — 2) = 1
6) используя заданную рекуррентную формулу, находим, что F(7) = F(7 — 1) * F(7 — 2) = 1
7) используя заданную рекуррентную формулу, находим, что F(8) = F(8 — 1) * F(8 — 2) = 1
8) используя заданную рекуррентную формулу, находим, что F(9) = F(9 — 1) * F(9 — 2) = 1
9) используя заданную рекуррентную формулу, находим, что F(10) = F(10 — 1) * F(10 — 2) = 1
10) используя заданную рекуррентную формулу, находим, что F(11) = F(11 — 1) * F(11 — 2) = 1
11) используя заданную рекуррентную формулу, находим, что F(12) = F(12 — 1) * F(12 — 2) = 1
12) используя заданную рекуррентную формулу, находим, что F(13) = F(13 — 1) * F(13 — 2) = 1
13) используя заданную рекуррентную формулу, находим, что F(14) = F(14 — 1) * F(14 — 2) = 1

Читайте также  При наборе номера идут короткие гудки

Ответ: 1

Задание №4. Дан рекурсивный алгоритм:

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

РЕШЕНИЕ:

1) используя заданную рекуррентную формулу, находим, что F(2) = F(2 — 1) * F(2 — 2) + 5 = 6
2) используя заданную рекуррентную формулу, находим, что F(3) = F(3 — 1) * F(3 — 2) + 5 = 11
3) используя заданную рекуррентную формулу, находим, что F(4) = F(4 — 1) * F(4 — 2) + 5 = 71
4) используя заданную рекуррентную формулу, находим, что F(5) = F(5 — 1) * F(5 — 2) + 5 = 786

Ответ: 786

Задание №6. Дан рекурсивный алгоритм:

procedure F(n: integer);begin writeln(n);
if n = 6 процедура выводит число n и заканчивает работу без рекурсивных вызовов:
S(n) = n при n >= 6
при n 0 then begin
writeln(‘*’);
F(n-5);
F(n div 2);
F(n div 2);
end
end;

Сколько символов звездочка будет напечатано на экране при выполнении вызова F(8)?

РЕШЕНИЕ:

S(0) = 1
S(1) = 2 + S(1-2) + 2*S(1 div 2) = 2 + 1 + 2 = 5
S(2) = 2 + S(2-2) + 2*S(2 div 2) = 2 + 1 + 10 = 13
S(3) = 2 + S(3-2) + 2*S(3 div 2) = 2 + 1 + 10 = 13
S(4) = 2 + S(4-2) + 2*S(4 div 2) = 2 + 1 + 26 = 29
S(5) = 2 + S(5-2) + 2*S(5 div 2) = 2 + 1 + 26 = 29
S(6) = 2 + S(6-2) + 2*S(6 div 2) = 2 + 5 + 26 = 33
S(7) = 2 + S(7-2) + 2*S(7 div 2) = 2 + 13 + 26 = 41
S(8) = 2 + S(8-2) + 2*S(8 div 2) = 2 + 13 + 58 = 73

Таким образом правильный ответ = 73

Задание №8. Дан рекурсивный алгоритм:

procedure F(n: integer);
begin writeln(‘*’);
if n > 0 then begin
writeln(‘*’);
F(n-8);
F(n div 2);
end
end;

Сколько символов звездочка будет напечатано на экране при выполнении вызова F(6)?

РЕШЕНИЕ:

S(0) = 1
S(1) = 2 + S(1-2)+S(1 div 2) = 2 + 1 + 1 = 4
S(2) = 2 + S(2-2)+S(2 div 2) = 2 + 1 + 4 = 7
S(3) = 2 + S(3-2)+S(3 div 2) = 2 + 1 + 4 = 7
S(4) = 2 + S(4-2)+S(4 div 2) = 2 + 1 + 7 = 10
S(5) = 2 + S(5-2)+S(5 div 2) = 2 + 1 + 7 = 10
S(6) = 2 + S(6-2)+S(6 div 2) = 2 + 1 + 7 = 10

Таким образом правильный ответ = 10

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

F(0) = 1,
F(1) = 1
F(n) = F(n–1) * F(n — 2) + 5, при n > 1

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

РЕШЕНИЕ:

F(0) = 1,
F(1) = 1
F(2) = F(2 — 1) * F(2 — 2) + 5 = 6
F(3) = F(3 — 1) * F(3 — 2) + 5 = 11
F(4) = F(4 — 1) * F(4 — 2) + 5 = 71
F(5) = F(5 — 1) * F(5 — 2) + 5 = 786
F(6) = F(6 — 1) * F(6 — 2) + 5 = 55811
F(7) = F(7 — 1) * F(7 — 2) + 5 = 43867451

Ответ: 43867451

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

procedure F(n: integer);
F(1) = 1;
G(1) = 1;
F(n) = 8*F(n–1) – 8*G(n–1);
G(n) = F(n–1) + 3*G(n–1), при n >=2

Чему равно значение величины F(5) — G(5)? В ответе запишите только целое число.

РЕШЕНИЕ:

F(1) = 1 : G(1) = 1
F(2) = 8*F(1) — 8*G(1) = 0 : G(2) = F(1) + 3*G(1) = 4
F(3) = 8*F(2) — 8*G(2) = -32 : G(3) = F(2) + 3*G(2) = 12
F(4) = 8*F(3) — 8*G(3) = -352 : G(4) = F(3) + 3*G(3) = 4
F(5) = 8*F(4) — 8*G(4) = -2848 : G(5) = F(4) + 3*G(4) = -340
F[5] — G[5] = -2508

Таким образом правильный ответ = -2508

© Северобайкальск, Russia
Александр Козлов, 2017

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Бейсик Python

Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?

Первым действием процедура F(1) выведет число 1. Далее процедура F(1) вызовет процедуру F(n + 1), в результате выполнения которой на экране появится число n + 1 = 2. Процедура F(2) вызовет процедуру F(3), которая выведет на экран число 3 и вызовет процедуру F(4), которая выведет на экран число 4 и вызовет F(5), которая выведет на экран число 5.

Читайте также  Сборка моделей из дерева

После этого управление вернётся к процедуре F(4), которая начнёт выполнять следующий шаг своего алгоритма, т. е. обратиться к процедуре F(n + 3) = F(7). Процедура F(7) выведет на экран число 7. Далее управление вернётся к процедуре F(3). Рассуждая аналогично приходим к выводу, что процедура F(3) дополнительно выведет на экран число 6, процедура F(2) — 5.

Последним действием процедуры F(1) будет вызов процедуры F(n + 3) = F(4), которая выведет на экран числа

Таким образом, на экране будут числа 1, 2, 3, 4, 5, 7, 6, 5, 4, 5, 7. Их сумма равна 49.

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

Урок "Решение задач по теме "Рекурсивные алгоритмы выполнения функций и процедур" (язык программирования Паскаль).

Цель урока : познакомить учащихся с рекурсивными алгоритмами, проанализировать их работу, рассмотреть типичные задачи ЕГЭ по этой теме.

1 этап урока : объяснение нового материала :

Слово рекурсия от лат. recursio означает круговорот. Синонимами этого слова являются возвращение, повторение. Классическим примером рекурсивного алгоритма является алгоритм решения задачи "Ханойские башни". Есть три стержня, на одном из которых находятся кольца разного диаметра. Необходимо переложить их с первого стержня на свободный, используя еще один.

Рассмотрим случай с пятью кольцами.

Учащимся предлагается самостоятельно составить алгоритм к этой задаче и устно описать его.

Далее учитель загружает файл Hanoy.exe и демонстрирует учащимся работу алгоритма.

Переместить пятое кольцо самого большого диаметра невозможно до тех пор, пока мы не перенесем четыре верхних. Т.е задача приводит нас к решению подобной задачи, но уже с меньшим количеством колец — четырьмя. Переместив пятое кольцо нам нужно будет положить на него четвертое, освободить которое мы можем только убрав верхние три. Т.е следующая задача, которую мы будем решать эта задача перекладывания трех колец. Продолжая наши рассуждения мы дойдем до того момента, когда нам нужно будет переложить всего лишь одно кольцо. Рекурсивный алгоритм обязательно должен иметь условие остановки. Если остановки не произойдет, он будет работать бесконечно. В нашем случае это произойдет когда количество колец для перекладывания станет равно 0.

Рекурсия это способ определения объекта , который опирается на само понятие объекта на основе заданных простых базовых случаев. Преимущество такого определения заключается в том, что оно способно описывать бесконечно большое число объектов. Мы разрабатываем алгоритм, сводя исходную задачу к более простым. Рекурсия позволяет сделать решение более понятным, сократить текст программы, упростить ее.

Рекурсивная (процедура) функция вызывает сама себя напрямую или через другие процедуры и функции . Количество таких вызовов называется глубиной рекурсии .

Классическим примером рекурсивного алгоритма является алгоритм нахождения факториала числа n. Факториал может быть введен с помощью рекуррентной формулы, которая связывает факториал числа с факториалом предыдущего числа.

базовые случаи здесь: 0!=1, 1!=1

рекурентная формула: N != N *( N -1)! при N >=2

На языке Паскаль функция выглядит следующим образом:

function factorial(N: integer) : longint;
begin
if N = 0 then factorial := 1
else
factorial := factorial(N-1) * N
end;

Что же происходит, если одна функция вызывает другую?

в памяти размещаются параметры, передаваемые функции

для внутренних переменных вызываемой функции также отводится новая область памяти (несмотря на совпадение их имен и типов с переменными вызывающей функции);

запоминается адрес возврата в вызывающую функцию;

управление передается вызванной функции.

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

Действия, выполняемые функцией до входа на следующий уровень рекурсии, выполняются на прямом ходу рекурсии, а действия, выполняемые по возврату с более глубокого уровня к текущему, – выполняются на обратном ходу рекурсии.

Читайте также  Расширение 001 чем открыть

2 этап : практическая работа за компьютером

Продемонстрируем ход рекурсии. Учащимся предлагается ввести программу в компьютер и пошагово проследить как она работает.

var glubina: i nteger := 0;
function factorial(N: integer) : longint;
begin
<при входе в функцию увеличиваем переменную, которая считает глубину рекурсии>
glubina := glubina + 1;
w riteln(‘Прямой ход рекурсии. Глубина = ‘, glubina);
result := 1;
if N > 0 then result := factorial(N-1) * N;
Writeln(‘ Обратный ход рекурсии . Глубина = ‘, glubina);
< при выходе из функции — уменьшаем эту переменную >
glubina := glubina — 1;
end;
begin
factorial(3);
end.

При запуске этой программы, будет выведено:

Прямой ход рекурсии. Глубина = 1
Прямой ход рекурсии. Глубина = 2
Прямой ход рекурсии. Глубина = 3
Прямой ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 3
Обратный ход рекурсии. Глубина = 2
Обратный ход рекурсии. Глубина = 1

3 этап : закрепление нового материала при решении задач.

Рассмотрим задачи ЕГЭ , в которых присутствуют рекурсивные алгоритмы выполнения процедур. В процессе выполнения таких задач будут осуществляться рекурсивные вызовы процедуры. Необходимо правильно проследить порядок вызовов. Это возможно сделать разными способами, один из которых нарисовать дерево вызовов. Дерево может получится достаточно громоздким, поэтому более простым способом решения является анализ алгоритма, его связи с вопросом задачи. Внутри алгоритма могут находится следующие операторы:

Writeln(*); в этом случае возможен вопрос: сколько * выведется на экран после выполнения алгоритма.

Writeln(n); в этом случае может быть задан вопрос :какова сумма всех n, выводимых на экран или потребуется записать последовательность из выводимых n.

Рассмотрим следующую задачу:

Найдите сумму чисел, которые будут выведены при вызове F(2).

сумму чисел, полученных при вызове F ( n ) обозначим через S ( n ).

аккуратно и последовательно выполним вычисления:

s(2)=2+s(4)+S(6), т . е необходимо найти S(4) и s(6).

Рассмотрим еще один рекурсивный алгоритм:

if n > 0 then begin

Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

обозначим через Z(n) количество звездочек, которые выводит программа при вызове F(n)

из программы видим, что

Z(n) = 1 при всех n

Z(n) = 1 +Z(n-2) + Z(n div 2) + Z(n div 2) при n > 0

n div 2– это частное от деления n на 2

попробуем начать с нуля:

Z(1) = 1 + Z(-1) + Z(0) + Z(0) = 1 + 1 +2* 1 =4

Z(2) = 1 + Z(0) + Z(1) + Z(1) = 1 + 1 + 2*4 = 10

Z(3) = 1 + Z(1) + Z(1)+ Z(1) = 1 +3* 4 = 13

Z(4) = 1 + Z(2) + Z(2) + Z(2) = 1 + 3*10 = 31

Z(5) = 1 + Z(3) + Z(2) + Z(2) = 1 + 13 +2*10 = 34

Можно анализировать с конца, как в предыдущей задаче, ответ будет таким же.

Определите, что выведет на экран программа при вызове F(9).

if n > 0 then begin

при вызове F(9) условие n>0 выполняется, распечатывается 9, затем вызывается F(n-4) = F(5), затем вызывается F(n div 2) = F(4); т.е. можно записать, что F(9)= 9 F(5) F(4)

аналогично рассматриваем F(5) и F(4)

теперь неизвестны F(2), F(1)

F(1)= 1 F(-3) F(0)=1, т.к при n

F(4)= 4 F(0) F(2) =4 2 1

F(5)= 5 F(1) F(2)=5 1 2 1

F(9)= 9 F(5) F(4)=9 5 1 2 1 4 2 1

Учащиеся могут проверить данную задачу на компьютере, выполнив следующую программу:

procedure F(n: integer);

if n > 0 then begin

Последовательность будет аналогичной.

выполнить следующие задания из открытого банка заданий ЕГЭ

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

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

В ответе запишите только натуральное число.

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

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

В ответе запишите только натуральное число.

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

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

В ответе запишите только натуральное число.

Ссылка на основную публикацию
Adblock
detector