Олимпиадные задачи, использующие комбинаторные конфигурации

Пример 1. На одном острове Новой Демократии каждый из его жителей организовал партию, которую сам и возглавил. Отметим, что ко всеобщему удивлению даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предпологалось по Конституции острова, президенты всех партий. Посовещавшись, Островитяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите Островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены члены всех партий.

Исходные данные: каждая партия и, соответственно, ее президент имеют одинаковый порядковый номер от 1 до N (4 £ N £ 150). Вам даны списки всех N партий Острова Новой Демократии. Выведите предлагаемый Вами парламент в виде списка номеров его членов. (Олимпиада стран СНГ, г. Могилев, 1992 г.)

Решение: с теоретической точки зрения, данная задача совпадает с задачей генерации всех подмножеств из множества жителей острова новой демократии. Причем наиболее подходящим кажется первый подход к решению данной задачи, связанный с генераций различных сочетаний, начиная с одного жителя. Для полноты изложения этого подхода, опишем функцию сheck, которую следует применить в данной задаче. Исходные данные следует записать в массив s:array[1..150] of set of 1..150, заполнив каждый из n первых элементов этого массива множеством тех партий, в которых состоит тот или иной житель. Тогда функция проверки сочетания из элементов этого массива примет следующий вид:

function check(var p:list;k:integer): boolean;

var i:integer; ss:set of 1..150;

begin

ss:=[];

for i:=1 to k do ss:=ss+s[p[i]];

check:=(ss=[1..n])

end;

Как видно из описания функции, использование типа “множество”, позволяет не только упростить данную программу, но и существенно ускорить ее выполнение, по сравнению с работой с массивами. Однако большая размерность данной задачи не позволяет считать приведенное решение удовлетворительным во всех случаях. Так, уже для n = 100, перебор всех сочетаний из 4-х и менее жителей приводит к рассмотрению около 4-х миллионов вариантов. Для построения кода, пригодного для решения данной задачи при любых входных данных, несколько изменим описание массива s:

s: array[1..150] of

record name,number:integer;

partys: set of 1..150

end;

Здесь поле partys совпадает по смыслу с первоначальным описанием массива s, поле name cоответствует номеру (то есть фактически имени) жителя и первоначально данное поле следует заполнить числами от 1 до n cогласно индексу элемента в массиве записей, и поле number соответствует количеству элементов во множестве из поля partys, то есть имеет смысл сразу подсчитать, в каком количестве партий состоит тот или иной житель. Теперь следует отсортировать массив s по убыванию значений поля number. Верхнюю оценку для числа членов парламента (kmax) подсчитаем, построив приближенное решение данной задачи следующим образом: во-первых, включим в парламент жителя, состоящего в максимальном количестве партий, затем исключим эти партии из остальных множеств и заново найдем в оставшемся массиве элемент с максимальным значением поля number (уже пересчитанного) и включим его в парламент, и так далее, до тех пор пока сумма значений пересчитанных полей number у жителей, включенных в парламент, не будет равна n. Найденное количество членов парламента и будет kmax.

Теперь следует рассматривать сочетания из (kmax – 1) элемента, затем из (kmax – 2) и т. д. элементов. Если для сочетаний из какого-то рассматриваемого количества элементов k, решение найдено не будет, то это означает, что точным является решение с количеством членов парламента k +1. Так как массив s упорядочен, то, если решение для того или иного значения k существует, то, скорее всего, оно будет найдено при рассмотрении в лексикографическом порядке первых же сочетаний по k элементов. Поэтому временная трудоемкость в переборе возникает, только если решения c данным значением k не существует. В такой ситуации можно воспользоваться следующим “ненаучным” приемом: на поиск решения для каждого k, меньшего, чем kmax отведем фиксированное количество времени, скажем 2-3 секунды (точнее данное время стоит определить экспериментальным путем). Если за отведенное время решение не найдено, то следует считать полный перебор невозможным и закончить выполнение программы. В любом случае, мы будем иметь какое-либо решение исходной задачи: точное или приближенное, то есть, возможно содержащее больше членов парламента, чем минимально возможно. Однако, на практике такой подход почти всегда приводит к точному решению, в силу перебора “с предпочтением”, проводимого для каждого k (невозможность проведения полного перебора для какого-либо k на практике соответствует отсутствию решения для данного k).

