Рекурсия в заданиях ЕГЭ

Рекурсия в задачах ЕГЭ

0 then begin write(n); F(n - 3); F(n div 3) end end; 9 6 3 1 3 2 0 0 1 -1 0 Ответ: 9631231 " width="640"

ДЕМО 2018

procedure F(n: integer);

begin

if n 0 then

begin

write(n);

F(n - 3);

F(n div 3)

end

end;

9

6

3

1

3

2

0

0

1

-1

0

Ответ: 9631231

2 then F := F(n-1) + G(n-2) else F := n+1; end; function G(n: integer): integer; begin if n 2 then G := G(n-1) + F(n-2) else G := n; end; F(7) = F(6)+G(5) = G(5) = G(4)+F(3) = " width="640"

ИН10103

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

Чему будет равно значение, вычисленное при выполнении вызова F(7)?

function F(n: integer): integer;

begin

if n 2 then

F := F(n-1) + G(n-2)

else

F := n+1;

end;

function G(n: integer): integer;

begin

if n 2 then

G := G(n-1) + F(n-2)

else

G := n;

end;

F(7) = F(6)+G(5) =

G(5) = G(4)+F(3) =

ИН10103

F(7) = F(6) + G(5) =

G(5) = G(4) + F(3) =

F(6) = F(5) + G(4) =

G(4) = G(3) + F(2) =

F(5) = F(4) + G(3) =

G(3) = G(2) + F(1) =

G(2) = 2

F(4) = F(3) + G(2) =

F(3) = F(2) + G(1) =

G(1) = 1

F(2) = 2 + 1 = 3

F(1) = 1 + 1 = 2

или

G(1) = 1

F(7) = F(6) + G(5) =

F(6) = F(5) + G(4) =

G(2) = 2

F(5) = F(4) + G(3) =

G(3) = G(2) + F(1) =

F(4) = F(3) + G(2) =

G(4) = G(3) + F(2) =

F(3) = F(2) + G(1) =

G(5) = G(4) + F(3) =

F(2) = 2 + 1 = 3

F(1) = 1 + 1 = 2

2 then F := F(n-2) + F(n div 2) else F := n end; F(9) = F(7) + F(4) = F(7) = F(5) + F(3) = F(5) = F(3) + F(2) = F(4) = F(2) + F(2) = F(3) = F(1) + F(1) = F(2) = 2 F(1) = 1 F(9) = F(7) + F(4) = = F(5) + F(3) + F(2) + F(2) = = F(3) + F(2) + F(1) + F(1) + 2F(2) = = F(1) + F(1) + 3F(2) + 2F(1) = = 4F(1) + 3F(2) = = 4 * 1 + 3 * 2 = 10 Ответ: 10 " width="640"

ИН10203

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

function F(n: integer): integer;

begin

if n 2 then

F := F(n-2) + F(n div 2)

else

F := n

end;

F(9) = F(7) + F(4) =

F(7) = F(5) + F(3) =

F(5) = F(3) + F(2) =

F(4) = F(2) + F(2) =

F(3) = F(1) + F(1) =

F(2) = 2

F(1) = 1

F(9) = F(7) + F(4) =

= F(5) + F(3) + F(2) + F(2) =

= F(3) + F(2) + F(1) + F(1) + 2F(2) =

= F(1) + F(1) + 3F(2) + 2F(1) =

= 4F(1) + 3F(2) =

= 4 * 1 + 3 * 2 = 10

Ответ: 10

0 then begin F(n – 3); F(n div 3); write(n) end end; 6 3 0 3 2 1 -2 0 0 0 -1 1 -2 0 Ответ: 1326139 " width="640"

ИН10303

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

9

procedure F(n: integer);

begin

if n 0 then

begin

F(n – 3);

F(n div 3);

write(n)

end

end;

6

3

0

3

2

1

-2

0

0

0

-1

1

-2

0

Ответ: 1326139

Задача

Процедура F(n), где n – натуральное число, задана следующим образом:

procedure F(n: integer);

begin

writeln(n);

if n

begin

F(n + 1);

F(n + 3)

end

end;

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

Если трудно поддаётся решение задачи:

• Запустить среду программирования PascalABC
• Скопировать/написать исходный код функции/процедуры …
• Написать несложный код вызова функции, например Begin F(9) End.
• Включить окно отладки (в PascalABC)
• Выполнить трассировку алгоритма со входом в подпрограммы
• Понять причину затруднений

3 1 - 2 3 - 2 1 - 3 2 - 1 2 - 3 1 - 3 } program recHanoi; procedure Hanoi(n, k, m: integer); var p: integer; begin { Exit не работает в АЛГО } if n = 0 then exit; p:= 6 - k - m; Hanoi(n-1, k, p); writeln(k, ' - ', m); Hanoi(n-1, p, m) end; begin Hanoi ( 3, 1, 3 ); End. " width="640"

Поляков К.Ю. §61 Рекурсия. Примеры:

{

Программа к учебнику информатики для 10 класса

К.Ю. Полякова и Е.А. Еремина.

Глава 8.

Программа № 26. Рекурсия. Ханойские башни

Вход:

нет

Результат:

1 - 3

1 - 2

3 - 2

1 - 3

2 - 1

2 - 3

1 - 3

}

program recHanoi;

procedure Hanoi(n, k, m: integer);

var p: integer;

begin

{ Exit не работает в АЛГО }

if n = 0 then exit;

p:= 6 - k - m;

Hanoi(n-1, k, p);

writeln(k, ' - ', m);

