Регистрация Спросить otvet5GPT
tyanhinata
08.12.2022 22:50
Информатика
Есть ответ 👍

Записан рекурсивный алгоритм f/ procedure f(n: integer); begin writeln(n); if n > 0 then begin f(n - 1); f(n - 3) end; end чему равна сумма всех чисел напечатанных на экране при выполнении вызова f5

162
356
Посмотреть ответы 2

Ответы на вопрос:

svfedunina
svfedunina
4,6(83 оценок)
Представим, что мы знаем ответ на вопрос "чему равна сумма всех выписанных чисел при выполнении вызова f(n)" для всех n < k. попробуем понять, как найти ответ для  n = k. что делает f(n)? читаем текст программы: сначала выводит n, а потом (если n > 0) запускает f(n - 1) и f(n - 3). обозначим s(n) - сумму всех чисел после вызова f(n), тогда (при n > 0)  s(n) = n + s(n - 1) + s(n - 3) для неположительных n получаем, что s(n) = n (т.к. f(n) просто выводит n и завершает работу, не запуская никаких других f). остается только расписать, чему равно s( s(-2) = -2 s(-1) = -1 s(0) = 0 s(1) = 1 + s(0) + s(-2) = 1 + 0 - 2 = -1 s(2) = 2 + s(1) + s(-1) = 2 -  1 - 1 = 0 s(3) = 3 + s(2) + s(0) = 3 + 0 + 0 = 3 s(4) = 4 + s(3) + s(1) = 4 + 3 - 1 = 6 s(5) = 5 + s(4) + s(2) = 5 + 6 + 0 = 11 ответ. 11. при исследовании рекурсивных алгоритмов бывает полезно понять, сколько вызовов функций делает программа (например, если рисовать дерево вызовов, это будет показывать количество "стрелочек" на этом дереве). представим себе, что мы стали выполнять алгоритм  на бумаге, попробуем понять, сколько чисел придется выписывать. если #(n) - число вызовов процедуры f при наивном вычислении f(n). понятно, что #(n) = #(n - 1) + #(n - 3) (при n < = 0 #(n) = 1).  не задаваясь целью получить точную формулу для #(n), получим только оценку (на самом деле, весьма показательную). очевидно, что #(n - 1) > = #(n - 3), тогда #(n) > = 2 *  #(n - 3). так как #(0) = 1, то #(3) > = 2 * #(0) = 2, #(6) > = 2 * #(3) > = 2^2, #(9) > = 2 * #(6) > = 2^3, и вообще #(3n) > = 2^n отсюда можно предположить, что #(n) растет не медленнее, чем 2^(n/3) > = 1.25^n. если 1,25^n кажется медленно растущей функцией - это вовсе не так, для n = 100 (это  немного, наверно? ) получим число, большее миллиарда. так что если не запоминать промежуточные результаты, результат будет считаться долго. s(n) также растет быстро, но это уже другая проблема.
Dron133
Dron133
4,5(55 оценок)

var a: array[1..100]of integer;

      k,i: integer;

begin

readln (n);

for i: =1 to n do

begin

read (a[i]);

if a[i]< 0 then k: =k+1;

end;

write (k);

end.

Реши свою проблему, спроси otvet5GPT

  • Быстро
    Мгновенный ответ на твой вопрос
  • Точно
    Бот обладает знаниями во всех сферах
  • Бесплатно
    Задай вопрос и получи ответ бесплатно

Популярно: Информатика

Caktus Image

Есть вопросы?

  • Как otvet5GPT работает?

    otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.

  • Сколько это стоит?

    Проект находиться на стадии тестирования и все услуги бесплатны.

  • Могу ли я использовать otvet5GPT в школе?

    Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!

  • В чем отличия от ChatGPT?

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

Подпишись на наш телеграмм канал

GTP TOP NEWS