Пример 2. Дан автобусный билет с номером, состоящим из N цифр. Расставить между цифрами знаки арифметических операций '+', '-', '*', '/' (целочисленное деление) и скобки таким образом, чтобы значение полученного выражения было равно 100. Можно образовывать многозначные числа из стоящих рядом цифр. Выражение должно быть корректным с точки зрения арифметики. Допустимы лишние скобки, не нарушающие корректности выражения. При вычислениях используется стандартный приоритет операций, число цифр N в номере билета не больше 6. (5-ая Всероссийская олимпиада по информатике, г.Троицк, 1993 г.)

Решение. для построения универсального алгоритма решения данной задачи будем считать слияние двух соседних цифр одной из операций. Тогда между каждой парой соседних цифр может стоять одна из 5 операций. Для N цифр получаем 5 ^{N -1} различных вариантов расстановки операций. Перебирать все варианты расстановки операций удобнее всего с помощью рассмотрения всех чисел в 5-ричной системе счисления, состоящих не более чем из N – 1 цифры, то есть для N = 6 от 00000 до 44444. Для перебора таких чисел необходимо написать процедуру прибавления 1 в 5-ричной системе счисления. Для каждого из вариантов расстановки операций перейдем от исходного массива из N цифр билета, к массиву из К чисел, где K = (N – количество операций слияния цифр в рассматриваемом варианте). Теперь мы должны рассмотреть все перестановки из K – 1 арифметической операции в данном варианте. Каждая перестановка соответствует одному из порядков выполнения арифметических операций. Так, для 4-х чисел, перестановка номеров операций 3, 1, 2 означает, что сначала нужно выполнить арифметическое действие между 3-м и 4-м числом, затем между 1-м и 2-м и затем оставшееся. Если результат выполнения действий данного варианта в порядке, соответствующем текущей перестановке, равен искомому числу 100, то задача решена и можно перейти к печати результата. Для данной задачи возможны и более эффективные решения, но в силу ее небольшой размерности, комбинаторный перебор оказывается вполне приемлемым.

Пример 3. Губернатор одной из областей заключил с фирмой " HerNet " контракт на подключение всех городов области к компьютерной сети. Сеть создается следующим образом: в области устанавливается несколько станций спутниковой связи, и затем от каждого города прокладывается кабель до одной из станций. Технология, используемая компанией требует при увеличении расстояния увеличения толщины кабеля. Таким образом, стоимость кабеля, соединяющего город со станцией, при используемой компанией технологии будет равна kL ², где L - расстояние от города до станции, а k - некий коэффициент. Вам требуется написать программу, определяющую минимальные затраты компании на установку сети.

Входные данные. Во входном файле записано число n (1 ≤ n ≤ 10) - количество городов в области. Затем идут положительные вещественные числа: k - коэффициент стоимости кабеля и P - стоимость постройки одной станции. Далее следует n пар вещественных чисел, задающих координаты городов на плоскости.

Выходные данные. В первую строку выходного файла нужно вывести минимальные затраты на установку сети (с тремя знаками после десятичной точки), во вторую - количество устанавливаемых станций. Далее вывести координаты станций (с тремя знаками после десятичной точки), а затем - список из n целых чисел, в котором i -ое число задает номер станции, к которой будет подключен i -ый город. (Кировский командный турнир по программированию, 2000 г.)

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

Решение геометрических задач.

Пусть даны две точки А (х₁,у₁) и В (х₂,у₂), как известно на плоскости они однозначно определяют одну единственную прямую. Давайте вспомним, как выглядит общее уравнение прямой: Ах+Ву+С=0. Тогда если считаем что наша прямая задана точками А и В, то уравнение прямой проходящей через эти две точки выглядит так: . Если пользоваться данной формулой, то нам придется постоянно делать проверку на деление на ноль, что не очень удобно, чтобы это избежать, лучше использовать такое равенство: (х-х₁)(у₂-у₁)=(у-у₁)(х₂-х₁).

Иногда бывает удобнее пользоваться уравнением прямой заданной в параметрическом виде:

, где t некий параметр, а (х₁,у₁) и (х₂,у₂) – координаты точек расположенных на рассматриваемой прямой.

Полезно будет так же вспомнить и как вычисляется расстояние между двумя точками: .

Задача: Вычислить расстояние которое пройдет путник двигаясь из точки А в точку В (при этом необходимо вычислить кратчайшее расстояние), если известно, что от точки (-1,0) до (1,0) вырыт непроходимый ров, пересечь который нельзя, можно лишь проходить по его краю.

(Пояснение:)

