|
Содержание работы или список заданий
|
1.Задание: Черепашка
На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.
Формат входных данных
Первая строка — N — размер доски.
Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску.
Формат выходных данных
Одно число — максимальная сумма.
Подсказка:
Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора “Черепашки”. Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен “максимальный” путь для всех клеток, кроме правой нижней (функция F(X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение:
Function F(x,y:integer):longint;
begin
if B[x, y] = –1 then
if F(x-1, y) > F(x, y - 1)
then B[x, y] := F(x - 1, y) + A[x, y]
else B[x, y] := F(x, y - 1) + A[x, y];
F := B[x, y]
end;
Теперь необходимо подумать о граничных условиях. Логически правильнее было бы просчитать нашу функцию для левой и верхней границы. Это делается легко, так как для этих клеток существует только один маршрут (непосредственно вдоль границы). Но еще проще ввести в рассмотрение фиктивные нулевые строку и столбец и присвоить им нулевые значения. Действительно, эти клетки, в принципе, недостижимы, поэтому максимальная сумма равна нулю.
Итеративное заполнение массива также довольно просто. После введения граничных условий (любых из рассмотренных выше) дальнейшее заполнение осуществляется двойным циклом:
for i:=1 to N do
for j:=1 to N do
if B[i - 1, j] > B[i, j - 1]
then B[i, j] := B[i - 1, j] + A[i, j]
else B[i, j] := B[i, j - 1] + A[i, j];
2.Задание.Робот
В исследовательской лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robots&Co заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.
Формат входных данных
Во входном файле находятся три числа K, X и Y (0 <= K <= 16, |X|, |Y| <= 16), разделенные пробелами.
Формат выходных данных
В выходной файл ваша программа должна поместить одно число — количество программ для робота.
Подсказка:
В этой задаче мы впервые сталкиваемся с функцией трех переменных: F(X, Y, Z) - показывает количество маршрутов длины Z, приводящих в клетку (X, Y). К сожалению, такая структура данных как
Array [-16..16, -16..16, 0..16] of LongInt;
в память не помещается. Забудем пока об этой трудности и напишем рекурсивную часть. Для ответа на поставленный в задаче вопрос можно посчитать число маршрутов длины Z - 1 в четыре клетки, смежных с заданной, а результаты сложить, не забывая случаи клеток на границе. Граничными условиями будут F(X, Y, 0) = 0, если хотя бы одна из координат X или Y отлична от нуля, и F(0, 0, 0) = 1. Действительно, если робота не двигать, то он может оказаться только в начале координат. Теперь вспомним о проблеме хранения данных. Выхода существует два. Первый, чисто программистский, заключается в разбиении большой структуры на несколько меньших и размещении их в динамической памяти. Сделать это можно, например, так
Type T1 = array[-16..16, -16..16] of LongInt;
T2 = array [0..16] of ^T1;
Var D : T2;
Тогда наша функция будет записана так (предполагается, что память выделена, граничные условия введены, а для не вычисленных значений функции в массиве хранится "-1"):
Function F(X, Y, Z : integer) : longint;
var s : longint;
begin
if D[Z]^[X, Y] = -1 then
begin
s := 0;
if X <> -16 then s := s + F(X - 1, Y, Z - 1);
if X <> 16 then s := s + F(X + 1, Y, Z - 1);
if Y <> -16 then s := s + F(X, Y - 1, Z - 1);
if Y <> 16 then s := s + F(X, Y + 1, Z - 1);
D[Z]^[X, Y] := s
end;
F := D[Z]^[X, Y]
end;
Это, конечно, решение, но оно далеко не оптимальное (с точки зрения расходования памяти). Действительно, для вычислений в некий момент времени необходимы данные только за предыдущий, что же происходило ранее, нас не интересует - с этим мы уже справились. Значит, достаточно хранить только 2 квадратные матрицы размером 31, - одна несет данные в предыдущий момент времени, а вторая вычисляется для текущего с использованием первой матрицы. После окончания расчета данные первой уже не нужны, ей присваиваем значение второй матрицы, увеличиваем счетчик времени и т.д. Ясно, что такую идею можно реализовать только итеративно.
for z := 1 to k do
begin
Way2 := Way1;
for i := -16 to 16 do
for j := -16 to 16 do
begin
s := 0;
if i <> -16 then s := s + Way2[i - 1, j];
if i <> 16 then s := s + Way2[i + 1, j];
if j <> -16 then s := s + Way2[i, j - 1];
if j <> 16 then s := s + Way2[i, j + 1];
Way1[i, j] := s
end
end;
Интересно, что итеративное решение на некоторых тестах работает несколько дольше рекурсивного (правда это заметно только на слабых машинах, примерно до 486SX). Это становится понятным, если учесть, что в итеративной форме мы подсчитываем количества всевозможных маршрутов, а в рекурсивном делаем только то, что нас просят.
Ссылка: http://comp-science.narod.ru/WebPage/lesson2.htm
3.Задание.
Подсказка к задаче:
Аналогичная задача: Воспитательница Марина работает в детском саду. У нее N детей в группе. На обед было приготовлено K запеканок. Каждый ребенок просит разное количество запеканок. Марине необходимо удовлетворить наибольшее количество детей. У запеканок также есть свойство: если количество запеканок кратно 3, то ребенку кажется, что он их съел в 3 раза больше.
Итак, Марине необходимо разделить запеканки на детей так, чтобы максимальное количество детей было довольно. Можно использовать не все запеканки.
Формат файла входных данных:
На вход подаются числа: n и k (1 <= n <= 100, 1 <= k <= 10^5). Далее идут n натуральных чисел - количество запеканок, которое просит ребенок.
Формат файла выходных данных:
Нужно вывести одно число - наибольшее детей, которых удастся удовлетворить.
Пример:
mydefence.in mydefence.out
2 4
1 9 2
1 5
8 1
5 7
1 2 5 8 10 3
Решение задачи подсказки на языке Phyton:
n, k = map(int, input().split())
a = list(map(int, input().split()))
det = 0
for x in range(n):
var1 = a[x]
while (var1 % 9 != 0):
var1 += 1;
var1 = var1 // 3;
minvar = min(a[x], var1)
if (minvar<=k):
det += 1
k -= minvar
print(det)
|