Решение 18 задачи по Информатике. Горюшкина И.В._18 задание. Уровень сложности повышенный 1 Макс первичный балл 1 балл 2 Время выполнения

Название	Уровень сложности повышенный 1 Макс первичный балл 1 балл 2 Время выполнения
Анкор	Решение 18 задачи по Информатике
Дата	26.11.2022
Размер	4.83 Mb.
Формат файла
Имя файла	Горюшкина И.В._18 задание.ppt
Тип	Задача #813767

Уровень сложности - повышенный

1

Макс. первичный балл – 1 балл

2

Время выполнения – 6 мин

3

Проверяемые элементы

Умение обрабатывать вещественные выражения в электронных таблицах.

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

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

Задача №1
(Стандартная)
Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх — в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монеты с собой; это также относится к начальной и конечной клетке маршрута Робота.

Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
1 8 8 4
10 1 1 3
1 3 12 2
2 3 5 6
Для указанных входных данных ответом должна быть пара чисел 35 и 15.

Открываем файл к данной задаче.

Открываем файл к данной задаче.
В начале найдём максимальную сумму.

Обозначим мысленно ту область, где мы будем составлять наше решение, пропустив одну или две строчки снизу. По размеру область будет такая же.

В каждой ячейке этой области будет лежать максимальная cумма, которую может собрать Робот, дойдя до этой клетки. Т.к. Робот идёт в верхнюю правую клетку, то, соответственно, в ячейке K12 будет находится нужный нам ответ. Наш Робот идёт из левой нижней клетки. Поэтому формулу, решающую эту задачу, составим сначала для ячейки B21. Кликаем на ячейку B21 и пишем формулу: =МАКС(A21;B22)+B10

После того, как столбец готов, выделяем этот столбец, и аналогично, распространяем его на всё пространство.

В итоге получается такая картина:

Аналогичным образом ищется минимальное значение, только в формуле вместо функции МАКС будет использоваться функция МИН.

Протестируем на примере и сверим ответы.

Максимальное значение получилось 1298.
Минимальное значение получилось 589.
Ответ: 1298589

Задача №2

Задача №2
(Два Робота)
Квадрат разлинован на N×N клеток (2 < N < 19). В каждой клетке лежат монеты, количество которых соответствует записанному числу. Количество монет не может быть меньше 1.
Два исполнителя – ВЕРХ и НИЗ – существуют на одинаковых полях. Первый имеет две команды – вверх и вправо, второй – вниз и вправо, которые, соответственно, перемещают исполнитель на одну клетку вверх, вниз или вправо. Исполнитель ВЕРХ начинает движение в левой нижней ячейке, исполнитель НИЗ – в левой верхней.

Откройте файл. Какой из исполнителей соберет большее количество монет в результате своей работы, если известно, что каждый из них запрограммирован собрать максимальное количество монет?
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пример:
1 8 8 4 10
10 1 1 3 2
1 3 12 2 8
2 3 5 6 11
3 19 14 11 5
Для указанных входных данных ответом является комбинация из названия исполнителя и количества собранных монет
ВЕРХ84

Решение: Перенесём таблицу чисел на один столбец вправо.

Найдём, сколько соберёт монет исполнитель ВЕРХ.
Исполнитель "ВЕРХ" начинает идти с левой нижней клетки. Поэтому первую формулу мы зададим для клетки B27. Эта ячейка является нижней левой клеткой для области, где мы будем составлять решение.
Напишем в ячейке B27:
=МАКС(A27;B28)+B13

Распространим формулу на всё пространство.

Когда исполнитель пройдёт всё поле, в ячейке N15 будет находится ответ. Максимальное количество монет, которое может собрать исполнитель ВЕРХ будет 1743.
Теперь найдём максимальное количество монет, которое может собрать исполнитель НИЗ. Решать будем аналогичным образом, удалив все следы от предыдущего исполнителя.

Т.к. исполнитель НИЗ стартует с левой верхней клетки, то мы сначала составим формулу для ячейки B15. Эта клетка олицетворяет левую верхнюю ячейку для области, где будет происходить решение.
=МАКС(B14;A15)+B1

В ячейке N27 будет максимальное значение для исполнителя НИЗ. Получилось 1686.
Видим, что у исполнителя ВЕРХ получилось собрать больше монет.
Ответ: ВЕРХ1743

Задача №3

Задача №3
(Роботы встречаются в одной из клеток) Квадрат разлинован на N×N клеток (2 < N < 20), N – нечетное число. В каждой клетке лежат монеты, количество которых соответствует записанному числу. Количество монет не может быть меньше 1.
Два исполнителя – ПРАВО и ЛЕВО – существуют в рамках одного поля. Первый имеет две команды – вверх и вправо, второй – вверх и влево, которые, соответственно, перемещают исполнитель на одну клетку вверх, вправо или влево. Исполнитель ПРАВО начинает движение в левой нижней ячейке, исполнитель ЛЕВО – в правой нижней.
Исполнители обязательно встречают в одной из клеток, находящихся в среднем столбце. При этом движение вверх по данному столбцу запрещено.
Например, при работе в квадрате 5х5 исполнители встречаются в одной из клеток третьего столбца. Какую максимальную сумму монет могут собрать исполнители.

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

Пример входных данных:
1 4 3 1 2
10 1 1 3 2
1 3 13 10 8
2 3 5 6 11
3 19 14 11 5
Для указанных входных данных ответом является число 75 (3+19+3+3, 5+11+8+10, 13)

Решение: Перенесём таблицу чисел на один столбец вправо.
Роботы должны встретиться в среднем столбце.
Один робот перемещается в левой части таблицы, другой в правой.

Найдём максимальное значение суммы количества монет для каждой ячейки левой и правой области (исключая средний столбец).
Составим формулу для исполнителя ПРАВО в ячейке B27:
=МАКС(A27;B28)+B13

Применим данную формулу на левую часть рабочей области.

Теперь составим формулу для исполнителя ЛЕВО в ячейке N27:
=МАКС(N28;O27)+N13

Применим эту формулу для правой части рабочей области.
Получается следующая картина:

Теперь нужно заполнить средний столбец и определить, где сумма получится наибольшая. Пишем в ячейку H15: =G15+H1+I15

Распространяем данную формулу на весь столбец H внутри рабочей области

Видим, что максимальное значение в среднем столбце будет 22884.
Это и будет ответ.
Ответ: 22884

Задача №4
(Ладья, см. Статград , февраль 2021)

В ячейку Q1 мы запишем формулу = А1

В ячейку R1 будет записана сумма значений из ячейки В1 первой таблицу и максимального значения из впереди стоящих чисел из второй таблицы.

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

Аналогичные действия выполняем и по вертикали, только фиксируем номер строки.

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

Применяем данную формулу ко всей таблице, мы получаем максимальное значение равное 323

Проверим наше решение на примере.

https://www.youtube.com/channel/UCxAZM_7sunA166ycxTj0Etw
(Alex Danov)
https://www.youtube.com/channel/UCua84AO42i-WrLAIsGn6QYg
(Информатика от блондинки)

Спасибо за внимание!