Решение задачи будет несколько проще, если мы введем функцию, которая позволяет определять взаимное положение трех точек. Итак, значит, у нас есть три точки: А (х₁,у₁), В (х₂,у₂) и С (х₃,у₃). Две из них однозначно определяют одну прямую и следовательно расположены на ней, весь вопрос состоит в том, а будет ли на этой же прямой располагаться и третья точка. Пусть прямую у нас определяют точки А и В, для того чтобы определить лежит на этой прямой точка С, составим следующую функцию: . Или F=((х₃-х₁)(у₂-у₁)-(у₃-у₁)(х₂-х₁)). Если 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, следовательно, получили, что если точка лежит слева от прямой, то функция имеет отрицательное значение, а если справа, то соответственно положительный.

Задачи:

1. В городе Глупове транспорт может делать повороты и развороты только на площадях, причем левые повороты мэр запретил. И поэтому за каждый левый поворот установлен штраф в размере 50$. Определить количество левых поворотов и размер штрафа, если известны координаты площадей, через которые проезжает автомобилист.

2. В городе Глупове транспорт может делать повороты и развороты только на площадях, причем левые повороты мэр запретил. При этом он установил такую систему штрафов, за первый левый поворот штраф 50$, за каждый последующий на 10% больше предыдущего, но любой разворот на 180° или проезд через площадь без поворота сбрасывает размер штрафа опять до 50$.

3. Известны координаты вершин многоугольника в порядке их обхода. Определить является ли данный многоугольник выпуклым.

4. Известны координаты вершин многоугольника в порядке их обхода. Определить является ли данный многоугольник выпуклым. При этом если многоугольник является не выпуклым, то проверить можно ли выбросить одну точка, такую чтобы многоугольник стал выпуклым. Указать порядковый номер этой точки, ее координаты, а также изобразить исходный и полученный многоугольники на экране.

Помимо того, что рассмотренная нами с вами функция F позволяет определить взаимное расположение трех точек, а так же в случае, когда эти точки не лежат на одной прямой, определить по какую сторону третья точка расположена от прямой, она удобна еще и тем, что модуль значения этой функции (в случае, когда она не равна нулю) равен двум площадям треугольника, вершины которого расположены в исходных трех точках, то есть Sr=1/2|F|.

Задачи:

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

2. Вычислить площадь произвольного n-угольника.

Контрольная работа.

Задача: Заданы координаты концов двух отрезков, определить взаимное расположение этих отрезков (определить лежат они параллельных, совпадающих или пересекающихся прямых, в случае совпадения прямых определить имеют отрезки общую точку, общую часть или не имеют общих точек, в случае пересечения прямых определить имеют отрезки общую точку или нет).

Приближенные методы вычислений.

Задача 1. Вычислить приближенное значение суммы

1 + x/1! + x2/2! + x3/3! + …

Считаем, что нужное приближение получено, если вычислена сумма нескольких слагаемых, и очередное слагаемое оказалось по модулю меньше, чем данное малое положительное число e.

Для решения задачи мы должны выполнить следующие действия:

2) получить очередное слагаемое (назовем его а);

3) сравнить абсолютную величину слагаемого а с e и, в зависимости от результата сравнения, либо продолжить, либо прекратить вычисления.

Program p;

var a: real;

x: real;

e: real;

i: integer;

S: integer;

begin

readln(x, e);

i:=1;

a:=1;

S:=0;

WHILE a>e DO

begin

S:=S+a; i:=i+1; a:=a*x/i;

end;

writeln(‘приближенное значение суммы=’,S:4:2)

end.

Задача 2. Рассмотрим часто встречающуюся задачу приближенного решения уравнения f(x)=0, где f(x) – заданная функция. Решить уравнение – значит найти такое значение х*, при котором f(x*)=0. Поиск решения осуществляется на интервале [a;b], причем f(a)<0, а f(b)>0. Используем метод деления пополам. Находим точку с=(а+b)/2 – середина отрезка. Если f(c)>0, то границу b изменяем на значение с, а если f(с)<0, то изменяем а. Процесс продолжаем, пока длина интервала не будет меньше заданной точности.

Y     f(x)     0 a c b X

Пусть f(x)=x²-2, т.е. мы попытаемся найти значение квадратного корня из 2.

Program popolam;

const eps=1.0E-3;

var a,b,c:real;

Function eg(x,y:real):boolean;

begin

Eg:=Abs(x-y)<eps

end;

Function F(x:real):real;

