Помогите с информатикой, задание ** фото

0 голосов
38 просмотров

Помогите с информатикой, задание на фото

image
Информатика (96 баллов) | 38 просмотров
0

Это только программно решать, вручную крыша отъедет от такого объема рекурсии

оставил комментарий (142k баллов)
Дан 1 ответ
0 голосов
Правильный ответ

Для решения задачи написана программа, в которую вставлены операторы вывода с целью трассировки.

// PascalABC.NET 3.1, сборка 1192 от 07.03.2016
function G(n:integer):integer; forward;

function F(n:integer):integer;
begin
  Writeln('Вход в F(',n,')');
  if n=1 then Result:=1
  else Result:=F(n-1)-G(n-1);
  Writeln('Выход из F(',n,') со значением ',Result)
end;

function G(n:integer):integer;
begin
  Writeln('Вход в G(',n,')');
  if n=1 then Result:=1
  else Result:=F(n-1)+G(n-1);
  Writeln('Выход из G(',n,') со значением ',Result)
end;

begin
  Writeln('РЕЗУЛЬТАТ: ',F(5)/G(5)) 
end.

Результат выполнения программы (трассировочная таблица)
Вход в F(5)
Вход в F(4)
Вход в F(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из F(3) со значением -2
Вход в G(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из G(3) со значением 2
Выход из F(4) со значением -4
Вход в G(4)
Вход в F(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из F(3) со значением -2
Вход в G(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из G(3) со значением 2
Выход из G(4) со значением 0
Выход из F(5) со значением -4
Вход в G(5)
Вход в F(4)
Вход в F(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из F(3) со значением -2
Вход в G(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из G(3) со значением 2
Выход из F(4) со значением -4
Вход в G(4)
Вход в F(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из F(3) со значением -2
Вход в G(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из G(3) со значением 2
Выход из G(4) со значением 0
Выход из G(5) со значением -4
РЕЗУЛЬТАТ: 1

Вариант с хранением данных

// PascalABC.NET 3.1, сборка 1192 от 07.03.2016
var
  RF,RG:array[-100..100] of integer;

function G(n:integer):integer; forward;

function F(n:integer):integer;
begin
  Writeln('Вход в F(',n,')');
  if RF[n]<>777 then Result:=RF[n]
  else begin
    if n=1 then Result:=1
    else Result:=F(n-1)-G(n-1);
    RF[n]:=Result
    end;
  Writeln('Выход из F(',n,') со значением ',Result)
end;

function G(n:integer):integer;
begin
  Writeln('Вход в G(',n,')');
  if RG[n]<>777 then Result:=RG[n]
  else begin
    if n=1 then Result:=1
    else Result:=F(n-1)+G(n-1);
    RG[n]:=Result
    end;
  Writeln('Выход из G(',n,') со значением ',Result)
end;

begin
  for var i:=-100 to 100 do begin
    RF[i]:=777; RG[i]:=777
    end;
  Writeln('РЕЗУЛЬТАТ: ',F(5)/G(5))
end.

Результат выполнения программы
Вход в F(5)
Вход в F(4)
Вход в F(3)
Вход в F(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из F(2) со значением 0
Вход в G(2)
Вход в F(1)
Выход из F(1) со значением 1
Вход в G(1)
Выход из G(1) со значением 1
Выход из G(2) со значением 2
Выход из F(3) со значением -2
Вход в G(3)
Вход в F(2)
Выход из F(2) со значением 0
Вход в G(2)
Выход из G(2) со значением 2
Выход из G(3) со значением 2
Выход из F(4) со значением -4
Вход в G(4)
Вход в F(3)
Выход из F(3) со значением -2
Вход в G(3)
Выход из G(3) со значением 2
Выход из G(4) со значением 0
Выход из F(5) со значением -4
Вход в G(5)
Вход в F(4)
Выход из F(4) со значением -4
Вход в G(4)
Выход из G(4) со значением 0
Выход из G(5) со значением -4
РЕЗУЛЬТАТ: 1

(142k баллов)
0

Точонн, задача усложнится, уменьшится количество вызовов функций.

оставил комментарий (142k баллов)
0

*точнее

оставил комментарий (142k баллов)
0

А усложниться еще и тем, что мы изначально не знаем глубины рекурсии, следовательно не знаем, какого размера массив понадобится. Следовательно, придется делать списочную структуру. И еще, нужен будет эффективный механизм поиска в ней. Так что лучше уж так, по-простому.

оставил комментарий (142k баллов)
0

Cпасибо большое, я решала вручную, и ,можно сказать, примитивно: сначала считала f(2), Q(2) и так далее до F(5), Q(5). В итоге, ответ получился такой же

оставил комментарий (96 баллов)
0

Ой, т.е. вместо Q, G

оставил комментарий (96 баллов)
0

Сейчас дам вариант с табличкой, это примерно как человек бы считал.

оставил комментарий (142k баллов)
0

Вручную такое решать могут только ну очень замотивированные люди.

оставил комментарий (142k баллов)
0

Красиво. Себе сохранил. Классный код

оставил комментарий (13.9k баллов)
0

Спасибо

оставил комментарий (142k баллов)
0

Это задание из ЕГЭ, так что у меня выбора нет :)

оставил комментарий (96 баллов)
Похожие задачи