Презентация, доклад по информатике по теме Рекурсия. Задание №11 в ЕГЭ по информатике

Юлия Михайловна

на основе заданных простых базовых случаев.

хранится
В доме,
Который построил Джек.
А это весёлая птица-синица,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.
Вот кот,
Который пугает и ловит синицу,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.
Вот пёс без хвоста,
Который за шиворот треплет кота,
…
Самуил Маршак

Базовое предложение

друга зеркала: в них образуются два коридора из уменьшающихся отражений зеркал.

напрямую или через другие процедуры и функции.

Чтобы определить рекурсию, нужно:
задать условие остановки рекурсии (базовый случай или несколько базовых случаев)
рекуррентную формулу.

* К.Ю. Поляков

число, задан следующими соотношениями:
F(1) = 1;
F(2) = 1;
F(n) = F(n - 2) * (n - 1), при n > 2.
Чему равно значение функции F(7)? 

F(7) = F(5) * 6 =
F(5) = F(3) * 4 =
F(3) = F(1) * 2 =

Ответ: 48

2

8

48

– натуральное число, задан следующими соотношениями:
F(1) = 1;
G(1) = 1;
F(n) = 2*F(n–1) – G(n–1),
G(n) = 2*F(n–1) + G(n–1), при n >=2
Чему равно значение величины F(5)-G(5)?

= 2*F(n–1) + G(n–1), при n >=2 F(5)-G(5) -?

F(5) = 2*F(4)-G(4)=-17
F(4) = 2*F(3)-G(3)=-7
F(3) = 2*F(2)-G(2)=-1
F(2) = 2*F(1)-G(1)=1

Ответ: -6

G(5) = 2*F(4)+G(4)=-11
G(4) = 2*F(3)+G(3)=3
G(3) = 2*F(2)+G(2)=5
G(2) = 2*F(1)+G(1)=3

F(5)-G(5) =-17-(-11)=-17+11=-6

integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer); begin    if n > 0 then       G(n - 1); end;
procedure G(n: integer); begin    writeln('*');    if n > 1 then       F(n - 3); end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?

F(11)   G(10)   F(7)   G(6)   F(3)   G(2)   F(-1)

Ответ: 3

then
  begin
    writeln('*');
    F(n - 1);
    F(n div 3)
  end
end
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(6)?

3) Сколько «*» при вызове F(6) -?

Ответ: 11

-1

div 3

процедуры F(6)?

Ответ: 10

Procedure F(n: integer);
begin
  if n mod 2 = 0 then
     writeln('*')
else
writeln('**');
if n > 0 then
    F(n - 1);
    end;

выполнении вызова F(5)?

Ответ: 11

procedure F(n: integer);
    begin
        writeln(n);
        if n > 0 then
            begin
                F(n - 1);
                F(n - 3)
            end
end

Решение:
1 способ.




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

выполнении вызова F(5)?

procedure F(n: integer);
    begin
        writeln(n);
        if n > 0 then
            begin
                F(n - 1);
                F(n - 3)
            end
end

Решение:
2 способ.

Находим сумму: 5+4+3+2+1+0+(-2)+(-1)+0+1+0+(-2)+2+1+0+(-2)+(-1)=11

begin
writeln(n);
F(n - 3);
F(n div 3)
end
end;

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Ответ: 9631231

№1

№2

№3

№4

№5

№6

№7

n >= 3 then begin
write(n+1);
F(n - 1);
F(n - 2)
end
end;

Задание № 8

Ответ: 6544