begin

F:=Sgr(x)-2

end;

BEGIN

Writeln(‘введите интервал’); readln(a,b);

if F(a)*F(b)>0 then writeln(‘на этом интервале мы не можем

найти решение уравнения’)

else begin

while Not Eg(a,b) do

begin c:=(a+b)/2;

if F(c)>0 then b:=c else a:=c

end;

writeln(‘Результат ’,a)

end;

readln

end.

Можно с помощью этой программы решить уравнения:

x2-6x+5=0 x-cosx=0 x-lnx-2=0 2x3-9x2-60x+1=0

Метод итераций

Пусть нужно решить уравнение f(х)=0, из которого мы получаем уравнение следующего вида: х=u(х), для решения этого уравнения методом итераций необхдимо составить последовательность приближений, причем надо учитывать что далеко не каждая последовательность приведет нас к нахождению корня, необходимым и достаточным условием для использования метода итераций является u’(x)<1. Итак, для нахождения последовательности выбираем произвольно х0, вплоть до случайного числа, вычисляем х1=U(х0), х2=U(х1) х3=U(х2) и т.д. опка не будет выполнено неравенство |х_i-x_i+1|<e.

Y     0 a x1 x2…..... xn-2 xn X

Задача 3. Пусть непрерывная положительная на отрезке [a,b] (a<b) функция. Вычислим площадь фигуры, ограниченную графиком функции f(x), осью х и прямыми х=а и х=b. Для этого разобьем отрезок [a,b] на n равных отрезков одинаковой длины Dx=(b-a)/n a=x0<x1<…<xi<xi+1<….<xn=b

На каждом из отрезков [xi,xi+1] как на основании, построим прямоугольник с высотой f(xi).

Площадь прямоугольников мы умеем находить. Сумма площадей всех прямоугольников даст приближенное значение площади фигуры:

Sприб=(b-a)/n*(f(x0)+….f(xn-1))

Естественно, что чем мельче будет разбиение, тем точнее мы подсчитаем площадь фигуры.

Для отладки программы возьмем функцию f(x2) на отрезке [1,2]. Площадь фигуры равна 2,333….

program trapez;

const eps=1.0E-3;

var a,b,s,dx:real;

i,n: integer;

Function eg(x,y:real):boolean;

begin

Eg:=Abs(x-y)<eps

end;

Function F(x:real):real;

begin

F:=Sgr(x)

end;

BEGIN

Writeln(‘введите интервал и число частей для разбивки’); readln(a,b,n);

x:=a; dx:=(b-a)/n; s:=0;

For i:=1 to n-1 do

begin

s:=s+F(x);

x:=x+dx;

end;

writeln(‘Результат = ’,(b-a)/n*s);

readln;

end.

Вычислить площадь криволинейных трапеций для следующих функций: f(x)=1/(1+x) [0,1] f(x)=1/x [1,3]

f(x)=sinx [0,p/2]

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

Задача 4. Для вычисления элементарных функций в математике широко распространено представление этих функций в виде некоторых бесконечных сумм. Не вдаваясь в обоснование таких представлений, приведем некоторые их них:

ex=1 + x + x2/2! + x3/3! + … + xn/n! + …

sinx=x – x3/3! + x5/5! – x7/7! +…+ (-1)nx2n-1/(2n+1)! +….

cosx= 1 – x2/2! + x4/4! – x6/6! +…+ (-1)nx2n/(2n)! +….

ln(1+x)=x – x2/2 + x3/3 – x4/4 + …+ (-1)n+1xn/n + ….. (-1<x<=1)

В каждом из разложений точность представления функции будет, вообще говоря, тем выше, чем больше взято слагаемых в сумме. Причем значения самих слагаемых с ростом n стремятся к нулю. Для вычисления значений функции с некоторой заданной точностью e поступают следующим образом. Вычисляют и суммируют слагаемые до тех тор, пока очередное слагаемое не станет по абсолютной величине меньше e или абсолютное значение разности между соседними слагаемыми не станет меньше e. Полученную сумму и принимают за приближенное значение функции.

Вычисли функцию sinx.

Program rad;

const eps=1.0E-3;

var x,sn,ss: real;

p, n: integer;

{p – используется для чередования знака слагаемого}

Function Eg(x,y;real):boolean;

begin

Eg:=Abs(x-y)<eps

end;

Function F(n:integer;var x:real):real;

var i:integer;

s:longint;

begin

s:=1;

