Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи с решениями на Turbo Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.826 RSS
←   Март 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 02-12-2001

Автор
Aslof

Статистика

3.826 подписчиков
0 за неделю
←   Все выпуски   →

Олимпиадные задачи с решениями на Turbo Pascal


Информационный Канал Subscribe.Ru
NP-полные задачи
Бодрого времени суток, уважаемые подписчики.

Разбор полетов

К сожалению, мы вынуждены сказать, что обе задачи предыдущего выпуска правильно решил только один человек - CupIvan. Остальные либо не захотели довести решение до финала, либо им эти задачи оказались не по зубам, хотя, на самом деле, в них нет ничего сложного. Поскольку мы сочли задачу про подматрицы сложнее задачи про подпоследовательности, то в этом номере мы опубликуем решение только 3-й задачи, а другую оставим до следующего выпуска. Сложность задачи №3 предполагалась равной O(n), а задачи №4 - O(n^3).

Идея алгоритма: вначале ищем первый положительный элемент в последовательности. Если такого не окажется, то наибольший из просмотренных и будет решением. Если такой элемент нашелся, то считаем, что текущая сумма и максимальная равны этому элементу. Начинаем просматривать эту последовательность до конца. На каждом шаге увеличиваем текущую сумму на текущий элемент. Если текущая сумма оказаласть отрицательной - зануляем ее. Кроме того, если значение текущей суммы окажется больше максимальной, то максимальную сумму считаем равной текущей. Вот рабочий код:

var min,j,maxsum,sum,n: longint;

    inp, outp: text;

begin

  assign(inp,'input.txt');

  reset(inp);

  readln(inp);

  read(inp,min);

  while (not eof(inp))and(min<=0)do

  begin

    read(inp,j);

    if j>min then min:=j;

  end;

  maxsum:=min;

  sum:=min;

  while not eof(inp) do

  begin

    read(inp,j);

    inc(sum,j);

    if sum>maxsum then maxsum:=sum;

    if sum<0 then sum:=0;

  end;

  assign(outp,'output.txt');

  rewrite(outp);

  write(outp,maxsum);

  close(inp);

  close(outp);

end.

Новые горизонты

NP-полные задачи.

Теория сложности классифицирует не только сложность конкретных алгоритмов решения задачи, но и сложность самих задач. Теория сложности рассматривает минимальное время и объем памяти, необходимые для решения самого сложного варианта задачи на теоретическом компьютере, известном как машина Тьюринга. Задачи, которые можно решить с помощью алгоритмов, сложность которых определяется многочленом (полиномиальное время), называют разрешимыми, поскольку обычно при разумных входных данных могут быть решены за приемлемое время. (Точнее, определение "приемлемости" зависит от конкретных обстоятельств). Задачи, которые невозможно решить за полиномиальное время, называют труднорешаемыми, или просто трудными, поскольку вычисление их решений быстро становится невозможным.

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

P<=NP<=EXPTIME

Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно угадывая”, либо перебирая все предположения параллельно – и проверяет свое предположение за полиномиальное время.

Класс NP включает в себя класс P, поскольку любую задачу, решаемую за полиномиальное время на детерминированной (обычной) машине Тьюринга, можно решить и на недетерминированной за полиномиальное время, просто этап предположения опускается.

Если все задачи класса NP решаются за полиномиальное время и на детерминированной машине, то P=NP. Тем не менее, никем не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что это классы неравны.

Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такие задачи называются NP-полными. То есть, если такая задача решается за полиномиальное время, то P=NP.

Таким образом, для программиста NP-полнота означает полный перебор, причем сложность этого перебора будет экспоненциальной или факториальной. Но следует понимать, что не всякий полный перебор имеет такую сложность. Наапример, если решать задачи из предвдущего выпуска полным перебором, то сложность полученных алгоритмов будет полиномиальной - O(n^2) для задачи про подпоследовательности и O(n^6) для задачи про подматрицы.

Наконец, существует класс задач EXPTIME. Эти задачи решаются за экспоненциальное время. В настоящее время можно доказать, что EXPTIME-полные задачи невозможно решить за детерминированное полиномиальное время. Кроме того, доказано, что P<>EXPTIME.

Приведем теперь список некоторых задач, которые являются NP-полными:

    • ВЕРШИННОЕ ПОКРЫТИЕ ГРАФА. Заданы граф G(V, E) и число K, не превосходящее количества вершин в графе. Нужно выяснить, существуют ли К или меньше вершин таких, что любое ребро в графе содержало хотя бы одну из них.
    • РАСКРАШИВАЕМОСТЬ ГРАФА (ХРОМАТИЧЕСКОЕ ЧИСЛО). Заданы граф G(V, E) и число K, не превосходящее количества вершин в графе. Нужно выяснить, можно ли раскрасить вершины графа в K различных цветов так, чтобы концы любого ребра оказались раскрашены в 2 различных цвета.
    • ГАМИЛЬТОНОВ ЦИКЛ И ПУТЬ. Задан граф G(V, E). Нужно выяснить, существует ли в данном графе гамильтонов цикл и гамильтонов путь.
    • УПАКОВКА В КОНТЕЙНЕРЫ. Дано N предметов, размеры которых S[i]. Требуется определить, можно ли их разбить на K кучек так, чтобы сумма размеров предметов в каждой кучке не превосходила R.
    • ЗАДАЧА КОММИВОЯЖЕРА. Задано множество M городов и расстояния между ними D[i,j]. Нужно определить, существует ли маршрут, начинающийся в k-м городе, проходящий через все города по одному разу и заканчивающийся в начальном городе с тем условием, что его длина не превышает K.
    • СУММА РАЗБИЕНИЯ. Задано N предметов и их массы M[i]. Требуется определить, можно ли выделить такую группу предметов, чтобы их масса равнялась K.
    • РЮКЗАК. Задано N предметов, их массы M[i] и стоимости C[i]. Существует ли такая группа этих предметов, что их суммарная масса не превосходит P, а суммарная стоимость не меньше S. Иногда задача формулируется следующим образом: под P понимают вместимость рюкзака и просят найти максимально возможное S (то есть заполнить рюкзак так, чтобы суммарная стоимость всех положенных в него предметов оказалась наибольшей).

