Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите решить срочно!

Сергей Кузнецов Ученик (95), на голосовании 4 месяца назад
Обозначим через mod(a, b) остаток от деления натурального числа a на натуральное число b. Алгоритм вычисления значения функции F(n), где n  - целое неотрицательное число, задан следующими соотношениями: F(0) = 0; F(n) = F(n / 3), если n > 0 и при этом mod(n, 3)  =  0; F(n) = mod(n, 3) + F(n − mod(n, 3)), если mod(n, 3) > 0. Назовите минимальное значение n, для которого F(n) = 9.
Голосование за лучший ответ
Shaolin Мыслитель (6836) 5 месяцев назад
Анализ алгоритма:

• Базовый случай: F(0) = 0.
• Деление на 3: Если число n делится на 3 (mod(n, 3) = 0), то функция F(n) равна значению функции F для числа n, деленного на 3.
• Остаток от деления: Если число n не делится на 3 (mod(n, 3) > 0), то функция F(n) равна сумме остатка от деления n на 3 и значения функции F для числа n, уменьшенного на этот остаток.

Поиск минимального n:

Давайте посмотрим, как работает функция для небольших значений n:

• F(1) = 1 + F(0) = 1
• F(2) = 2 + F(0) = 2
• F(3) = F(1) = 1
• F(4) = 1 + F(1) = 2
• F(5) = 2 + F(2) = 4
• F(6) = F(2) = 2
• F(7) = 1 + F(4) = 3
• F(8) = 2 + F(5) = 6
• F(9) = F(3) = 1
• F(10) = 1 + F(7) = 4
• F(11) = 2 + F(8) = 8
• F(12) = F(4) = 2
• F(13) = 1 + F(10) = 5
• F(14) = 2 + F(11) = 10
• F(15) = F(5) = 4
• F(16) = 1 + F(13) = 6
• F(17) = 2 + F(14) = 12
• F(18) = F(6) = 2
• F(19) = 1 + F(16) = 7
• F(20) = 2 + F(17) = 14
• F(21) = F(7) = 3
• F(22) = 1 + F(19) = 8
• F(23) = 2 + F(20) = 16
• F(24) = F(8) = 6
• F(25) = 1 + F(22) = 9

Ответ: Минимальное значение n, для которого F(n) = 9, равно 25.

Вроде так
S.H.I. Оракул (69133) 5 месяцев назад
161
 def F(n): 
if n == 0:
return 0
elif n % 3 == 0:
return F(n // 3)
else:
return n % 3 + F(n - (n % 3))

n = 1
while F(n) != 9:
n += 1

print(n)
Похожие вопросы