Перейти на главную страницу
При решении олимпиадных задач чаще всего заранее неизвестно, сколько именно элементов исходного множества должно входить в искомое подмножество, то есть необходим перебор всех подмножеств. Однако, если требуется найти минимальное подмножество, то есть состоящее как можно из меньшего числа элементов (или максимальное подмножество), то эффективнее всего организовать перебор так, чтобы сначала проверялись все подмножества, состоящие из одного элемента, затем из двух, трех и т. д. элементов (для максимального подмножества — в обратном порядке). В этом случае, первое же подмножество, удовлетворяющее условию задачи и будет искомым и дальнейший перебор следует прекратить. Для реализации такого перебора можно воспользоваться, например, процедурой cnk, описанной в предыдущем разделе. Введем в нее еще один параметр: логическую переменную flag, которая будет обозначать, удовлетворяет текущее сочетание элементов условию задачи или нет. При получении очередного сочетания вместо его печати обратимся к процедуре его проверки check, которая и будет определять значение флага. Тогда начало процедуры gen следует переписать так:
procedure gen(m,L:integer);
var i:integer;
begin
if m=0 then
check(p,k,flag);
if flag then exit
end
Далее процедура дословно совпадает с предыдущей версией. В основной же программе единственное обращение к данной процедуре следует заменить следующим фрагментом:
k:=0;
flag:=false;
k:=k+1;
until flag or (k=n);
if flag then print(k)
else writeln('no solution');
Очевидно также, что в основной программе запрос значения переменной k теперь не производится.
С
уществует также альтернативный подход к перебору всех подмножеств того или иного множества. Каждое подмножество можно охарактеризовать, указав относительно каждого элемента исходного множества, принадлежит оно данному подмножеству или нет. Сделать это можно, поставив в соответствие каждому элементу множества 0 или 1. То есть каждому подмножеству соответствует n-значное число в двоичной системе счисления (строго говоря, так как числа могут начинаться с произвольного количества нулей, которые значащими цифрами не считаются, то следует заметить, что в соответствие ставятся n- или менее -значные числа). Отсюда следует, что полный перебор всех подмножеств данного множества соответствует перебору всех чисел в двоичной системе счисления от
Прежде, чем перейти к рассмотрению программ, соответствующих второму способу перебора, укажем, когда применение этих программ целесообразно. Во-первых, данные программы легко использовать, когда необходимо в любом случае перебрать все подмножества данного множества (например, требуется найти все решения удовлетворяющие тому или иному условию). Во-вторых, когда с точки зрения условия задачи не имеет значения, сколько именно элементов должно входить в искомое подмножество. На примере такой задачи мы и напишем программу генерации всех подмножеств исходного множества в лексикографическом порядке. Задача взята из книги [5].
function check(j:longint):boolean;
var k:integer; s:longint;
begin
for k:=1 to n do
if ((j shr (k-1))and 1)=1 {данное условие означает, что в
k-й справа позиции числа j, в 2-й системе, стоит 1}
then s:=s+a[k];
if s=m then
begin
for k:=1 to n do
writeln
end;
procedure subsets(n:integer);
var q,j:longint;
begin
for j:=1 to q-1 do {цикл по всем подмножествам}
if check(j) then exit
end;
Заметим, что если все элементы в массиве положительные, то, изменив порядок рассмотрения подмножеств, решение приведенной выше задачи можно сделать более эффективным. Так, если сумма элементов какого-либо подмножества уже больше, чем M, то рассматривать подмножества, включающие его в себя уже не имеет смысла. Пересчет же сумм можно оптимизировать, если каждое следующее сгенерированное подмножество будет отличаться от предыдущего не более, чем на один элемент (такой способ перечисления подмножеств показан в [2]). Приведенная же программа черезвычайно проста, но обладает одним недостатком: мы не можем ни в каком случае с ее помощью перебирать все подмножества множеств, состоящих из более, чем 30 элементов, что обусловлено максимальным числом битов, отводимых на представление целых чисел в Турбо Паскале (32 бита). Но, как уже было сказано выше, на самом деле, перебор всех подмножеств у множеств большей размерности вряд ли возможен за время, отведенное для решения той или иной задачи.
Количество различных перестановок множества, состоящего из n элементов равно n!. В этом нетрудно убедиться: на первом месте в перестановке может стоять любой из n элементов множества, после того, как мы на первом месте зафиксировали какой-либо элемент, на втором месте может стоять любой из n – 1 оставшегося элемента и т.д. Таким образом, общее количество вариантов равно n(n – 1)(n – 2)...321 = n!. То есть рассматривать абсолютно все перестановки мы можем только у множеств, состоящих из не более, чем 10 элементов.
Рассмотрим рекурсивный алгоритм, реализующий генерацию всех перестановок в лексикографическом порядке. Такой порядок зачастую наиболее удобен при решении олимпиадных задач, так как упрощает применение метода ветвей и границ, который будет описан ниже. Обозначим массив индексов элементов — p. Первоначально он заполнен числами 1, 2, ..., n, которые в дальнейшем будут меняться местами. Параметром i рекурсивной процедуры Perm служит место в массиве p, начиная с которого должны быть получены все перестановки правой части этого массива. Идея рекурсии в данном случае следующая: на i-ом месте должны побывать все элементы массива p с i-го по n-й и для каждого из этих элементов должны быть получены все перестановки остальных элементов, начиная с (i+1)-го места, в лексикографическом порядке. После получения последней из перестановок, начиная с (i+1)-го места, исходный порядок элементов должен быть восстановлен.
{описание переменных совпадает с приведенным выше}
procedure Permutations(n:integer);
procedure Perm(i:integer);
var j,k:integer;
begin
if i=n then
else
for j:=i+1 to n do
begin
Perm(i+1);
end;
{циклический сдвиг элементов i..n влево}
k:=p[i];
for j:=i to n-1 do p[j]:=p[j+1];
p[n]:=k
end
Perm(1)
readln(n);
for i:=1 to n do p[i]:=i;
a:=p; {массив a может быть заполнен произвольно}
Permutations(n)
end.
Число разбиений n-элементного множества на k блоков произвольного размера но таких, что каждый элемент множества оказывается “приписан” к одному из блоков, выражается числом Стирлинга второго рода S(n,k) [6,7]. Очевидно, что S(n,k) = 0 для k > n. Если согласиться, что существует только один способ разбиения пустого множества на нулевое число непустых частей, то S(0,0) = 1 (именно такая договоренность, как и в случае с факториалом, приводит в дальнейшем к универсальным формулам). Так как при разбиении непустого множества нужна по крайней мере одна часть, S(n,0) = 0 при n > 0. Отдельно интересно также рассмотреть случай k = 2. Если непустое множество разделили на две непустые части, то в первой части может оказаться любое подмножество исходного множества, за исключением подмножеств, включающих в себя последний элемент множества, а оставшиеся элементы автоматически попадают во вторую часть. Такие подмножества можно выбрать 2n-1 – 1 способами, что и соответствует S(n,2) при n > 0.
Для произвольного k можно рассуждать так. Последний элемент либо будет представлять из себя отдельный блок в разбиении и тогда оставшиеся элементы можно разбить уже на k – 1 частей S(n – 1,k – 1) способами, либо помещаем его в непустой блок. В последнем случае имеется kS(n – 1,k) возможных вариантов, поскольку последний элемент мы можем добавлять в каждый блок разбиения первых n - 1 элементов на k частей. Таким образом
S(n,k) = S(n – 1, k – 1) + kS(n – 1, k), n > 0. (5)
Полезными могут оказаться также формулы, связывающие числа Стирлинга с биномиальными коэффициентами, определяющими число сочетаний:
Е
сли же значение k теперь не фиксировать и рассмотреть все разбиения n-элементного множества, то их количество выражается числом Белла
П
о формулам (7) можно подсчитать, что в рамках принятых выше допущений можно построить все разбиения множества, состоящего не более чем из 15 элементов (B15=1382958545).
Перейдем теперь к рассмотрению способа генерации всех разбиений исходного множества. Прежде всего следует договориться о том, как обозначать текущее разбиение. Так как в каждом из разбиений участвуют все элементы исходного множества, будем в массиве индексов p записывать в какой блок попадает каждый из элементов в текущем разбиении. Параметр i в рекурсивной процедуре part означает, что на текущем шаге мы именно i-ый элемент будет размещать в каждом из допустимых для него блоков, а j как раз и определяет максимальный номер допустимого блока. После того, как i-ый элемент помещен в один из блоков, рекурсивно решается такая же задача уже для следующего элемента (в данном случае фактически работает универсальная схема перебора с возвратом [8]).
procedure partition(n : integer; var p:list);
procedure part(i, j: integer);
var l: integer;
begin
if i > n then print(n, p) else
begin
if l = j then part(i+1, j+1)
else part(i+1, j)
end
part(1,1)
end;
Как ни странно, в данном случае процедура print оказывается совсем не тривиальной, если требуется печатать (или анализировать) элементы каждого из блоков разбиения в отдельности. Поэтому приведем возможный вариант ее реализации (как и ранее, распределяли по блокам мы индексы, а печатаем или анализуруем сами элементы исходного массива a):
var i,j,imax:integer;
begin
imax:=1;{определяем количество блоков в разбиении}
if p[i]>imax then imax:=p[i];
for i:=1 to imax do {цикл по блокам}
begin
if p[j]=i then write(a[j]:4);
write(' |') {блок напечатан}
end;
end;
Если при этом рассматривать массив p как n-значное число n-ричной системе счисления, то можно ввести понятие лексикографического порядка для разбиений множества и ставить задачи определения номера разбиения и обратную ей. Как и ранее (см. [1-3]), они решаются методом динамического программирования и не используют непосредственную генерацию всех разбиений.
Для полноты рассмотрения данной темы самостоятельно измените процедуру partition так, чтобы она генерировала все разбиения, состоящие не более, чем из k блоков. После этого напишите процедуру разбиения множества уже на ровно k непустых частей.
Олимпиадные задачи, использующие комбинаторные конфигурации
Пример 1. На одном острове Новой Демократии каждый из его жителей организовал партию, которую сам и возглавил. Отметим, что ко всеобщему удивлению даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предпологалось по Конституции острова, президенты всех партий. Посовещавшись, Островитяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите Островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены члены всех партий.
Исходные данные: каждая партия и, соответственно, ее президент имеют одинаковый порядковый номер от 1 до N (4 N 150). Вам даны списки всех N партий Острова Новой Демократии. Выведите предлагаемый Вами парламент в виде списка номеров его членов. (Олимпиада стран СНГ, г. Могилев, 1992 г.)
function check(var p:list;k:integer): boolean;
var i:integer; ss:set of 1..150;
begin
for i:=1 to k do ss:=ss+s[p[i]];
check:=(ss=[1..n])
end;
s: array[1..150] of
record name,number:integer;
partys: set of 1..150
Здесь поле partys совпадает по смыслу с первоначальным описанием массива s, поле name cоответствует номеру (то есть фактически имени) жителя и первоначально данное поле следует заполнить числами от 1 до n cогласно индексу элемента в массиве записей, и поле number соответствует количеству элементов во множестве из поля partys, то есть имеет смысл сразу подсчитать, в каком количестве партий состоит тот или иной житель. Теперь следует отсортировать массив s по убыванию значений поля number. Верхнюю оценку для числа членов парламента (kmax) подсчитаем, построив приближенное решение данной задачи следующим образом: во-первых, включим в парламент жителя, состоящего в максимальном количестве партий, затем исключим эти партии из остальных множеств и заново найдем в оставшемся массиве элемент с максимальным значением поля number (уже пересчитанного) и включим его в парламент, и так далее, до тех пор пока сумма значений пересчитанных полей number у жителей, включенных в парламент, не будет равна n. Найденное количество членов парламента и будет kmax.
Входные данные. Во входном файле записано число n (1 ≤ n ≤ 10) - количество городов в области. Затем идут положительные вещественные числа: k - коэффициент стоимости кабеля и P - стоимость постройки одной станции. Далее следует n пар вещественных чисел, задающих координаты городов на плоскости.
Выходные данные. В первую строку выходного файла нужно вывести минимальные затраты на установку сети (с тремя знаками после десятичной точки), во вторую - количество устанавливаемых станций. Далее вывести координаты станций (с тремя знаками после десятичной точки), а затем - список из n целых чисел, в котором i-ое число задает номер станции, к которой будет подключен i-ый город. (Кировский командный турнир по программированию, 2000 г.)
Решение. В силу небольшой размерности мы можем рассмотреть все возможные варианты разбиения городов на группы, подразумевая что для каждой группы будет установлена своя станция, причем оптимальным образом (найти оптимальное местонахождение станции для одной группы городов можно по формуле, аналогичной формуле нахождения центра масс). Затем нужно из всех разбиений выбрать то, для которого общая сумма затрат на установку сети будет минимальной.
Решение геометрических задач.
Иногда бывает удобнее пользоваться уравнением прямой заданной в параметрическом виде:
Полезно будет так же вспомнить и как вычисляется расстояние между двумя точками: .
Задача: Вычислить расстояние которое пройдет путник двигаясь из точки А в точку В (при этом необходимо вычислить кратчайшее расстояние), если известно, что от точки (-1,0) до (1,0) вырыт непроходимый ров, пересечь который нельзя, можно лишь проходить по его краю.
(Пояснение: )
Решение задачи будет несколько проще, если мы введем функцию, которая позволяет определять взаимное положение трех точек. Итак, значит, у нас есть три точки: А (х1,у1), В (х2,у2) и С (х3,у3). Две из них однозначно определяют одну прямую и следовательно расположены на ней, весь вопрос состоит в том, а будет ли на этой же прямой располагаться и третья точка. Пусть прямую у нас определяют точки А и В, для того чтобы определить лежит на этой прямой точка С, составим следующую функцию:. Или F=((х3-х1)(у2-у1)-(у3-у1)(х2-х1)). Если F=0, то все три точки лежат на одной прямой, если же F>0 или же F<0, то третья точка лежит по одну из сторон от исходной прямой.
Тогда наша рассмотренная ранее задача будет сводиться к следующему: необходимо определить будут ли лежать точки по разные стороны ото рва, то есть вычислить произведение функций FА* FВ и если оно отрицательно, то точки расположены по разные стороны ото рва, но при этом необходимо еще проверить, а будут ли они пересекаться.
(Тесты: А(-3,1), В(5,4) – расстояние 8,54; А(-1,4), В(4,-4) – расстояние 9,43; А(-2,-3), В(2,5) – расстояние 8,99; А(0,0), В(4,-1) – расстояние 4,12; А(0,5), В(0,-2) – расстояние 7,34).
Рассмотрим теперь, в зависимости от того, по какую сторону от прямой будет лежать точка, какой знак будет иметь функция F? Для этого рассмотрим вполне определенный пример, а именно, пусть А(-1,0), В(1,0), а С(0,1). Вычислим F=(0-(-1))(0-0)-(1—0)(1-(-1))=0-2=-2<0, следовательно, получили, что если точка лежит слева от прямой, то функция имеет отрицательное значение, а если справа, то соответственно положительный.
Задачи:
Задачи:
Программа алгоритм, записанный на языке программирования, служащий для выполнения каких-либо действий
25 09 2014
10 стр.
В языке программирования Turbo Pascal все данные, используемые программой должны принадлежать к какому-либо типу данных. Некоторые из них
13 10 2014
1 стр.
Блеза Паскаля. На основе языка Паскаль в 1985 г фирма Borland выпустила версию Turbo Pascal версии с этого времени язык Паскаль используется во всем мире в учебных заведениях в кач
02 10 2014
4 стр.
25 09 2014
1 стр.
Блеза Паскаля. Первоначально этот язык был создан для обучения программированию. Однако благодаря заложенным в нем большим возможностям структурного программирования он стал широко
25 09 2014
6 стр.
Основными достоинствами Паскаля являются легкость при изучении и наглядность программ. Кроме того, в языке Паскаль отражена концепция структурного программирования, имеется богатый
25 09 2014
1 стр.
В33 Середовище програмування Turbo Pascal 0: Підруч для учнів 10 кл серед загальноосв шк. – Ввпк: „Коледж”, 2008 – 47с
25 09 2014
4 стр.
Приведём простейший пример программы, единственная цель которой – вывести на экран какое-нибудь приветствие
14 09 2014
14 стр.