Основное назначение этого списка - дать вам возможность попытаться свести задачи, которые вы подозреваете в NP-полноте к этим: если это удасться, то вы должны, не ища более оптимального решения, грамотно организовать перебор. Разумеется, этот список является далеко не полным. Дополнительную информацию о сложности алгоритмов, а также большой список труднорешаемых задач (более 300) можно найти в прекрасной книге М. Гэри и Д. Джонсона "Вычислительные машины и труднорешаемые задачи".

 

 

Этим выпуском мы открываем огромную тему в программировании: "Структуры данных и алгоритмы их обработки". Существует много литературы, посвященной этим вопросам, отметим здесь лишь несколько книг: Д.Э. Кнут, "Искусство программирования", том I "Основные алгоритмы"; А. Ахо, Д. Хопкрофт, Д. Ульман, "Структуры данных и алгоритмы"; Р. Седжвик, "Фундаментальные алгоритмы на C++".

В этом выпуске мы не будем рассматривать собственно структур данных, а лишь коснемся некоторых моментов, связанных с использованием указателей.

Указателем называется переменная, которая хранит адрес в памяти другой переменной. Указатели бывают двух типов: нетипизированные (содержат в себе просто некий адрес) и типизированные (содержат в себе адрес переменной конкретного типа). Рассмотрим примеры:

type PInt = ^integer;

PRec = ^TRec;

TRec = record

  a: integer;

  pa: PInt;

end;

var r: PRec;

В данном примере у нас есть r - указатель на запись, в которой содержится переменная целого типа и указатель на эту же переменную. Тогда доступ к полю a можно получить двумя способами:

c := r^.a

или

c := r^.pa^

При этом мы считаем, что запись, на которую ссылается переменная r, уже заполнена:

r^.a := 1;

r^.pa := @r^.a;

Здесь ^ - оператор разыменования указателя - получения содержимого памяти по адресу. Обратим ваше внимание на то, что этот оператор применим лишь к типизированным указателям. Оператор @ обратен оператору ^ - он позволяет получить адрес переменной.

Поместим теперь в определение записи TRec еще один указатель – указатель на такую же запись:

type PRec = ^TRec;

TRec = record

  a: integer;

  pa: PInt;

  rec: PRec;

end;

Если поле rec будет указывать на саму запись, то ничего интересного мы не получим. Напротив поле rec может указывать на другую запись, та на третью и так далее. Если на некотором шаге поле rec ни на что не указывает, то оно должно равняться значению nil. Таким образом можно организовывать весьма длинные цепочки. Кроме того, в определение записи можно добавить еще указатели, даже массивы указателей, получая при этом весьма сложные структуры.

Вообще говоря традиционно считается, что указатели - сложная для новичков тема, поэтому, если вы испытываете какие-то трудности с указателями, обратитесь к соответствующей литературе, благо ее сейчас более, чем достаточно, или же пишите нам - мы обязательно объясним вам непонятные моменты. Указатели не только сложная, но и чрезвычайно важная тема, знание которой потребуется от вас в ближайших выпусках.

Время покодить.

Начиная с этого выпуска мы вводим систему рейтингов задач, то есть за верное решение каждой задачи вы будете получать определенное количество баллов (от 1 до 5), которое определяется сложностью задачи. Критерии оценок следующие:
  • 1 балл - простая задача, требующая для своего решения простой, но гениальной идеи, задача на сообразительность.
  • 2 балла - в целом несложная задача, требующая для своего решения не слишком очевидной идеи.
  • 3 балла - в нормальная задача, требующая для своего решения идеи, которую стоит еще поискать.
  • 4 балла - более сложная задача, требующая для своего решения нетривиальной идеи или какого-то специфического алгоритма.
  • 5 балла - весьма сложная задача. Требует занчительного времени и усилий для решения.

Задача №5. Шутка. (1 балл)

(задача предоставляется для решения в том виде, в котором она была предложена на межвузовской олимпиаде 2004 года проходившей в гор.Вологда)

Дано натуральное число N(1£ N£ 1 000 000 000). Вычислить Sqrt(13+ 23+ 33 +...+ N3).

Input.txt: число N.

Output.txt результат вычислений с точностью до 2-го знака.

Пример:

Input.txt

3

Output.txt

6.00

Задача №6. Коэффициенты многочлена. (1 балл)

Дан многочлен (an*xn+a(n-1)*x(n-1)+...+a1*x+a0)k . Необходимо посчитать сумму коэффициентов многочлена после возведения в степень.

Input.txt:

В первой строке N - степень многочлена в скобках.

Во второй строке через пробел N+1 число - коэффициенты an в порядке убывания индекса.

В третьей строке k - степень, в которую возводится многочлен.

Входные данные таковы, что результат не превосходит 1 000 000 000.

Output.txt:

Сумма коэффициентов многочлена после возведения в степень.

Пример:

Input.txt:

1

1 1

2

Output.txt

4

Комментарий: (x+1)2=x2+2x+1.

1+2+1=4.

Оптимальных решений! Пишите на olimp@math.pomorsu.ru
Ищешь фильм? http://aslof.balzer.ru/
http://subscribe.ru/catalog/rest.cinema.filmforyou

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное