Динамическое программирование электронные таблицы

Содержание

Задание 18 ЕГЭ информатика по теме «Обработка числовой информации в электронных таблицах»
ЕГЭ по информатике 18 задание объяснение
Решение 18 задания ЕГЭ
Исполнитель Робот
Тема Динамическое программирование
18 (повышенный уровень, время – 6 мин)
Пример задания:
Пример задания:
Динамическое программирование
18 (повышенный уровень, время – 6 мин)
Пример задания:
Пример задания:

Задание 18 ЕГЭ информатика по теме «Обработка числовой информации в электронных таблицах»

На уроке рассмотрен материал для подготовки к ЕГЭ по информатике, разбор 18 задания. Объясняется тема об обработке числовой информации в электронных таблицах.

ЕГЭ по информатике 18 задание объяснение

18-е задание: «Обработка числовой информации в электронных таблицах»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — да,
Максимальный балл — 1,
Примерное время выполнения — 6 минут.

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

Решение 18 задания ЕГЭ

Плейлист видеоразборов задания на YouTube:

Исполнитель Робот

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

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

Ответ: 1204 | 502
Решение подобного задания смотрите в следующем ниже разборе.
📹 YouTube здесь

Видеорешение на RuTube здесь

Исходные данные записаны в файле (выше) в виде электронной таблицы прямоугольной формы.
Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой НИЖНЕЙ клетки в правую ВЕРХНЮЮ. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Ответ: 1133 | 522

При попытке зайти на клетку со стеной Робот разрушается. Исходные данные записаны в файле в виде электронной таблицы прямоугольной формы. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю, не разрушившись. Известно, что такой путь существует. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

=ЕСЛИ(И(L25>0;ИЛИ(K12=500));K12+L25;0)

Если выполняются одновременно два условия: L25>0 И либо K12 либо K12>=500 , то собираем монету с текущей ячейки ( K12 ) и добавляем монету с L25 , так как там нет стены ( L25>0 )

=ЕСЛИ(И(L25>0;ИЛИ(L11=500));L11+L25;0)

Если выполняются одновременно два условия: L25>0 И либо L11 либо L11>=500 , то собираем монету с текущей ячейки ( L11 ) и добавляем монету с L25 , так как там нет стены ( L25>0 )

Здесь логика формулы следующая: если текущее значение ячейки соответствует стене, то записываем 0; ИНАЧЕ — если обе ячейки, в которые может двигаться Робот, — стены, то записываем в текущую ячейку 0; ИНАЧЕ — если ячейка справа — стена, то двигаемся вниз, собирая по пути монеты; ИНАЧЕ — если ячейка снизу — стена, то двигаемся вправо, собирая по пути монеты; ИНАЧЕ — выбираем минимальное значение из соседних ячеек и собираем монеты.

Ответ: 1492 640

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

формула для J21: =ЕСЛИ(ОСТАТ(J10;8)=0;J10;8*ЧАСТНОЕ(J10;8))

формула для J20: =ЕСЛИ(ОСТАТ(J9;8)=0;J9+J21;8*ЧАСТНОЕ(J9;8)+J21)

формула для I21: =ЕСЛИ(ОСТАТ(I10;8)=0;I10+J21;8*ЧАСТНОЕ(I10;8)+J21)

формула для I20: =ЕСЛИ(ОСТАТ(I9;8)=0;I9+МАКС(J20;I21);8*ЧАСТНОЕ(I9;8)+МАКС(J20;I21))

Источник

Тема Динамическое программирование

Единственный в мире Музей Смайликов

Самая яркая достопримечательность Крыма

Скачать 1.13 Mb.

18 (повышенный уровень, время – 6 мин)

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

3.4.3. Использование инструментов решения статистических и расчётно-графических задач.

1.1.2. Умение представлять и анализировать табличную информацию в виде графиков и диаграмм.

в задачах, которые предлагаются в этом задании КИМ, нужно найти оптимальный путь для Робота, который перемещается на клетчатом поле. Робот может на каждом шаге выбирать одно из двух направлений движения (например, только вправо и вниз).
в каждой клетке Робот получает некоторую награду («берёт монету»), и нужно найти такой путь, при котором общая награда будет наибольшая (или наименьшая, если это не награда, а штраф)
конечно, теоретически можно решить такую задачу полным перебором вариантов: рассмотреть все возможные пути и выбрать лучший. Однако количество возможных путей для полей даже не очень большого размера слишком велико для того, чтобы решить эту задачу за время проведения ЕГЭ, даже если вам удастся безошибочно написать программу для такого перебора.
эта задача успешно и быстро решается с помощью динамического программирования – метода оптимизации, который предложил американский математик Ричард Беллман. Он сформулировал очень простой принцип оптимальности пути: любая часть оптимального пути оптимальна. Например, пусть мы нашли оптимальный путь из точки А и точку Б, который проходит через точки В, Г и Д:

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

Пример задания:

Р-01 (А. Кабанов). Дана последовательность натуральных чисел. Рассматриваются всевозможные пары чисел, номера которых i и j в последовательности различаются не более чем на 5 (i+1  j  i+5). Определите количество таких пар, в которых сумма чисел меньше 100. Исходная последовательность записана в виде одной строки электронной таблицы.

Решение (электронные таблицы):

Рассмотрим решение на примере следующей таблицы.