for i:=2 to n do s:=s*i;

x:=x*sqr(x); F:=x/s

end;

BEGIN

writeln(‘Введите значение х’);

readln(x);

ss:=0; sn:=x; n:=1; p:=1;

Repeat

ss:=sn; {предыдущее значение слагаемого}

{ новое значение слагаемого}

n:=n+2; p:=-1*p; sn:=ss+p*F(n,x)

Until Eq(ss,sn) or (n>=12);

Writeln(‘Результат=’,sn); readln

end.

Задача 5. Метод Монте-Карло для приближенного вычисления площади.

Пусть есть какая-нибудь фигура на плоскости, расположенная внутри стандартного квадрата со сторонами параллельными координатным осям.

Пусть про любую точку квадрата мы можем быстро узнать, попадает ли эта точка внутрь фигуры или нет.

Для выбора точек используют случайные числа Random(x)

Если вызвать функцию много раз подряд, то множество полученных чисел будет равномерно распределено по отрезку [0,a]

Program ss;

var n: integer; {количество точек}

a: integer; {длина стороны квадрата}

m, i: integer;

x,y: real;

begin

writeln(‘введите кол-во точек и сторону квадрата’);

readln(n,a);

m:=0;

for i:=1 to n do

begin

x:=Rondom(a); y:=Random(a);

if точка(x,y) внутри квадрата then m:=m+1

end;

S:=(m/n)*a*a

writeln(‘Результат ’,s);

end.

Множества.

Множество в Паскале представляет собой набор различных элементов одного (базового) типа.

Базовый тип – это совокупность всех возможных элементов множества. Всего в базовом типе должно быть не более 256 различных элементов. Значение переменной множественного типа может содержать любое количество различных элементов базового типа – от нуля элементов (пустое множество) до всех возможных значений базового типа

Множества, используемые в программе, могут быть описаны либо в разделе Type:

Type <имя типа> = Set Of <тип элементов>;

Var <имя множества>: <имя типа>;

Либо непосредственно в разделе описания переменных Var:

Var <имя множества>: Set Of <тип элементов>;

Пример.

Type mnog_Char=Set Of Char;

Var mn1: Set Of Char;

mn2: mnog_Char;

mn3: Set Of ‘A’..’Z’;

s1: Set Of Byte;

s2: Set Of 1000..1200;

Здесь mn1 и mn2 – это множества символов; так как различных символов всего 256, то тип Char можно использовать в качестве базового;

mn3 – множество больших латинских букв;

s1 – множество целых чисел (от 0 до 255); так как тип Byte содержит только целые числа от 0 до 255, его тоже можно использовать в качестве базового типа элементов;

s2 – множество целых чисел от 1000 до 1200.

Формирование (конструирование) множеств. В программе элементы множества задаются в квадратных скобках, через запятую. Если элементы идут подряд друг за другом, то можно использовать диапазон.

Пример Type digit = Set Of 1..5;

Var s: digit;

Переменная s может принимать значения, состоящие из любой совокупности целых чисел от 1 до 5;

[ ] - пустое множество;

[1], [2], [3], [4], [5] – одноэлементные множества;

[1,2], [1,3], …., [2,4], [4,5] – двухэлементные множества (пара любых элементов);

[1,2,3], [1,2,4], …, [3,4,5] - трехэлементные (тройка элементов);

[1,2,3,4], [1,2,3,5], [1,2,4,5], [1,3,4,5], [2,3,4,5] - четырехэлементные;

[1,2,3,4,5] – полное множество (взяты все элементы базового типа).

Операции над множествами

Объединение двух данных множеств называется множество элементов, принадлежащих хотя бы одному из этих множеств. Знак операции объединения множеств - «+».

A B A+B

Примеры

1) [‘A’, ‘F’] + [‘B’, ‘D’] = [‘A’, ‘F’, ‘B’, ‘D’];

2) [1..3, 5, 7, 11] + [3..8, 10, 12, 15..20] = [1..8, 10..12, 15..20]

Пусть S1:=[1..5, 9], a S2:=[3..7, 12]. Тогда если S:=S1 + S2,

то S=[1..7, 9, 12].

Пусть А1:=[‘a’..’z’]; A1:=A1 = [‘A’]. Тогда A1=[‘A’, ‘a’..’z’].

Пересечением двух множеств называется множество элементов, принадлежащих одновременно и первому, и второму множеству. Знак операции пересечения - «*».

А B A*B

Примеры.

3. [‘A’, ‘F’] * [‘B’, ‘D’] = [ ], так как общих элементов нет;

2) [1..3, 5, 7, 11] * [3..8, 10, 12, 15..20] = [3, 5, 7];

3) если S1:=[1..5, 9] и S2:=[3..7, 12], a S:=S1 * S2, то S=[3..5].

Разностью двух множеств называется множество, состоящее из тех элементов первого множества, которые не являются элементами второго. Знак операций вычитания множеств - «¾»

A B A-B

Примеры.

[‘A’, ‘F’] – [‘B’, ‘D’] = [‘A’, ’F’ ], так как общих элементов нет;

[1..3, 5, 7, 11] – [3..8, 10, 12, 15..20] = [1, 2, 11];

если S1:=[1..5, 9] и S2:=[3..7, 12], a S:=S1 – S2, то S=[1, 2, 9];

A1:=[‘A’..’Z’]; A1:=A1 – [‘A’]. Тогда А1=[‘B’..’Z’].

Операция определения принадлежности

элемента множеству

Эта логическая операция обозначается служебным словом in. Результат операции имеет значение true, если элемент входит в множество, и false в противном случае.

Примеры.

4. Выражение 5 in [3..7] имеет значение true, так как 5 Î [3;7]

Выражение ‘a’ in [‘A’..’Z’] имеет значение false, так как маленькой латинской буквы «а» нет среди больших латинских букв.

Сравнение множеств

Для сравнения множеств используются операции отношения:

= - проверка на равенство (совпадение) двух множеств;

<> - проверка на неравенство двух множеств;

<=, < - проверка на вхождение первого множества во второе множество;

>=, > - проверка на вхождение второго множества в первое множество.

Первое множество меньше или равно второму (A£B)

B A B A B A

true false true

Первое множество меньше второго (A<B)

B

B A B A A

true false false

Пример. Составить программу выделения следующих множеств из множества целых чисел от 1 до 30:

- множества чисел, кратных 2;

- множества чисел, кратных 3;

- множества чисел, кратных 6;

- множества чисел, кратных 2 или 3;

Вопросы для обсуждения:

