
Вопрос задан 03.05.2019 в 21:26.
Предмет Информатика.
Спрашивает Власов Александр.
Записан рекурсивный алгоритм f/ procedure F(n: integer); begin writeln(n); if n > 0 then
begin F(n - 1); F(n - 3) end; end чему равна сумма всех чисел напечатанных на экране при выполнении вызова f5

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

Отвечает Гребенюк Лина.
Представим, что мы знаем ответ на вопрос "чему равна сумма всех выписанных чисел при выполнении вызова 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(5)...
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) также растет быстро, но это уже другая проблема.
Что делает 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(5)...
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) также растет быстро, но это уже другая проблема.



Отвечает нейросеть ChatGpt. Будьте внимательны, ответы нейросети могут содержать ошибочные или выдуманные данные.
При выполнении вызова F(5) будут напечатаны следующие числа на экране:
5 4 3 2 1 0 -1 2 1 0
Сумма всех этих чисел равна 17.


Топ вопросов за вчера в категории Информатика

Информатика 565

Информатика 25

Информатика 22

Информатика 27

Информатика 34

Информатика 58

Информатика 63

Информатика 23
Последние заданные вопросы в категории Информатика
Предметы
-
Математика
-
Литература
-
Алгебра
-
Русский язык
-
Геометрия
-
Английский язык
-
Химия
-
Физика
-
Биология
-
Другие предметы
-
История
-
Обществознание
-
Окружающий мир
-
География
-
Українська мова
-
Информатика
-
Українська література
-
Қазақ тiлi
-
Экономика
-
Музыка
-
Право
-
Беларуская мова
-
Французский язык
-
Немецкий язык
-
МХК
-
ОБЖ
-
Психология
-
Физкультура и спорт
-
Астрономия
-
Кыргыз тили
-
Оʻzbek tili