Hanoi(n-1, p, m)

end;

begin

Hanoi ( 3, 1, 3 );

End.

program recBinCode;

var N: integer;

procedure printBin(n: integer);

begin

{ Exit не работает в АЛГО }

if n = 0 then exit;

printBin(n div 2);

write(n mod 2)

end;

begin

write ( 'Введите натуральное число: ' );

read ( N );

write ( 'Двоичный код ' );

printBin ( N );

end.

{

Программа к учебнику информатики для 10 класса

К.Ю. Полякова и Е.А. Еремина.

Глава 8.

Программа № 27. Рекурсия. Двоичный код

Вход:

99

Результат:

Двоичный код 1100011

}

= 10 then sum:= sum + sumDig(n div 10); sumDig:= sum; end; begin write ( ' Введите натуральное число: ' ); read ( N ); write ( ' Сумма цифр ', sumDig(N) ); end. { Программа к учебнику информатики для 10 класса К.Ю. Полякова и Е.А. Еремина. Глава 8. Программа № 28. Рекурсия. Сумма цифр Вход: 12345 Результат: Сумма цифр 15 } " width="640"

program recSumDigits;

var N: integer;

function sumDig(n: integer):

integer;

var sum: integer;

begin

sum:= n mod 10;

if n = 10 then

sum:= sum + sumDig(n div 10);

sumDig:= sum;

end;

begin

write ( ' Введите натуральное число: ' );

read ( N );

write ( ' Сумма цифр ', sumDig(N) );

end.

{

Программа к учебнику информатики для 10 класса

К.Ю. Полякова и Е.А. Еремина.

Глава 8.

Программа № 28. Рекурсия. Сумма цифр

Вход:

12345

Результат:

Сумма цифр 15

}

b then NOD:= NOD(a - b, b) else NOD:= NOD(a, b - a) end; begin write ( ' Введите два натуральных числа: ' ); read ( a, b ); write ( ' НОД(', a, ',', b, ')= ', NOD(a,b) ); end. { Программа к учебнику информатики для 10 класса К.Ю. Полякова и Е.А. Еремина. Глава 8. Программа № 29. Рекурсия. Алгоритм Евклида Вход: 14 21 Результат: НОД(14,21) = 7 } " width="640"

program recNOD;

var a, b: integer;

function NOD(a,b: integer):

integer;

begin

if (a = 0) or (b = 0) then

begin

NOD:= a + b;

{ Exit не работает в АЛГО }

exit;

end;

if a b then

NOD:= NOD(a - b, b)

else NOD:= NOD(a, b - a)

end;

begin

write ( ' Введите два натуральных числа: ' );

read ( a, b );

write ( ' НОД(', a, ',', b, ')= ', NOD(a,b) );

end.

{

Программа к учебнику информатики для 10 класса

К.Ю. Полякова и Е.А. Еремина.

Глава 8.

Программа № 29. Рекурсия. Алгоритм Евклида

Вход:

14 21

Результат:

НОД(14,21) = 7

}

N=2 - N=1 2 } program recFact; var N: integer; function Fact(N: integer): integer; begin writeln ( '- N=', N ); if N Fact:= 1 else Fact:= N * Fact(N - 1); writeln ( 'end; begin write ( ' Введите натуральное число: ' ); read ( N ); writeln ( Fact(N) ); end. В Интернете много разных решений этих задач с помощью рекурсии. " width="640"

{

Программа к учебнику информатики для 10 класса

К.Ю. Полякова и Е.А. Еремина.

Глава 8.

Программа № 30. Рекурсия. Факториал

Вход:

2

Результат:

- N=2

- N=1

2

}

program recFact;

var N: integer;

function Fact(N: integer): integer;

begin

writeln ( '- N=', N );

if N

Fact:= 1

else

Fact:= N * Fact(N - 1);

writeln ( '

end;

begin

write ( ' Введите натуральное число: ' );

read ( N );

writeln ( Fact(N) );

end.

В Интернете много разных решений этих задач с помощью рекурсии.

Существуют языки программирования, работающие только на рекурсиях.

Волшебная пружинка

Ограничение времени

1 секунда

Ограничение памяти

64Mb

Ввод

стандартный ввод или input.txt

Вывод

стандартный вывод или output.txt

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

Так вот представьте, что на вершине длинной лестницы, содержащей К ступенек, расположена волшебная пружинка новейшей модификации, которая начинает спускаться вниз по лестнице, прямиком к ее основанию. Пружинка может переползти или на одну ступеньку вниз, или через одну ступеньку, или даже через 2.

(Пример: пружинка находится на 97-й ступеньке. Получается, что она может переместиться на 96-ую, 95-ую или 94-ую ступеньки)

Узнайте сколькими способами пружинка может спуститься с «небес» на землю.

Формат ввода

Количество ступенек в лестнице – К – целое число.

Формат вывода

Количество способов спуска – целое число.

Пример 1

Ввод Вывод

4 7

Пример2

Ввод Вывод

• 13

Пример 3

Ввод Вывод

1 1

F(1) = 1

F(2) = 2

F(3) = 4

F(4) = 4 + 2 + 1

F(5) = 7 + 4 + 2 = 13

…

F(n) = F(n-1)+F(n-2)+F(n-3)

Рекуррентная формула:

Пишем код программы:

var k:int64;

function f(n:int64):int64;

begin

case n of

1,2: f:=n;

3: f:=4;

else f:=f(n-1)+f(n-2)+f(n-3);

end;

end;

begin

read(k);

write(f(k));

end.