Условие:
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n ≥ 10 000,
F(n) = n/4 + F(n/4 + 2), если n < 10 000 и n делится на 4,
F(n) = 1 + F(n + 2) , если n < 10 000 и n не делится на 4.
Чему равно значение выражения F(174) – F(3)?
Решение:
Рассмотрим функцию F(n), определённую рекуррентно следующим образом: 1) Если n ≥ 10 000, то F(n) = n. 2) Если n 10 000 и n делится на 4, то F(n) = n/4 + F(n/4 + 2). 3) Если n 10 000 и n не делится на 4, то F(n) = 1 + F(n + 2). Нам нужно вычислить F(174) – F(3). Проанализируем вычисления по шагам. ────────────────────────────── Шаг 1. Вычисление F(174) n = 174 меньше 10 000. Проверим деление на 4: 174 делится на 4? 174 ÷ 4 = 43.5, остаток 2 → не делится. По правилу (3): F(174) = 1 + F(174 + 2) = 1 + F(176). ────────────────────────────── Шаг 2. Вычисление F(176) 176 10 000 и 176 дел...