Рекурсивные выражения. Алгоритмы с рекурсией

В6_ В11 ЕГ рекурсивные процедуры рекуррентные функции

Реш 1( метод подст:

1) снач опр рекур флу; обозн G(n) сумму чисел, кот выв при вызове F(n)

2) при n = 6 процедура выв число n и заканч работу без рекурс вызовов: G(n) = n при n = 6

3) при n

4) в рез вызова F(1) получ G(1) =1 +G(3)+G(3) G(3)=3+G(5)+G(9)=3+G(5)+9G(5)=5+G(7)+G(15)=5+7+15=27 5) исп обр подст: G(3) =3 +G(5) +9=3 +27+9 = 39 G(1) = 1 + 2*G(3) = 79 6) Ответ: 79

Реш1 ( динам прог):

п. 1-3 такие же, как в первом варианте решения

запол таблицу G(n) при n = 6 (где G(n) = n)

ост ячейки заполн, нач с n = 5 справа налево, исп ф-лу :G(n)=n+G(n+2)+G3n)

Реш2

G(n) = 1 при всех n G(n)=1+G(n-2)+G(n div 2) при n 0

по этим ф-лам заполняем таблицу, нач с 0:

G(0) = 1 G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3

G(2) = 1+ G(0) + G(1) = 1+1 +3 = 5 G(3) =1+G(1)+G(1) = 1+3+3 = 7

G(4) = 1+G(2)+ G(2)= 1+5+5= 11 G(5) =1 + G(3) + G(2) = 1 + 7 + 5 = 13

G(6) = 1+G(4) + G(3) = 1 +11+7 =19 G(7) =1+G(5)+G(3)= 1+13+7 = 21

Реш2, «с конца»):

пп. 1-3 – как в вар 1

по флам G(7) = 1+ G(5) + G(3), поэтому н найти G(5) и G(3)

G(5) = 1 + G(3) + G(2), н G(3) и G(2) G(3) = 1 + G(1) + G(1), н G(1)

G(2) =1+G(0)+G(1) =2 +G(1), н G(1) G(1)=1+G(-1)+G(0) =1+1+1=3

теперь идем «обратным ходом»:

G(2) = 2 + G(1) = 5 G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7

G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13 G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21

Реш 1

F(5)/G(5) = 1

Реш 2

запишем в таблицу базовые случаи

для бóльших n имеем рек ф-лу F(n) = F(n-1) +F(n-2)+F(n-2) = F(n-1)+2*F(n-2)

заполняем табл, используя рекуррентную формулу

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

F(5) = F(4) + 2*F(3) = 11 F(6) = F(5) + 2*F(4) = 21

Метод 2-ичн дерева

procedure F(n: integer);

begin

writeln(n);

if n

BeginF(n + 1);F(n + 3) end

end;

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

складывая все эти числа, получаем 49

http://информатика.1сентября.рф/article.php?ID=200800502

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

B6 № 4558. Алгоритм вычисл зн функции F(n), где n – нат

F(1) = 1 F(n) = F(n–1) * n, при n 1 Чему равно зн функ F(5)?

B6 № 4642. Алг вычисл зн функции F(n), где n – нат число, задан след соотн:
F(1) = 3 F(n) = F(n–1) * (n–1), при n 1 Чему равно зн функ F(6)?

B6 № 4643. Алг вычисл зн функции F(n), где n – натуральн, задан след соотн:
F(1) = 1 F(n) = 5*F(n–1) + 3*n, при n 1 Чему равно зн функ F(4)?

B6 № 4644. Алгоритм вычисл зн ф F(n), где n – нат, задан следующ соотн:
F(1) = 1 F(n) = F(n–1) * F(n–1) − F(n–1) * n + 2 * n, при n 1 Чему равно знач ф F(4)?

B6 № 4645. Алгоритм вычисл зн функции F(n), где n – нат, задан след соотн:
F(1) = 1 F(2) = 3 F(n) = F(n–1) * n + F(n–2) * (n – 1) , при n 2 Чему равно зн ф F(5)?

B6 № 4646. Алг вычисл зн функции F(n), где n – нат, задан след соотн:
F(1) = 1 F(2) = 3 F(n) = F(n−1) * F(n−2) + (n−2), при n 2 Чему равно з функции F(5)?

B6 № 4647. Алгоритм вычисл зн функции F(n), где n – нат, задан соотношениями:
F(1) = 1 F(2) = 2 F(n) = 2 * F(n–1) + (n – 2) * F(n–2), при n 2
Чему равно зн функции F(6)?

B6 № 4648. Посл-ть чисел Фибоначчи зад рек соот:
F(1) = 1 F(2) = 1 F(n) = F(n–2) + F(n–1), при n 2, где n – нат.
Чему равно 8-е число И 9-е число в посл-ти Фибоначчи?

B6 № 4650. Посл-ть чисел трибоначчи задается рекурр соот:
F(1) = 0 F(2) = 1 F(3) = 1 F(n) = F(n–3) + F(n–2) + F(n–1), при n 3, где n – нат.
Чему равно 9-е число в посл-ти трибоначчи? Чему равно 11-е число в посл-ти трибоначчи?

