Рекурсивни алгоритми

По-долу има две рекурсивни процедури, F и G:

процедура F (n: цяло число); напред;

процедура G (n: цяло число); напред;

процедура F (n: цяло число);

процедура G (n: цяло число);

Колко звездички ще бъдат отпечатани на екрана при извикване на F (11)?

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

ако състоянието н > 0 изпълнява се следният ред: G (n - 1), процедура за извикване G след намаляване н от 1

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

ако е изпълнено условието n> 0, се изпълнява следният ред: G (n - 1), процедура за извикване G след намаляване н от 1

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

ако е изпълнено условието n> 0, се изпълнява следният ред: G (n - 1), процедура за извикване G след намаляване н от 1

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

след като получи стойност -1 и се увери, че условието не е изпълнено, Паскал прекратява програмата.

И просто трябва да изчислим колко пъти е била отпечатана звездичката. В нашия случай това се случи точно 3 пъти

Общо, верен отговор: 3

Внимание! За да превъртите условието на анимацията, кликнете върху него с левия бутон на мишката и натиснете бутона „НАДОЛУ“ или „НАГОРЕ“

Интерактивен треньор 11 Унифициран държавен изпит DEMO 2015
за "Рекурсивни алгоритми"

Ако уловът на задачата не е напълно видим, щракнете върху него с курсора на мишката и натиснете клавиша "надолу" или "нагоре"

Примери за задачи и техните решения, генерирани от интерактивен симулатор за задачи 11 Унифициран държавен изпит 2015 г.
Рекурсивни алгоритми.

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

процедура F (n: цяло число);
започнете
writeln (n);
ако 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

Даден рекурсивен алгоритъм:
процедура F (n: цяло число);
започнете
writeln (n);
ако 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 е естествено число, се дава от следните отношения:

---