Максимум и минимум монет

ЕГЭ · Информатика · Тапсырма 8 · Динамикалық бағдарламалау

ЖоғарыФИПИF7EDCCҚысқа жауап≈ 10 минут

Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Исполнитель Робот может перемещаться только вправо или вниз, если между соседними клетками нет стены. Посетив клетку, Робот забирает находящуюся в ней монету, включая начальную и конечную клетки маршрута. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. Исходные данные представлены в прилагаемом файле — электронной таблице размером $N \times N$; внутренние и внешние стены обозначены утолщёнными линиями.

Файл тапсырмаға

F7EDCC.zipАрхив ZIP · 34 КБВнутри: 1_18.xls, 1_18.xlsx, 1_18.ods

Условие как в банке ФИПИ — открыть и сверить

Дұрыс жауапты жазыңыз.

Тапсырма выполняется с использованием прилагаемых
файлов.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо немесе вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз –
в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

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

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

Пример входных данных

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Сіздің жауабыңыз

Формат: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.

3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, алдыңғысы оқылған кезде, — жауапқа бірден секіріп кетпеу үшін.

1Мягкая — с чего смотретьдеңгей 1 из 3

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

2Жетекші — қандай сандарды есептеудеңгей 2 из 3

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

3Тікелей — іс жүзінде шешімдеңгей 3 из 3

Заполните две таблицы динамического программирования с учётом стен. В правой нижней клетке первой таблицы получится максимальная сумма, а второй — минимальная.

Всё равно не складывается?Полное Шешім с обоснованием каждого шага — на отдельной странице.

Шешімді ашу

ПредыдущаяМаксимальная и минимальная суммаСледующаяВычисление рекурсивной функции

Тапсырма 8 ЕГЭ, информатика