B6 № 4652. Посл-ть чисел Люка задается рек соотношением:
F(1) = 2 F(2) = 1 F(n) = F(n–2) + F(n–1), при n 2, где n – нат.
Чему равно 8 число в посл=ти Люка? Чему равно 10-е число в посл-ти Люка?

B6 № 4654. Посл-ть чисел Падована задается рекуррентным соотношением:
F(1) = 1 F(2) = 1 F(3) = 1 F(n) = F(n–3) + F(n–2), при n 3, где n – натуральное число.
Чему равно 10-е число в посл-ти Падована? Чему равно 12-е число в посл-ти Падована?

B6 № 4656. Алг вычисл з функции F(n) и G(n), где n – нат, задан след соотн:
F(1) = 0 F(n) = F(n–1) + n, при n 1 G(1) = 1 G(n) = G(n–1) * n, при n 1
Чему равно зн функции F(5) + G(5)?

B6 № 4657. Алг вычисл зн функции F(n) и G(n), где n – нат, задан сле соотн:
F(1) = 1 F(n) = 2 * G(n–1) + 5 * n, при n 1 G(1) = 1 G(n) = F(n–1) + 2 * n, при n 1
Чему равно значение функции F(4) + G(4)?

B6 № 4658. Алгоритм вычисл зн функции F(n), где n – натур, задан след соотношениями:
F(1) = 1 F(2) = 1 F(n) = F(n–1) * n − 2 * F(n–2), при n 2
Чему равно значение функции F(6)?

B6 № 4659. Алгоритм вычисл зн функции F(n), где n – нат, задан след соотн:
F(1) = 1 F(2) = 2 F(n) = F(n–1) − F(n–2) + 2 * n, при n 2
Чему равно з функции F(6)?

B6 № 4660. Алгоритм вычисл зн функ F(n), где n – натур, задан след соотн:
F(1) = 1 F(2) = 2 F(n) = (F(n–1) − F(n–2)) * n, при n 2
Чему равно значение функции F(8)?

B6 № 4692. Алгоритм вычисл зн функции F(n). где n — нат, задан след соотн:
F(1) = 1; F(n) = F(n-1) * (n+1), при n 1. Чему равно зн функции F(4)?

B6 № 4724. Алгоритм вычисл зн функции F(n). где n — нат, задан след соотн:
F(1) = 1; F(n) = F(n-1) * (n+1), при n 1. Чему равно зн функции F(5)?

задачи на алг – прогр цикл не использовать

вывод цифр p-ичн предст зад 10-ичн нат числа (2≤p≤9).

Вып действий после рекурс вызова ( на рекурсивном возврате)

Procedure From10(a: longint; p: byte);
Var remin: byte; 
Begin
If a = p Then 

From10(a div p, p);
remin := a mod p; { ост для тек зн парам процедуры}
write(remin); {Вывод его}
End;

Вывод всех делителей нат числа.

Чтоб делители б напеч в порядке возр н исп рекурсию

Procedure Dived(n, d: longint); //Вывод всех делителей нат числа

Var dd: longint; //dd — делитель симм найденному

Begin

if (dn) then Exit;

If n mod d = 0 Then {встретился делитель n}

Begin

dd := n div d;{Запоминаем 'симметричный' делитель}

If (d dd) Then

Begin

Dived(n, d + 1);{Перех к проверке след числа d}

write(dd, ' ');{После возвр из проц Dived печат делитель dd}

End

End

Else {n mod d 0}

Dived(n,d+1); {провер следующего числа d}

End;

действия как на рекурс спуске, так и на рекурсив возврате).

1. Разр прогр для расч чла сочет из n эл по m (о ), исп рекурс описание: 

Function Cnm(n, m: byte): word;
Begin
If (m = 0) Or (n = m) Then Cnm := 1 
Else Cnm := Cnm(n — 1, m) + Cnm(n — 1, m — 1)
End;

1)Для зад целого a и нат n вычислить .

3) Вычислить n-й член посл-ти Фибоначчи

4) При пом рекурс функции опр кол цифр в зад нат числе n

6)Для зад одномерн массива A из N эл найти зн макс эл массива. Рекурсив функцию примен каждый раз отд для первой трети массива и для ост части (2/3) массива. Рекурс вызовы заканчи, когда ост только один или два элемента. Напр, для N=6:

7) Составить прог-функцию возвр наиб общий делитель двух нат чисел x и y.

Реш. Обозн через nod(x,y) – наиб общий делитель x и y. Известно, что

8) Сост прогр-функцию, возвр наим общ кратное нат чисел a_p (p=0..n-1, n³2), явл к-тами вектора v=(a₀,a₁,…,a_n-1)^T.

Реш. Обозн через nok(a₀,a₁,…,a_n-1) – наим общее кратное чисел a_p (p=0..n-1). Известно, что

и

Далее, если n ³2 и dn(n)=2, то n – простое. но пров n на простоту этим спос весьма неэкономна

10) Составить прогр-функцию провер, явля ли заданное натурально число n простым?

Решение. Пусть рекурсивная функция isprim(n) явл решением задачи и

рассм след обобщ зад. Пусть a, b, n - нат числа и . Верно ли, что зад n не дел ни на одно целое из отрезка [a, b]? Пусть эту задачу решает функция