Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела рекурсия
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#56475

Алгоритм вычисления значения функции F(x, y, z), где x, y, z - натуральные числа, задан следующим образом:

F (x,y,z) = 0,  если x = 11,y = 13,z = 17  ,

            18
F (x,y,z) = 10 ,  если x < 0  , либо y < 0  , либо z < 0,

F (x,y,z) = min (F(x− 1,y,z),F (x,y− 1,z),F (x,y,z − 1))+ 1,  иначе

Вычислите F (105,106,107).

Показать ответ и решение

Заметим, что функция ищет манхэттенское расстояние в 3хмерном простанстве между точками (x,y,z)  и (11,13,17)  . Причем работает корректно только если x >= 11,y >= 13,z >= 17  .

Примечание: Манхеттенское расстояние, или расстояние городских кварталов - расстояние между двумя точками в n-мерном пространстве равное сумме модулей разностей их координат. Для 2хмерного пространства можно представить себе уличную планировку города Манхеттен, а именно квадратную сетку, где мы можем ходить только по этой сетке и расстояние между двумя ближайшими пересечениями равно единице.

PIC

Можем заметить, что сумма координат минус значение функции от этих координат всегда равно сумме координат точки, до которой мы ищём расстояние(11+ 13+ 17 = 41)

Иными словами здесь инвариантом является x + y+ z − f(x,y,z) = 41  .

Отсюда можем выразить f(x,y,z) = x+ y +z − 41

Ответ: f (x,y,z) = 105 +106 + 107 − 41 = 11099959

Ответ: 11099959

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!