1. Сколько множеств надо описать? (Каков тип их элементов? (четыре множества с элементами типа Byte).

2. Каково начальное значение множеств? (начальное значение множеств – пустое множество).

3. Как формируются множества? (Первые два формируются перебором всех чисел данного промежутка и отбором подходящих, а третье и четвертое получаются из первых двух путем применения операции пересечения или объединения).

4. Как осуществить вывод сформированных множеств? (Вывод множеств производится ТОЛЬКО поэлементно, поэтому удобно составить процедуру и передавать в нее множество, элементы которого и будут выводить на экран. Для этого в разделе типов надо создать соответствующий тип и использовать его в дальнейшем).

Program mnog;

const n=30;

type mn=Set Of 1..n;

var n2, n3, n6, n23: mn;

k: integer;

procedure print(m: mn);

var i: integer;

begin

for i:=1 to n do if i In m then write(i:3);

writeln;

end;

BEGIN

n2=[ ]; n3=[ ];

for k:=1 to n do

begin

{если число делится на 2, то заносим его в n2 }

if k Mod 2 = 0 Then n2:=n2+[k];

{если число делится на 3, то заносим его в n3 }

if k Mod 3 = 0 Then n3:=n3+[k];

end;

{числа, кратные 6, - это те, которые кратны и 2 и 3, поэтому это пересечение двух множеств, а числа, кратные 2 или 3, - это объединение этих же множеств}

n6:=n2*n3; n23:=n2+n3;

writeln(‘числа, кратные 2’); print(n2);

writeln(‘числа, кратные 3’); print(n3);

writeln(‘числа, кратные 6’); print(n6);

writeln(‘числа, кратные 2 или 3’); print(n23);

END.

Пример 2. Если взять то общее, что есть у боба с ложкой, добавить кота и поместить в тепло, то получится муравей. Так ли это?

program bob;

var y1, y2, y3, y4, x: Set Of Char;

s: Char;

BEGIN

y1:=[‘б’, ‘о’, ‘б’]; y2:=[‘л’, ‘о’, ‘ж’, ‘к’, ‘а’];

y3:=[‘к’, ‘о’, ‘т’]; y4:=[‘т’, ‘е’, ‘п’, ‘л’, ‘о’];

x:=(y1*y2) + y3 – y4;

writeln(‘множество х’);

for s:=’a’ to ‘я’ do if s In x then write(s); writeln;

{проверка: состоит ли муравей из кота}

if y3<=x then write(‘муравей состоит из кота’)

else write(‘муравей не состоит из кота’);

END.

Пример 3. Дан ребус МУХА + МУХА = СЛОН

Каждой букве соответствует некоторая цифра, разным буквам соответствуют разные цифры. Необходимо заменить буквы цифрами так, чтобы получить верное равенство.

Для решения этой задачи применим метод перебора с возвратом. Используем множество S1 для хранения цифр слова МУХА, причем будем заносить в него цифры последовательно, учитывая уже внесенные цифры. Начальное значение S1 – пустое множество. После выбора всех цифр первого слова формируем соответствующее число и находим число, соответствующее слову СЛОН. Выделяем цифры СЛОНа (множество S2), и если слова состоят из различных цифр (то есть пересечение S1 и S2 пустое) и все цифры СЛОНа разные, то выводим решение на экран. Далее удаляем из множества S1 последнюю внесенную цифру и пытаемся выбрать еще одно ее значение. Таким образом, мы перебираем все возможные варианты и выводим на экран только те, которые удовлетворяют равенству.

Заметим, что букве «М» в слове МУХА может соответствовать цифра от 1 до 4, а букве «А» в этом же слове не может соответствовать 0.

Program myxa;

type mn=Set Of 0..9;

var m, y, x, a: 0..9; {цифры числа МУХА}

n1, n2: integer; {числа МУХА и СЛОН}

a1, a2, a3, a4: 0..9; {цифры числа СЛОН}

S1, S2:mn;

procedure Print(x,y:integer); {вывод решения в виде ребуса }

begin

writeln(x:5);

writeln(‘+’);

writeln(x:5);

writeln(‘____’);

writeln(y:5);

end;

BEGIN

s1:=[ ]; s2:= [ ];

for m:=1 to 4 do

begin

s1:=s1+[m]; { заносим первую использованную цифру}

for y:=0 to 9 do {если это цифра не была еще взята, то добавляем ее во множество цифр числа МУХА и выбираем цифру для следующей буквы }

if Not (y In s1)

then begin s1:=s1+[y];

for x:=0 to 9 do

if Not (x In s1)

then begin s1:=s1+x;

for a:=1 to 9 do

if Not (a In s1)

then begin s1:=s1+[a];

n1:=1000*m+100*y+10*x+a;

n2:=2*n1;

a1:=n2 div 1000;

a2:=n2 div 100 mod 10;

a3:=n2 div 10 mod 10;

a4:=n2 mod 10;

s2:=[a1,a2,a3,a4];

if (s1*s2=[]) and ([a1]*[a2]*[a3]*a[4]=[])

then Print(n1,n2);

s1:=s1-[a];

end;

s1:=s1-[x];

end;

s1:=s1-[y];

end;

s1:=s1-[m];

end;

END.

Задачи:

14.1 Дана непустая последовательность символов. Построить и напечатать множества, элементами которых являются встречающиеся в тексте:

· цифры от ‘0’ до ‘9’ и знаки арифметических операций;

· буквы от ‘A’ до ‘F’ и от ‘X’ до ‘Z’;

· знаки препинания и буквы от ‘E’ до ‘N’.

14.2 Вывести в алфавитном порядке элементы множества, составленного из произвольных букв от ‘A’ ….’Z’.

14.3 Составить программу печати в возрастающем порядке всех цифр, входящих в десятичную запись данного числа..

14.4 Дан текст. Вывести в алфавитном порядке все буквы текста, входящих в него: а) не менее двух раз;б)не более двух раз; в) более двух раз.

14.5 Дан текст. Подсчитать количество строчных и прописных букв.

14.6 Составить программу подсчета общего количества цифр и знаков ‘+’, ‘-‘, ‘*’ в строке s, введенной с клавиатуры.

14.7 Задано множество вычислительных машин. Известен набор машин, имеющих в каждом из 10 техникумов. Построить и распечатать множества, включающие в себя вычислительные машины:

а) которыми обеспечены все техникумы;

б) которые имеет хотя бы один техникум;

в) которых нет ни в одном техникуме.

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

14.9 Написать программы решения ребусов:

а) ЛОБ + ТРИ = САМ, б) ИСК + ИСК = КСИ,

в) ТОЧКА + КРУГ = КОНУСг) VOLVO + FIAT = MOTOR,

д) АВ + ВС + СА = АВС.

14.10 Дана не пустая последовательность символов. Напечатать количество вхождений в данную последовательность заглавных латинских букв ‘A’, ‘B’, ‘C’.

14.11 Вывести на экран все простые числа от 11 до 101.

Создание меню.

Меню бывает линейное и вложенное, горизонтальное и вертикальное, причем вложенное меню создают горизонтальным. Для организации линейного меню необходимо вывести имена каждого меню на экран, причем первое выделив каким нибудь образом. При нажатии стрелок влево или вправо происходит смещение выделения с одного раздела меню на другое, то есть с того которое было выделено снимается подсветка, а следующее (предыдущее) подсвечивается, если стрелка была нажата на конечном меню, то необходимо с него снять а подсветить либо первое, либо последнее. При нажатии клавиши Home – подсвечивается первый раздел меню, End – последний, при нажатии Esc – происходит выход из программы. При нажатии клавиши Enter происходит выполнение действия которое указано в меню.

Задача: Составить программу для организации функционирования следующего меню:

1 число

2 число

сложение

вычитание

умножение

деление

результат

При выборе первых двух пунктов появляется экран на котором запрашивается значения соответсвенно первого или второго чисел, при выборе 3, 4, 5 или 6 пунктов выдается сообщение что соответсвующее дейсвтие выполнено, но полученное значение не выводится. При этом необходимо отслеживать введены ли оба числа, если не хватает хотя бы одног нужно выдать сообщения вида: «Не хватает данных». При выборе меню результат нужно вывести результат выполнения последнего действия, если действий не было совершено то нужно об этом сказать.

Для организации линейного меню необходимо пользоваться одномерным массивом.

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

Работа с мышью

Для того чтобы добавить в прорамму курсор мыши и организовать с ним работу, необходимо подключить модуль mouse. При этом в текстовом режиме курсор будет выглядеть в виде прямоугольника (размерами 8х8, при этом указывается координаты верхнего левого угла), а в графическом в виде стрелки.

Для того чтобы на экране появился курсор мыши необходимо запустить процедуру mouseshow. Для отключения изображения курсора выполняется процедура mousehide. Это необходимо делать из-за того, что при выводе на экран в точку, где изображен курсор, может происходить несколько не приятные искажения игуры или числа (т.к. в графическом режиме точки закрытые курсором закрашены не будут).

Для организации действий по желчку мыши необходимо использовать процедуру mouseread(x,y,b); где х и у – это координаты указателя (в графическом режиме размер 640х200), а b – информация о нажатой клавише мыши, все три параметра должны иметь тип word. Варианты значений параметра b: 0 – клавиша не была нажата; 1 – была нажата левая клавиша мыши; 2 – была нажата правая клавиша мыши; 3 – были нажаты одновременно левая и правая клавиши мыши (либо средняя).

Приведем фрагмент программы выполнение которой приведет к тому что по щелчку левой клавиши мыши на экране в левом верхнем углу будут отображаться сведения о координатах нахождения курсора мыши.

Для графического режима:

mouseshow;

repeat

mouseread(x,y,b);

if b=1 then begin

delay(100);

setfillstile(1,0);

bar(0,0,60,10);

str(x,xg); str(y,yg);

outtextxy(1,1,xg);

outtextxy(30,1,yg);

end;

until b=2;

Ниже приведен фрагмент программы который отображает в верхнем левом углу сведения о координатах курсора мыши соответсвующие его местоположению на экране.

Для текстового режима:

mouseshow;

repeat

mouseread(x,y,b);

gotoxy(1,1);

write(x:3,y:5);

xt:=x div 8+1;

yt:=y div 8+1;

gotoxy(1,2);

write(xt:3,yt:5);

until b=2;

Задачи:

1. Изображение звездочки в точке нажатия клавиши мыши.

2. Создать модель пианино. Изображение клавиш при щелчке, по которым происходит звук соотвествующий нажатой ноте.

3. Дана панель содержащая буквы алфавита, а также кнопку очистки экрана. при щелчке по букве происходит ее выделение, при двойном щелчке выделение снимается, при щелчке по другой букве с предыдущей выделение снимается а выделяется та по которой произвели щелчок. При выделенной букве и при щелчке в любом месте экрана кроме панели появляется изображение этой буквы на экране там где произвели щелчок. Щелчок по кнопке очистка приводит к тому, что очищается весь экран за исключением панели.

4. Аналогично третьей задаче только происходит перетаскивание букв на экран.