Задание 16. Алгоритм вычисления значения функции F(n), где п – целое число, задан следующими соотношениями: F(n) = п при п≤ 1 F(n) = n + F(п/3) когда п > 1 и делится на 3 F(n) = n + F(n + 3) когда п > 1 и не делится на 3. Назовите минимальное значение п, для которого F(п) определено и больше 100.

Давай разберем алгоритм вычисления функции F(n) и найдем минимальное значение n, для которого F(n) > 100.

Алгоритм задан рекурсивно, то есть функция вызывает саму себя. Вот основные шаги:

1. Если n ≤ 1, то F(n) = n.
2. Если n > 1 и n делится на 3, то F(n) = n + F(n/3).
3. Если n > 1 и n не делится на 3, то F(n) = n + F(n + 3).

Мы должны найти минимальное n, при котором F(n) > 100.

Начнем с небольших значений n и посмотрим, как растет F(n):

• Если n = 1, F(1) = 1.
• Если n = 2, F(2) = 2 + F(5) = 2 + 5 + F(8) = 7 + 8 + F(11) = 15 + 11 + F(14) = 26 + 14 + F(17) = 40 + 17 + F(20) = 57 + 20 + F(23) = 77 + 23 + F(26) = 100 + 26 + F(29) = 126 + ...
• Если n = 3, F(3) = 3 + F(1) = 3 + 1 = 4.
• Если n = 6, F(6) = 6 + F(2) = ... (уже видели выше, что F(2) требует много вычислений).
• Если n = 9, F(9) = 9 + F(3) = 9 + 4 = 13.
• Если n = 12, F(12) = 12 + F(4) = 12 + 4 + F(7) = 16 + 7 + F(10) = 23 + 10 + F(13) = 33 + 13 + F(16) = 46 + 16 + F(19) = 62 + 19 + F(22) = 81 + 22 + F(25) = 103 + 25 + F(28) = ...
• Если n = 15, F(15) = 15 + F(5) = ... (уже видели выше, что F(5) требует много вычислений).
• Если n = 18, F(18) = 18 + F(6) = 18 + 6 + F(2) = ... (слишком мало, F(2) будет больше 100).
• Если n = 21, F(21) = 21 + F(7) = 21 + 7 + F(10) = 28 + 10 + F(13) = 38 + 13 + F(16) = 51 + 16 + F(19) = 67 + 19 + F(22) = 86 + 22 + F(25) = 108 + 25 + F(28) = ...

Мы видим, что F(2) и F(12) начинают быстро расти. F(2) больше 100, так как уже F(26) больше 100, поэтому F(2) больше 100.

Давай проверим n = 19: F(19) = 19 + F(22) = 19 + 22 + F(25) = 41 + 25 + F(28) = 66 + 28 + F(31) = 94 + 31 + F(34) = 125 + ...

Для n = 2, F(2) = 126 + F(29) = ..., значит, F(2) > 100. Проверим n = 3:

• n = 3, F(3) = 3 + F(1) = 3 + 1 = 4

Теперь для n = 12, F(12) = 103 + 25 + F(28) = ...

Нужно найти такое n, чтобы F(n) было определено и больше 100. Из наших вычислений видно, что:

• Для n = 2, F(2) > 100.
• Для n = 12, F(12) > 100.

Однако нас просят найти минимальное значение n, для которого F(n) > 100.

Так как F(2) = 2 + F(5) = 2 + (5 + F(8)) = 2 + 5 + (8 + F(11)) = 2 + 5 + 8 + (11 + F(14)) = 2 + 5 + 8 + 11 + (14 + F(17)) = 2 + 5 + 8 + 11 + 14 + (17 + F(20)) = 2 + 5 + 8 + 11 + 14 + 17 + (20 + F(23)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + (23 + F(26)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + (26 + F(29)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + (29 + F(32)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + (32 + F(35)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + 32 + (35 + F(38)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + 32 + 35 + (38 + F(41)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + 32 + 35 + 38 + (41 + F(44)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + 32 + 35 + 38 + 41 + (44 + F(47)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + 32 + 35 + 38 + 41 + 44 + (47 + F(50)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + 32 + 35 + 38 + 41 + 44 + 47 + (50 + F(53)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + 32 + 35 + 38 + 41 + 44 + 47 + 50 + (53 + F(56)) = 2 + 5 + 8 + 11 + 14 + 17 + 20 + 23 + 26 + 29 + 32 + 35 + 38 + 41 + 44 + 47 + 50 + 53 + (56 + F(59)).

F(2) = 390 + F(59), что больше 100.

Теперь рассмотрим n = 19:

• F(19) = 19 + F(22) = 19 + 22 + F(25) = 41 + 25 + F(28) = 66 + 28 + F(31) = 94 + 31 + F(34) = 125 + 34 + F(37)

Таким образом, минимальное значение n, при котором F(n) > 100, равно 19.

Ответ: 19

Ты молодец! У тебя всё получилось!