Дискретный анализ ← ЛабораторныеЛабораторная работа №8

Жадные алгоритмы

Разрабтать жадный алгоритм решения задачи, определяемой своим вариантом. Доказать его корректность, оценить скорость и объём затрачиваемой оперативной памяти.

Реализовать программу на языке C или C++, соответствующую построенныму алгоритму. Формат входных и выходных данных описан в варианте задания.

Варианты

1. Размен монет

На первой строке заданы два числа, N и p > 1, определяющие набор монет некоторой страны с номиналами p0, p1, ..., pN−1. Нужно определить наименьшее количество монет, которое можно использовать для того, чтобы разменять заданную на второй строчке сумму денег M ≤ 232 - 1 и распечатать для каждого i-го номинала на i-ой строчке количество участвующих в размене монет. Кроме того, нужно обосновать почему жадный выбор неприменим в общем случае (когда номиналы могут быть любыми) и предложить алгоритм, работающий при любых входных данных.

Пример:

Входной файл Выходной файл
  3 5
  71
  1
  4
  2

2. Выбор отрезков

На координатной прямой даны несколько отрезков с координатами [Li, Ri ]. Необходимо выбрать минимальное количество отрезков, которые бы полностью покрыли интервал [0, M ]. Формат входных данных: на первой строчке располагается число N, за которым следует N строк на каждой из которой находится пара чисел Li, Ri ; последняя строка содержит в себе число M . Формат выходных данных: на первой строке число K выбранных отрезков, за которым следует K строк, содержащих в себе выбранные отрезки в том же порядке, в котом они встретились во входных данных. Если покрыть интервал невозможно, нужно распечатать число 0.

Пример:

Входной файл Выходной файл
  3
  -1 0
  -5 -3
  2 5
  1
  0
Входной файл Выходной файл
  2
  -1 0
  0 1
  1
  1
  0 1

3. Максимальный треугольник

Заданы длины N отрезков, необходимо выбрать три таких отрезка, которые образовывали бы треугольник с максимальной площадью. Формат входных данных: на первой строке находится число N, за которым следует N строк с целыми числами-длинами отрезков. Формат выходных данных: если никакого треугольника из заданных отрезков составить нельзя — 0, в противном случае на первой строке площадь треугольника с тремя знаками после запятой, на второй строке — длины трёх отрезков, составляющих этот треугольник. Длины должны быть отсортированы.

Пример:

Входной файл Выходной файл
  4
  2
  1
  3
  5
  0
Входной файл Выходной файл
  4
  3
  5
  3
  4
  6.000
  3 4 5

4. Откорм бычков

Бычкам дают пищевые добавки, чтобы ускорить их рост. Каждая добавка содержит некоторые из N действующих веществ. Соотношения количеств веществ в добавках могут отличаться. Воздействие добавки определяется как

c1a1 + c2a2 +· · ·+cNaN,

где ai — количество i-го вещества в добавке, ci — неизвестный коэффициент, связанный с веществом и не зависящий от добавки. Чтобы найти неизвестные коэффициенты ci, Биолог может измерить воздействие любой добавки, использовав один её мешок. Известна цена мешка каждой из M (M ≥ N ) различных добавок. Нужно помочь Биологу подобрать самый дешевый наобор добавок, позволяющий найти коэффициенты ci. Возможно, соотношения веществ в добавках таковы, что определить коэффициенты нельзя.

Входные данные: в первой строке текста — целые числа M и N ; в каждой из следующих M строк записаны N чисел, задающих соотношение количеств веществ в ней, а за ними — цена мешка добавки. Порядок веществ во всех описаниях добавок один и тот же, все числа — неотрицательные целые не больше 50. Выходные данные: -1 если определить коэффциенты невозможно, иначе набор добавок (и их номеров по порядоку во входных данных). Если вариантов несколько, вывести какой-либо из них.

Пример:

Входной файл Выходной файл
  3 3
  1 0 2 3
  1 0 2 4
  2 0 1 2
  -1
Входной файл Выходной файл
  3 2
  2 1 2
  1 2 9
  1 2 3
  1 3

5. Оптимальная сортировка чисел

Дана последовательность длины N из целых чисел 1, 2, 3. Необходимо найти минимальное количество обменов элементов последовательности, в результате которых последовательность стала бы отсортированной. Входные данные: число N на первой строке и N чисел на второй строке. Выходные данные: минимальное количество обменов.

Пример:

Входной файл Выходной файл
  3
  3 2 1
  1

6. Топологическая сортировка

Заданы N объектов с ограничиениями на расположение вида «A должен находиться перед B». Необходимо найти такой порядок расположения объектов, что все ограничения будут выполняться. Входные данные: на первой строке два числа, N и M, за которыми следует M строк с ограничениями вида «A B» (1 ≤ A, B ≤ N ) определяющими относительную последовательность объектов с номерами A и B. Выходные данные: −1 если расположить объекты в соответствии с требованиями невозможно, последовательность номеров объектов в противном случае.

Пример:

Входной файл Выходной файл
  3 2
  1 2
  2 3
  1 2 3