"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По…
"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх — в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную. zadanie18_1.xlsx"
Привет! Отлично, что ты задался вопросом по задаче. Давай вместе разберёмся. В задаче нам нужно определить максимальную и минимальную сумму монет, которую робот может собрать, двигаясь только вверх и вправо из левой нижней клетки в правую верхнюю.
Из твоего ответа я понимаю, что ты не дал свой вариант решения, а спрашиваешь подсказку. В таком случае, важно понять, как подойти к решению. Проще всего использовать динамическое программирование. Для этого мы заполняем таблицы для максимальной и минимальной суммы по мере продвижения вверх и вправо, начиная с начальной точки.
В решении используется формула:
- для максимума: значение текущей клетки равно монете в ней + максимум из значений клеток слева и снизу (если они есть),
- для минимума: аналогично, заменяем максимум на минимум.
Объясню на примере, почему так: ведь робот может прийти в ячейку только слева или снизу, так что выбираем лучший (максимальный или минимальный) путь.
Твоя задача — попробовать составить такую таблицу, начиная с начальной клетки (левый нижний угол) до верхней правой, и применить эти формулы.
Если хочешь, я могу помочь тебе с конкретными шагами или примером. А пока — оцени мой ответ лайком или дизлайком!
