Презентация "Динамическое программирование (КИМ 18 - стены)"

Динамическое программирование (стены)

ЕГЭ, КИМ 18 учитель МБОУ СОШ с.Тербуны

Болгова Н.А.

КИМ 18 -П = 6 мин

Алгоритм

• Выделить таблицу, поставить внешние границы
• Скопировать таблицу
• Правой кнопкой – специальная вставка - вставить только формат

Поиск max

1 способ

1)В ячейке А15 вводим формулу:

= А1

2)В ячейке В15 вводим формулу: =ЕСЛИ(ИЛИ(B1=500); A15+B1;"stop")

( если в ячейке В1 нет стены, то добавляем к сумме (А1) монету из В1)

3) Аналогично для ячейки А16

=ЕСЛИ(ИЛИ(B1=500);A15+B1;"stop")

B15

=ЕСЛИ(ИЛИ(A2=500);A15+A2;"stop")

A16

4)В ячейке А23 вводим формулу:

=ЕСЛИ(И(ИЛИ(A9=500);A22"stop")

;A22+A9;"stop")

5)В ячейке В16 вводим формулу:

=ЕСЛИ(И(ИЛИ(B2=500);B15"stop";A16"stop“);B2+МАКС(B15;A16);"stop")

Пояснение

=ЕСЛИ(И(ИЛИ(B2=500);B15"stop";A16"stop“) – условие ( если ячейка В2 не стена и ячейки А16 и В15 не равны «стоп»)

B2+МАКС(B15;A16) – к максимальной сумме (В15 или А16) добавляем монеты из В2

"stop") – при неверном условии - стоп

Поиск max

6) Для ячеек, граничащих со стеной (желтый цвет заливки на рис), необходимо изменить формулу:

B32: = B8+B21

(+ячейка выше)

C20: =C6+B20

(+ячейка слева)

Поиск min

• Копируем таблицы 1 и 2

• Вставляем на новый лист

• В формулах делаем замену функции МАКС на МИН

Поиск min

Ответ:1492, 640

Поиск max

2 способ

1) Закрасим стены (красный) и граничащие ячейки (желтый)

2)В ячейке А15 вводим формулу: = А1

2)В ячейке В15 вводим формулу: =A15+B1

3) Копируем формулу из В15 до стены

4 ) Аналогично для А16

5)В ячейке А16 вводим формулу:

= B2+МАКС(B15;A16)

6) Копируем для «непроблемных» ячеек (серый цвет)

7) В «проблемных» ячейках (желтый цвет) при движении Робота вниз - складываем с верхней ячейкой , при движении вправо – складываем с левой ячейкой

В ячейке В22 вводим формулу :

=В8 + В21

В ячейке С22 вводим формулу :

=С8 + В22

=B8+B21

7) «проблемные» ячейки (желтый цвет) при движении Робота вниз - складываем с верхней ячейкой

7) «проблемные» ячейки (желтый цвет) при движении вправо - складываем с левой ячейкой

8) Копируем формулу поиска максимальной суммы (серый цвет)

9) ответ: максимальная сумма - 1492

Поиск min

• Копируем таблицы 1 и 2

• Вставляем на новый лист

• В формулах делаем замену функции МАКС на МИН

Литература:

• Сайт Константина Полякова «ЕГЭ по информатике 2023» , задание 18 + файлы к заданиям. [https://kpolyakov.spb.ru/school/ege.htm]