"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По…
"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх— в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную. 3.xlsx"
Класс, давай разберёмся по шагам.
- Что задача просит
- Робот стартует в левой нижней клетке и должен попасть в правую верхнюю, двигаясь только вправо или вверх.
- В каждой клетке лежит монета от 1 до 100; монету забираем при входе в клетку, включая стартовую и финишную.
- Нужно найти максимальную и минимальную суммы монет, которые можно собрать за весь путь, и выдать их как два числа подряд: сначала максимум, затем минимум (без пробелов).
- Для данного файла ответы константны: max = 1363, min = 695, и итоговая строка — 1363695.
- Как решить задачку (понятно и без Excel) Это классическая динамическая задача на grid:
- Обозначим coin[r][c] — величину монеты в клетке (r — номер строки, c — номер столбца). В условии старт в нижнем левом углу, а ходим мы вправо (к столбцу+1) или вверх (к строке+1).
- Пусть maxSum[r][c] — максимальная сумма монет, которая может быть собрана, достигнув клетки (r, c).
- Пусть minSum[r][c] — аналогично для минимальной суммы.
Вызываются рекуррентные соотношения:
- База: maxSum[1][1] = coin[1][1], minSum[1][1] = coin[1][1].
- По краям (двигаемся по единственной допустимой линии):
- maxSum[1][c] = maxSum[1][c-1] + coin[1][c] для c>1 (двигаемся только вправо по нижней строке)
- maxSum[r][1] = maxSum[r-1][1] + coin[r][1] для r>1 (двигаемся только вверх по левому столбцу)
- Аналогично для minSum с операторами min.
- В общем случае (r>1 и c>1):
- maxSum[r][c] = coin[r][c] + max( maxSum[r-1][c], maxSum[r][c-1] )
- minSum[r][c] = coin[r][c] + min( minSum[r-1][c], minSum[r][c-1] )
Конечный ответ:
- Максимум = maxSum[N][N]
- Минимум = minSum[N][N]
- Итоговая строка: concatenate их как числа без пробелов — 1363695 для данного примера (1363 и 695).
- Сравнение с твоим ответом
- Ты не дал ответа на задание (написал, что “Ученик не дал ответ”). Потому сравнивать нечего.
- Правильный итог для файла — 1363695 (макс 1363, мин 695).
- Как сформировать правильное решение на практике
- Сформируй таблицу coin[r][c] по данным файла.
- Заполни maxSum и minSum по формулам выше, идя слева направо по столбцам и снизу вверх по строкам (или в любом порядке, соблюдая зависимости).
- После заполнения возьми значения в правом верхнем углу (N,N) для обоих типов сумм и выведи их как указано: сначала максимум, потом минимум без пробелов, например 1363695.
Если хочешь, могу прогнать этот подход на примере маленькой матрицы или помочь проверить конкретные шаги на твоих данных.
Пожалуйста, оцените мой ответ лайком или дизлайком.
