Динамическое программирование
 Скачать 0.98 Mb.
|
|
18-93.xls размером N x N, каждая ячейка которых соответствует клетке квадрата. (А. Кабанов) Квадрат разлинован на N x N клеток (1 < N < 20). Исполнитель Буквоед может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Буквоед перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке пересечь границы квадрата, обозначенные жирными линиями, Буквоед разрушается. В каждой клетке квадрата указан её тип латинскими буквами A, B или C. Посетив клетку, Буквоед платит или получает деньги за её посещение; это также относится к начальной и конечной точке маршрута. За посещение клетки A взимается плата 10 монет, за посещение клетки B Буквоеду выплачивают 1 монету, за посещение клетки C Буквоеду выплачивают 2 монеты. Определите максимальную прибыль и максимальный убыток, который может получить получит Буквоед, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальный убыток, затем максимальную прибыль. Исходные данные записаны в электронной таблице 18-94.xls размером N x N, каждая ячейка которой соответствует клетке квадрата. Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд: вправо, вверх или вправо-вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю, а по команде вправо-вверх – на одну клетку вправо и вверх по диагонали. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата записана величина вознаграждения от 1 до 100. Попав в клетку после хода вправо или вверх, Робот получает указанное в ней вознаграждение, а если он попал в клетку после выполнения команды вправо-вверх, вознаграждение удваивается. Это также относится к начальной и конечной клетке маршрута Робота. Определите максимальное и минимальное вознаграждение, которое может получить Робот, пройдя из левой нижней клетки в правую верхнюю. В ответе укажите два числа – сначала максимальное вознаграждение, затем минимальное. Исходные данные записаны в файле 18-95.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд: вправо, вниз или вправо-вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю, а по команде вправо-вниз – на одну клетку вправо и вниз по диагонали. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата записана величина вознаграждения от 1 до 100. Попав в клетку после хода вправо или вниз, Робот получает указанное в ней вознаграждение, а если он попал в клетку после выполнения команды вправо-вниз, вознаграждение удваивается. Это также относится к начальной и конечной клетке маршрута Робота. Определите максимальное и минимальное вознаграждение, которое может получить Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальное вознаграждение, затем минимальное. Исходные данные записаны в файле 18-95.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд: влево, вниз или влево-вниз. По команде влево Робот перемещается в соседнюю левую клетку, по команде вниз – в соседнюю нижнюю, а по команде влево-вниз – на одну клетку влево и вниз по диагонали. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата записана величина вознаграждения от 1 до 100. Попав в клетку после хода влево или вниз, Робот получает указанное в ней вознаграждение, а если он попал в клетку после выполнения команды влево-вниз, вознаграждение удваивается. Это также относится к начальной и конечной клетке маршрута Робота. Определите максимальное и минимальное вознаграждение, которое может получить Робот, пройдя из правой верхней клетки в левую нижнюю. В ответе укажите два числа – сначала максимальное вознаграждение, затем минимальное. Исходные данные записаны в файле 18-95.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд: влево, вверх или влево-вверх. По команде влево Робот перемещается в соседнюю левую клетку, по команде вверх – в соседнюю верхнюю, а по команде влево-вверх – на одну клетку влево и вверх по диагонали. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата записана величина вознаграждения от 1 до 100. Попав в клетку после хода влево или вверх, Робот получает указанное в ней вознаграждение, а если он попал в клетку после выполнения команды влево-вверх, вознаграждение удваивается. Это также относится к начальной и конечной клетке маршрута Робота. Определите максимальное и минимальное вознаграждение, которое может получить Робот, пройдя из правой нижней клетки в левую верхнюю. В ответе укажите два числа – сначала максимальное вознаграждение, затем минимальное. Исходные данные записаны в файле 18-95.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток вправо или вниз (влево и вверх ладья ходить не может). Определите минимальную и максимальную сумму чисел в клетках, в которых может остановиться ладья при перемещении из левого верхнего угла в правый нижний. Исходные данные записаны в файле 18-99.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток влево или вниз (вправо и вверх ладья ходить не может). Определите минимальную и максимальную сумму чисел в клетках, в которых может остановиться ладья при перемещении из правого верхнего угла в левый нижний. Исходные данные записаны в файле 18-99.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток вправо или вниз (влево и вверх ладья ходить не может). Определите минимальную и максимальную сумму чисел в клетках, в которых может остановиться ладья при перемещении из левого верхнего угла в правый нижний. Исходные данные записаны в файле 18-101.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток влево или вниз (вправо и вверх ладья ходить не может). Определите минимальную и максимальную сумму чисел в клетках, в которых может остановиться ладья при перемещении из правого верхнего угла в левый нижний. Исходные данные записаны в файле 18-101.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку вправо, вниз или по диагонали вправо-вниз. Определите минимальную и максимальную сумму чисел в клетках, через которые может пройти Робот при перемещении из левого верхнего угла в правый нижний. Исходные данные записаны в файле 18-101.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку влево, вниз или по диагонали влево-вниз. Определите минимальную и максимальную сумму чисел в клетках, через которые может пройти Робот при перемещении из правого верхнего угла в левый нижний. Исходные данные записаны в файле 18-101.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку вправо, вниз или по диагонали вправо-вниз. Определите минимальную и максимальную сумму чисел в клетках, через которые может пройти Робот при перемещении из левого верхнего угла в правый нижний. Исходные данные записаны в файле 18-105.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку влево, вниз или по диагонали влево-вниз. Определите минимальную и максимальную сумму чисел в клетках, через которые может пройти Робот при перемещении из правого верхнего угла в левый нижний. Исходные данные записаны в файле 18-105.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. (М. Коротков, г. Челябинск) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Пассажир на Самокатике перемещается из левой верхней клетки в правую нижнюю, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо он перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Самокатик разваливается на части и прекращает движение. В каждой клетке квадрата записано целое число в диапазоне от -100 до 100. Самокатик – электрический; начальный уровень заряда его батареи указан в левой верхней клетке квадрата. При посещении очередной клетки уровень заряда батареи Самокатика изменяется на указанное в ней значение, но не может стать меньше 0 или больше 100. Это также относится к конечной клетке маршрута. Всякий раз, когда уровень заряда батареи Самокатика опускается до нуля, Пассажир спешивается и тащит его на себе. Определите максимально возможный уровень заряда батареи Самокатика в конечной клетке, если Пассажиру на протяжении всего маршрута: A) запрещено спешиваться; B) разрешено спешиваться. Исходные данные записаны в файле 18-107.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала ответ на вопрос А, затем – ответ на вопрос B. (М. Коротков, г. Челябинск) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Пассажир на Самокатике перемещается из левой нижней клетки в правую верхнюю, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо он перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. При попытке выхода за границу квадрата Самокатик разваливается на части и прекращает движение. В каждой клетке квадрата записано целое число в диапазоне от -100 до 100. Самокатик – электрический; начальный уровень заряда его батареи указан в левой нижней клетке квадрата. При посещении очередной клетки уровень заряда батареи Самокатика изменяется на указанное в ней значение, но не может стать меньше 0 или больше 100. Это также относится к конечной клетке маршрута. Всякий раз, когда уровень заряда батареи Самокатика опускается до нуля, Пассажир спешивается и тащит его на себе. Определите максимально возможный уровень заряда батареи Самокатика в конечной клетке, если Пассажиру на протяжении всего маршрута: A) запрещено спешиваться; B) разрешено спешиваться. Исходные данные записаны в файле 18-108.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала ответ на вопрос А, затем – ответ на вопрос B. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку вправо или на одну клетку вниз. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из левого верхнего угла в правый нижний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом нижнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку вправо или на одну клетку вверх. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из левого нижнего угла в правый верхний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом нижнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку влево или на одну клетку вверх. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из правого нижнего угла в левый верхний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку влево или на одну клетку вниз. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из правого верхнего угла в левый нижний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную. (М. Коротков) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 10. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите: A) максимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю; B) количество различных маршрутов из левой верхней клетки в правую нижнюю, каждый из которых позволяет Роботу собрать денежную сумму из п. А. Исходные данные записаны в файле |