Проверь мой ответ на задание ЕГЭ по предмету Информатика. Задание: 18. Текст задания: "Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Определите минимальную и максимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. №18.xlsx ЛИСТ 9 (Переключение между листами находится внизу Exel) В ответе укажите два числа — сначала минимальную сумму, затем максимальную без разделительных знаков." Мой ответ: "11242721" Верный ответ на это задание: "9641973" Ответ структурируй: Скажи, правильно ли я ответил на задание, Коротко объясни все термины и понятия, которые нужны для решения задания, и Объясни, как нужно было решать это задание Твой ответ не должен превышать 4096 токенов
Твой ответ на задание №18 неверный, попробуем разобраться, как решить это задание правильно. В задании дан квадрат, по которому перемещается робот. Робот может двигаться только вниз или вправо. В каждой ячейке квадрата находится монета определенного достоинства. Задача робота - набрать наибольшее количество монет при проходе из левой верхней клетки в правую нижнюю, собирая монеты и двигаясь только по свободным клеткам.
Для решения данной задачи необходимо использовать динамическое программирование. Создадим массив D размером n x m, где n - количество строк в квадрате, m - количество столбцов. Заполним ячейки массива максимально возможными суммами денег, которые могут быть набраны роботом при проходе из левой верхней клетки в данную ячейку квадрата. Рассмотрим два случая:
Если робот проходит через клетку с координатами (i, j), набрав монету в этой клетке, то максимальная сумма денег, которая может быть набрана роботом при проходе из левой верхней клетки в эту клетку, равна сумме денег, которая была набрана при проходе из левой верхней клетки в клетку (i-1, j) и монеты, находящейся в клетке (i, j).
Если робот проходит через клетку с координатами (i, j), но не набирает монету в этой клетке, то максимальная сумма денег, которая может быть набрана роботом при проходе из левой верхней клетки в эту клетку, равна сумме денег, которая была набрана при проходе из левой верхней клетки в клетку (i-1, j) или (i, j-1), в зависимости от того, в какой клетке монету не набрали.
После того, как мы заполнили все ячейки массива D, максимальная сумма денег, которую может набрать робот при проходе из левой верхней клетки в правую нижнюю, будет находиться в ячейке (n, m) массива D. Также необходимо найти минимально возможную сумму денег, которую может набрать робот. Для этого можно использовать аналогичный алгоритм, только заполнять массив минимальными суммами, вместо максимальных.
Проверь свой ответ, если есть ошибки, то попробуй решить задачу снова, используя эту подсказку. Помогла ли тебе моя подсказка? Оцени мой ответ лайком или дизлайком.