Для определённости будем двигаться справа налево. Для каждого числа a_i рассмотрим набор из пяти предыдущих чисел (если таковые существуют). Число a_i будет образовывать подходящие пары с числами, меньшими 100 – a_i. С помощью формулы СЧЁТЕСЛИ подсчитаем, сколько из предыдущих пяти чисел меньше 100 – a_i. Например, в ячейке F2 формула будет иметь вид =СЧЁТЕСЛИ(A1:E1;»
ifstream file_name(«18-0.csv»);

char delimiter = ‘;’; //Разделитель

vector > data; //Записываем всю таблицу

string s; //Считываем из фала в строку

stringstream stream(s); // Преобразуем в поток

vector d; // Будем записывать значения,

// которые будут в строке

while(getline(stream, num, delimiter))

d.push_back(atoi(num.c_str()));

calc[N — 1][M — 1] = data[N — 1][M — 1];

for(int i = M — 2; i >= 0; i—)

calc[N — 1][i] = data[N-1][i] + calc[N-1][i+1];

for(int i = N — 2; i >= 0; i—)

calc[i][M — 1] = data[i][M — 1] + calc[i + 1][M — 1];

for(int i = N — 2; i >= 0; i—)

for(int j = M — 2; j >= 0; j—)

max(calc[i][j + 1], calc[i + 1][j]);

cout Arrays.stream(line.split(«;»))

final int N = data.length;

final int M = data[0].length;

// заполняем первую строку

Источник

Динамическое программирование

Единственный в мире Музей Смайликов

Самая яркая достопримечательность Крыма

Скачать 0.98 Mb.

18 (повышенный уровень, время – 6 мин)

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

3.4.3. Использование инструментов решения статистических и расчётно-графических задач.

1.1.2. Умение представлять и анализировать табличную информацию в виде графиков и диаграмм.
- в задачах, которые предлагаются в этом задании КИМ, нужно найти оптимальный путь для Робота, который перемещается на клетчатом поле. Робот может на каждом шаге выбирать одно из двух направлений движения (например, только вправо и вниз).
- в каждой клетке Робот получает некоторую награду («берёт монету»), и нужно найти такой путь, при котором общая награда будет наибольшая (или наименьшая, если это не награда, а штраф)
- конечно, теоретически можно решить такую задачу полным перебором вариантов: рассмотреть все возможные пути и выбрать лучший. Однако количество возможных путей для полей даже не очень большого размера слишком велико для того, чтобы решить эту задачу за время проведения ЕГЭ, даже если вам удастся безошибочно написать программу для такого перебора.
- эта задача успешно и быстро решается с помощью динамического программирования – метода оптимизации, который предложил американский математик Ричард Беллман. Он сформулировал очень простой принцип оптимальности пути: любая часть оптимального пути оптимальна. Например, пусть мы нашли оптимальный путь из точки А и точку Б, который проходит через точки В, Г и Д:
- рассмотрим применение динамического программирования на простом примере: Робот идёт по клетчатому полю из левого верхнего угла в правый нижний; на каждом шаге он может переместиться на одну клетку вправо или на одну клетку вниз. В каждой клетке лежит заданное количество монет:
Пример задания:

Пример задания:

Р-01 (А. Кабанов). Дана последовательность натуральных чисел. Рассматриваются всевозможные пары чисел, номера которых i и j в последовательности различаются не более чем на 5 (i+1  j  i+5). Определите количество таких пар, в которых сумма чисел меньше 100. Исходная последовательность записана в виде одной строки электронной таблицы.

Решение (электронные таблицы):
1. Рассмотрим решение на примере следующей таблицы.
1. Для определённости будем двигаться справа налево. Для каждого числа a_i рассмотрим набор из пяти предыдущих чисел (если таковые существуют). Число a_i будет образовывать подходящие пары с числами, меньшими 100 – a_i. С помощью формулы СЧЁТЕСЛИ подсчитаем, сколько из предыдущих пяти чисел меньше 100 – a_i. Например, в ячейке F2 формула будет иметь вид =СЧЁТЕСЛИ(A1:E1;»
  ifstream file_name(«18-0.csv»);
  
  char delimiter = ‘;’; //Разделитель
  
  vector > data; //Записываем всю таблицу
  
  string s; //Считываем из фала в строку
  
  stringstream stream(s); // Преобразуем в поток
  
  vector d; // Будем записывать значения,
  
  // которые будут в строке
  
  while(getline(stream, num, delimiter))
  
  d.push_back(atoi(num.c_str()));
  
  calc[N — 1][M — 1] = data[N — 1][M — 1];
  
  for(int i = M — 2; i >= 0; i—)
  
  calc[N — 1][i] = data[N-1][i] + calc[N-1][i+1];
  
  for(int i = N — 2; i >= 0; i—)
  
  calc[i][M — 1] = data[i][M — 1] + calc[i + 1][M — 1];
  
  for(int i = N — 2; i >= 0; i—)
  
  for(int j = M — 2; j >= 0; j—)
  
  max(calc[i][j + 1], calc[i + 1][j]);
  
  cout Arrays.stream(line.split(«;»))
  
  final int N = data.length;
  
  final int M = data[0].length;
  
  // заполняем первую строку
  
  Источник
  
  Читайте также: Magicar 5 scher khan таблица программирования