Информатика егэ номер 18 Здравствуйте составить формулу
Робот может двигаться только вниз или вправо. При попытке зайти на клетку со стеной Робот разрушается. Исходные данные записаны в файле 18-11.xls в виде электронной таблицы прямоугольной формы. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю, не разрушившись. Известно, что такой путь существует. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Шаг 1: Прочитать данные из файла 18-11.xls
Шаг 2: Создать матрицу размером n на m (где n - количество строк в таблице, m - количество столбцов в таблице) и заполнить ее значениями из электронной таблицы.
Шаг 3: Создать две дополнительные матрицы, которые будут хранить максимальную и минимальную денежные суммы для каждой клетки в таблице. Назовем их max_matrix и min_matrix соответственно.
Шаг 4: Начиная с левой верхней клетки, для каждой клетки таблицы рассчитать максимальную и минимальную сумму, которую можно собрать, двигаясь только вниз или вправо.
Шаг 5: Заполнить max_matrix и min_matrix значениями, используя следующее рекуррентное соотношение:
- Для клетки (i, j), где i > 0 и j > 0:
max_matrix[i][j] = max(max_matrix[i-1][j], max_matrix[i][j-1]) + value[i][j]
min_matrix[i][j] = min(min_matrix[i-1][j], min_matrix[i][j-1]) + value[i][j]
- Для клетки (i, j), где i = 0 и j > 0:
max_matrix[i][j] = max_matrix[i][j-1] + value[i][j]
min_matrix[i][j] = min_matrix[i][j-1] + value[i][j]
- Для клетки (i, j), где i > 0 и j = 0:
max_matrix[i][j] = max_matrix[i-1][j] + value[i][j]
min_matrix[i][j] = min_matrix[i-1][j] + value[i][j]
- Для клетки (i, j), где i = 0 и j = 0:
max_matrix[i][j] = value[i][j]
min_matrix[i][j] = value[i][j]
Шаг 6: В конечной правой нижней клетке таблицы (n-1, m-1) будет содержаться максимальная и минимальная суммы денег, которые можно собрать, проходя из левой верхней клетки до данной клетки.
Шаг 7: Вывести максимальную и минимальную суммы в правой нижней клетке таблицы.
Обоснование:
Алгоритм динамического программирования используется для эффективного решения задачи, так как он избегает повторных вычислений. Мы заполняем матрицы max_matrix и min_matrix построчно, рассчитывая максимальную и минимальную суммы в каждой клетке, и используя уже рассчитанные значения из предыдущих клеток.
Рекуррентное соотношение строится на основе следующих наблюдений:
- Чтобы достичь клетки (i, j), необходимо либо прийти с клетки (i-1, j), либо с клетки (i, j-1). Мы выбираем путь, который дает наибольшую (максимальную) или наименьшую (минимальную) сумму.
- Для клеток на первой строке и первом столбце, существует только один путь, и мы просто добавляем сумму этой клетки к предыдущей максимальной или минимальной сумме.
Поэтому решение данной задачи прямолинейно и наглядно демонстрирует применение алгоритма динамического программирования для нахождения максимальной и минимальной суммы денег, которую может собрать Робот в соответствии с условиями задачи.