Проверь мой ответ на задание ЕГЭ по предмету Информатика. Задание: 18. Текст задания: "Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В правом верхнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку влево, вниз или по диагонали влево вниз. Выходить за пределы квадрата робот не может. Необходимо переместить робота в левый нижний угол так, чтобы сумма чисел в клетках, через которые прошёл робот (включая начальную и конечную), была максимальной. В ответе запишите максимально возможную сумму. Исходные данные записаны в электронной таблице. Задание 18 Пример входных данных (для таблицы размером 4 × 4): 4 21 −36 11 37 −12 29 7 −30 24 −1 −5 8 −8 9 21 Для указанных входных данных ответом будет число 79 (робот проходит через клетки с числами 11, 7, 29, 24, 8)." Мой ответ: "918" Верный ответ на это задание: "842" Ответ структурируй: Скажи, правильно ли я ответил на задание, Коротко объясни все термины и понятия, которые нужны для решения задания, и Объясни, как нужно было решать это задание Твой ответ не должен превышать 4096 токенов

Question 1

Задача Задача №9433

А

Аноним

05 июня 2023 07:53 · публичный вопрос

А

Аноним 05 июня 2023 07:53

Проверь мой ответ на задание ЕГЭ по предмету Информатика. Задание: 18. Текст задания: "Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В правом верхнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку влево, вниз или по диагонали влево вниз. Выходить за пределы квадрата робот не может. Необходимо переместить робота в левый нижний угол так, чтобы сумма чисел в клетках, через которые прошёл робот (включая начальную и конечную), была максимальной. В ответе запишите максимально возможную сумму. Исходные данные записаны в электронной таблице. Задание 18 Пример входных данных (для таблицы размером 4 × 4): 4 21 −36 11 37 −12 29 7 −30 24 −1 −5 8 −8 9 21 Для указанных входных данных ответом будет число 79 (робот проходит через клетки с числами 11, 7, 29, 24, 8)." Мой ответ: "918" Верный ответ на это задание: "842" Ответ структурируй: Скажи, правильно ли я ответил на задание, Коротко объясни все термины и понятия, которые нужны для решения задания, и Объясни, как нужно было решать это задание Твой ответ не должен превышать 4096 токенов

Answer

Твой ответ на задание не верный.

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

Заполнять новую таблицу нужно следующим образом: для первой строки и первого столбца ее заполняем, как сумму предыдущего значения и текущей клетки, т.е. для первой строки ячейки заполняются так: dp[0][i] = dp[0][i-1] + a[0][i], аналогично для первого столбца. Для всех остальных клеток матрицы мы смотрим на максимальную сумму, которую можно получить "сверху", "слева" и "по диагонали сверху слева" и суммируем ее с текущей клеткой.

Таким образом мы можем заполнить всю таблицу и найти максимальную сумму, которая была набрана в последней клетке.

В твоем ответе не была учтена особенность данной задачи - она относится к задачам на динамическое программирование, находить максимально возможную сумму по клеткам надо через последовательно пройденные клетки.

Пожалуйста, оцени мой ответ лайком или дизлайком.

Question 2

Проверь мой ответ на задание ЕГЭ по предмету Информатика. Задание: 18. Текст задания: "Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В правом верхнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку влево, вниз или по диагонали влево вниз. Выходить за пределы квадрата робот не может. Необходимо переместить робота в левый нижний угол так, чтобы сумма чисел в клетках, через которые прошёл робот (включая начальную и конечную), была максимальной. В ответе запишите максимально возможную сумму. Исходные данные записаны в электронной таблице. Задание 18 Пример входных данных (для таблицы размером 4 × 4): 4 21 −36 11 37 −12 29 7 −30 24 −1 −5 8 −8 9 21 Для указанных входных данных ответом будет число 79 (робот проходит через клетки с числами 11, 7, 29, 24, 8)." Мой ответ: "918" Верный ответ на это задание: "842" Ответ структурируй: Скажи, правильно ли я ответил на задание, Коротко объясни все термины и понятия, которые нужны для решения задания, и Объясни, как нужно было решать это задание Твой ответ не должен превышать 4096 токенов

Answer

Твой ответ на задание не верный. Для прохождения данного задания нужно использовать динамическое программирование, которое заключается в следующем: мы создаем новую таблицу размером с исходную таблицу, в которой мы будем хранить на каждом шаге, какая максимальная сумма была набрана в данной клетке. Заполнять новую таблицу нужно следующим образом: для первой строки и первого столбца ее заполняем, как сумму предыдущего значения и текущей клетки, т.е. для первой строки ячейки заполняются так: dp[0][i] = dp[0][i-1] + a[0][i], аналогично для первого столбца. Для всех остальных клеток матрицы мы смотрим на максимальную сумму, которую можно получить "сверху", "слева" и "по диагонали сверху слева" и суммируем ее с текущей клеткой. Таким образом мы можем заполнить всю таблицу и найти максимальную сумму, которая была набрана в последней клетке. В твоем ответе не была учтена особенность данной задачи - она относится к задачам на динамическое программирование, находить максимально возможную сумму по клеткам надо через последовательно пройденные клетки. Пожалуйста, оцени мой ответ лайком или дизлайком.