Автор: Корженевич Ю.В.
Теги: комбинаторный анализ теория графов теория вероятностей математическая статистика программирование информатика
ISBN: 5-7855-0251-8
Год: 1989
Текст
Ю В КОРЖЕНЕВИЧ
Комбинаторные задачи;
олимпиады
z Mill \V6f llll/xiljg /
по програттироВанию
Ю. В. КОРЖЕНЕВИЧ
Комбинаторные задачи:
олимпиады
по
программированию
УЧЕБНО-МЕТОДИЧЕСКОЕ
ПОСОБИЕ
Минск
„Университетское”
1989
ББК 22.174
К 66
УДК 519.1-37 (079.1)
Рецензент
кандидат физико-математических наук В. М. Котов
К
1602100000-072
М 317(03)-89 39-89
ISBN 5-7855-0251-8
© Издательство „Университетское”, 1989
ПРЕДИСЛОВИЕ
Методы дискретной математики широко используются в самых раз-
нообразных прикладных дисциплинах. Дискретная математика являет-
ся фундаментом для систем проектирования технических устройств и
систем с дискретным принципом действия, для построения машинных
алгоритмов. Занимательный характер комбинаторных задач позволяет
широко и эффективно использовать их для олимпиад по программиро-
ванию*
Опыт Республиканских и Всесоюзных олимпиад показывает, что
участники, в совершенстве знающие языки программирования и опера-
ционные системы, часто оказываются беспомощными перед предлагае-
мыми задачами.
Программа, по определению Н. Вирта, есть структура данных + алго-
ритм. При этом решение комбинаторных задач связано с выполнением
вычислений на дискретных конечных математических структурах, что,
естественно, предполагает выделение структур данных сложного типа
с их последующей реализацией средствами выбранного языка програм-
мирования.
Первая глава книги посвящена структурам данных и основным ба-
зисным операциям над ними. Рассмотрены стеки, очереди (кольцевой
буфер), связанные списки (одно- и двунаправленные), структура дан-
ных (N-дольный граф).
Во второй главе приведены алгоритмы и программы генерации сис-
темы подмножеств множества, перестановок и сочетаний; представлена
схема поиска с возвращением, являющаяся наиболее общим методом
для создания и исследования некоторого класса комбинаторных (диск-
ретных и конечных) объектов; алгоритмы случайного поиска.
Третья глава содержит программы решения некоторых заниматель-
ных комбинаторных задач: формирования ряда Фарея, ханойской башни,
генерации кольца Вирта, определения принадлежности точки много-
угольнику, подсчета числа изолированных 0-областей в (0,1 ^матри-
це и т. д.
Материал книги предполагает знание основ языков программирова-
ния (бейсик, фортран, паскаль, ПЛ/1).
Разработке и анализу алгоритмов посвящены книги [2,10]. Описание
различных структур данных имеется в [5, 18]. Вопросы исчерпывающего
3
поиска, порождения и представления комбинаторных объектов рассмот-
рены в [12, 17, 18, 22, 26, 32, 38]. Методы случайного поиска представле-
ны в [30, 37], алгоритмы на графах и функциональных семантических
сетях излагаются в [1, 3, 4, 13-15, 20-29, 31-34, 36, 39, 40]. Примеры раз-
личных занимательных задач приведены в [6-9,11,16,35].
Автор выражает благодарность Воробьеву В. Д., Бекеру В. 3., Гиршо-
вичу Б. Д., Лесковцу Е. А., Рудицкому А. А., Шиманскому Е. В., Черня-
ку С. П. за помощь при подготовке рукописи к изданию.
Глава 1.СТРУКТУРЫ ДАННЫХ
Решение комбинаторных задач предполагает выделение структур
данных сложного типа с их последующей реализацией средствами вы-
бранного языка программирования. При этом структура данных может
не зависеть от конкретных языковых конструкций (абстрактная струк-
тура данных).
Под структурой данных понимают совокупность элементов фикси-
рованных типов и набор базисных операций, определяющих организа-
цию и способ обработки данных.
Рассмотрим некоторые основные структуры данных.
1.1. Стеки
Стеком называется одномерная структура данных, загрузка или
увеличение элементов для которой осуществляется с помощью указа-
теля стека в соответствии с правилом LIFO (last-in, first-out - последним
введен, первым выведен).
Указатель стека sp (stack pointer) содержит в любой момент времени
индекс (адрес) текущего элемента, который является единственным
элементом стека, доступным в данный момент времени для обработки.
Существуют следующие основные базисные операции для работы со
стеком (для случая, когда указатель стека всегда задает ячейку, нахо-
дящуюся непосредственно над его верхним элементом).
1. Начальная установка:
sp := 1;
2. Загрузка элемента х в стек:
stack [sp] := х;
sp := sp + 1;
3. Извлечение элемента из стека:
sp := sp - 1;
х := stack [sp];
4. Проверка на переполнение и загрузка элемента в стек:
if sp < = sd then
begin stack [sp] := x; sp := sp + 1 end
else
{переполнение};
5
Здесь sd — размерность стека.
5. Проверка наличия элементов и извлечение элемента стека:
if sp > 1 then
begin sp := sp - 1; x := stack [sp] end
else
{антипереполнение};
6. Чтение данных из указателя стека без извлечения элемента:
х := stack [sp — 1],
Отметим, что изменение значений указателя стека может быть осу-
ществлено в противоположном направлении. В этом случае указатель
стека определяет последний элемент массива. Тогда удаление элемента
будет сопровождаться увеличением значения указателя стека, а загруз-
ка элемента - уменьшением.
Пример состояний стека представлен на рис. 1.1.
Рис. 1.1. Состояния стека:
а — исходное; б — после загрузки элемента х; в — после загрузки элемента у; г — после
загрузки элемента z; д — после извлечения элемента z; е — после извлечения элемента у;
ж — после извлечения элемента х
6
1.2. Очереди
Очередь - одномерная структура данных, для которой загрузка или
извлечение элементов осуществляется с помощью указателей начала
(head) и конца (tail) очереди в соответствии с правилом FIFO (first-in,
first-out - первым введен, первым выведен).
Рис. 1.2. Кольцевой буфер
Как правило, при работе с очередью используется кольцевой &уфер
(рис. 1.2). Для его организации существуют следующие основные базис-
ные операции:
7
a 5 6
toil^ heo(T toil * head tail r head
У
X X
г g e
toil tail toil r
head head heodr
z z 2
У У
X
Рис. 1.3. Состояния очереди:
a — исходное; б — после добавления элемента х; в — после добавления элемента у;
г ** после добавления элемента z; д — после исключения элемента х; е — после исклю-
чения элемента у
1. Начальная установка:
head := 1; tail := 1;
2. Добавление элемента х :
queue [tail] := х; tail := tail + 1;
if tail > qd then tail := 1;
Здесь qd - размерность очереди.
3. Исключение элемента х:
х := queue [head]; head := head + 1;
if head > qdthen head := 1;
4. Проверка переполнения очереди и включение в нее элемента:
temp := tail + 1;
if temp > qd then temp := 1;
if temp = head then
{переполнение]
else begin queue [tail] := x; tailtemp end;
8
5. Проверка наличия элементов и исключение элемента х:
if head := tail then
{очередь пуста}
else begin
x := queue [head]; head := head + 1;
if head > qd then head := 1;
end;
Отметим, что при извлечении элемента из очереди все элементы мо-
гут также перемещаться на один шаг к ее началу (рис. 1.З.).
1.3. Связанные списки
Связанный список представляет собой структуру данных, состоя-
щую из узлов (как правило, записей), содержащих указатели на следую-
щий узел. Указатель, который ни на что не указывает, снабжается
значением null. Таким образом, в каждый элемент связанного списка
добавляется указатель (звено связи).
Приведем основные базисные операции для работы с однонаправ-
ленным связанным списком.
1. Включение элемента Q после элемента Р:
link [q] := link [р];
link [р] := q;
Здесь q - индекс элемента, который должен быть вставлен в список после элемента с
индексом р.
2. Исключение преемника элемента X:
if link [х j < > null then
link [x] := [link [x ]]
else
{элемент X не имеет преемника};
Отметим, что элемент, следующий в списке за элементом X, называ-
ется преемником элемента X, а элемент, расположенный перед элемен-
том X, называется предшественником элемента X. Если элемент X не
имеет преемника, то содержащемуся в нем указателю присваивается
значение null.
3. Включение элемента Y перед элементом X:
prev := 0;
while (link [prev ] < > null) and (link [prev ] < > x) do
prev :=link [prev];
if link [prev ] = x then
begin link [prev ] := y; link [y ] := x end
else
{элемент X не найден};
Здесь link [0] является началом списка.
9
a
указатель — б
данные -* head: null
a — формат элемента списка; б — пустой список; в — список из четырех элементов; г — вклю-
чение элемента после элемента q; д — исключение элемента р
10
4. Исключение элемента*.
prev:« 0;
while (link [prev] < > null) and (link [prev] < > x) do
prev := link [prev];
if link [prev] := x then link [prev] := link [link [prev]];
else
(элемент X не найден];
Рис. 1.5. Состояния двунаправленного связанного списка:
а — формат элемента списка; б — пустой список; в — список из четырех элементов; г —
включение элемента у перед элементом х; д — исключение элемента х
11
Отметим, что исключение последнего элемента из однонаправлен-
ного списка связано с просмотром всего списка (рис. 1.4).
В двунаправленном связанном списке (рис. 1.5) каждый элемент
имеет два указателя (succlink - описывает связь элемента с преем-
ником, prediink - с предшественником).
Приведем основные базисные операции для работы с двунаправлен-
ным связанным списком.
1. Включение элемента Y перед элементом X:
succlink [у] := х;
prediink [у] :s prediink [х];
succlink [prediink [х]] := у;
prediink [х] := у;
2. Включение элемента Y после элемента X:
succlink [у] := succlink [х];
prediink [у] := х;
prediink [succlink [х]] у;
succlink [х] :=у;
3. Исключение элемента X :
prediink [succlink [х]] := prediink [х];
succlink [prediink [х]] := succlink [х];
1.4. N-дольный граф*
В общем случае структуру данных S можно определить:
S = (D, R),
где D и R соответственно множества элементов и отношений между эле-
ментами данных. ___
Пусть множество D состоит из N подмножеств { Vr}, k = 1, N; а мно-
жество R из г < (2) подмножеств { Rr? J, где (2) “ число сочетаний из N
по 2 (см. п. 2.3 ). При этом для каждого подмножества Vrc D существует
хотя бы одно подмножество Vic D, 1 + к, для которого Vr и Vi находят-
ся в отношении Rr, ic R.
Будем называть подмножества{ Vr}, k = 1, Nдолями графа: Vi - пер-
вой долей, Nг - второй долей и т. д. Элементы, составляющие к-ю долю
графа Vr, ке{ 1,2,...,N}, назовем к-вершинами графа: Vr = {v^}, i = IjIr.
Считаем, что i-я вершина к-й доли графа Vp^ Vk соединена ребром
и । с j-вершиной 1-й доли графа v?e Vj при наложенном на эти вершины
отношении Rk р
* Данный подраздел написан совместно с В. 3. Бекером и В. Д. Воробьевым.
12
Заменив подмножество Rkl£R множеством Uk> i = {u^’ ]}, i® {1,...
...,nk}, j ® а множество R - множествами {Uk> J, k,
к * 1, получим
SN = ({Vk},{Uk>iD,
где SN - N-дольный граф; {Vk} - множества вершин графа; {Uk - мно-
жества ребер графа.
Примеры N-дольных графов для Ne (2,3,5} приведены на рис. 1.6.
Структура данных - N-дольный граф может быть описана:
type вершина = record верш: char;
степ 1: integer;
степ 2: integer;
CTenN_j г integer;
первая = array [l..ML|] of вершина;
вторая = array [l..ML2] of вершина;
N-я = array [l..MLxj] of вершина
строка 2 = array [I..ML2] of char;
таблица! 2 - array [1..ML J of строка^;
строку 3 = array [i..ML3] of char;’
Ta6nHua1>3 = array[l..ML1]of строка! 3;
строка2 з « array [l..ML3] of char;
таблица2 3-array [l..ML2] of строка2 3;
таблица
строка 2 2 = array [1..ML 2 ] of char;
CN-11CN „ CN
r2 r2 = array [1..ML 2 1 of строка
CN—l’cN CN—1
varU! 2 таблица! 2;
U! 3 таблица! 3;
r2 r2 5
U2 3 таблица2 3;
V!: первая;
V2: вторая;
VN: N-я;
В приведенном описании на каждую пару долей Vk с D и <= D на-
ложено отношение Rk b k = 1, N; 1 = 1, N; к ¥= 1. При этдм двумерные мас-
сивы Uk ! (i, j) описывают множества ребер графа, а одномерные массивы
Vk (i) - множества вершин графа. Для описания вершин используются
идентификаторы вершин - Vk (i). верш и степеней вершин - Vk (i). степ$,
s = 1, N-1. Степень вершины Vk(i). степ5, s {1, 2,..., N—1} определяет
количество ребер между данной вершиной и вершинами s-й доли.
13
Рис. 1.6. N-дольные графы:
а — двудольный граф; б — трехдольный граф;
в — пятидольиый граф
Отметим, что любой N-дольный
граф SN можно представить в виде
объединения двудольных графов S?,
i = l,r:
sN=и S? .
i=l 1
Таким образом, основные базисные
операции над N-дольным графом SN
могут быть сведены к операциям над
двудольными графами.
Двудольный граф. Приведем опи-
сание двудольного графа S2 = {(VL,
VR),U) (рис. 1.7):
type вершина = record верш.: char;
степ.: integer;
end;
L-вершина = array (l..ML]of вершина;
R-вершина - array [1..MRJ of вершина;
строка матрицы = array [1..MR] of char;
матрица смежности = array [1..ML] of строка
матрицы;
var U : матрица смежности;
VL: L- вершины;
VR: R-вершины;
IL, IR: integer;
1. Начальная установка:
П*: ( индексы
IR : « 0; J
MR ’ * *. граиичные значения
2. Ввод вершины
2.1. Ввод L-вершины:
IL: = IL + 1;
if IL > ML then {переполнение};
VL (IL), верш : =A;
2.2. Ввод R-вершины:
IR i-IR + i;
if IR > MR then {переполнение};
VR (IR). верш.: =B;
VR (IR). степ.: 0;
Здесь А и В соответственно > идентификаторы левой и правой вершин.
3. Ввод ребра:
for 1: = 1 to IL do if VL (1). верш я A and
VL(I). степ» 0 then
begin
form : = 1 toIR do if VR(m). верш = В and
VR(m). степ » 0 then
14
В
VL UJ2 . . . NR ... MR
begin
if U(l, m) = 7NO7 then
begin
U(l, m): = 'YES7;
VL(1). степ: = VL(1). степ + 1 ;
VR(m). степ: = VR(m). степ + 1;
goto 2;
end;
end;
end;
Г. {ошибка при занесении ребра АВ}
4. Удаление ребра:
for 1: = 1 to IL do if VL(1). верш: = A and
VL(1). степ> Othen
begin,
for m: «1 to IR do if VR (m). верш: » В and
VR (m). степ > 0 then
begin
if U(l, m) = 'YES7 then
begin
U(l,m):»7NO7;
VL (1). степ; e VL (1). степ -1;
VR(m). степ: = VR(m). степ -1;
15
goto 2;
end;
end;
end;
1: {ошибка при задании ребра АВ}
5. Удаление вершины
5.1. Удаление L-вершины:
for 1: = 1 to IL do
if VL (1). верш: = A and VL (1). степ > 0 then
begin
form: = 1 to IR do if U (1, m): = 'YES' then
begin
U(l,m):«,NO/;
VR (m). степ: = VR (m). степ -1;
VL (1). степ: = VL (1). степ-1;
go to 2;
end;
end;
1: {вершина отсутствует}
2:
5.2. Удаление R-вершины
for 1:1 to IR do
if VR (1). верш = В and VR (1). степ > 0 then
begin
for m: = 1 to IL do if U (m, 1): = 'YES' then
begin
U (m, 1): ='NO';
VR (1). степ: = VR (1). степ -1;
VL (m). степ: = VL (1). степ -1;
goto 2;
end;
end;
1: {вершина отсутствует}
2:
6. Определение L(R)-BepniHH, смежных хотя бы с одной из R(L)-Bepnn«<oft
6.1.Определение R-вершин, смежных хотя бы с одной L-вершиной:
г: 0; for к : = 1 to 1 do
for i: = 1 to IL do
if L (k): VL (i). верш and VL (i). степ > 0 then
be8for j: = 1 to IR do if U (i, j): =' YES'Леп
begin
r: = r + 1; R(r): = VR (j). верш;
end;
end.
В массиве L находятся заданные L-вершины, в массиве R - искомые R-вершины.
6.2. Определение L-вершин, смежных хотя бы с одной R-вершиной:
1: = 0; for к : = 1 to р do
for i: = 1 to IR do
if P (k): = VR (О.верш and VR (i). степ > 0 then
begin
16
for j : = 1 to IL do if U G, i): = 'YES' then
begin
1: = 1 + 1; L(l): = VLG). верш;
end;
end.
В массиве R находятся заданные R-вершины, в массиве L - искомые L-вершины.
7. Определение R(L)-вершин, смежных с каждой из заданных L(R)-вершин
7.1. Определение R-вершин, смежных с каждой из заданных L-вершин:
к: = 0; for i: = 1 to IL do
for j: = 1 to 1 do
if L(j): = VL(i). верш then
begin к: = к +1; N (k) : = i; end;
else if j = 1 then {элемент не найден};
г: s 0; for i: = 1 to IR do
begin
for j: = 1 to 1 do
begin if U (j, i): = 'NO 'then goto 1; end;
r: = r + 1; R(r) : = VR(i);
1: end.
7.2. Определение L-вершин.смежных с каждой из заданных R-вершин:
к: = 0; for i: = 1 to IR do
for j: = 1 to p do
if P (j): = VR (i). верш then
begin к: = к + 1; N(k): = i; end;
else if j: = p then {элемент не найден };
к: = 0; for i: «1 to IL do
begin
for j: - 1 top do
begin if U (i, j): « 'NO' then goto 1 end;
к: я к + 1; L(k): = VL (i). верш;
1: end.
Приведем вариант программной реализации (ПЛ/1, ОС ЕС и PDL)
структуры данных - двудольный (рис. 1.8) и N-дольный граф (рис. 1.9).
Операции над двудольным графом, используемые в программах 1.1, 1.2,
представлены в виде подпрограмм (программы 1.3 - 1.14).
Очевидно, что приведенные структуры данных не являются исчер-
пывающими, т. е. для эффективного выполнения той или иной операции
целесообразно разрабатывать соответствующую структуру данных.
Например, над множествами могут быть выполнены следующие типы
операций:
принадлежать (a, S) - устанавливает принадлежность элемента а
множеству S;
вставить (a, S) - заменяет S на S и {а};
удалить (a, S) - заменяет S на S I {а};
объединить (Sb S2, S3) - строит множество S3 = Si и S2;
найти (а) - определяет имя того множества, которому в данный
момент времени принадлежит а;
расцепить (a, S) - делит линейно упорядоченное множество на два
подмножества Si« {xlx а, х е S} и S2 = {xix> а, х е S1;
2. Зак. 3901.
min (S) - определяет наименьший элемент множества S.
При этом с каждой операцией связана соответствующая структура
данных. Так, структура данных, которую можно использовать для
выполнения последовательности операций „принадлежать”, „вставить”,
„удалить”, называется словарем. В то же время словарь можно реали-
зовать таблицей расстановки, деревом двоичного поиска и т. д.
FORMSTR: PROCEDURE ОРТ IONS(МЛ IN);
DCL GVL(LVL) CHAR(2+...) CONTROLLED,
GVR(LVR) CHAR(2+...) CONTROLLED,
GRBK(LVL.LVR) BIT(l) CONTROLLED;
DCL GERL CHAR(...),
GERR CHAR(...),
GKOD BIN FIXED(15);
LVL=...;
LVR=...;
ALLOCATE GVL INIT((LVL)0);
ALLOCATE GVR INIT((LVR)0);
ALLOCATE GRBR INIT((LVL*LVR)0);
/♦ ВВОД ДАННЫХ В ДВУДОЛЬНЫЙ ГРАФ */
CALL WSTR(GVL,GVR,GRBR,GKOD);
IF GKODn=0 THEN DO; ... END;
CALL WINVL(GERL,GVL,GVR,GRBR,GKOD);
IF GKOD"’=0 THEN DO; ... END;
CALL WINVR(GERR,GVL,GVR,GRBR,GKOD);
IF GKOD"1=0 THEN DO; ... END;
CALL WINRBR(GERL,GERR,GVL,GVR,GRBR,GKOD);
IF GKODn=0 THEN DO; ... END;
CALL WONSTR(GVL,GVR,GRBR,GKOD);
if gkod-’=0 Then do; ... end;
/* ПРОВЕДЕНИЕ ВЫЧИСЛЕНИЙ ♦/
LMVERL=...;
CALL WVLEVR(MVERL,LMVERL,MVERR,LMVERR,GVL,GVR,GRBR,GKOD);
IF GKOD_,=0 THEN DO; ... END;
18
LMVERR=...;
CALL WVRTVL(MV£RR,LMVERR,MVERL,LMVERL,GVL,GVR,GRBR,GKOD);
IF GKOOn=0 THEN DO; ... END;
FREE GVL;
FREE GVR;
FREE GRBR;
END FORMSTR;
ПРОГРАММА 1.1. ВВОД ДАННЫХ В ДВУДОЛЬНЫЙ ГРАФ
PROBLEM: PROCEDURE OPTIONS(MAIN);
DCL GVL(LVL) GHAR(2+...) CONTROLLED,
GVR(LVR) CHAR(2+...) CONTROLLED,
GRBR(LVL.LVR) BIT(l) CONTROLLED;
DCL GERL CHAR(..»),
GEkR CHAR( .*••);
GKOD BIN FIXEDC15);
DCL MVERLC...) CHAR(...),
MVERR(...) CHARC...);
DCL (LMVERL,LMVERR) BIN FIXED(15) INIT(0)
LVL=...;
LVR=...;
ALLOCATE GVL INIT((LVL)0);
ALLOCATE GVR INIT((LVR)0);
ALLOCATE GRBR INIT((LVL*LVR)0);
/♦ КОРРЕКТИРОВКА ДАННЫХ ДВУДОЛЬНОГО ГРАФА */
CALL WINSTR(GVL,GVR,GRBR,GKOD);
IF GKOD^xH THEN DO; ... END;
CALL WONVL(GERL,GVL,GVR,GRBR,GKOD);
IF GKOD"»=0 THEN DO; ... END;
CALL WONVR(GERR,GVL,GVR,GRBR,GKOD);
IF GKODn=0 THEN DO; ... END;
19
CALL WONRBR(GERL,GERR,GVL,GVR,GRBR,GKOD)
IF GKODn=0 THEN DO; ... END;
CALL WINVL(GERL,GVL,GVR,GRBR,GKOD);
IF GKOD"*=0 THEN DO; ... END
CALL WINPBR(GERL,GERR,GVL,GVR,GRBR,GKOD);
IF GKOD"I=0 THEN DO; ... END;
/* ПРОВЕДЕНИЕ ВЫЧИСЛЕНИЙ */
LMVERL=...•
CALL WVLTVR(MVFHL,LMVERL,MVERR,LMVERR,GVL,GVR,GRBR,GKOD)
IF GKODn=0 THEN DO; ... END;
LMVERR=*..;
CALL WVREVL(MVERR,LMVERR,MVERL,LMVERL,GVL,GVR,GRBR,GKOD)
IF GK0D-»=O THEN DO; ... END;
FREE GVL;
FREE GVR;
FREE GRBR
ENO PROBLEM
ПРОГРАММА 1.2. КОРРЕКТИРОВКА ДАННЫХ ДВУДОЛЬНОГО ГРАФА
WSTR: PROC(VL,VR,RBR,KOD);
DCL (ML,MR,MEL,MER,IL,IR) BIN FIXED(15) INIT(0) EXT;
DCL KOD BIN FIXEDC15);
DCL VL(*) CHAR(*)J
DCL VR(*) CHAR(*)J
DCL RBR(»,*) BIT(l);
DCL (I.J.K) BIN FIXED(15) INIT(0);
DCL CHLO BIN FIXED (15),
1 CHL BASED(ACHLO),
2 (CHL1.CHL2) CHAR(l),
CHLB CHAR(2) BASED(ACHLO);
DCL STRKA CHAR(126),
BAIT CHAR(l),
B(8) BIT(l) BASED(ABAIT);
ACHLO=ADDR(CHLO);
ABAIT=ADDR(BAIT);
IL=0; IR=0;
ML = DIM(VL,1);
20
MR = DIM(VR,1);
MEL = LENGTHCVLC1));
HER = LENGTHCVR(1));
CHLO=0;
DO 1=1 TO ML; SUBSTRCVLСI),1,2)=CHLB; END;
DO 1=1 TO MR; SUBSTRCVRCI),1»2)=CHLB; END;
KOD=0;
END 4STR;
ПРОГРАММА 1.3. НАЧАЛЬНАЯ УСТАНОВКА.
WINVL: PROCCVERL,VL,VR,RBR,KOD);
DGL (ML,MR,MEL,MER,IL,IR) BIN FIXEDC15) EXT;
DCL KOD BIN FIXEDC15);
DCL VLC*) CHARC*),
VRC*) CHARC*),
RBRC*,*) BITC1),
VERL CHARC*);
DCL STEP BIN FIXEDC15),
STEPB CHARC2) BASEDCASTEP);
DCL VER CHARCMEL-2);
ASTEP=ADDRCSTEP);
KOD=0; J=0;
DO 1=1 TO IL;
STEPB=SUBSTRCVLCI), 1,2);
IF STEP=0 THEN DO; J= I; GOTO BLA; END;
END;
IL=IL+i;
IF IL>ML THEN D0;K0D=4; GOTO ENH; END;
J=IL;
BLA:
VER=VERL;
STEP=0; DO 1=1 TO MR; RBRCJ,I)='0'B; END;
SUBSTRCVLCJ),1,2)=STEPB;
SUBSTRCVLCJ),3,MEL-2)=VER;
ENH:
END WINVL;
ПРОГРАММА 1.4. ВВОД L-ВЕРМИНЫ.
WINVR: PROCCVERR,VL,VR,RBR,KOD);
DCL CML'MR,MEL,MER,IL, IR) BIN FIXEDC15) EXT;
DCL KOD BIN FIXEDC15);
DCL VLC*) CHARC*),
VRC*) CHARC*),
RBRC*,*) BITC1),
VERL CHARC*);.
DCL STEP BIN FIXEDC15),
STEPB CHARC2) BASED(ASTEP);
DCL VER CHARCMEL-2);
ASTEP=ADDRCSTEP);
KOD=0; J=0;
DO 1=1 TO IR;
STEPB=SUBSTRCVRCI),1,2);
IF STEP=0 THEN DO; J=I; GOTO BLA; END;
END;
IR=IR+1;
IF IR>MR THEN D0;K0D=4; GOTO ENH; END;
J=IR;
21
BLA :
VERsVERR;
STEP=0; DO 1=1 TO ML; RBR(I,J) = '0'B ; ENO;
SUBSTR(VR(J),1,2)=STEPB;
SUBSTR(VR(J),3,MER-2)=VER;
ENH:
END tfINVR;
ПРОГРАММА 1.5. ВВОД R-ВЕРШИНЬ.'.
WINRBR: PROC(VERL,VERR,VL,VR,RBR,KOD);
DCL (ML,MR,MEL,MER,IL,IR) BIN FIXFD(15) EXT;
DCL KOD BIN FIXED(15);
DCL VL(*) CHAR(*),
VR(*) CHAR(*),
RBR(*,*) BIT(1),
VERL CHAR(*),
VERR CHAR(*);
DCL STEP BIN FIXED(15),
STEPB CHAR(2) BASED(ASTEP);
DCL VLVER CEAR(MEL-2),
VRVEH CHAR(MER-2);
DCL (I,J) BIN FIXEDC15);
ASTEP=ADDR(STEP);
KOD=0;
DO 1=1 TO IL;
STEPB=SUBSTR(VL(I),1,2);
VLV£R=SUBSTR(VL(I),3,MEL-2);
IF VLVER=VERL & STEP>=0 THEN GOTO BLa;
END;
GO TO ENDM;
BLA:
DO J=1 TO IR;
STEPB=SUBSTR(VR(J),1,2)J
VRVER=SUBSTR(VR(J),3,MER-2);
IF VRVER=VERR & STEP>=0 THEN GOTO BLB;
END;
GO TO ENDM;
BLB:
IF RBiiU, J)='1'B THEN GOTO ENDK;
STEPB=SUBSTR(VL(I),1,2);
SUBSTHCVL(I),1,2)=STEPB;
STEPB=SUBSTR(VR(J),1,2);
SUBSTK(VR(J),1,2)=STEPB;
RBR(I,J)=*1rВ;
GO TO ENDK;
ENDM: K0D=4;
ENDK:
END WINRBR;
ПРОГРАММА 1.6. ВВОД РЕБРА
WONRBR: PROC(VERL,VERR,VL,VR,RBR,KOD)J
DCL (ML,MR,MEL,MER,IL,IK) BIN FIXED(15) EXT;
DCL KOD BIN FIXED(15);
DCL VL(*) CHAR(*),
VR(*) CHAR(*),
22
RBR(*,*) BIT(l),
VERL CHAR(*),
VERR CHAR(*);
DCL STEP BIN FIXEDU5) ,
.STEPB CHAR(2) BASED(ASTEP);
DCL VLVER CHAR(MEL-2),
VRVER CHAR(MER-2);
DCL (I,J) BIN FIXED(15);
ASTEP=ADDR(STEP);
KOD=0;
DO 1=1 TO IL;
STEPB=SUBSTR(VL(I),1,2);
VLVER=SUBSTR(VL(I),3,MEL-2);
IF VLVER=VERL a STEP>=0 THEN GOTO BLA;
END;
GO TO ENDM;
BLA:
DO J=1 TO IR;
STEPB=SUBSTR(VR(J),1,2);
VRVER=SUBSTR(VR(J),3,MEd-2);
IF VRVER=VERR & STEP>=0 THEN GOTO BLB;
END;
GO TO ENDM;
BLB:
IF RBR(I,J)='0'B THEN GOTO ENDK;
STEPB=SUBSTR(VL( I) , 1,2);
STEP=STEP-1;
SUBSTR(VL(I),1,2)=STEPB;
STEPB=SUBSTR(VH( J),1,2);
step=step-i;
SUBSTR(VR(J),1,2)=STEPB;
RBR(I,J)='0'B;
GO TO endk;
ENDM: K0D=4;
ENDK:
END WONRBR;
ПРОГРАММА 1.7. УДАЛЕНИЕ РЕБРА
WONVL: PROC(VERL,VL,VR,RBR,KOD),
DCL (ML,MR,MEL,MER,IL,IH) BIN FIXEDC15) EXT;
DCL KOD BIN FIXEDC15);
DCL VL(*) CHAR(*),
VR(*) CHAR(*),
RBR(*,*) BIT(1),
VERL CHAR(*)J
DCL STEP BIN FIXEDC15),
STEPB CHAR(2) BASED(ASTEP);
DCL VLVER CHAR(MEL-2);
DCL (I,J) BIN FIXED(15);
ASTEP=ADDR(STEP);
KOD=0;
DO J=1 TO IL;
STEPB=SUBSTR(VL(J),1,2);
VLVER=SUBSTR(VL(J),3,MEL-2);
IF VLVER=VERL & STEP>=0 THEN GOTO BLA;
END;
K00=4; RETURN;
BLA:
STEP=0; DO 1=1 TO MR; RBR(J,I)=r0'B; END;
23
SU3STRCVLC J),1,2)=STEPB;
SUBSTRCVL(J),3,MEL-2)='
END WONVL;
ПРОГРАММА 1.8. УДАЛЕНИЕ L—ВЕРШИНЫ
WONVR: PROC(VERR,VL,VR,RBR,KOD);
DCL (ML,MR,MEL,MER,IL,IR) BIN FIXED(15) EXT;
DCL KOD BIN FIXEDC15);
DCL VL(*) CHARC*),
VR(*) CHARC*),
RBRC*,*) BIT(l),
VERR CHARC*);
DCL STEP BIN FIXEDC15),
STEPB GHARC2) ВASEDCASTEP);
DCL VRVER CHAR(MEL-2);
DCL (I,J) BIN FIXEDC15);
ASTEP-ADLRCSTEP);
KOD=0;
DO J=1 TO IR;
STEPB=SUBSTRCVRCJ),1,2);
VRVER=SUBSTRCVR(J),3,MER-2);
IF VRVER=VERR * STEP>=0 THEN GOTO BLA;
END;
K0D=4; RETURN;
BLA:
STEP=0; DO 1=1 TO ML; RBRCI,J)='0'B; END;
SUBSTRCVR(J),1,2)=STFPB;
SUBSTRCVRCJ),3,MER~2)='
END WONVR;
ПРОГРАММА 1.9. УДАЛЕНИЕ R—ВЕРШИНЫ
WVLTVR: PROC(M“VERL,L“M“VERL,M“VERR,L-M-VERR,VL,VR,RBR,KOD);
DCL (ML,MR,MEL,MER,IL,IR) BIN FIXED(lb) EXT;
DCL KOD BIN FIXEDC15);
DCL VLC*) C4AR(*);
DCL VRC*) CHARC*);
DCL RBRC*,*) BITC1);
DCL (I,J,K,L) BIN FIXEDC15) INIT(0);
DCL M-VERLC*) CHARC*),
M-VERRC*) CHARC*);
DCL CL~M-VERL,L-’4-VERR) BIN FIXEDC15);
DCL STEF BIN FIXEDC15) INITC0),
STEPB CHARC2) BASED(ASTEP);
DCL VLVER CHARCMEL-2),
VRVER CHARCMER-2);
ASTEP=ADDR(STEP);
IF L-M-VERL <= 0 THEN DO; KOD=1; GOTO ENDM; END;
L-M-VERR = Л;
DO 1=1 TO L-M-VERL;
DO J=1 TO IL;
STEPB=SUBSTR(VL(J),1,2);
VLVER=SUBSTR(VLCJ),3,MEL-2);
IF M~VERL(I)=VLVER 8 STEP>0 THEN
DO K=1 TO IR;
IF RBRCJ,K)='1'B THEN
BEGIN;
DO L=1 TO L-M-VERR;
24
IF M~VERR(L)=SUBSTR(VR(К),3,MER—2) THEN GOTO METK
END;
DO;
L“M~VERR=L“M~VERR+1;
IF L“M~VERR<=DIM(M~VERR,1) THEN
M-VERR(L-M-VERR)=SUBSTR(VR(K),3,MER-2);
ELSE GOTO ENDX;
END;
METK:
END;
END;
END;
IF L“'4~VERR=0 THEN DO; KOD=2; GOTO ENDM; END;
END;
GO TO ENDM;
ENDX: K0D=6;
ENDM:
END WVLTVR;
ПРОГРАММА 1.10. ОПРЕДЕЛЕНИЕ R-BEPftiHH,
СМЕЖНЫХ ХОТЯ БЫ С ОДНОЙ L-ВЕРШИНОй
WVRTVL:
PROC(M“VERR,L”М~VERR,М“VERL,L~М~VERL,VL,VR,RBR,KOD);
DCL (ML,MR,MEL,МЕР,IL,IR) BIN FIXED(15) EXT;
DCL KOD BIN FIXED(16);
DCL VL(*) CHAR(*);
DCL VR(*) CHAR(*);
DCL RBR(*,*) BIT(l);
DCL (I,J,K,L) BIN FIXEDC15) INIT(0);
DCL M“VERR(*) CHAR(*),
M~VERL(*) CHAR(*)J
DCL (L-M-VERR,L“M~VERL) BIN FIXEDC15);
DCL STEP BIN FIXED(15) INIT(0),
STEPB CHAR(2) BASEDCASTEP);
DCL VRVER CHAR(MER-2),
VLVER CHARCMEL-2);
ASTEP=ADDR(STEP);
IF L“M”VERR <= 0 THEN DO; KOD=1; GOTO ENDM; END;
L-M“VERL = 0;
DO 1=1 TO L-M-VERR;
DO J=1 TO IR;
STEPB=SUBSTR(VR(J),l,2)J
VRVER=SUBSTR(VR(J),3,MER-2);
IF M-VERR(I)=VRVER & STEP>0 THEN
DO K=1 TO IL;
IF RBR(K,J)='1'B THEN
BEGIN;
DO L=1 TO L-M“VERL;
IF M-VERL(L)=SUBSTR(VL(K),3,MEL-2) THEN GOTO METK;
END;
DO;
L-M-VERL=L-M-VERL + 1;
IF L-M“VSRL<=DIM(M-VERL,1) THEN
M-VERL(L-M-VERL)=SUBSTR(VL(K),3,MEL-2) ;
ELSE GOTO ENDX;
END;
METK:
END;
END;
25
END;
IF L—M~VERL=0 THEN DO; K0D=2; GOTO ENDM; END;
END;
GO TO ENDM;
ENDX: K0D=6;
ENDM:
END WVRTVL;
ПРОГРАММА 1.11. ОПРЕДЕЛЕНИЕ L-ВЕРЫИН,
СМЕЖНЫХ ХОТЯ БЫ С ОДНОЙ R-ВЕРШИНОИ
WVLEVR:
PROC(М~VERL, L“M“VERL, M“VERR, L“№VERR, VL , VR, RBR, KOD);
DCL (ML,MR,MEL,MER,IL,IR) BIN FIXED(15) EXT;
DCL KOD BIN FIXEDC15);
DCL VL(*) CHAR(*);
DCL VR(*) CHAR(*)J
DCL RBR(*,*) BIT(I);
DCL (I,J,K,L) BIN FIXED(IS) INIT(0);
DCL M-VERLC*) CHAR(*),
M“VERR(*) CHAR(*);
DCL (L—M“VERL,L~M“VERR) BIN FIXED(15);
DCL STEP BIN FIXED(15) INIT(0),
STEPB CHAR(2) BASED(ASTEP);
DCL VLVER CHAR(MEL-2),
VRVER CHAR(MER-2);
ASTEP=ADDR(STEP);
IF L-M-VERL <= 0 THEN DO; KOD=1; RETURN; END;
IF L“M~VERL>D I M( M.—VERL, 1) THEN DO; KOD=1; RETURN; END;
DO 1=1 TO IL;
DO J=1 TO L-M-VFRL; VLVER=VL(I);
IF M-VERL(J) = SUBSTR(VL(I),3,MEL-2) THEN
DO;
STEPB=SUBSTR(VL(I),1,2);
IF STEP=0 THEN GOTO BL2;
M-VERL(J)=STEPB; GOTO BLO;
END;
END;
BLO:
END;
DO J=1 TO L~M~VERL;
STEPB=SUBSTR(M-VERL(J),1,2); IF STEP<0 THEN GOTO BL2
END;
К = 0;
DO 1=1 TO IR;
DO J=1 TO L-M-VERL;
STEPB=SUBSTR(M-VERL(J), 1,2);
IF RBRCSTEP,I)=0 THEN GOTO BL1;
END;
DO L=1 TO K;
IF M—VERR(L)=SUBSTR(VR(I),3,MEL-2) THEN GOTO BL1;
END;
K=K+1;
IF K>DIM(M~VERR,1) THEN DO; K0D=6; RETURN; END;
M“VERR(K)=SUBSTR(VR(I),3,MER—2);
BL1:
END;
L-M-VERR = K;
DO 1=1 TO L-M-VERL;
STEPB=M~V£RL(I);
M-VERL(I)=SUBSTR(VL( STEP),3,MEL-2);
26
END;
RETURN;
BL2: K0D=2;
END WVLEVR;
ПРОГРАММА 1.12. ОПРЕДЕЛЕНИЕ R-BEPillHH,
СМЕЖНЫХ О КАЖДОЙ ИЗ ЗАДАННЫХ L-BEP’rtHH
WVREVL:
PROCC M—VERR, L-M—VERR,.M~VERL, L—M—VERL , VL , VR, RBR, KOD );
DCL (ML,MR,MEL,MER,IL,IR) BIN FIXEDC15) EXT;
DCL KOD BIN FIXED(IS);
DCL VLC*) CHARC*);
DCL VR(*) CHARC*);
DCL RBRC*,*) BIT(1);
DCL (I,J,K,L) BIN FIXEDC16) INIT(ld);
DCL M-VERL(*) CHARC*),
M-VERRC*) CHARC*);
DCL (L-M-VERL,L-M-VERR) BIN FIXEDC15);
DCL STEP BIN FIXEDC15) INITC0),
STEPB CHAR(2) BASEDCASTEP);
DCL VLVER CHARCMEL-2),
VRVER CHARCMER-2);
ASTEP=ADDH(STEP)J
IF L-M-VERR < = 0 THEN DO; KOD=1; RETURN; END;
IF L-M-VERR>DIM(M-VERR, 1) THEN DO; KOD=1;RETURN; END;
DO 1=1 TO IR;
DO J=1 TO L-M-VERR; VRVER=VR(I);
IF M-VERR(J) = SUBSTRCVR(I),3,MER-2) THEN
DO;
STEPB=SUBSTRCVRCI),1,2);
IF STEP=0 THEN GOTO BL2;
M-VERRCJ)=STEPB; GOTO BLO;
END;
END;
BLO:
END;
DO J=1 TO L-M-VERR;
STEPB=SUBSTR(M-VEKR(J),1,2); IF STEP<0 THEN GOTO BL2
END;
к = 0;
DO 1=1 TO IL;
DO J=1 TO L-M-VERR;
STEPB=SUBSTR(M-VERR(J), 1,2);
IF RBRCI,STEP)=0 THEN GOTO BL1;
END;
DO L=1 TO K;
IF M“VERL(L)=SUBSTR(VL(I),3,MEL-2) THEN GOTO BL1;
END;
k=k+i;
IF K>DIMCM-VERL,1) THFN DO; K0D=6; RETURN; END;
M-VERL(K)=SUBSTR(VL(I),3,MEL-2);
BL1:
END;
L—M—VERL = K;
DO 1=1 TO L-M-VERR;
STEPB=M-VERRCI) ;
M-VERRCI)=SUBSTR(VR(STEP),3,MER-2);
END;
RETURN:
BL2: K0D=2;
27
END WVREVL;
ПРОГРАММА 1.13. ОПРЕДЕЛЕНИЕ L-ВЕРМИН,
СМЕЖНЫХ С КАЖДОЙ ИЗ ЗАДАННЫХ R-ВЕРМИН
WINSTR: PROC(VL,VR,RBR,KOD);
DCL (ML,MR,MEL,MER,IL,IR) BIN FIXED(15) EXT;
DCL KOD BIN FIXED(15);
DCL VL(*) CHAR(*)J
DCL VR(*) CHAR(*);
DCL RBR(*,*) BIT(l);
DCL IN FILE RECORD SEQL;
DCL (I,J,K) BIN FIXED(15) INIT(0);
DCL CHLO BIN FIXED (15),
1 CHL BASED(ACHLO),
2 (CHL1,CHL2) CHAR(l),
CHLB CHAR(2) BASED(ACHLO);
DCL STRKA CHAR(128),
BAIT CHAR(l),
B(8) BIT(l) BASED(ABAIT);
achlo=addr(chlc) ;
ABAIT=ADDR(BAIT);
IF ML “•= DIM(VL,1) I
MR DIM(VR.l) !
MEL "•= LENGTH(VL(1)) I
MER ’’= LENGTH(VR(1)) THEN DO; KOD = 1; GOTO ENMP;END
ON ENDFILE (IN) GOTO ENDF;
OPEN FILE (IN);
/♦ ЧТЕНИЕ ПРИЗНАКА "W",ПЕРЕМЕННЫХ: MEL,MER,IL,IR -♦/
READ FILE (IN) INTO(BAIT);
IF BAIT -•= 'W' THEN DX); K0D=3; GOTO ENDF; END;
CALL READCHLO; MEL=CHLO;
CALL READCHLO; MER=CHLO;
CALL READCHLO; IL=CHLO;
CALL READCHLO; IR=CHLO;
K0D=3; ,
/♦ КОНТРОЛЬ ПАРАМЕТРОВ СТРУКТУРЫ ♦ /
IF MELO ! MERO THEN GOTO ENDF;
IF IL>ML ! IR>MR ! IL<0 ! IR<0 THEN GOTO ENDX;
/♦ ВОССТАНОВЛЕНИЕ RBR */
DO 1=1 TO IL;
DO J=1 TO IR;
IF K=0 THEN READ FILE(IN) INTO(BAIT);
K=K+1; RBR(I,J)=B(K);
IF K=6 THEN K=0;
END;
END;
/♦ ВОССТАНОВЛЕНИЕ VL ♦/
DO 1=1 TO IL;
CALL READEL(MEL.STRKA);
VL(I)=STRKA;
BAIT=STRKAJ IF B(1)='1'B THEN GOTO ENDY;
ENO;
IF IL<ML THEN DO I=IL+1 TO ML; VL(I)='0'; END;
/♦ ВОССТАНОВЛЕНИЕ VR ♦/
DO J=1 TO IR;
CALL READEL(MER,STRKA);
VR(J)=STRKA;
BAIT=STRKA; IF B(l)=rl'B THEN GOTO ENDY;
END;
28
IF IR<MR THEN DO J=IR+1 TO MR; VR(J)='0'; END;
GO TO ENDF;
ENDY: KOD=3;
ENDF: CLOSE FILE (IN);
READCHLO: PROC;
K0D=3;
READ FILE(IN) INTO(BAIT); CHL1=BAIT;
READ FILE(IN) INTO(BAIT); CHL2=BAIT;
KOD=0;
END READCHLO;
READEL: PROC(LELEM,STROKA);
DCL LELEM BIN FIXED(15),
STROKA CHAR(128),
STRC128) CHAR(l) BASED(ASTROKA),
I BIN FIXED(15);
ASTROKA=AODR(STROKA);
K0D=3;
DO 1=1 TO LELEM;
READ FILE(IN) INTO(BAIT); STR(I)=BAIT;
ENO;
KOD=0;
END READEL; ENMP:
END WINSTR;
ПРОГРАММА 1.14. ВВОД ДАННЫХ В ДВУДОЛЬНЫЙ ГРАФ
С МАГНИТНОГО НОСИТЕЛЯ
WONSTR: PROC(VL,VR,RBR,KOD);
DCL (ML,MR»MEL,MER, IL, I R) BIN FIXED(IS) EXT;
DCL KOD BIN FIXED(IS);
DCL VL(*) CHAR(*);
DCL VR(*) CHAR(*)J
DCL RBR(*,*) BIT(l);
DCL ON FILE RECORD OUTPUT; /* SEQL ENV(F(1)); ♦/
DCL (I,J,K) BIN FIXEDU5) INIT(0);
DCL CHLO BIN FIXED (15),
1 CHL BASED(ACHLO),
2 (CHL1.CHL2) CHAR(l),
CHLB CHAR(2) BASED(ACHLO);
DCL STRKA CHAR(128),
BAIT CHAR(l),
B(8) BIT(l) BASED(ABAIT),
BSTR(128) CHAR(l) BASED(ASTRKA);
ASTRKA=ADDR(STRKA);
ACHLO=ADDR(CHLO);
ABAIT=ADDR(BAIT);
IF ML ч= DIM(VL,1) !
MR n= DIM(VR,1) THEN GOTO ENDX;
put skip data(mel.mer);
IF MEL -*= LENGTH(VLd)) I
MER “•= LENGTH(VR(1)) THEN GOTO ENDX;
ON ENDFILE (ON) GOTO ENDF;
OPEN FILE (ON);
/♦ ЗАПИСЬ ПРИЗНАКА "W",ПЕРЕМЕННЫХ: MEL,MER,IL,IR ♦/
BAIT='Wr; WRITE FILE (ON) /* ПРИЗНАК ФАЙЛА ♦/ FROM(BAIT);
CHLO=MEL; CALL WRITECHLO;
CHLO=MER; CALL WRITECHLO;
CHLO=IL; CALL WRITECHLO;
CHLO=IR; CALL WRITECHLO;
29
/* ЗАПИСЬ RBR */
к=0;
DO 1=1 ТО IL;
DO J = 1 TO IR;
k=k+i; b(k)=rbr(i,J);
IF K=8 THEN K=0;
IF K=0 THEN WRITE FILE(ON) FROM(BAIT);
END;
END; ,
IF F“*=0 THEN WRITE FILE(ON) FROM(BAIT);
/♦ ЗАПИСЬ VL ♦/
DO 1=1 TO IL;
STRKA=VL(I);
DO J=1 TO MEL;
BAIT=BSTR(J);
WRITE FILE (ON) FROM(BAIT);
END;
END;
/♦ ЗАПИСЬ VR */
DO 1=1 TO IR;
STRKA=VR(I);
DO J=1 TO MER;
BAIT=BSTR(J);
WRITE FILE (ON) FROM(BAIT);
END;
END;
GO TO ENDF;
ENDX: K0D=3;
ENDF: CLOSE FILE (ON);
WRITECHLO: PROC;
KOD=3;
BAIT=CHLi; WRITE FILE(ON) FROM(BAIT);
BAIT=CHL2; WRITE FILE(ON) FROM(BAIT);
KOD=0;
END WRITECHLO;
END WONSTR;
Рис. 1.8
proc вставка!(number) {* вставка доли в линейный *
{* N-дольный граф - I способ *
scalar N,M,Nd,numl,number,i,j: integer
scalar range: logikal
array A[Mj,Matr[M,M]: integer
^питЬег“ВеДвЛеНИе num^ и ran#e *}
then
numl,range:=1,true
else
^numl,range:=number,number=N
Nd:=number*1 {* этот номер будет иметь
run INS(Nd) {* М^*М?Г?ГЯвМаЯ ДОЛЯ *}
for
i:=l to М-1
do
if
JA[lJ=numl) or ((Ari]=numl*l) and range)
then {* создание ребра {i,M}
Matr[i,M],Matr[M;i]:=!,! ' *
if
30
tange and (A[i]=numl)
then {* удаление ’’паразитных” ребер *}
for
J:=l to M-l
do
if
(MatrFi,j]=l) and (A[j]=numl*l)
then {* удаление ребра {i,j} *}
fMatrti,jJ,Matr[j:i]:=0,0 1
od
fi
fi
перенумерация долей *}
A[i]>number
then
fA[i]:=A[i]+l
od
N:=N+1
corp
proc вставка2(пшпЬег) {* вставка доли в линейный *)
{♦ N-дольный граф - 2 способ *}
scalar N,М,Nd,numl,number,i,j,Ml: integer
scalar range: logikal
array A[MJ,MatrLM,M]: integer
if {* определение numl и range *}
number=O
then
numl,range:=1,true
numl,range:=number,number=N
fi
4 Nd:=number+l {* этот номер будет иметь *}
> (* вставляемая доля *}
! М1:=М {* первоначальное количество вершин *}
for
i:=l to Ml
do
if F* поиск вершин соседней доли *}
А Г iJ=numl
then
if {* граничная ли доля вставляется ♦}
range
then
INS(Nd) J* М:=М=1 *}
Matr[i,M],Matr[M,i]:=l,l
else
for
j:=l to Ml
do
if {* разрываемое ребро *}
(Matr[i,33=1) and (A[j]=numl+l)
then
INS(Nd) {* M:=M+1 *}
MatrFi,Ml,MatrFM,i1:=1, 1
Matr Г j,M],MatrFM,J]:=1,1
Matr L1,j J,Matr[j , 1J : =0,0
f i
od
fi
fi
if {* перенумерация долей *}
A[1]>number
then
A£i]:=A[i]+l
31
od
МН
corp
proc удаление (Nd) {ж удаление доли в линейном *}
{* N-дольном графе *}
scalar N,M, Nd, i , j t к: integer
scalar range: logikal
array A[M],Matr[M,M]: integer
range:=(Nd=l) or (Nd=N)
i:=l
do
if
A[i]=Nd {* вершина принадлежит удаляемой доле *}
then
if
range
then
for
j:=1 to M
do
if
(Matr[i,j]=l) and (Afj]<Nd)
then
for
k:=l to M
do
if
^Matr[i,k] = l) and (A[k]>Nd)
*Matr[j,k],Matr[k,j]:=1,1
od
fi
od
Ьеьси
{ж -----> вычеркивание строки и столбца матрицы
1* смежности. Номер 1 будет теперь у вершины, которая
1* раньше имела номер i+1 ------->
---> переход к следующей вершине
i* вершина не принадлежит удаляемой доле *}
ЦГД* перенумерация долей ж} J
ALi j>Nd
then
fACi]=A[i]-l
{ж переход к следующей вершине ж}
until
i>M
od
N:=N-1
corp
proc непосредственно_достижимые_вершины(x,i)
f* поиск вершин некоторой доли
{ж непосредственно достижимых
{* из данной вершины
scalar M,i,j,k,Td,x,step: integer
T* x - исходная вершина
{* i - искомая доля
array АГМ1.MatrfM,Ml: integer
array MASKtM],MASfcl[M],faiI(M]: logikal
Td:= A[x] {* текущая доля ж}
if {ж определение направления движения ж}
Td<i
then
step:=1
else
step:--1
fi
MASK:=false {ж MASK[1]
MASK[x]:= true
ж
ж
*
*
ж
ж
ж
= MASKCM] = false
*}
32
while
Tdoi
do
MASKl:=false
for
j:=l to M
do
iMASK[j]
then
f or
k:=l to M
do
i(Matr[j,k]=1) and (A[k]-Td=step)
^MASKl[k]:=true
fi
od
fi
MASK,Td:=MASKl,Td+step
od
corp
proc направленный_путь(TOP,EOP,path,retcode)
.{* поиск направленного пути от
{* вершины ТОР к вершине ЕОР *}
{* к началу работы стек path
должен быть пуст
xLi?step,s: integer
l[0J : integer
>gikal
integer
*
scalar TOP,EOP,n.л,±.эы
scalar retcode: logikal
array ........
array MASKt
stack path:
if
path=empty {* стек пуст *}
then {* подготовка к работе *}
MASK:=false {* MASK[1]=...=MASK[M]=false *}
retcode:=false
top(path):=TOP {* занесение TOP в стек *}
if T* определение направления движения *}
{* предполагается, что вершины ТОР и *}
д^^ЕОРдЗаве^омо принадлежат различным долям
then
step:=1
else
step:=-1
fi
run направленный_путь(TOP,EOP,path,retcode)
n {* рекурсивный вызов *j
определение вершины стека *
без ее удаления *;
определение следующей доли *}
Matr
*}
else
x:=top(path) £*
top(path):=x
s:=Alx]+step {*
A[EOP]=s
then
if
Matr[x,EOP]=l
then {* направленный путь найден *}
top(path),retcode:=EOP,true
else
x:=top(path) {* удаление вершины стека
fi
else
x:=top(path) [* определение вершины стека
{* без ее удаления
top(path):=х
for
i:=l to M
do
if
'“retcode
then
if
3. Зак. 3901.
33
(~MASK[iJ) and (A[i]=s) and (Matr[i,x]=1)
then
MASK[i],top(path):=true.i
run направленный_путь(TOP,EOP,path,retcode
{* рекурсивный вызов *
f i
fi
od
if
"retcode
then
x:=top(path)
fi
fi
fi
corp
Рис. 1.9
Глава 2. АЛГОРИТМЫ ГЕНЕРАЦИИ КОМБИНАТОРНЫХ
КОНФИГУРАЦИЙ
Решение комбинаторной задачи, как правило, состоит в генерации
начального объекта, преобразовании текущего объекта в последующий
и проверки условия окончания генерации. При этом выполнение исчер-
пывающего поиска на множестве всех возможных решений может
осуществляться как с помощью специализированных алгоритмов, свя-
занных со спецификой задачи (генерирование подмножеств множества,
перестановок и сочетаний), так и с помощью универсальных алгоритмов
(поиск с возвращением, метод ветвей и границ, случайный поиск).
2.1. Система 7П подмножеств множества Е = {а1э а2,...,ап}
В качестве комбинаторного числа, связанного с системой 7п подмно-
жеств множества Е, как правило, используется мощность 7п - 17п|.
Если 2 е 7п и S сопоставлен взаимооднозначным образом двоич-
ный набор{аь а2,...,ап)
\ 1, если е 2,
ai= J 0, если а^ 2,
то имеем
К1=|е?1=2п.
Таким образом, алгоритм порождения (перечисления) всех под-
множеств множества Е состоит в формировании всех наборов (ab a2>...
...an}. Рассмотрим возможные алгоритмы формирования двоичных
наборов {ab a2,..7an}.
Алгоритм А
Шаг 1. Присвоить
tti = 0 Vi = 1, n +1;
j = t
34
Шаг 2. Если j < п, то выполнить шаги 3~7 алгоритма, иначе - завершить алгоритм.
Шаг 3. Сформировать двоичный набор
{aj Vi = nJ
{an, апФ...а1}.
Шаг 4. Присвоить
j = l.
Шаг 5. Если a j = 1, то перейти к шагу 6, иначе — к шагу 7.
Шаг 6. Присвоить
«j = O;j=j + l.
Перейти к шагу 5.
Шаг 7. Присвоить
“j=1-
Перейти к шагу 2.
Программы (рис. 2.1, 2.2), соответствующие формированию всех
подмножеств множества, основаны на генерации всех п -разрядных
двоичных наборов.
10 1
20 ’
30 1
40 :
50
60 ]
70 ,
80 ’
90 :
100
110 ________
120 B(J}=0:
130 WEND
140 B(J)=1
150 WEND
’программа генерации подмножеств
’ используется двоичный код
ЩМ В(15)
INPUT "введите N=",N
IF N>14 THEN PRINT "слишком много": GOTO 40
FOR 1=1 TO N+l: B(I)=0: NEXT I
WHILE J<=N
FOR I=N TO 1 STEP -1: PRINT B(I); : NEXT I: PRINT
) J = 1
) WHILE B(J)=1
‘ T' J-J+l
Рис. 2.1
program prim3;
type per^array [1..15] of integer;
procedure BINCOD(var B:per;var flag:Boolean;N:integer);
35
var j:integer;
begin
fla^:=true;
while B[j]=l do
begin
j:=succ(j)
end ;
ВГ j]•=1;
if j>N then flag:=false
end; {процедуры BINCOD}
procedure Printper(A:per;N:integer);
var i-integer;
begin л л
for i:=N downto 1 do
write(ACi];4);
writein _ . _
end; {процедуры Printper }
begin { главная программа }
repeat
begin
write(’ВВЕДИТЕ N=’);
readln(N)
end
until (N<15); л
for i:=l to Й+1 do B[i]:=0;
repeat
begin
PrintPer(В,N);
BINCOD(B,flagi,N)
end
until not flagl
end. { программы }
Рис. 2.2
Очевидно, что данный алгоритм не формирует подмножества, соот-
ветствующего инверсии только одного разряда в текущем двоичном
наборе. Такая последовательность двоичных наборов получила назва-
ние кодов Грея. При этом n-разрядный код Грея
G(n) = (G(n)0,G(n)i,...,G(n)2n_j)
может быть определен рекурсивно следующим образом:
G(l) = (0,l);
G(m+1) = (OG(m)0> 0G(m)1>...,0G(m) m , IG(m) m ,lG(rn)m .......lG(m)0
2 “1 2 -—I 2 -2
для любого m > 1.
Приведем пример одного из кодов Грея для случая п = 4:
Go = 0000 G6 = 0101 Gn = 1110
Gi = 0001 G7 = 0100 G12 = 1010
G2 = 0011 G8 = 1100 G13 = 1011
G3 = 0010 G9 = 1101 'Ср, = 1001
G4 = 0110 Gio = 1111 G15 = 1000
g5 = oih
Коды Грея G(n) можно также представлять последовательностью
переходов Тп, т. е. упорядоченным списком номеров разрядов (прону-
36
мерованных справа налево), которые меняются при переходе от одного
кодового слова к другому. Например, Т4 = 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1.
Алгоритм В
Шаг 1. Присвоить
а. = 0 Vi = 1,п + 1;
j=l.
Шаг 2. Если j С п, выполнить шаги 3-7 алгоритма, в противном случае завершить алгоритм.
Шаг 3. Сформировать
otj® ai + j Vi =n, 1.
Шаг 4. Присвоить
j = l.
Шаг 5. Если cq в 1,то перейти к шагу 6, иначе — перейти к шагу 7.
Шаг 6. Присвоить
ai = O,j=j + l.
Перейти к шагу 5.
Шаг 7. Присвоить
“j=l-
Перейти к шагу 2.
Соответствующие программы (рис. 2.3, 2.4) генерации подмножеств
с минимальными изменениями основаны на преобразовании п-разряд-
ного кода Грея.
10
20
30
40
50
60
70
’ПРОГРАММА ГЕНЕРАЦИИ ПОДМНОЖЕСТВ С НАИМЕНЬШИМИ
’лтпыимами лт лплтлмиу (иг'пппк'зутгтга КОД ГРЕЯ)
’ОТЛИЧИЯМИ ОТ СОСЕДНИХ (ИСПОЛЬЗУЕТСЯ
DIM В(15)
INPUT ‘•ВВЕДИТЕ N=M,N
IF N>14 THEN PRINT ’’СЛИШКОМ МНОГО” :
FOR 1=1 TO N+l: B(I)=0 : NEXT I
J — 1
GOTO
40
80 WHILE J<N
90 GOSUB 1000 ’ПРЕОБРАЗОВАНИЕ ДВОИЧНОГО КОДА В КОД ГРЕЯ
100 J = 1
WHILE B(J)=1
- — : J=J + 1
110 I____ _
120 B(J)=0 :
130 WEND
140 B(J)=1
150 WEND
160 Г"
1000
1010
1020
1030
1040
END
> FOR I=N TO 1 STEP -1
> IF B(I)=1 XOR B(I+1)=1 THEN PRINT “I”
1 NEXT I
> PRINT
1 RETURN
ELSE PRINT ”0
ВВЕДИТЕ N=4
0 0 0 0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
Рис. 2.3
program prim3;
type per=array [1..15] of integer;
var N,1,:integer;
B,G:per;
flagl:Boolean;
37
procedure BINCOD(var В:per;var
var j:integer;
begin
fIa|:=true;
while B[j]=1 do
begin
Bbn=o;
j:=succ(j )
end;
ВГj 1:=1;
if j>N then flag:=false
end; {процедуры BINCOD}
flag:Boolean;N:integer);
}
}
procedure Printper(A:per;N:integer);
var i:integer;
begin
for i:=N downto 1 do
write(A[i]:4);
writein
end; {процедуры Printper }
procedure GRAYCOD(var B,G:per;var flag:
var i:integer
begin
BINCOD(B,flag,N);
if flag then
for i:=N downto 1 do
if (B[j] = l) xor (B[i+1?
then Gfi1:=1
else G[i]:=0
end; { процедуры GRAYCOD
begin { главная программа
repeat
begin
write(’ВВЕДИТЕ N=’);
readln(N)
end
until (N<15);
for i:=1 to N+l do
begin
ВГ1]:=0;
GFij:=0
end;
repeat
begin
PrintPer(G,N);
GRAYCOD(B,6,fiagl,N)
end
until not flagl
end. { программы }
Boolean,N:integer);
Рис. 2.4
2.2. Размещение элементов из множества Е по к
Размещением элементов из Е = {а|,...,ап} по к называется упорядо-
ченное подмножество из к элементов, принадлежащих Е.
Например, все размещения из множества Е ={ ар а2» аз} по 2:
(ab а2), (а2, а!), (ab а3), (а3, aj), (а2, а3), (а3, а2).
Число размещений (п)к определяется как
(n)k = n(n- l)...(n-k + 1) при к5? п.
При этом
(п)к = 0 при к> п;
(О)о = (п)о = 1;
(п)к = п(п-1)к_1 =(п)к_! (п-к + 1).
38
Перестановки из элементов - частный случай размещения элемен-
тов из Е по к при к - п: (п)п = п!
Приведем алгоритм генерации перестановок в лексиграфическом
порядке для множества Е = {a1,...,an}; ai = i|Vi=l,n .
Алгоритм С
Шаг 1. Присвоить
at = i Vi = 1, n .
Шаг 2. Вывести
af V i = 1, n .
Шаг 3. Для! = n-l, n-2,...,l найти i, для которого
af < а4 + 1.
Если i, удовлетворяющее данному условию, существует, перейти к шагу 4, в против-
ном случае завершить алгоритм.
Шаг 4. Присвоить
min = n + 1;
j = i + l.
Шаг 5. Если aj < min и а{ < а^, то положить
min = aj, jmin = j.
Шаг 6. Если j < n, положить j = j + 1.
Перейти к шагу 5.
Шаг 7. Присвоить
sa = ар aj = ajmin, ajmin - sa.
Шаг 8. Присвоить
ss = n + i + 1
medium = [ss /2].
Шаг 9. Для 1 = i + 1, i + 2,..., medium выполнить шаги 10,11 и перейти на шаг 2.
Шаг 10. Присвоить
Ipost = ss ~ 1.
Шаг 11. Присвоить
sa = а^ aj = aj„ost, ajpost = sa.
Соответствующие программы (рис. 2.5, 2.6) основаны на генерации
перестановок в лексиграфическом порядке.
DIM А(15)
INPUT “введение N",N:IF N>14 THEN 20
FOR 1=1 TO N:A(I)= t:NEXT I
FOR 1 = 1 TO N-.PRINT A(I);:NEXT I:PRINT
GOSUB 70
GOTO 40
FOR I=N-1 TO 1 STEP -1
IF A(I)<A(I+1) THEN 110
NEXT I
I STOP
I MIN=N+1
। FOR J=I+1 TO N
I IF A(I)>A(J) GOTO 150
। IF A(J)<M1N THEN MIN=A(J):JMIN=J
। next j
I SA=A(I):A(I)=A(JMIN):A(JMIN)=SA
• SS=N+I+1
I SERED=INT(SS/2)
। FOR L=I+1 TO SERED
I LPOST=SS-L
10 :
20
30 :
40 :
50 I
60 <
70 :
80
90 ;
100
110
120
130
140
150
160
170
180
190
200
39
210 (L):А(L)=А(LPOST):A(LPOST)=SA
£ 4- и ийл 1 L
230 RETURN
введителЫ=4
1
1
1
1
1
2
2
2
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
2
2
3
3
4
4
3
3
4
4
1
1
2
2
4
4
1
1
2
2
3
3
3
4
2
4
2
3
3
4
1
4
1
3
2
4
1
4
1
2
2
3
1
3
1
2
4
3
4
2
3
2
4
3
4
1
3
1
4
2
4
1
2
1
3
2
3
1
2
1
Рис. 2.5
program priml;
type per=array [1..15] of integer;
var N,i;integer;
A:per;
f lagl:Boolean;
procedure LEXYC(var A:per; var flag:Boolean; N:integer);
var i,j,MIN,Jmin,sa,ss,sered,1,Ipost:integer);
procedure Poiskl(vat flag:Boolean;var ii:integer;
A:per;N:integer);
var i:integer;
begin
flag-‘=true;
for i:=N-l downto 1 do
if A[i]<A[i+l] then
begin
ii:=i;
end:
flag:=false
end; { процедуры Poiskl }
begin
Poisk-1 (f lag, i, A, N);
if flag then { генерация не закончена }
begin
MIN:=N+1;
for j:=i+l to N do
if (A[i]<+A[j]) and (A[j]<MIN) then
begin
MIN:=A[j];
Jmin:=3
end:
sa:=A(i]: A[i]:=A[Jmin]; A[Jmin]:=sa;
ss:=N+i+l; sered:=ss div 2;
for l:=i+l to sered do
begin
Ipost:=ss~l:
sa:=A[l]; A[l]:=A[lpost]; A[Ipost]:=sa;
end
end
end; {процедуры LEXYC }
40
procedure PrintPer(A:per; N:integer);
var i:integer;
begin
for i:=l to N do
write(A[i]:4);
writein
end; { процедуры PrintPer }
begin { главная программа }
repeat
begin
write(’ВВЕДИТЕ N=’);
readln(N)
end
until (N<15);
for i:=l to N do A[i]:=i; {начальная перестановка)
repeat
begin
PrintPerCA,N);
LEXYC(A,rlagl,N)
end
until not flagl;
end. {программы}
Рис. 2.6
Рассмотрим теперь алгоритм, минимизирующий объем работы по
переходу от текущего объекта к последующему.
Алгоритм D
Шаг 1. Присвоить
ai = i,qi = i, d^-1 Vi = l,n ;
d1BO,ao = n + l,an+1sn + l,m = n + l.
Шаг 2. Если m<> 1, перейти к шагу 3, в противном случае завершить алгоритм.
Шаг 3. Вывести
V i = 1, п .
Шаг 4. Присвоить
m = и.
Шаг 5. Если aflm + dm > m, то перейти к шагу 6, иначе — к шагу 7.
Шаг 6. Присвоить
dm * - dm> m = m- L
Перейти к шагу 5.
Шаг 7. Осуществить замену
aqm и aqm +
qmHQ
т aqm
Перейти к шагу 2.
Соответствующие программы (рис. 2.7, 2.8) минимизируют объем
работы по переходу от текущего объекта к последующему.
’программа генерации перестановок
* с наименьшими изменениями
OPTION BASE 0 _
DIM Р(15),Q(15),D(15)
ТИППТ "пплпито Ы~ М
10
20
30
40 ,-x--,
50 INPUT "введите N=",N ,, ____
60 IF N>14 THEN PRINT "слишком много : GOTO 50
70 ГСГ. ’ —’
80 P(I):
90 NEXT
FOR 1=1 TON „ ,
----=1: Q(I)=I: D(I)=-1
90 NKX.T I
100 D(l)=0: P(O)=N+1: P(N+1)=N+1: M=N + 1
41
110
120
130
140
150
160
170
180
190
200
WHILE Mol
FOR 1=1 TO N: PRINT P(I);: NEXT I: PRINT
M=N
WHILE P(Q(M)+D(M))>M
D£M^=-D(M): M=M-1
QM=Q(M): DM=D(M)+QM
SA=P(QM): P(QM)=P(DM): P(DM)=SA
SA=Q(M): Q(M)=Q(P(QM)): Q(P(QM))=SA
WEND
введите N=4
12 3 4
1
1
4
4
1
1
1
3
3
3
4
4
3
3
3
2
2
2
4
4
2
2
2
2
4
1
1
4
3
3
1
1
4
3
3
4
2
2
3
3
4
2
2
4
1
1
4
2
2
3
3
4
2
2
4
1
1
2
2
4
1
1
4
3
3
1
1
4
3
3
3
3
2
2
2
4
4
2
2
2
1
1
1
4
4
1
1
1
3
3
3
4
Рис. 2.7
program prim2;
type per=array[0..15] of integer;
procedure RECURS(var P,Q,D:per;var flag:Boolean;N:integer);
var M,qm,dm,sa:integer;
begin
flag:=true;
begin
M:=N;
while P[ Q[M]+D[M] ]> M do
begin
D?M]:=-D[M];
M:=pred(M)
end:
qm:=Q[M]: dm:=qm+D£M];
if Й=1 then flag:=false
end; { процедуры RECURS }
procedure PrintPer(A:per; N:integer);
var i:integer;
begin
for i:=l to N do
write(A[i]:4);
writein
end; { процедуры PrintPer
1
begin {главная программа }
repeat
begin
write(’ВВЕДИТЕ N=’);
42
readln(N)
end
until (N<15):
for i:=1 to N do
begin
P[i]:=i;
Qfij:=i;
DFiJ=“1
Р[0]:=N+1; P[N+1]:=N+1;
repeat
begin л zTS
PrintPer(P,N);
RECURS(P,Q,D,ilagl,N)
‘end .
until not flagl;
end. {программы }
Рис. 2.8
2.3. Сочетания элементов из E по к
Сочетанием элементов из Е по к называется неупорядоченное под-
множество из к элементов, принадлежащих Е.
Например, для Е = {а1э а2, а3} и к = 2 имеем (ар а2), (ар а3), (а2, а3).
Сочетание отличается от размещения тем, что в нем не учитывается
порядок. Число (к) сочетаний из п элементов по к (0 к С п) определяет-
ся как
[п\ (п)к = п!
к! к!(п —к)1’
т. е. каждому сочетанию соответствует к! размещений.
Отметим, что
Последнее рекуррентное соотношение позволяет построить для чи-
сел (к)таблицУ’ называемую треугольником Паскаля.
Приведем алгоритм порождения сочетаний, основанный на представ-
лении сочетания {aj...ап} в виде вектора С = (Ср...,Ст), компоненты
которого расположены в порядке возрастания слева направо (т. е.
Ci< Ci+1 для любого!).
Алгоритм Е
Шаг 1. Присвоить
С (i) = i Vi - 17пГ.
Шаг 2. Вывести
43
C(i) Vi» l,m .
Шаг 3. Для i = -1,..., 1 найти такое i, что
C(i) <> n - m + i
и перейти к шагу 4.
Если i, удовлетворяющее данному условию, отсутствует, завершить алгоритм.
Шаг 4. Присвоить
C(i)=C(i) + l.
Затем для j = i + 1, i + 2.m положить
C(j) = C(j - 1) + 1.
Перейти к шагу 2.
Соответствующие программы (рис. 2.9, 2.10) основаны на представ-
лении сочетания в виде вектора, компоненты которого расположены в
порядке возрастания слева направо.
’ПРОГРАММА ГЕНЕРАЦИИ СОЧЕТАНИЙ
’ПО М ЭЛЕМЕНТОВ ИЗ N
10
lo ’ТЙСПОЛЬЗУЕТСЯ'КОД ГРЕЯ)
30 DIM C(15)
40 INPUT "ВВЕДИТЕ N=",N: IF
50 ~
60
70
80
lOONEXtt....... ”
110 STOP
120 C(I)=C(I)+1
130 FOR J=I+1 TO M: C(J)=C(J-l)+l: NEXT J
140 GOTO 70
_____ __________ .... IF N>14 THEN 40
INPUT "ВВЕДИТЕ M=".M: IF M>N THEN 50
FOR 1=1 TO M : C(lS=I: NEXT I
FOR 1=1 TO M: PRINT C(I);: NEXT I: PRINT
FOR I=M TO 1 STEP -1
IF C(I)ON-M+I THEN 120
1 NEXT I
ВВЕДИТЕ N=7
ВВЕДИТЕ^M=4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
3
3
3
3
4
5
6
7
5
6
7
6
7
7
5
6
7
7
6
7
7
7
5
6
7
6
7
7
6
7
7
7
6
7
7
7
7
Рис. 2.9
44
program priml2;
type per=array[1..15] of integer;
var M.N,i:integer;
C:per;
f lagl:Boolean;
procedure SOCHET(var C:per; var flag:Boolean;N,M:integer);
var i,j:integer;
procedure Poiskl(varii:integer; var flag:Boolean);
var i:integer;
begin
flag:=true;
for i:=M downto 1 do
if not ( C[i]=N-M+i ) then
begin
ii:=i;
EXIT
end;
flag:=false
end: { процедуры Poiskl }
begin
Poiskl(i.flag);
If flag lhen
begin
И Al - 1 IT1 ,
for j:=i+l to M do
C[j]:=C[j-l]+l
end
end; { процедуры SOCHET }
procedure PrintPer(A:per; N:integer);
var i:integer;
begin
for i:=l to N do
write(A[i]: 4);
writein
end; { процедуры PrintPer }
begin {главная программа }
repeat
begin
write(’ВВЕДИТЕ N=’);
readln(N)
end
until (N<15);
repeat
begin
write(’ВВЕДИТЕ M=’);
readln(M)
end
until (M<=N);
for i:=1 to n do
C[i]:=i;
repeat
begin
PrintPer(C.M):
SOCHET(C,fiagi,N,M)
end
until not flagl
end. { программы }
Рис. 2.10
Отметим, что порождение сочетаний может быть также выполнено
в порядке наименьшего изменения, т. е. таким образом, чтобы каждое
последующее сочетание получалось из предыдущего заменой только
одного элемента. Данная последовательность наборов
G(n, k) = (G (n, к)х, G(n, k)2,...,G(n, k)/n\
45
может быть определена рекурсивно:
G(n,0) = (G(n, 0)1) = (00...0);
G(n,n) = (G(n, n)1) = (l
G(n, k) = (0G (п -1, к)ь 0G(n - 1, k)2,...,0G(n - 1, кк _ Л
(к /
lG(n - 1, к - l)j, lG(n - 1, к - 1)2,..„ lG(n- 1, к - 1)/п_ м ,
_____________ U -1/
где G (п - 1, к - 1); - обращение двоичного набора G (п - 1, к - 1);.
При этом данная последовательность получается удалением из кода
Грея G(n) всех кодовых слов с числом единиц,не равных к при условии,
что два любых соседних кодовых слова различаются только в двух
разрядах.
2.4. Поиск с возвращением
Рассмотренные алгоритмы генерации комбинаторных объектов сос-
тояли из трех этапов: построение начального объекта; преобразование
текущего объекта в последующий; проверка условия окончания генера-
ции, и представлены в виде:
{Построить начальный объект и взять его в качестве текущего!
while not {Условие окончания генерации} do
begin (Вывести текущий объект}
{Преобразовать текущий объект в последующий объект) end
{Вывести текущий объект)
При этом для генерации комбинаторных объектов в пп. 2.1- 2.3 ис-
пользовались специализированные методы, связанные со спецификой
задач.
Рассмотрим универсальные алгоритмы исчерпывающего поиска на
множестве всех возможных решений.
Пусть решение задачи имеет вид вектора (а!, а2,...), длина которого
не определена, но ограничена сверху некоторым числом г. При, этом в
качестве возможных решений рассматриваются элементы конечных ли-
нейно упорядоченных множеств Aj х А2 х ...х Ai? af G Af для любого i, где
i < г. В качестве начального частичного решения берется пустой вектор
( ) и определяется подмножество Sp состоящее из € Aj и элементы
которого удовлетворяют заданным в задаче ограничениям. Затем необ-
ходимо определить, из какого подмножества Sk множества Ак выбира-
ются элементы для расширения частичного решения от (aj, а2,...,ак_1)
до (ab a2,...,ak-i> ак). Если частичное решение (ab а2,...,ак _ j) не позво-
ляет определить новое ак, то происходит возврат и выбор нового эле-
мента ак _ j из Sk _ р Если новый элемент ак _ j выбрать нельзя, то
происходит еще один возврат и делается попытка выбрать очередной
элемент ак_2 ит. д.
46
Общая схема алгоритма, осуществляющего поиск с возвращением
для нахождения всех решений, может быть представлена в виде
к: = 1
Вычислить S} (например, в качестве S| можно взять А|);
while k> 0 do
begin
while He пусто do
begin (продвижение)
В качестве взять наименьший элемент из , удалив его из ;
if(a1,a2,..-,ak) является решением
then Записать это решение
if k< г
then begin k: = k + 1; Вычислить S^. ; (например, в качестве можно взять )
end
end;
(возврат)
k: = к - 1
end
(Все решения найдены)
В рекурсивной форме процедура поиска с возвращением имеет вид
procedure ПОИСК (X: ВЕКТОР; I: integer);
begin
if X является решением then Записать его;
if I < г
then begin Вычислить sp
for any a from do
ПОИСК (X) И (a), (I + 1)
end
end
Здесь (alt a2,... ) - вектор решения задачи, длина которого не опре-
делена, но ограничена сверху некоторым (известным или неизвестным)
числом г, aj в Ар Aj - конечное линейно упорядоченное множество;
Sj - подмножество возможных решений из ; и - операция конкатена-
ции (соединения) двух векторов, т. е.
U1...ап)"(Ь1....bm) = (ai..an, bj...Ью);
( )«(a!) = (ai)
для любых ai....an, bb...,bm, где ( ) - пустой вектор. Вызов процедуры
ПОИСК (( ), 1) находит все решения. При этом возвраты скрыты в ме-
ханизме, регулирующем рекурсию.
Как правило, описанная процедура поиска с возвращением иллюст-
рируется задачей о нахождении таких расстановок восьми ферзей на
шахматной доске, при которых ни один ферзь не атакует другого
(см. рис. 3.8).
47
В заключение отметим, что процедура поиска с возвращением мо-
жет быть усовершенствована за счет отсечения ветвей (поиск с ограни-
чениями), слияния (или склеивания) ветвей, переупорядочения поиска.
Так, широко используемый вариант поиска с возвращением, называе-
мый методом ветвей и границ (рис. 2.11)у фактически является лишь
специальным частным случаем метода поиска с ограничениями. В ряде
случаев может оказаться целесообразным осуществление поиска случай-
ным образом.
program mvg; {Метод ветвей и границ. Задача о порядке выполнения
работ}
const maxn=10;
type time=integer;
job=recora
tl,t2,t3:time;
end;
dimjob=array[l..maxn] of job;
var
tab,vl :dimjob;
b :job;
tkr,minoz,tO:time;
optimum :dimjob;
i,j,kfl :integer; { kf : к-во фиксированных работ }
n :integer; { к-во работ }
koz -‘real; { к-во оценок }
function max (x,у:time):time;
begin
if x>y then max:=x
else max:=y;
end;
function ozenka(v:dimjob;rsv:time;kf:integer):time;
var
tp,ozl:time;
, i:integer;
begin
koz:=koz+l;
ozl:=0;
tp:=rsv;
for i:=kf to n do begin
tp:=tp+v[i].t2;
ozl:=max(tp+[iJ.t3,ozl);
end;
ozenka:=max(tkr,oz1);
end;
procedure mvgmgr(vpr:dimjob;sopr,ozold:time:kf:integer >•
type vard?record6 П° минимальной нижней границе } 8 ’’
v:dimjob{
rsv,oz:time;
end;
dimvar=array [O..maxn] of vard;
kv,i,k,j:integer;
se:time;
b:vard;
dv:dimvar;
var
~r f
.вариантов для заданного kf }
.•-кг ro n do begin
=kv+l;
kv’ '
kv
kv'
kv
• v: =dv[kv-l] . v:
•v[kf]:=dv[kv-li.v[ij-
.rsv:=max(se.dv[kvJ.v[
.oz:=max(ozold,ozenka(
begin
se:=sopr;
kv:=0:
dvfkvj.v:vpr;
for i: =
kv
dv
dv
dv
dv ,avj . x a
dvfkvj.oz
end;
for j: =2CtoTkv°doabeainaHT°B П° возрастани1° оценок }
Ъ *• =dv [ j ] ;
(•tl);
kv].v,dv[kv].rsv,kf)) ;
48
к:=л-1;
while (dv[k].oz>b.oz) and (k>=l) do begin
dv(k+lj:=dv[k];
k:=k-l;
end:
dv[fc+l]:=b;
end:
if kf=n then
if dv[kv].oz<minoz then begin
minoz:=dv(kv].oz;
optimum:=vpr;
exit;
end;
{ фиксация следующей работы или отсечение }
for к:=1 to kv do
if dv[k].ozCminoz then begin
sopr:=dv[ki.rsv+dv[kl.vfkf].t2;
mvgmgr(dv[k].v,sopr,dvCk].oz,kf+l);
end
end; { mvgmgr }
procedure mvgvet (v:dinjob;sopr,ozold:time;kf:integer);
( развитие дерева по ветвям }
var i,j :integer;
jtemp:job;
rvs,se,oz:time;
begin
se:=sopr;
if kf<n then
{расчет вариантов для заданного kf }
for i:=kf to n do begin
begin
{ ввод данных }
к-во работ’);
rvs:=max(se.v[kf].tl);
oz:=max(ozold,ozenka(v,rvs,kf));
{ фиксация следующей работы или отсечения }
if oz<minoz then begin
sopr:=rvs+v[kf].t21;
mvgvet(v,sort,oz,kf+1);
end
end
else begin
oz:=max(ozold,ozenka(v,max(se,v[kf],tl).kf));
if oz<minoz then begin
minoz:=oz;
optimum:=v;
end
end
end;.{ mgvet }
begin
writeln(’введите n:
readln(n);
tkr:=0;
{ tkr: критический путь без учета необходимости в ресурсах }
for i:=l to n do begin
read(tabГiJ.tl,tab[i].t2,tabri].t3);
tkr:=max(tkr,tab[iJ.tl+tab[ij.t2+tab[i].t3);
end;
{сортировка по убыванию t3 }
for j:=2 to n do begin
b:=tab[j];
while itabfil.t3<b.t3) and (i>=l) do begin
tab^i+1]:=tab[i];
end:
tab[i+l]:=b;
end;
{ инициализация }
vl:=tab:
minoz:=MaxInt;
kfl:=l;
t0:=0:
koz:=0:
writein(’Метод ветвей и границ.*):
wrlteln(’Исходные данные. К-во работ=’,п);
writelnl ’------------------------------------' );
writelnl' tl t2 t3 ’);
writein (’------------------;
for i:=1 to n do
4. Зак. 5901.
49
writelnftabfi].tl:5,’ ’,tab[i].t2:5,’ ’,tab[i].t3:5);
writein;
writelnf’ветвление по минимальной нижней границе’);
mvgmgr(vl,tO,tO,kf1);
writelnf’К-во оценок =’,koz:9,’ Оптимум(time)=’,minoz);
writelnf ’------------------------------------------------- );
writelnf’ tl t2 t3 ’ );
writeinf’-------------------’ ) ;
for i:=1 to n do
writelnfoptimum[i].tl:5,’ ’,optimum[i].t2:5,’ ’,optimum[i].t3:5);
minoz:=Maxlnt;
koz:=0:
writein;
writelnf’развитие дерева по ветвям’);
mvgvet f vl,tO,tO,kf1);
writelnf’K-во оценок= ,koz:9,’ оптимум(time)=’,minoz);
writelnf ’-----------------------------------------------’ );
writelnf’ tl t2 t3 ’);
writelnf ’------------------’ );
for i : = 1 to n do
writelnf optimum[i].tl:5,’ ’,optimum[i].t2:5,’ ’,optimwn[i].t3:5);
end.
Метод ветвей и границ. Задача о порядке выполнения работ.
Исходные данные. К-во работ = 9
tl t2 t3
11 87 456
345 34 432
234 56 321
123 67 234
41 34 221
76 99 98
45 23 76
54 432 56
23 321 34
ветвление по минимальной нижней границе
К-во оценок=45 Оптимум (time)=1198
tl t2 t3
11 87 456
41 34 221
123 67 234
76 99 98
234 56 321
345 34 432
45 23 76
54 432 56
23 321 34
развитие дерева по ветвям
К-во оценок=211 Оптимум(г1те)=1198
tl t2 t3
11 87 456
41 34 221
123 67 234
76 99 98
234 56 321
345 34 432
45 23 76
54 432 56
23 321 34
Рис. 2.11
2.5. Случайный поиск
Методы, позволяющие получать случайные числа с тем или иным
законом распределения, как правило, основаны на использовании слу-
чайных равномерно распределенных на интервале [0,1] действительных
50
чисел. В то же время для решения ряда комбинаторных задач случай-
ные целые числа так же полезны, как и случайные действительные. При
этом следует отметить, что формирование действительного числа на
интервале [0,1] начинают с получения целого числа, равномерно распре-
деленного в некоторой области неотрицательных целых чисел.
Широко используемый метод получения псевдослучайных чисел
состоит в выборе некоторой функции f, отображающей множество це-
лых чисел в себя, т. е.^выбрав некоторое х0, получаем каждое следую-
щее число посредством функции xk + 1 = f(xk). Чаще всего применяют
функцию f вида
f(x) = ах + с (mod m),
где для t-разрядных двоичных чисел тп обычно равно 2f.
Здесь х0, а и с - целые числа из той же области, на них накладыва-
ются следующие ограничения: х0 - произвольное целое число; в ка-
честве а выбирается число, удовлетворяющее требованиям a (mod 8) = 5;
m/100 < а < m - Уль двоичные знаки а не должны иметь очевидного
шаблона; в качестве с следует выбирать нечетное число, такое, что
с/ш* 1/2-(1/6) 0,21132.
В пакет прикладных программ для научных расчетов ЕС ЭВМ вхо-
дит датчик случайных чисел RANDU со значением a s 65539 и с е 0. Как
результат этого в последовательности, вырабатываемой подпрограммой
RANDU, наблюдается крайне высокая корреляция между тремя подряд
идущими случайными целыми числами
хк + 2 = 6хк ♦ 1" 9хк vk-
Известен также универсальный датчик случайных чисел URAND
(рис. 2.12), результаты моделирования которого дают удовлетворитель-
ный результат.
с
с
с
С ИЛЛЮСТРИРУЮЩАЯ ПРОГРАММА
С ДЛЯ URAND
С
IY=2
DO 9 1=1,20
IF (URAND(IY).LT.0.5) GO TO 5
PRINT 3**
GO TO 9
5 PRINT 7
9 CONTINUE
3 F0RMATC19X,'HEADS')
7 F0RMATC19X,'TAILS')
STOP
END
C
C URAND - ЭТО ДАТЧИК РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ
С СЛУЧАЙНЫХ ЧИСЕЛ. ЗНАЧЕНИЯ ФУНКЦИИ URAND
51
С ЯВЛЯЮТСЯ ЧИСЛАМИ ИЗ ИНТЕРВАЛА (0,1)
С
REAL FUNCTION URAND(IY)
INTEGER IY
INTEGER I A , IC,ITWO,М2,4,MIC
DOUBLE PRECISION DATAN,DSQRT
DATA М2/0/,ITWO/2/
IF(M2.NE.0) GO TO 20
C
С ЕСЛИ ЭТО ПЕРВЫЙ ВХОД,TO ВЫЧИСЛИТЬ ДЛИНУ
С ЦЕЛОЧИСЛЕННОГО МАШИННОГО СЛОВА
С
М=1
10 М2=М
M=ITW0*M2
IF(M.GT.M2) GO ТО 10
HALFM=M2
С
С ВЫЧИСЛИТЬ МНОЖИТЕЛЬ И ПРИРАЩЕНИЕ
С ЛИНЕЙНОГО КОНГРУЭНТНОГО МЕТОДА
С
IA=8*IDINT(HALFM*DATAN(1.D0)/8.D0)+5
IС=2*ID INT(НALFM*(0.5.D—DSQRT(3.D0)/6.D0))+ 1
MIC=(M2-IС)+M2
C
C S - МАСШТАБИРУЮЩИЙ МНОЖИТЕЛЬ ДЛЯ
С ПРЕОБРАЗОВАНИЯ В ЧИСЛО
С ПЛАВАЮЩЕЙ ТОЧКОЙ
С
S=0.5/HALFM
С
С ВЫЧИСЛИТЬ СЛЕДУЮЩЕЕ СЛУЧАЙНОЕ ЧИСЛО
С
20 IY=IY*IA
С
С СЛЕДУЮЩИЕ ОПЕРАТОРЫ ДЛЯ ВЫПОЛНЕНИЯ
С URAND НА РАЗЛИЧНЫХ ТИПАХ МАМИН
С
IF(IY.GT.M2) IY=(IY-M2)-M2
IY=IY+IC
I F( IY/2.GT.M2) IY=( IY-f42)-M2
IFCIY.LT.0) IY=(IY+M2)+M2
URAND=FLOAT(IY)*S
RETURN
END
Рис. 2.12
В то же время представляет интерес построение последовательнос-
тей, реализованных отличными от рассмотренных выше методов, но
хорошо приспособленных для конкретного применения. В данной связи
ЛПТ-последовательности, представляющие собой последовательность
точек Рр, в единичном кубе Кп в n-мерном пространстве, для
которой любой ее двоичный участок, содержащий не менее чем 2Т+1 то-
чек, есть Пт -сетка, т. е. состоящая из N = 2V точек куба Кп. При этом каж-
дому двоичному параллелепипеду с объемом 2T/N принадлежат 2Т
точек сетки (предполагается, что v > т). Например, 8 точек (рис. 2.13,а)
52
образуют По-сетку в К2 (каждому из 32 прямоугольников (рис. 2.13,6)
площадью 1/8 принадлежит одна из точек сетки). Однако также содер-
жащая восемь точек плоская сетка (рис. 2.13,в) является Пр сеткой
(каждому Пк с |Пк1 = 1/4 принадлежат две точки). Программа расчета
(рис. 2.14) ЛПТ-последовательности предполагает наличие таблицы на-
правляющих точек , V®,..., гдеУр) - координаты точки У^
представляют собой двоично-.рациональные числа вида уФ = гФ 2~s. В
двоичной системе i = lm...l211 координаты точки Qf ЛПт-пос-
ледовательности вычисляются по формуле:
= — * ljm\ 1 j < n.
Операции * соответствуют правила 0 + 1 = 1 + 0 = 1; 0 + 0 = 1 + 1 = 0. Табли-
цы числителей г W составлены для 1 < s < 20,1 < j < 51 и позволяют вычис-
лять точки Qi ЛПТ-последовательности размерности и < 51 в количестве
N<221.
Интерес представляет также применение клеточных автоматов для
моделирования различных конфигураций. Клеточный автомат состоит
из Множества одинаковых компонент (ячеек), каждая из которых раз-
вивается в соответствии с заданным набором правил и принимает зна-
чение из небольшого числа возможных состояний.
Пусть каждая ячейка клеточного автомата находится в одном из
состояний
Х = {х0,х1,...,х1П}.
Эволюция состояний клеточного автомата описывается отношением
х (k, t) = f {х (к - 1, t - 1), х (к -1 + 1, t - 1),...,х (к, t - 1),...,х (к +1, t - 1)}.
Здесь к - индекс ячейки клеточного автомата; t = 1,2,...- дискретные
моменты времени; 1 - число ближайших соседей ячейки, от состояния
которых зависит эволюция клеточного автомата.
/ Tj
53
5
Рис. 2.13
54
с
с
С ИЛЛЮСТРИРУЮЩАЯ ПРОГРАММА
С ДЛЯ LPTAU
С
DIMENSION NR(8,10),0(8)
READ 3.NR
3 FORMAT(10l4)
N = 2
DO 9 1=1,20
CALL LPTAU(NR,I,N,Q)
IF(Q(N).LT.0,5) GO TO 5
PRINT 7
GO TO 9
5 PRINT 11
9 CONTINUE
7 FORMATC19X,'HEADS')
11 F0RMATU9X, 'TAILS')
STOP
END
C
С ПОДПРОГРАММА LPTAU ДЛЯ РАСЧЕТА
С СЛУЧАЙНЫХ ЧИСЕЛ
С
SUBROUTINE LPTAU(NR,I,N,Q)
DIMENSION NR(8,10),Q(8)
D(X)=X—INT(X)
A=I
M=1+INT(ALOG(A)/0.693147) -
DO 33 J=1,N
S = 0
DO 12 K=1,M
NS=0
DO 17 L=K,M
17 NS=NS+INT(2*D(A/2**L))*INT(2*D(B/2**(L+1-K)))
12 S=S+D(0.5*NS)/2**(K-1)
33 Q(J)=S
RETURN
END
Рис. 2.14
Данное отношение может быть задано гиперграфом Н = (X, U, R), где
X = {х} - множество возможных состояний ячеек клеточного автомата,
называемых вершинами; U = {Uo, UUn} - множество подмножеств
X вида(х (k 1, t - 1),...,х (к + 1, t - 1)}, элементы которого называются
ребрами; R-друхместный предикат R (X, U), определенный для всех
х е X, u е U, называемый инцидентором.
Вершины гиперграфа называются смежными, если существует хотя
бы одно ребро, которому они обе инцидентны. Ребра гиперграфа называ-
ются смежными, если существует хотя бы одна вершина, которой они
инцидентны. >
Число ребер U, инцидентных вершине х, называется степенью вер-
шины х и обозначается iU (x)i; число вершин х. инцидентных ребру U,
называется степенью ребра U и обозначается Ix(u)i.
Любой конечный гиперграф может быть однозначно задан матрицей
55
инциденций. Матрица, соответствующая гиперграфу (рис. 2.15), приве-
дена ниже:
Ui и2 и3 и4 и5
х2 1 0 0 1 О
х2 1 О О О О
х3 1 000 1
х4 0 1 0 1 О
х5 0 1 О О О
х6 О 1 О О 1
х7 О О 1 1 О
х8 О О 1 О О
х9 О О 1 О 1
Любой гиперграф представляется двудольным графом, его элементы
представляются вершинами, а ребра двудольного графа соединяют эти
вершины, если в гиперграфе выполняется соответствующее равенство
R (X, U) = 1. Двудольный граф (рис. 2.16) соответствует рассмотренному
выше гиперграфу (см. рис. 2.15).
Всякий двудольный граф может быть также представлен гипергра-
фом. В данном случае одно из множеств вершин X* или X2 двудольного
56
Рис. 2.16
графа G = (X1, X2, U) представляется вершинами образуемого гипергра-
фа, а другое - ребрами. Множество U гиперграфа указывает соответст-
вие между вершинами и ребрами.
Число подмножеств U определяется соотношением
n + 1 = (m + 1)21 + 1.
Поставим в соответствие каждому ребру и гиперграфа Н некоторое
неотрицательное целое число р (и), два ребра и£ и Uj гиперграфа Н будем
считать равными, если р (uj) = р (и,-).
Множество всех ребер гиперграфа Н, равных Р (Н) = У , обозначим как
Up , а число ребер гиперграфа, равных? -1 Upi.
Пусть для всех матриц инциденций гиперграфа Н выполняется ус-
ловие „
f гц-lVj = 0,1,...,п,
Г»0
т. е. каждый столбец матрицы содержит только один отличный от нуля
элемент.
При распределении формируемой клеточным автоматом последова-
тельности состояний X, близких к равномерному закону распределения,
матрица инциденций гиперграфа Н удовлетворяет условию
57
(х0, хь х2) и и = {u0,
у rif=---=(m + l)21, Vi = 0,l,...,m.
j=o J m +1
Очевидно, что в этом случае каждое состояние следует из (m + I)21
равновероятных размещений предшествующих состояний по (21 + 1)
ячейкам клеточного автомата.
Пусть каждая клетка одномерного автомата находится в одном из
трех состояний X ={ х8, хь х21. Эволюция состояния клеточного автома-
та описывается отношением (1=1)
X (k, t) = fl (к- 1, t - 1), (к, t - 1), (к + 1, t - 1)1.
Рассмотрим гиперграф Н = (X, U, R). Здесь X =
ub...,u2g}, где
и0 = (х0,х0,х0);
u3 = (xbx0,x0);
и6 = (хо,х2,хо);
«9 = (х2, х0, х0);
и12 = (х1>хо>х2);
«15 = (x2,X0,Xj);
U18 = (xbXbX2);
«21 = (х2> х1> х1)’
«24 = (х2> ХЬ х1);
Определим неотрицательное целое число Р (и) для ребра гиперграфа
как сумму индексов, входящих в отношение f.
Тогда
ир ={ц61; Up = (ubu2, u3l; Up ={u4,u5,u6,u7,u8,u9};
Up ={«10> «11, «12, «13’ «14» «15» «16^
Up ={«17> «18’ «19’ «20> «2b «22^ 1 Up = ^U23> «24’ «25^ 1
UP={U26},
alU;i = l;iUji = 3;iU2l=7;iU;i = 6;
lU*i =3;lUp«i = l.
Соответствующая матрица инциденций гиперграфа (рис. 2.17) имеет
вид
0 1 2 4 5 6 7 8 9 10 11 12 13 1415 16 17 18 19 20 21 22 23 24 25 26
U1 = (x0,X0,X1);
u4 = (xo,xq,x2);
u7 = (xbx0,x1);
u10 = (x0,xi,x2);
ui3 = (xi>xi>xi);
U16 = (x2-xb xo);
«19 = (xb x2> xl)l
«22 = (x2> x2> xo);'
«25 = (x2> x2> xl);
u2 = (х0, хь х0);
u5 = (xo,x1,x1);
и8 = (хьХ1,х0);
Ull =(xo>x2,x1);
U14 = (xi,x2,x0);
u17 = (x0,x2,x2);
«20 = (x2, x0, x2);
u23 = (xl> x2, x2);
«26 = (x2> x2> x2'*
Xu 10000000011111110000000001
x“o 1 1 11 11 1100000000000000000
x2 00000000 0 00000001 11 11 11 110
Изменение состояний клеточного автомата для исходного начального
состояния 0, 2, 2, 1, 1, 0 изображено на рис. 2.18. Отметим, что на всех ша-
гах, за исключением второго, число ячеек, находящихся в одинаковом
состоянии, равно 2.
58
Рассмотрим теперь случай,
когда клетка находится только
в двух состояниях X = (0,1}.
Очевидно, что множество ребер
U гиперграфа имеет вид:
u ={0,0,0}; u4=fl,0,0};
u ={0,1,1}; u7 = {l,l,l};
u6 = { 1,1,0}; u2 = {0,1,0};
U1={0,0,ll; u5 = {l,0,I};
Пусть величина p (u) равна сум-
ме элементов множеств U, т. е.
p(u0) = 0; P(u2)=l;
р (u5) = 2; р (u7) = 3;
P(ui)=l; p(u3) = 2;
P(u6) = 2; p(u4) = l.
В результате
U®={u0}; Uj ={ubU2, u4};
Up ={u3, us, u6}; Up={u7}.
Тогда матрица инциденций
гиперграфа Н (рис. 2.19) может
быть задана следующим обра-
зом:
0 1 2 3 4 5 6 7
0 ~ 6 6 1 6 1 1 0
10 110 10 0 1
Изменение состояний кле-
точного автомата, заданного
гиперграфом Н, представлено
на рис. 2.20. Соответствующая
программа моделирования
(рис. 2.21) позволяет имитиро-
вать большое число шагов в
эволюции клеточного автомата.
Введем дискретный закон
распределения ап. Данное рас-
пределение зависит от двух па-
раметров а и п, которые яв-
ляются целыми положительны-
ми числами. Алгоритм получе-
ния такого распределения име-
ет следующий вид.
59
Рис. 2.19
60
Рис. 2.20
Шаг 1. Формируется а строк из а единиц, сдвинутых влево относительно друг друга на
один разряд.
Шаг 2. Производится суммирование по столбцам, в результате которого получаются
симметричные суммы.
Шаг 3. Если п > 2, то строка полученных симметричных сумм записывается а раз.
Каждая строка сдвигается влево относительно предыдущей строки на один разряд.
В противном случае перейти к шагу 6.
Шаг 4. Производится суммирование по столбцам, в результате которого получаются сим-
метричные суммы.
Шаг 5. Шаг 3 и шаг 4 выполняются п-2 раз.
Шаг б. Количество полученных симметричных сумм является числом различных состоя-
ний а"-распределения.
В качестве примера а “-распределения рассмотрим случай а = 4,
п = 3. В этом случае получим
1111
1111
1111
1111
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 3 6 10 12 12 10 6 3 1
61
откуда
Р (х0) = Р (х9) = 1/64;
Р(х1) = Р(х8) = 3/64;
P (х2) = Р (х7) = 6/64;
Р(х3) = Р(х6) = 10/64;
Р(х4) = Р(х5) = 12/64.
Здесь число различных состояний равно 10.
Программы формирования симметричной суммы для ап (рис. 2.22),
определения основных характеристик ап-распределения (рис. 2.23), мо-
делирования чисел по ап-распределению (рис. 2.24) обеспечивают воз-
можность построения различных симметричных конфигураций.
SPS: PROC OFTlONS(MAIw);
/* ПРОГРАММА ДЛЯ ПОЛУЧЕНИЯ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ И
ОЦЕНКИ ЕЕ ХАРАКТЕРИСТИК */
DCL KOD(0:7) BIT(1), /* КОДЫ ВОЗМОЖНЫХ СУММ */
RAB BIT(3),
IK DEC FL0AT(6),
KABB(4) BIT(4),
ISX0D(16) В IT(1), /* НАЧАЛЬНАЯ ЗАГРУЗКА */
KOL(0:15) DEC FIXED(6) INIT((16)0),
HISTE(0:15) FLOAT(lb), /♦ ЗНАЧЕНИЯ ГИСТРОГРАММЫ ♦/
DP DEC FIXED(3),
DPI DEC FIXED(4,1)
PESH CHAR(DP) CONTROLLED,
SUM FL0AT(15),
К DEC FIXED(15),
MASR(K) DEC FLOAT(6) CONTROLLED,
KORR FL0ATU5) , /* КОЭФФ. КОРРЕЛЯЦИИ ♦/
MX FL0ATU5) , /♦ МАТ. ОЖИДАНИЕ */
DX FLOAT(15) , /♦ ДИСПЕРСИИ ♦/
N DEC FIXED(6); /* N-ОБЬЕЛ ВЫБОРКИ */
ОН ENDFILE(SYSIw) GOTO COW;
ON CONVERSION GOTO ME;
MZ; GET EDIT(KOD)(SKIP,8(X(1),A(1)));
GET ED IT(ISXOD)(SKIP,16(X(1),A(1)));
GET ED IT(N)(SKIP,F(6));
PUT EDITt'BEKTOF КОДОВ')(SKIP(3),A);
PUT ED IT(KOD)(X(5),8(X(5),В(X(1 ) , A (1 ) ) ) ;
PUT ED IT('НАЧАЛЬHAH ЗАГРУЗКА')(SKIP(2),A);
PUT ED IT(ISXOD)(X(2 ) ,16(X(1 ) , A(I ) ));
PUT EDIT('OBbEM ВЫБОРКИ',N)(SKIP,A,F(6));
K=N;
ALLOCATE MASH;
DO 1=1 TO N BY 4;
КЭ=С; K1=O;
DO M=2 TO 15;
RAB=ISXUD(M-1)!IISXOD(M)!IISXOD(M+1) ;
IK=HAd;
IF KOD(IK)='l'B THEN DO;
ISXODR(M)='l'B;
K1=K1+1;
END;
62
ELSE DO;
ISXODR(M)='0'В;
K0=K0+1;
END;
END;
IF K0=K1 THEN DO;
IF ISXOD(7)='0'B THEN DO;
ISXOD(1)='0'B;
ISXOD(16)='l'B;
END;
ELSE DO;
ISXODR(1)='1'В;
ISXODRC16)='0'B;
END;
END;
IF К0Ж1 THEN ISXODRC1),ISXODR(16)='1'В;
IF KO<K1 THEN ISXODRC1),ISXODR(16)='0'B;
RABBC1)=ISXODR(1)I!ISXODRC2)!!ISXODRC3)!!ISXODRC4);
RABB(2)=ISXODRC5)!!ISXODR(6)!!ISXODRC?)!!ISXODRCfi);
RABBC3)=ISX0DRC9)!!ISXODRC10)!!ISXODRC11)!!ISXODRC12);
RABBC4)=ISXOD(13)!!ISXOD(14)!!ISXOD(15)!!ISX0DC16);
IK=RABB(1);
MASRCI)=IK;
KOL(IK)=KOL(IK)+1;
IK=RABB(2);
KOLCIK)=KOL(IK)+1;
MASRCI+1)=IK;
IK=RABB(3); KOL(IK)=KOL(IK)#1; MASRCI+2)=1K;
IK=RABB(4); KOL(IK)=KOL(IK) + 1; MASRCI+3)=IK;
isxod=isxodr;
END;
SUM=0;
DO J=0 TO 15;
SUM=SUM+KOL(J);
END;
PUT EDIT((15)'*')(SKIP(3),XC50),A);
PUT EDITC'#','*')(SKIP,X(50),A,X(13),A);
PUT EDITC'#','ГИСТОГРАММА','*')(SKIP,X(50),A,XC1),A,X(1),A);
PUT EDITC'#','#')(SKIP,X(50),A,X(13),A)J
PUT ED IT((15)'*')(SKIP,X(50),A);
PUT EDITC'OBbEM ВЧБОРКИ'»SUM)(SKIP(3),X(20),A,X(5),F(6));
PUT EDITC(60)'#')(SKIPC3),XC20),A);
PUT EDITC'♦',*♦') (SKIP» X(20) ,’A,X(10) , А» X(48) , A) 5
PUT EDITC'#',' u','#','hIbTE(J) ' ,'#'«) ( SK IP , X ( HU ) , A , X ( 4 ) , A ,
X ( 4 ) , A , X ( 1 0 ) , A , X ( 28 ) , A ) ;
PUT ED IT ( ' #' , ' ♦ ' , ' ♦ ' ) ( SK I p , X ( 20 ) , A , X (10 ) , A , X ( 48 ) , A.) ;
PUT EDITC(60)'*')(SKIP,X(20),A);
DO J=0 TO 15;
H1STECJ)=KOL(J)/SUM;
PUT EDITC'*',J,'*', HloTECJ),)(SKIP,X(2w),A,X(4) ,r(2) ,
X(4),A,X(lu),E(21,14,la),X(l?),A);
END;
PUT ED IT((60)'♦') (SK IP,X(20),A); KOL = 0;
PUT SKIFC2) ;
PUT ED IT ( С1 0 ) ' 0..' , ' 1 ' ) ( SK IP , X С1 5 ) , A , A ) ;
CSKIP,XC15),10(A,X(9))tA);
DO 1=0 TO 15;
DP1=HISTE(I)*100;
DP = ROUkDCDPl ,0) ;
ALLOCATE PESH;
63
DO J = 1 TO 2;
PUT ED IT('.')(SKIP,X(15 ) , A );
END;
DO LS=1 TO DP;
SUBSTR(PESH,LC , 1)='*';
END;
POT ЕЫТ( I,PECH)(SKlP,F(lb) ,X(1 ) ,A) ;
FkEE FESH;
END;
MX=0;
do 1=1 то к;
MX=MX+MASh(I);
end;
mx=mx/k;
PUT EDIT('MAT. ОЖИДАНИЕ MX = ',MX)(SKIP(3),A,E(21,1 4,15)) ;
DX=0 ;
DO 1=1 TO K;
DX=DX+(MASR(I)-MX)**2;
END;
DX=DX/(K-t);
PUT ED IT('ДИСиЕРСИЯ DX = ' , DX ) ( SK 1 P , A , E ( 21 ,14,15 ) ) :
DO 1=1 TO 16;
SUM=e;
DO J=1 TO K-I;
SUM=SUM+MASR(J)*MASR(J+I);
EwD;
KOKh=(SUM/(rt-I)-MX**2)/DX;
PUT ЕО1Т('КЭЭФФ. КОРРЕЛЯЦИИ KORh',I,'=',КОЬК)
(SKIP,A,h(2),A,E(21,14,15));
END;
FREE maSn;
GOTO MZ;
ME: PUT ED IT('КОРРЕКТИРУЙТЕ ИСХОДНЫЕ ДАННЫЕ')(SKIP,A);
CON:PUT EDIT('KOHEU РАБОТЫ')(SKIP,A);
END SPS;
ВЕКТОР КОДОВ 01101Й01
НАЧАЛЬНАЯ ЗАГРУЗКА 0110100101110100
ОБЪЕМ ВЫБОРКИ 5000
***************
♦ *
♦ ГИСТОГРАММА *
* *
***************
ОБЪЕМ ВЫБОРКИ 5000
*********************************************
♦ * ♦
♦ J ♦ HISTE(J) ♦
♦ ♦ *
*********************************************
* 0 * 4.90000000000000Е-02 *
♦ 1 ♦ 6.860000И0000000Е—02 *
♦ 2 * 6.74000000000000Е—02 *
♦ 3 ♦ 8.18000000000000Е-02 ♦
♦ 4 ♦ 5•58000000000000Е—02 *
♦ 5 ♦ 8.38000000000000Е-02 ♦
♦ б ♦ 3.70000000000000Е-02 *
♦ 7 * 5.66000000000000Е-02 *
64
4с в * 5.720000000Й0000Е-02 *
* 9 ♦ 3.70000000000000Е-02 *
♦ 10 * В.48000000000000Е-02 *
* ц ♦ 5.64000000000000Е-02 *
* 12 * 8.06000000И00000Е-Э2 *
* 13 * 6.92000000000000Е-02 *
* 14 * 6.660000000000005-02 *
* 15 * 4.82000И00000000Е-02 *
***♦♦*♦*♦**♦*♦****♦**************************
0 1
* ♦
0.0...........................................................
0 1 2 3 4 5 6 7 8 9 10 И 12 13 14 15
МАТ. ОЖИДАНИЕ МХ= 7.490400000000Р0Е+00
ДИСПЕРСИЯ ОХ= 2.12277533906743Е+01
КОЭФФ. КОРРЕЛЯЦИИ KORR 1=-3.19019337742106Е-И2
КОЭФФ. КОРРЕЛЯЦИИ KORR 2=-1.15444622425407Е-01
КОЭФФ. КОРРЕЛЯЦИИ KORR 3=-7.90396974634440Е-И2
КОЭФФ. КОРРЕЛЯЦИИ KORR 4=-6.42884350685899Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 5= 1.28555425758522Е-01
КОЭФФ. КОРРЕЛЯЦИИ KORR 6=-1.01704384651077Е-01
КОЭФФ. КОРРЕЛЯЦИИ KORR 7=-8.75620627860627Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 8=-1.61991993400966Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 9= 1.00515643264182Е-03
КОЭФФ. КОРРЕЛЯЦИИ KORR10=—9.94028966324370Е—02
КОЭФФ. КОРРЕЛЯЦИИ KOFRU= 2.34584248439834Е-01
КОЭФФ. КОРРЕЛЯЦИИ K0RR12= 4.43675229619041Е-02
КОЭФФ. КОРРЕЛЯЦИИ K0RR13= 2.08941976727096Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR14= 8.58738562588666Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR15=-7.44456937538320Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR16= 5.96636963769438Е-03
Рис. 2.21
SIMMjPrtOC ОРТ IОNb(мА 1h );
DCL SUM(*) FIXED BlN(15) CTL,
FIXED Ь1л(15) CTL,
(A,H) FIXED ЫЛ15),
(I,J,K,LR) FIXED dIu(15);
GET EDIT(A,H) (F(1),F(1));
LR=H*(A-1)+1;
ALLOC SUM(LR),BUF(lk) ;
5. Зак. 5901.
65
DO 1=1 TO a;
SUM(I)=l;
END;
do 1=1 то H-i;
BUF=SuM;
DO J=1 TO A-l;
DO K=LK TO 2 BY -1 ;
BUF(К)=FJF(K-l);
END;
BUF(1)=0;
SU¥=SUM+BUF;
EHD;
END;
PUT EDIT (SUM) (oKIP,(o5)(r(3),X(1)))J
FREE SuMtBUF;
END SIMM;
1 4 10 20 31 40 44 40 31 20 10 4 1
Z2:PR0C OPTIONS(MAIN);
DCL(A,H) BIN FIXED(IS);
GET EDIT(А»H)(F(l));
DCL MAS(100);
L=A;
MAS=0;
do 1=1 to a;
mas(I)=i;
END;
DO 1=2 TO h;
DO II=L ТО 1 BY -1;
MAS(II+A—l)=MAS(11);
MAS(II)=0;
END;
L=L+A-1:
DO M=1 TO L;
DO J=M*1 TO M+A-l;
MAS(M)=MAS(M)+MAS(J);
END;
END;
END;
PUT SKIP EDIT((MAS(I) DO 1=1 TO L))(F(4));
END Z2;
33
1 3 6 7 6 3 1
44
1 4 10 20 31 40 44 40 31 20 10 4 1
35
1 6 15 30 45 51 45 30 15 5 1
Рис. 2.22
SW.’PROCEDURE OPTIONS(MAIN);
DCL (A»ST,CIKL)
(J»11,12,1,RAST,K(RZ)
DP
DPI
PESH
(D,M)
SUM
((MASK,MASR) (K)
DEC FIXED(7),
DEC FIXEDU5),
DEC FIXED(3),
DEC FIXED(4<1),
CHAR(DP) CONTROLLED
DEC FL0AT(15),
DEC FL0ATC15),
DEC FIXE0C15),
66
PMASN (К) DEC FL0AT(15),
(P(O:K),FN(O:RZ)) DEC FL0AT(15)) CONTROLLED;
GET EDIT(CIKL) (F(7))j
PUT EDIT('ПРОГРАММА ДЛЯ ВЫЧИСЛЕНИЯ ПО ПРОИЗВОЛЬНЫМ '
' ЗНАЧЕНИЯМ А И ST ФУНКЦИИ','1) РАСПРЕДЕЛЕНИЯ
'2) ВЕРОЯТНОСТИ','МАТЕМАТИЧЕСКОГО ОЖИДАНИЯ',
'ДИСПЕРСИИ')
(SKIP,Х(10),А,А,4(SKIР,X(10)<А))J
DO 12=1 ТО CIKL;
GET EDIT (A,ST) (SKIР,2(F(7)));
К=А*(А—1)♦(ST—1);
RZ=K+i;
ALLOCATE MASN,MASR,P,FN,PMASN;
DO 1=1 TO K-A;
MASN(I)=0;
END;
DO I=(K*1)-A TO K;
MASN(I)=1;
END;
PUT EDIT('MASN=') (SKIP,A);
do м=1 то к;
PUT EDIT(MASN(M)) (F(15))j
END;
DO 1=1 TO K;
MASR(I)=MASN( I ) ;
END;
DO J=1 TO ST-1;
DO 1=1 TO A-1;
DO 11=1 TO K-l;
MASN(11)=MASN(11+ 1);
END;
MASN(K)=0;
DO 11=1 TO KJ
MASR(11)=MASR(11)*MASN(11);
END;
END;
DO 1=1 TO KJ
MASN(I)=MASR(I);
END;
END;
PUT EDIT('MASN=') (SKIP,A);
DO M=1 TO к;
PUT EDIT(MASN(M)) (F(16));
END;
RAST=A**ST;
PUT EDIT('RAST=',RAST) (SKIP,A,F(16));
P(0)=0;
M=0;
D=0;«
SUM=0;
FN(O)=0;
FN(1)=0;
DO 1=1 TO к;
PMASN(I)=MASN(I);
P(I)=PMASN(I)/RAST;
SUM=SUM*P(I);
FN(1*1)=SUM;
M=M*I*P(I);
D=D+I**2*P(I);
END;
D=D-M**2;
67
PUT EDITC'A”,A,'ST=', ST,'MAT.ОЧИЛАНИE=M,'ЦИСПЕРСИЯ=',D)
(SKIP(2),X(40),2(X(2),A»F(7)),2(SKIP,X(40),A,£(21,14,15)));
PUT EDITC(120)'*') (SKIPC3),A);
PUT EDITC'*','*') (SKIP,XC42),A,X(33),A);
PUT ED I ТС ' X','*', PCX)','*','FtlCX)')
(SKIP,X(25),A,XC16),A,X(14),A,X(15),A,X(14),A);
PUT EDITC'*','*') (SKIP.XC42),A.XC33),A);
PUT EDITC(120)'*') (SKIP,A);
DO 1=0 TO K;
PUT EDITCI,'*',PC I),'*',FN(I )) (SKIP,X(1 в),F(15),X(9),A,
X(6),E(21,14,15),X(6),A,X(6),EC 21,14,15));
END;
PUT EDITC'*','*',FN(PZ)
(SKIP.XC42),A,X(33),A,X(6),E(21,14,15)) ;
PUT EDITCC120)'*') (SKIP,A);
PUT SKIPC5);
PUT ЕО1Т('ГРАФИК ФУНКЦИИ ВЕРОЯТНОСТИ') (SKIP,X(25),A);
PUT SKIPC2);
PUT EDIT((10)'O.........','!') (SKIP.XC15) , A, A) ;
PUT EDITCC10)'. ','.') (SKIP,X(15) , A,A) ;
PUT EDITC'0','1','2','3','4','5','6','7','0','9','0')
(SKIP,X(15),10(A,X(9)),A);
do 1=1 то к;
DP1=P(I)*100;
DP=ROUND(DP1,0);
ALLOCATE PESH;
DO J=1 TO 2;
PUT EDITC'.') (SKIP,X(15),A);
fnd;
DO LS=1 TO DP;
SUFSTR(PFSH,LS,!)='♦';
END;
PUT EDITCI,PESH) (SKIP,F(15),X(1),a);
FREE PESH;
END;
PUT SKIPC2);
PUT ЕО1Т('ГРАФИК ФУНКЦИИ РАСПРЕДЕЛЕНИЯ')
(SKIP.XC25),A);
PUT SKIPC2);
DO 1=1 TO К;
DP1=FN(1+1)*100;
DP=ROUND(DP1,0);
IF DP=0 THEN DO;
PUT EOIT(I) (SKIP,F(15));
DO JS=1 TO 2;
PUT EDITC'.') (SKIP,XC15),A);
END;
GOTO MET1;
END;
ALLOCATE PESH;
DO J=1 TO 3;
DO LS=1 TO DP;
SUBSTR(PESH,LS,1)='.';
END ;
SURSTR(PESH,DP,1)='*';
IF J=1 THEN
PUT EDIT(I.PESH) (SKIP,F(15),X(1),A);
ELSE
PUT EDITC'.',PESH) (SKIP,X(15),A,A);
END;
FREE PESH;
68
МЕТ1: END;
FREE MASN,MASR,P,FN,PMASN;
END;
END S'M;
ПРОГРАММА ДЛЯ ВЫЧИСЛЕНИЯ ПО ПРОИЗВОЛЬНЫМ ЗНАЧЕНИЯМ
А И ST ФУНКЦИИ, РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТИ
МАТЕМАТИЧЕСКОГО ОЖИДАНИЯ,ДИСПЕРСИИ
MASN= 1 0 1 0 1 0 0 0 0 1
MASN= 1 3 6 10 12 12 10
б 3 1
RAST= 64
А= 4 ST= 3
МАТ.ОЖИДАНИЕ= 5.50000000000000Е+00
ДИСПЕРСИЯ= 3.75000000000000Е+00
♦♦***********************************************************
♦ *
X * Р(Х) * FN(X)
* *
***********************ж****♦♦*♦*♦♦♦****♦*♦*♦**♦*************
0 * 0.00000000000000Е+00
1 * 1.56250000000000Е—02
2 * 4.66750000000000Е-02
3 * 9.37500000000000Е-02
4 ♦ 1.56250000000000Е-01
5 ♦ 1.87500И00000000Е-01
6 * 1.87500000000000Е—01
7 * 1.58250000000000Е-01
8 * 9.37500000000000Е-02
9 ♦ 4.68750000000000Е-02
10 ♦ 1.56250000000000Е-02
*
* 0.00300000000000Е+00
* 0.00000000000000Е+00
♦ 1.56250000000000Е—02
* 6.25000000000000Е-02
* 1.56250000000000Е—01
* 3.12500000000000Е-01
* 5.00000030000000Е—01
* б.87500000000000Е-01
* 8.43750000000000Е-01
* 9.37500000000000Е-01
* 9.84375000000000Е-01
♦ 1.00000000000000Е+00
*************************************************************
Рис. 2.23
S°S: РИОС ОРТ IОNS(wАI я);
/* ПРОГРАММА ИЛЯ ПОЛУЧЕНИЯ СЛУЧАЙНОЙ последовательности
ТИПА
DCL
А**Ь' И ОПЕНКИ ЕЕ ХАРАКТЕРИСТИК */
KOD(Э : 26 ) hA3 MATRI(и:26) СНАп(□), ChArt(5), CHAh(l), /* КОДЫ ВОЗ.ЧОКНыХ СУММ >
ISXOD(1 в ) ISXOORUo ) CHAn(1), С H A К ( 1 ) , /♦ пАЧАЯЬНАЛ ЗАГРУЗКА ♦>
KOL(0:2) DEC FIXED(6) I NITC(3)0),
Н15ТЕ(И:2) DP FLOAT(lb), DEC FIXED(3), /* ЗНАЧЕНИЕ ГИСТОГРАММЫ
DPI DEC FIXED(4,1),
PESH SUM CHAn(DP) COhThOLLED, FLOATC15),
К DEC FIXED(lu)
MASR(K) DEC FL0AT(6) COaTriOLLED,
KOHR FLOAT(lb), /* КОЭФФ. КОРРЕЛЯЦИИ */
MX FL0AT(15), /* мА Г. ПРИДАНML */
DX FLOAT(lb), /♦ дИСПЕРСИл */
N DEC F1XEDC6); /* N — ОВЬЕм В ы ь0 р К И */
69
Он ENDF ILE(SYS I»< ) GOTO сон;
Он CONVERSION GOTO мг;
MZ: GET EDIT(KOD)(SK IP ,27(X(1),a(S )));
GET ED IT(.4A1’F I ) ( SK I r , 27 ( X (1 ) , A ( 1 ) ) ) ;
GET EDIT(ISXCO)(SKIP,1 в(X(1), A ( 1)));
GET EDIT(N)(SnIr,f(c));
POT EDIT('ВЕКТОР КОиОв'>(SKIP(3)»A);
POT EDIT(KOD)(X(fi),27(X(1),A(o)));
POT EDIK'МАССИВ СООТВЕТСТВИЙ'.NATK1) (SKIP,A,л(б),27(X(1),A(1 ) ) )
POT EDIK 13X00 ) (X (2J, 16(X( 1 ) ,a( 1 ) ) ) ;
POT EDIT('OSb£M БяБОРлИ' , j ) (SK I P,A,Ь(В)) ;
и=м;
ALLOCATE MASR;
DO 1=1 TO N BX 16;
КР=П; Kl=;’; K2 = 0;
DO ‘<=2 TO 15;
m = ISX0D(M-l ) I I ISXOD(M) I I ISXOD(M*1 ) ;
DO J=0 TO 26;
IF KOD(J)=RAB THEN KK=J;
END;
ISXODR(M)=MATRI(KK);
IF MATRI(KK)='0r THEN K£=K0+1;
IF MATRI(KK)='l' THEN K1=K1+1;
IF MATRI(KK)='2' THEN K2=K2+1;
END;
IF (K1>=88K0=K2) THEN DO;
ISXODR(1)='2';
K2=K2+1;
ISXODR(16)='0';
K0=K0+1; GOTO ML; END;
IF (KI>=88K0>K2) THEN DO;
ISXODR(l),ISXODR(16)='2r;
K2=K2+2; GOTO ML; END;
IF (KI>=88K0<K2) THEN DO;
ISXODR(l),ISXODR(16)='0';
K0=K0+2; GOTO ML; END;
IF (KI<88K0>=48K2>=4) THEN DO;
ISXODR(l),ISX0DR(16)='l';
Kl=Kl+2; GOTO ML; END;
IF (KI<8&K0>=48K2<4) THEN DO;
ISXODR(l)='l'; ISXODR(16)=r2r;
K1=K1+1; K2=K2+1; GOTO ML; END;
IF (KI<8&K0<4dK2>=4) THEN DO;
ISXODH(1)=r0*; ISX0DK(16)=*l';
K0=K0+i; K1=K1*1; END;
ML: KOL(0)=KOL(0)+K0;
KOL(1)=KOL(1)+K1;
K0L(2)=K0L(2)+K2;
DO J=1 TO 16;
GET STRING(ISXODRCJ)) ED IT(MASR(I *J-l ))(F(1));
END;
ISXOD=ISXODR;
END;
SUM=0;
DO J=0 TO 2;
SUM=SUM+KOL(J);
END; <
70
PUT FDITC(lo)'*')(ShlP,X(o0) ,A);
PUT FDITCr*r,,*r)(3hIp,X(o0)lA,XC13),A);
PUT FDIT('*','ГИСТОГРАММA','*')(SKIP,X(bP),A,К(1),A,X(1),A ) J
PUT EDITC(SKIP,X(o0),A,X(13),A) ;
PUT FDIT(U5)'*')(SKIP,X(o0),A);
PUT FDlTC'OSbEM ВысиРлИ',5Um)(SKIP(о),X(20),A,X(5),F(b));
PUT FDIT( (M)'*')(3Hr<3) ,X(20) , A ) ;
PUT EDITC'*')(SKIp,X(20),A,X(10),A,X(48),A)J
PUT EDITC'*','O','HISTECJ) ','♦')(SKIP,X(20 ),A,X(4),A,
X(4 ) , A , X(10) , A , X(2d ) , A ) ;
PUT EDITC'*','♦','*')(SKIp,x(20),A,X(10),A,X(49),A) ;
put editc(би)'*')(Skip,xc20),a);
DO J=fc TO 21
HISTECJ)=KOL(J)/SUM;
PUT EDITC'*',J,'*',HISTECJ),'*')(SKIP,X(20 ),A,X(4),F(2),
X( 4 ) , A , X ( 1 J ) , E ( 21,1 4,15 ) , X ( 1 7 ) , A ) ;
EhD;
PUT FDIT((60)'♦')CSKIP,X(23),A); KOL=0J
PUT SKIPC2);
PUT EDITC C10) r0.......' ,'1' ) (SKlP.XClb) , A , A);
PUT EDITC(10)'.','.')(ShIp,X(15),A,A);
PUT FDITC'P','1','2','3','4','5','6','7','8','9','C')
(SKIP,X(15),10(A,X(9)),A );
DO 1=0 TO 2;
dpi=histecI)*i00;
DP=kOUMDCDP1,0);
ALLOCATE PESH;
DO J=1 TO 2;
PUT FDITC',')(SKIP,X(15),A);
EHD;
DO LS=1 TO OP;
SuBSTK(PESH,Lb,1) = '*';
EI»D;
PUT EDITCI,PESH)(SKIP,h(15), XC 1),A);
free PESH;
EHD;
MX=0;
DO 1=1 TO K;
mxsmx+vashC i );
END;
MX=MX/K*
PUT EDITC'MAT. ОЖИДАНИЕ MX=',MX)CSKIPC3), A,E(21,14,15) ) ;
DX=0;
DO 1=1 TO K;
DX=DX+CMASRCI)-MX)**2;
END;
DX=DX/CK-1);
PUT EDITC'ДИСПЕРСИЯ DX=',DX)(SKIP,A,E(21,14,15));
DO 1=1 TO 16;
SUM=0;
DO J=1 TO K-I;
SUM=SUM*MASR(J)*MASR(J+I);
END;
KO RR=(SUM/(К-1)-MX**2)ZD X;
PUT Е01Т('К0ЭФФ. КОРРЕЛЯЦИИ KORR',I,'=',KORR)
(SKIP,A,F(2),A,E(21,14,15));
END;
71
FREE MASR;
GOTO MZ;
ME: PUT EDIT('КОРРЕКТИРУЙТЕ ИСХОДНЫЕ ДАННЫЕ')(SKIP,A);
COKlPUT EDIT('KOH£II РАБОТЫ')(SKIF,A);
run c. p n •
ВЕКТОР КОДОВ ЗИИ 001 010 100 302 020 20И 011 101 110 012 102 120
210 201 021 111 022 202 220 112 121 211 122 212 221
222
МАССИВ СООТВЕТСТВИЙ 1 020210112110 2 1121012001211
НАЧАЛЬНАЯ ЗАГРУЗКА 1021100121121012
ОБЬЕМ ВЫБОРКИ 5200
♦ J * HISTE(J)
* * ♦
#***#**wt ♦*♦***********♦♦*********♦****★♦♦*♦****♦************
* 0 * 2.73437500000000Е—И1 *
♦ 1 * 4.49667500000000Е-01 *
* 2 * 2.76875000Й00000Е-01 *
* ****** ******** **** ********************* ***************
0.........0..........0..........0...... . . .0......0.
0 1 2 3 4 5
0 ******** 4г *************** Ж * *
1 ****♦♦*♦**♦♦*Ж*******************************
2 ****************************
ГИСТОГРАММА
МАТ. ОЖИДАНИЕ МХ= 1.0034375000000Й0Е+00
ДИСПЕРСИЯ DX= 5.50472706314453Е-01
КОЭФФ. КОРРЕЛЯЦИИ КОНИ 1=-2.91335571726245Е-01
КОЭФФ. КОРРЕЛЯЦИИ КОРН 2=~1.20440029503009с,—01
КОЭФФ. КОРРЕЛЯЦИИ KORR 3= 2.10146385776158Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 4= 8.29812090657475Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 5=-7.67605333559222Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 6=-3.07110623916828Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 7= 4.95035600341827Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 8=-1.87710154853124Е-02
КОЭФФ. КОРРЕЛЯЦИИ KORR 9=~5.86236306230576£-02
КОЭФФ. .КОРРЕЛЯЦИИ KORR10= 3.81724104993548Е-02
КОЭФФ. КОРРЕЛЯЦИИ KOER11= 1.82504806880920Е-02
КОЭФФ. КОРРЕЛЯЦИИ K0RR12= 1.73503742258882Е-03
КОЭФФ. КОРРЕЛЯЦИИ KORR13=—8.88920139955535Е—02
КОЭФФ. КОРРЕЛЯЦИИ K0RR14= 1.94467686106806Е—01
72
КОЭФФ. КОРРЕЛЯЦИИ K0RR15= 9.16323325848820Е-03
КОЭФФ. КОРРЕЛЯЦИИ KORR16=-6.38599292231945Е-02
Рис. 2.24
Глава 3. ПРИМЕРЫ КОМБИНАТОРНЫХ ЗАДАЧ
Ниже представлены наиболее интересные задачи Республиканских
и Всесоюзных олимпиад по программированию.
Отметим, что, по мнению выдающегося советского математика
Б. Н. Делоне, большое научное открытие отличается от хорошей олим-
пиадной задачи только тем, что для решения олимпиадной задачи тре-
буется 5 часов, а для получения крупного научного результата 5000 ча-
сов. При этом всегда следует помнить эмпирическое правило для реше-
ния комбинаторных задач: задача при достаточно малой размерности -
тривиальна, при большой - решается вручную, затем может быть решена
на ЭВМ и, наконец, для последующих значений параметров решение
получить невозможно.
3.1. Последовательность нулей и единиц составлена по следующему
правилу. Сначала вводится первый элемент А,равный 0 либо 1. Затем на
каждом шаге к уже написанной части последовательности приписывает-
ся новая той же длины, получаемая заменой всех нулей на единицы, а
единиц - на нули. Например, для А = 0 получим последовательность
01101001... . Составить программу формирования и вывода на печать
данной последовательности, состоящей из п элементов. Входная инфор-
мация для программы размещена на одной перфокарте, первая позиция
на перфокарте отведена под запись значения элемента А, вторая и
третья позиции - под запись общего числа элементов последователь-
ности.
Соответствующие программы решения данной задачи и результаты
представлены на рис. 3.1.
POSL:PROC OPTIONS(MAIN);
DCL
STR BITC500),
A BIT(l),
(Nl.N.I) FIXED BIN(15);
GET EDIT (A,N) (B(l),F(2));
Nl = l ;
SUBSTR(STR,1,1)=A;
DO WHILE(N>N1);
DO 1=1 TO Nl;
IF SUBSTR(STR,I,1)='1'B THEN
SUBSTR(STR,Nl+I,1)='0'BJ
ELSE
SUBSTR(STR,Nl + I, 1 ) = 'l'B;
END;
N1=2*N1;
END;
PUT EDIT (SUBSTRCSTR,1,N)) (SKIP.B);
73
END POSL;
125
10010110011010C1011010P11
DHENSIOi K(b0)
HEAD 1,1 a,::
1 MW’ATUi »I2)
K(1)=IA
L=1
2 4=L
DO 3 1 = 1,4
l=L + 1
K(L)=0
IF(K(I).EO.0)K(L)=1
IF(L.FQ.N)GO TG 4
3 CONTINUE
GO TO 2
4 PRINT 5, (л(I),1=1,N)
5 ЮкМАТ(5Х ,50 11 )
STOP
END
0110100
Рис. 3.1
3.2. Для любых положительных дробей A/В и С/Д (А/В < С/Д) дробь
(А + С)/(В + Д) удовлетворяет неравенствам А/В < (А + С)/(В + Д) < С/Д и
называется медиантой этих дробей. Выписывая несократимые дроби со
знаменателем, не большим Н (Н - номер строчки таблицы), в порядке
возрастания для заданных значений А, В, С, Дополучим таблицу рядов
Фарея. Каждая Н-я строчка таблицы (ряд Фарея) получается из (Н- 1)-й
по следующему правилу: нужно в (Н- 1)-й строке отметить все такие
пары соседних дробей А/В, С/Д, у которых сумма знаменателей равна Н,
и между ними вставить их медианты - дроби (А + С)/(В + Д). Например,
для А = 0 и В=С=Д=1 получим такую таблицу:
О 1
1 1
О 1 1
1 2 1
О 112 1
1 3 2 3 1
0 1112 3 1
1 4 3 2 3 4 1
Составить программу формирования и вывода на печать Н-й строчки
таблицы в форме несократимых дробей. Входная информация для про-
граммы размещена на одной перфокарте; в первой позиции - значение
А, во второй - В, в третьей - С, в четвертой - D, в пятой - Н.
Соответствующие программы решения данной задачи представлены
на рис. 3.2.
74
0 I MENS 10'1 M( 1 3fe. ) ,N(lu0)
HEAD 8,‘<(1) ,M1 ) ,M(2) ,Hz) ,NH
ft FOnMAT(5ll)
,\R=2
DO 6 K=2,Nh
1 = 1
ft IF (ЖЫСЫ),.^) uO TO 7
лИ=Чн+1
IS=I+2
NV=Nn-IS+l
DO 3 11=1,nV
M( jiF + l-Il )=M(Kh-Il )
3 h(NR+1-I1)=NCNh-Il)
M1=M<I)+M(1+2)
Nl=M(I)+*(1+2)
CALL SOKrt(Ml,N1,M2,N2)
M( 1 + 1 )=’<2
N(I+1)=N2
1 = 1+2
GO TO 1?
7 1=1+1
10 CONTINUE
IF (I-Nfc) 6,6,6
6 CONTINUE
PRINT 12,(M(I),h(D,I = l,NR)
12 F0nVATt2J(2X,Il,'/',Il))
STOP
END
SUBROUTINE SOKn(Ml ,?11 ,M2,N2)
M2=M1
N2=N1
1 K=M2-M2/42*N2
IF (K.EQ.0) GO TO 2
M2 = M2
K2=K
GO TO 1
2 M2=M1/U2
N2=N1/M2
hETUhN
END
0/1 1/3 1/2 2/3 1/1
♦PROCESS F(I);
Z3:Ph0C OPTIONSCMAlh);
DCL (CH,ZH)(267) Six FIXED(15);
GET FDIT(CH(1),ZH(1),CH(2),ZH(29,N)(F( 1 ));
NUM=2;
DO 1=1 TO N;
DO J=1 TO 257 JHILE(J<NUM);
IF ZH( J)+ZHU+1 ) = I THtN DO;
DO L=NU^ TO J+l BY -1;
ZH(L*1)=eH(L);
CH(L*1)=CH(L);
END;
NUM=NUM+1;
ZH(3+1)=ZH(J+2)+ZH(J);
CH(J+l)=CH(J+2)+CH(J);
J=J+1;
DO KK=ZH(J) TO 1 BY -1;
IF MOD(CH( J) ,KK)=0<*MOD(Zri( J) ,KK)=0 THEN DO;
CH(J)=CH(J)/KK;
75
ZH(J)=ZH(J)/KK;
E MD;
END;
END;
EhD;
EnD;
PUT SKIP EDIT
('ЧИСЛИТЕЛЬ I ЗНАМЕНАТЕЛЬ',(CH(J),ZH(J)DO J = 1 TO .*Um))
(A(257 ) (SKIP,F(7),F(10)));
Е.ЧП Z3;
01114
ЧИСЛИТЕЛЬ ! ЗНАМЕНАТЕЛЬ
0 1
1 4
1 3
1 2
2 3
3 4
1 1
01233
ЧИСЛИТЕЛЬ ! ЗНАМЕНАТЕЛЬ
0 1
1 2
4 7
3 5
5 8
2 3
12347
ЧИСЛИТЕЛЬ I ЗНАМЕНАТЕЛЬ
1 2
2 3
5 7
3 4 Рис. 3.2
3.3. В (0,1)-матрице подсчитать число изолированных 0-о(5ластей, т. е.
областей, состоящих из одних нулей. Отметим, что 0-область может сос-
тоять только из одного нулевого элемента. Например, для (0,1)-матрицы
видаА5х5:
1 [о] 1|_0 О
1 1 1
ПГо"о]
1 0 1
1 0 1
1 О
1 О
1 О
1 О
число изолированных 0-областей равно 3.
На рис. 3.3 представлены соответствующие программы решения
данной задачи.
3.4. Ханойская башня. На стержне А в исходном порядке находится
N дисков, уменьшающихся по размеру снизу вверх. Диски должны быть
переставлены на стержень С в исходном порядке при использовании в
случае необходимости промежуточного стержня В для временного хра-
76
FLl.’PBOC option^ vA i.o ;
/* VAT-MATPHUA Данных ♦/
/* v- СЧЕТЧИК НУЛЬ-ОьЛАСТЕй */
/* РН-ПРОНЬДУРА УДАЛЕНИЯ НУЛЬ-ОБЛАСТЕР */
DCL М.АТ(10,10) Р IT (1 ) , (( 11 ,11 , J1 , J J ) BIN FIX ( 16 , J ) ,
Pn ENTRY (BIN F IXED(1b,0),В IN г I Xh.0 (1 6 , J ) ) ;
GET ED IT(МАТ)((1 С)D(1),SKIP);
М=J ;
по 1=1 то 1л;
DO 3=1 ТО 10;
IF ЛМАТ( I ,J) THEN DO;
М=М+1;
CALL Ph(I,J) ;
END;
END;END;PUT LIST(M);
PH:PrtOC(IP,JP) RECURSIVE;
DCL (IP,JP,L,IK,J К) BIN FIXED(15,0);
IK=IP;JK=JP;MAT(I ?.,JK)='1'B;
DO L=1 TO 6;
U = (L=2I L=3 ! L=4)=(L=6 I L=7 I L=d ); II=IF+I1;
J1=(L=11L=2iL=b)=(L=4IL=5IL=6);JJ=JK+J1;
IF I KI I I I>10 I J J<1 I J J>10 THEN GOTO NEXT;
IF "”ИАТ( I I , JJ) THEN CALL FR( II , JJ) ;
NEXT:END;
RETUHMEND; END;
DIMENSION ri(ll ,12)
DO 1 1=2,11
nFAD(5,2)(Л(I,J),J=2,11)
2 FOnMAT(lvIl)
1 CONTINUE
DO 3 1=1,11
K(l,l)=l
K(I,1)=1
5 K(I,12)=1
L = 1
N=O
11=2
С ПОИСК И РАЗМЕТКА НУЛЕВЫХ ОБЛАСТЕЙ
3 D0 4 1=11,11
DP! 4 J=2 , Il
IF(K(I,J).лЕ.0)GOTO 4
IF(K(I-1,J-1).EQ.1)GOTO 5
K(1,J)=K(1-1,J-l)
5 IF<F(I,J-l).EQ.l)GOTO 6
M=K(I,J-l)
IF < К U,J).nE.0.A ND.К(I,J).NЕ.M)GOTO 8
K(I,J)=M
6 IF(K(I-1,J).EC.1)GOTO 10
M=K(I-1,J)
IF(KU , J ) , NE , И . A ND . К ( I , J ) . NE . M ) GOTO 6
K( I ,J)=M
10 IF(K(1-1,J+l),cQ.1)GOTO 11
M=K(1-1,J+l)
IF(K(I,J).uE.0.AND.K(I,J).NE.M)GOTO 8
K(I,J)=M
11 IFlKU, J).*E.0)GOTO 4
N = N+1
L=L+1
K( I, J) = L
4 CONTINUE
GOTO 12
77
С СЛИЯНИЕ ДВУУ НУЛЕВЫХ ОБЛАСТЕЙ В ОЛНУ
6 M = N-1
M1=K(I,J)
11=1
DO 7 1=2,11
DO 7 J=2,ll
IF<K<I,J).EO.M)K(I,J)=dl
7 CONTINUE
GOTO 9
12 РЯН’Т 13,N
13 r'OhMAT(It)
STOC
END
Рис. 3.3
нения дисков. В процессе перестановки дисков обязательно должны
соблюдаться правила: одновременно может быть переставлен только
один самый верхний диск (с одного из стержней на другой); ни в какой
момент времени диск не может находиться на другом диске меньшего
размера.
Программы, которые для произвольного числа дисков N позволят
получить последовательность перемещений дисков, представлены на
рис. 3.4.
♦PROCESS F(I) LINE 0FTC2);
MOV:PROC(Al,В1,Cl,N) RECURSIVE REORDER;
DCL 1 Al CONNECTED,
2 NUMA CHAR(l),
2 KOLA DIN FIXEDC15),
2 AC*) BIN FIXEDC15),
1 Bl CONNECTED,
2 NUMB CHARC1),
2 KOLB BIN FIXEDC15),
2 BC*) BIN FIXEDC15).
1 Cl CONNECTED,
2 NUMC CHAR(l),
2 KOLC BIN FIXEDC15),
2 GC*) BIN FIXEDC15),
G CHARC50),
HBOUND BULTIN,
SUBSTR BUILTIN,
LBOUND BUILTIN,
REPEAT BUILTIN,
I.W,J,К
SYSPRINT FILE;
IF N>1 THEN DO;
J=N—1;
CALL M0V(Al,C1,B1,J);
PUT SKIP EDITCA(KOLA),”:C ',NUMA,r-rO HA ',NUMC,'-И')(F(3),Cb)A);
KOLC=KOLC+1;C(KOLC) = A(KOLA);AC KOLA) = 0}KOLA = KOLA-1;
CALL PUT;
CALL MOVCB1,Al,C1,J);
END;
IF N=1 THEN DO;
PUT SKIP EDITCACKOLA),r:C *,NUMA,'-rO HA '.NUMC,'-И')CFC3),C5)A);
KOLC=KOLC*1;CCKOLC)=ACKOLA);AC KOLA)=0;KOLA = FOLA“1;
CALL PUT;
END;
78
RETURN;
PUTjPkOU REORDER;
DCL n СНАк(Ь0);
DO I=HBOUND(A,1) TG LBOUND(A,1) ВУ -1 J
S£LECT(nUHAI InUmBI InUMC);
WHEh(r123') DO; SUBSTK(R,1) =SUBSTR(REFEATC,A(I)),2);
SUBSThC h., 15 )=SUBSTR( REPEAT ( ', В( I ) ) ,2 ) ;
SbBoTR(H,30)®dUBSTK(REPEAT(,C(1)),2);
END;
WHE«('132r) DO; SUBSTn(H.l) =SUBSTR(REPEAT(,A(I)),2);
SUBbTh(R,15)=SUBSTR(REPEAT(,С(I)),2);
SUBSTk(K,30)=SUBSTR(KEPEAT('-',B(I)),2);
END;
WHEh(r213r) DO; SUBSTK(k,1) =SUBSTR(REP£AT('-',B(I)),2);
SUBSTk(K,15)=bUBSTR(REPEAT('-',A(I )),2);
SURSTk(rt,30)=SUBSTR(R£PEAT(,C(I)),2);
WHEN('231') DO; SUBSTR(R,1) =SUBSTR( REPEATC,C.( 1) ),2);
SUBSTk(k,15)=bUBSTR(REPEAT('-',л( I)) ,2);
SURSTn(K,30)=SUBSTR(REPEATC ,B(I)),2);
PhD;
END; .
*HFh('312') DO; SOBSTh(H,l) =SUESTR(REPEATCr»В(I)),2);
SUBSTh(h,15)=SUBSTR(F£PEAT(,C( I)) ,2);
SUBST ti( h, 30 )sSUBSTR( REPEATC ,A( I)) ,2);
END;
WHEN(r321') DO; SUBSTR(h,l) =SUBSTR(&EPEATC,C(I)),2);
SURSTK(K,15)=SUbSTR(REP£AT('-',d(I)),2;
SUB5Th(ft,30)=bUBSTR(KEPEAT(r->,A( I)),2);
EhD;
END;
PUT SKIP EDIT (R) (A);
END;
END;
END;
♦PROCESS F<I) LINE;
PERlPROC OFTIONS(MAIN);
DCL (PERE.PUT) ENTRY,
(I,L,M,J)SYSTEM,
SYSIN FILE,
О13РЬАУ('часло дисков-?,c,ha');
GET LIST(I,L,M);
DO J=1 TO 16;
PUT SKIP;
END;
CALL PUT(-L,I);
CALL PERE(I,L,M);
END PER;
♦PROCESS F(I) line;
PERE:PROC(I,L,M) RECURSIVE;
DCL (PERE,PUT) ENTRY,
(I,J,K,L,M) SYSTEM,
SYSPKINT file;
IF I>1 THEN DO;
J=I-1;K=6-L-M;N=1;
CALL PERE(J,L,K);
CALL PUT(L,M);
CALL PEREC J,K,*JI);
END;
END PERE;
7$
♦PROCESS F(I) LINE;
PUT:PROC(L.M);
DCL FPC22,80)CHARC1);
DCL FPCPC22)CHARC80)DFF FP;
DCL N(ll,3) static;
DCL CIF(10)CHAR(2)INIT('10','9','8','7','6','5','4','3',
'2','!');
DCL (I,JJ PIC'999' STATIC,J,K,L,M);
DCL SYSPRINT FILE;
DCL (SUBSTR,
ABS,
FIXED,
CHAR,
REPEAT)BUILTIN;
FP=' r.
IF L<0 THEN DO;
JJ=0;
NCli,*)=n;
N(11 , ABS(L) )=11—M;.
DO J=1 TO M;
NC10-M+J,ABS(L))=J;
END;
END;
ELSE DO;
JJ=JJ+1;
SUBSTRCFFCP(2),38,5)='-'!!JJ!!'-';
SUBSTRCFPCP(4),30,39)=
'ПЕРЕБРАСЫВАЕМ C '•!SUBSTRCCHARCL),9,1 )! !
' HA '!!SUBSTRCCHARCM),9,1);
N(11,M)=N(11,M)-1;
N(N(11,M),M) = N(N(11,L),L ) ;
N(11,L)=N(11,L)+1;
END;
DO 1=1 TO 3;
DO J=N(11,1) TO 10;
SUBSTRCFPCPC J+9),23*1-20,2)=CIF(J) ;
SUBSTRCFPCPC J + 9),23*1-8—N(J,I),22) = REPEATC'-',NCJ,I)*2);
END;
DO J=10 TO 20;
FP( J,23*1-8) = '!';
END;
END;
SUBSTRC FPCPC 20) , 4,70 ) = HEPE’AT( ' 0 ' ! ! ( 22 )' = ' , 2 ) I ! '0 ' ;
fpC*,1)='*';
FPC*,80)='*';
FP(1,*)='♦';
FPC22,♦)='*';
PUT EDIT(FP)CSKIP,80 A);
END PUT;
ЧИСЛО ДИСКОВ-?,C,HA
80
а к. 5901.
81
♦ I I I ♦
♦ 3 1----------- I I *
* 2 1----------- I I *
♦----------1 --------1-1 —I— 1 -I- ♦
* 0====^=========0=============0=============0 ♦
* ♦
^♦♦♦♦^♦♦♦♦♦♦♦♦♦♦********************************
•005—
ПЕРЕБРАСЫВАЕМ C 2 HA 1
82
83
84
85
* *
* *
* *
♦ I I I ♦
* I I I ♦
* I I I *
* I I I ж
♦ I I I *
* I I I *
* I I I ♦
* I I I *
* 2 ——• 1 <-»_ 2 ! I ж
♦ 4с 1 0= 1 ! ! -I-
* ж
4сЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖ*ЖЖЖЖЖЖЖЖЖЖЖЖЖ*ЖЖЖ**ЖЖЖЖ*Ж
86
♦ I I I *
* i 2 —I------ 2 —I— *
**************************************************
* -019- *
* ♦
* ПЕРЕБРАСЫВАЕМ C 1 HA 3 *
* *
* *
* *
♦ *
♦ *
* I I I ♦
* I I I *
* I I I *
* I I I ♦
* I I I ♦
* I I I ♦
* I I I *
* I I 3 -I- *
* I 2 j —_ 2 —- j —— ♦
♦ I 1 —r—— I 1 j *
♦ 0 = = = = = = = = = = = = = =:0 = = = ===== = = = = = 0 = === = ====== = = 0 *
* *
**************************************************
**************************************************
* -020- *
* *
* ПЕРЕБРАСЫВАЕМ C 2 HA 1 *
♦I 13 -I- ♦
♦ I 12 —I— *
**************************************************
* -021- ♦
♦ *
♦ ПЕРЕБРАСЫВАЕМ C 3 HA 2 ♦
* *
* *
♦ *
♦ *
♦ *
88
ж I I I ж
* I I I ж
* I I I ж
* I I I ж
♦ I I I ж
* I I I ж
♦ I I I ж
♦ I I I ж
♦ I 2 -I- 2 —I — ж
♦ 1 ♦ 0==: —— I 1 1 ж
Ж ж
ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж
89
*************** ******** **************** ***********
*
*
♦
*
*
*
*
*
*
*
*
*
*
*
♦
*
*
*
♦
♦
3
2
1
0
-024- *
♦
ПЕРЕБРАСЫВАЕМ С 2 НА 3 *
♦
♦
*
*
*
I I I *
I I I *
I I I *
I I I *
I I I ♦
I I I ♦
I I I *
-I- I I ♦
—I— I. 2 ------1-----*
----1 j j-------j------ *
:==========0=============0=============0 ♦
♦
**************************************************
**************************************************
*
*
♦
*
*
♦
*
♦
*
♦
♦
*
*
*
♦
♦
*
♦
*
*
*
*
—025—
ПЕРЕБРАСЫВАЕМ С
I I
I I
I I
I I
I I
I I
I I
I I
2 —I— I
1 —-I——. j
0==============0=======;
1 НА 3 ♦
*
*
♦
*
*
I *
I ♦
I *
I *
I *
I *
I *
3 -I- *
2--------1---------*
:===0=============0 *
*
**************************************************
**************************************************
♦ -026- ♦
♦ *
* ПЕРЕБРАСЫВАЕМ С 1 НА 2 *
* ♦
* ♦
♦ ♦
* *
* *
♦ I I I ♦
♦ I I I *
♦ I I I ♦
* I I I *
♦ I I I ♦
♦ I I I *
♦ I I I ♦
90
♦ I I 3 -I- *
♦ I 12-----------1----*
♦ t -1-j — I — 1------1----*
♦ 0===2==========0=============0=============0 ♦
* *
*♦♦♦**♦*♦***♦*♦*♦♦*♦****♦*♦♦♦***♦*♦*♦*♦♦**♦*♦**♦♦♦
**************************************************
* -027- *
* *
* ПЕРЕБРАСЫВАЕМ С 3 НА 2 *
* *
♦ ♦
* *
* ♦
♦ *
* I I I *
* I I I *
♦ I I I ♦
♦ I I I *
* I I I ♦
♦ I I I *
♦ I I I ♦
* I I I ♦
♦ I 2 -I- 2------1----- *
* t I t —I — 1------1----- *
♦ 0===========x==0====x==x=====0=============0 ♦
* *
**************************************************
**************************************************
♦ -028- ♦
♦ *
♦ ПЕРЕБРАСЫВАЕМ С 1 HA 3 *
♦ ♦
♦ *
♦ *
♦ *
♦ ♦
♦ I I I *
♦ I I I *
♦ I I I *
* 1 I I ♦
♦ I I I ♦
♦ I I I ♦
* I I I ♦
♦ I 13------------1------ *
* I 2 -I- 2-----1----- ♦
* i i —-I— 1-----1-----*
♦ 0==============0============x0=============0 *
* *
**************************************************
*******************************************ж******
—029—
ПЕРЕБРАСЫВАЕМ C 2 HA 1
*
*
*
♦
*
*
*
91
**************************************************
♦ -030- ♦
* *
♦ ПЕРЕБРАСЫВАЕМ С 2 НА 3 *
♦
*
*
♦
*
* I
* I
★ I
* I
* I
♦ I
* I
* I
♦ I
* 1 -I-
I
I
I
I
I
I 4
I 3
I 2
I 1
0== = ===== = = = = = 0
I *
I *
I *
— I--- ♦
——— J— *
* 0
**************************************************
♦ —031 — *
* *
♦ ПЕРЕБРАСЫВАЕМ С 1 НА 3 *
* ♦
♦ *
* *
* *
* *
* I I I *
♦ I I I *
* I I I *
♦ I I I ♦
* I I I ♦
♦ I I 5 — I — ♦
♦ I I 4 —— j —— *
* I I 3 —• j — ♦
♦ I I 2 —1 »j и *
* * I 0===== ==—: I 1 ———-1 — *
* ♦
**************************************************
Рис. 3.4
92
3.5. Постройте алгоритм, генерирующий кольцо из 2П цифр (нулей и
единиц), в котором каждая последовательность встречается только
один раз (п я 8).
Соответствующие программы решения данной задачи и результаты
выполнения программ представлены на рис. 3.5.
*PROUESS F(l) Lli.E;
KOD:PHOC OFTIONS(MAIn);
DCL СЧ ,?I)(*)CTL;
DCL (I , К К , J , J J , 11 , 12,1 d , N , N* , N aa t и , L) S i S Г E>.,
(MOD,
UNSPEC,
SIGN,
ALL,
ANtf ,
SUBSTR,
FIXED)cUI LiEN ,
(SYS IN,SYSPRI NT)FILE;
DO KK=1 BY 1;
DISPLAY('ВВОД N');
GET LIST(N);
IF N> = 15 THEN LEAVE;
NM=2**N;NM«=2**(N-l);
ALLOC МЮ«),>.(ьХ);
J, I=O;M1=3; 13=2;
DO JJ=1 BY 1;
IF N<=0 THEN LEAVE;
DO K=1 TO № UnTIL(J=1);
I=voD(I* I,+ IX ED(I/Ими);
M(K)=1;
END;
DO 11 = 1 TO Na л H I LE ( MOD (Ml ( 11 ) , N a* )"*=F IXED ( M ( 1 )/2 ) ) ;
END;
DO 12=13-2 TO 11*1 BY -1;
Ml( I2*K)=M1(12);
EwD;
DO L=1 TO K;
Ml(I1+L)=M(L);
END;
13 = 13*K;
DO J=0 TO N»-l aHILE(ANy(M1=J)!aLL(m1",=J-SIGN(MOD( J,2)-0,5))) ;
EnD;
I = J;
J=J/2*(1-MOD(J,2))*nAA;
IF i>xx-l THEN LEAVE;
ELSE I = J;
END;
PUT SKIP EDIT((SUBSTK(UNSPEC(M1(I)),16,1)DO 1=1 TO N«))(b);
END;
FREE M,M1 ;
END WOO;
ВВОД N
4
0101101001111000
ВВОД N
5
01001101100101011101000111110000
93
ВВОД N
в
01000111101110000100100110110110010010111011310001001111 10110000
0101001110101100010101011010101001010111101010000101100110100110
1011011101001000101111110100000011000111001110001100111100110000
110101110010100011011111001000001110111100010000111111110000000
Рис. 3.5
3.6. Задана матрица отношений R размера (пхп). Постройте алгоритм,
вычисляющий натуральные числа Xj и y^fi, j = такие, что
Xj < ур если Rij „меньше”;
xj = ур если Rij „равно”;
Xi > yj, если Rij „больше” .
Программы решения данной задачи и результаты выполнения про-
грамм представлены на рис. 3.6.
RELA.’PROC options(main) ;
DCL STR CHAR(*)CTL;
DCL (N,I,J)SYSTEM;
DCL SS(-1:1)CHaR(1)INIT(;
DCL (XM,XMA)BIN FIXED(15);
DCL (SYSIN,SYSPRINT)FILE;
DCL (REPEAT,
ONSOURCE,
ONCHAR,
SUBSTR,
STRING,
INDEX,
SUM,
SIGN,
ALL,
MAX,
MIN,
ANYjBUILTlN;
DCL (A(♦,♦),X(♦),Y(*))BIN FIXED CTL;
DO WHILE C'l'B);
ON CONV BEGIN;
IF ONSOURCE='HX' THEN GOTO END;
ONCHAR='0';
GOTO S;
END;
S:DISPLAY('ENTER DIMENSION*);
GET LIST(N);
IF N<=0 THEN GOTO S;
ALLOC STR CHAR(N),X(N),Y(N),A(N,N);
DO 1=1 TO N;
DISPLAY('ENTER STRING NUMBER'!!I)REPLYCSTR);
IF STR='HX' THEN GOTO END;
DO J=1 TO N;
A(I,J)=INDEX(STRING(SS),SUBSTR(STR,J,l))-2;
END;
X(I)=SUM(A(I,*))*1*N;
94
IF ANY(A(I2) THEN DO;
DISPLAY('REENTER');
END;
END;
DO 1=1 TO N;
XM,XMA=1;
do J=1 то :m;
SELECT(A(J,I));
;VHbN( 0) LEAVE;
WHEN(-l) IF X(XM )<X(J) THc.N X.M =J;
WHEN( 1) IF X(XMA)>X(J) THtN XMA=J;
END;
END;
select;
WHEN(J<=N) Y(I)=X(J);
WHEN(XM n=lJ!(XM=1«A(XM ,I)=-l))Y(I)=X(XM )+l;
WHEN(XMAn=lI(XMA=1»A(XMA,I) =1))Y(I) = X(X”A)-l;
END;
END;
DO 1=1 TO N;
IF ANY(SIGN(X(I)=Y(*))Л=А(I»♦)) THEN DO;
DISPLAY('THE RELATION ARRAY CONTAINS CONFLICT ITEMS')
X(1)=0;
LEAVE;
END;
END;
IF X(l)n=0 THEN
PUT SKIP EDIT
(' !'»Y, REPEAT ('---' ,.i),
(X(I),'I',(SS(A(I,J))DO J=1 TO N)DO 1=1 TO N))
(SFIP, A,(N)F'ZZZ',SKIP,A,(N)(SKIP,PrZZ*,A,(N)(X(2),A)));
END;
ENDiPFEE A,STR,X,Y;
END KELA:
ENTER DIMENSION
8
ENTER STRING NUMBER 1
=<<<<<<<
ENTER STRING NUMBER 2
>=<<<<<<
ENTER STRING NUMBER 3
>>=<<<<<
ENTER STRING NUMBER 4
>>>=<<<<
ENTER STRING NUMBER 5
>>>>=<<<
ENTER STRING NUMBER 6
>>>»=<<
ENTER STRING NUMBER 7
>>»>>=<
ENTER STRING NUMBER 8
>>>»»=
1 2 4 6 8 10 12 14 16
2! = <<<<<<<
4! > = <<<<<<
95
6! >> = <<<<<
0! >>> = <<<<
10! >>>> = <<<
12! >>>>> = <<
14! > > > > > > = <
16! > > > > > > > =
Рис. 3.6
3.7. В системе координат X, Y заданы координаты вершин много-
угольника: массив координат X; массив координат Y; число вершин
многоугольника и координаты произвольной точки Q, Z. Определить:
1) номера вершин, для которых
Z(xi + yi)=Q*Z,ie[l,N]
(среди слагаемых каждая из вершин может встречаться только один
раз);
2) принадлежит ли точка Q, Z многоугольнику.
На рис. 3.7 представлены соответствующие программы решения дан-
ной задачи и результаты выполнения программ.
♦ PROCESS КГ) LINE;
TOC:i:PROC OFT IО NS (м A I N) ;
DOL (X(*),x(*))CTL,
<XT,*T,ALF,R,I,L,N)SYSTEM,
II BIN rIXED(ol),
F BIT,
IB (*)B1T CTL,
(MOD,
ATA ND,
STHInG,
SUM,
SUBSTft,
ANY,
FLOAT,
UNSPEC,
ABS ) BU 1 LT I a,
(SYSIN,SYSPRI NT) FILE,
DO W’HILE('l'B) ;
DISPLAYl'РАЗМЕРНОСТЬ');
GET L1ST(N);
IF N<0lN>32 THEN HETUKN;
ALLOC X ( N ) , Y ( N ) , IB ( N ) ;
DISPLAY('КООРДИНАТЫ ');
GET SKIP LIST((X(I),Y(I)DO 1=1 TO N));
DISPLAY('ТОЧКА ');
GET SKIP LIST(XT,YT);
DISPLAYS НАБОРЫ ТОЧЕК,ДЛЯ КОТОРЫХ ВЫПОЛНЯЕТСЯ УСЛОВИЕ');
DISPLAYS СУ ММА ( X (I) ♦ Y (I) ) =Х * Y ');
F='1'B;
ПО 11 = 1 ТО 2**N-1 ;
STRING(IB )=SUBSTR(UNSPEC(II),33=N,N);
IF SUM(X*Y*FLOAT(lb))=XT*YT THEN DO;
PUT SKIP EDIT((IB(I)*I DO 1=1 TO N))(P'ZZZ')
F='0'B;
END;
END;
96
IF F THEN DISPLAY(' ОТСУТСТВУЮТ');
X=X-XT;
/=Y-YT;
IF "4 ANY(X=0SY=0)) THEN DO;
ALF=0;
DO 1=1 TO N;
L=MOD(I, N) + l;
P=4OD(ATAND(X(I),Y(I))-ATAND(X(L),Y(L)),360) ;
SELECT;
WHEN(R-l80>1E~2)ALF=ALF+R-360;
WHEN(160-R>1£-2)ALF=ALF+R;
WHEN(ABS(R-l80)<=1F-2)DO;
ALF=360;
LEAVE;
END ;
END;
END;
IF ABS(ALF)>=10 THEN
DISPLAY ('ТОЧКА ПРИНАДЛЕЖИТ МНОГОУГОЛЬНИКУ');
ELSE
DISPLAY ('ТОЧКА HE ПРИНАДЛЕЖИТ МНОГОУГОЛЬНИКУ');
END;
ELSE DISPLAY ('ТОЧКА ПРИНАДЛЕЖИТ МНОГОУГОЛЬНИКУ');
FREE X,Y,IB;
END;
END TOCH;
РАЗМЕРНОСТЬ
4
КООРДИНАТЫ
0,0
0^1
1»0
1,1
ТОЧКА
0,5,0.5
НАБОРЫ ТОЧЕК ДЛЯ КОТОРЫХ ВЫПОЛНЯЕТСЯ УСЛОВИЕ
СУЧМА(Х(I)*Y(I))=Х * Y
ОТСУТСТВУЮТ
ТОЧКА ПРИНАДЛЕЖИТ МНОГОУГОЛЬНИКУ
РАЗМЕРНОСТЬ
3
КООРДИНАТЫ
1,0
0,1
0,’и
ТОЧКА
2,0
НАБОРЫ ТОЧЕК ДЛЯ КОТОРЫХ ВЫПОЛНЯЕТСЯ УСЛОВИЕ
СУММА(Х(I)*Y(I))=Х ♦ Y
7. Зак. 5901.
97
3
2
2 3
1
1 3
1 2
1 2 3
ТОЧКА НЕ ПРИНАДЛЕЖИТ МНОГОУГОЛЬНИКУ
Рис. 3.7
3.8. Составить программу расстановки восьми ферзей на шахматной
доске, при которой ни один ферзь не атакует другого (рис. 3.8).
3.9. Составить программу, позволяющую получить контур изобра-
жения и изображение по его контуру (рис. 3.9).
3.10. Составить программу формирования функциональной семанти-
ческой сети (рис. 3.10,3.11).
3.11. Составить программу, позволяющую найти объекты, обладаю-
щие требуемыми свойствами (рис. 3.12).
3.12. Составить программу планирования действий на функциональ-
ной семантической сети (рис. 3.13).
3.13. Составить программу сортировки массива данных произволь-
ного типа,
На рис. 3.14 приведены программы сортировки.
•PROCESS F(I) LINE;
SHESSlPROC OPTIONS(MAIN);
DCL CHESS(20)CHAR(32)INIT
('ABCDEFGH
' | *** *** 41** *** | * t
'61 *** ♦♦♦ ***
' I *** *** I' t
'7| *** *** **•* ***
' | *** *** ♦ t
'6! *** *♦* I',
' | *♦* *** *** I',
'51 ♦** *** ♦**
' | *** *** *** *** ।'t
'4| *** j*t
' | *** m ♦** *** | r t
*3! ♦** *♦* !',
' | *** ♦** m t
'2! ♦** *** **♦ j',
' | *** *♦* I't
'11 *** *** ♦**
' -------------------------- ')•
DCL (I,J,K) SYSTEM;
DCL PR“N BIN FIXED.( 15) INIT(4);
DCL SYSPRINT FILE;
DCL PR(20«4)CHAR(32);
DCL F(8) BIN FIXED(15);
DCL (SUBSTR,
kOD) BUILTIN;
DCL L(8)INIT((8)1),
98
DI(~7;7) BIT(l),
D0(-7;7) BIT(l),
R0W(8) BIT(l);
DO WHILE('1'В);
di ,D0='i rB; m=n 'в;
DO 1=1 TO 8;
K=0;
DO J=1 TO L(I);
DO K=K+1 TO 8 WHILE(n(ROW<
END;
END;
IF K< = 8 THEN DO;
ROW(K)='0'B;
d i ( i=k)='0'-b;
do((9-i)-k)='0'B;
F(I)=K;
END;
ELSE LEAVE;
END;
IF 1=9 THEN DO;
PR~N=MOD(PR-N,4)+1;
PR(*,PR-N)=CHESS;
DO K=1 TO 8;
SUBSTR( PR( K+K+l , PR'
SUBSTR( PR( K+K+2, PR'
END;
IF PR~N=4 THEN PUT
END;
DO 1=1 TO 8;
L(I)=L(I) + f;
IF L(I)<=9—I THEN LEAVE;
ELSE L(I)=1;
END;
IF 1=9 THEN RETURN;
END;
END SHESS;
ABCDEFGH
I *** Q *** *** *** I
81 ***OOO*** *** ★** I
I *** **♦ ♦♦* *0* I
71 *** *** *♦* ООО j
I *0* **♦ *** *** I
61 000 ♦** *♦♦ *** I
I *** *** *♦* *** 0 I
51 *** *** *** ***000 I
I *** *** *c* *** I
41 *** *** qqq *** j
I *** *** о *** *♦* I
31 *** ***000*** *** I
I 0 *** *** *** ♦♦* I
21 OQO*** *** *** *** I
I *** *** *o* ♦*♦ I
11 *♦* *** ООО ♦** I
I (I-K)8D0( (9H )—K)));
’N) ,F(K)*3+2,1)= r0r ,
’N),F(K)*3*1,3) = '000';
ABCDEFGH
I *** *** о *★*• *** I
81 ♦*♦ ***000*** ♦** I
I *** *** *** *o* I
71 *** «** *** ООО I
I 0 *** *** *** **♦ I
61 000*** *** ♦** *** I
I *** *** о *★* ♦** I
51 *** ***qoo*** *** I
I *Q* *** *** **♦ I
41 000 *♦♦ *** *** I
I *** *** jc** ♦** о I
31 *** «** *** ***000 I
I *** *** *0* *** I
21 *** *** ООО ♦** I
I *** *o* ♦** *** t
11 **♦ ООО *** *** I
ABCDEFGH
I **♦ о *** *** *** I
81 ***000*** *** *** I
I *** *** *** о *** I
ABCDEFGH
I *** *0* *** *** I
81 *** ООО **♦ ♦** I
I *** о *** *** *** I
99
71 *жж *жж жжжОООжж* I 71 *ж*000*** жж* ЖЖ* I
I *0* *** **ж **♦ I I *жж жжж жжж 0 жжж I
61 000 жжж *ж* **♦ I 61 жжж жжж жжжоООжжж I
I ♦ *♦ *** *Q* ж** I I жж* *0* жжж жжж I
51 ЖЖЖ ♦♦ж 000 *ж* I 51 ♦** 000 ЖЖЖ ЖЖЖ I
I *** жж* *** *0* I I *** жжж жо* жжж I
41 Жж* жж* ж** 000 I 41 *** *жж 000 ♦*♦ I
I ♦ 0* *жж *** жжж I I жж* **ж жжж жжж о I
31 000 жжж **♦ ♦** I 31 ЖЖЖ ЖЖЖ жжж жжжООО I
I *** *** жжж 0 ж** I I жжж жжж 0 жжж жжж I
21 *** жжж жжжОООЖ** I 21 ж*ж жжжоООжжж жжж I
I жжж жж* 0 *** *жж I I Ж0Ж жжж жжж жжж I
1 I жжж ***000*** *** I 1 I 000 жжж жжж жжж I
Рис. 3.8
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
’ПОЛУЧЕНИЕ КОНТУРА ИЗОБРАЖЕНИЯ И ИЗОБРАЖЕНИЯ ПО ЕГО КОНТУРУ
DIM PCTR (17,51),GOR(17,51),VERT(17,51)
’ ВВОД ИЗОБРАЖЕНИЯ
FOR М=1 ТО 16
FOR N=1 ТО 50
READ PCTR(M.N)
IF PCTR(M,Nj = l THEN MD$=,’*,‘ ELSE MD$=" "
ST$=ST$+MD$
NEXT N
PRINT STS : ST$=U"
NEXT M
M=17
FOR N=1 TO 51
PCTR(M,N)-0
NEXT N
N=51
FOR M=1 TO 17
PCTR(M,N)=0
NEXT M
' ПОЛУЧЕНИЕ КОНТУРА ИЗОБРАЖЕНИЯ
FOR М=1 TO 16
FOR N=1 TO 50
IF PCTR(M,N)=1 THEN IF FLAG=0 THEN FLAG=1:GOR(M,N)=1
240
250
260
270
ELSE GOR(M.N)=0
ELSE IF FLAG=1 THEN GOR(M,N-l)=1:FLAG=0
ELSE GOR(M,N)=0
50
16
280
290
300
310
NEXT N,M
FOR N=1 TO
FOR M=1 TO _
IF PCTR(M,N)=1 THEN IF FLAG=0 THEN VERT(M,N)=l:FLAG=1)
ELSE VERT(M,N)=0
ELSE IF FLa6=1 T’—.......................
ELSE......... ~
NEXT M.N
FOR M=1 TO
FOR N=1 TO
IF GOR(M,N)=0
16
50
_ _______ THEN VERT(M-1,N)=1:FLAG=0
VERT(M,N)=0
IF VERT(M,N)=0 THEN PCTR(M,N)=0
PCTR(M,N)=1
320
330
340
350
360
370
380
390
400
THEN 1. ____
ELSE PCTR(M,ti)=.
ELSE PCTR(M,N)=1
IF VERT(M,N)=1 THEN MD$="^" ELSE MD$=" "
J. Г УДДЦП.И
ST$=ST$+Mt>$
NEXT N
PRINT ST$: ST$=""
NEXT M
’ПОЛУЧЕНИЕ ИЗОБРАЖЕНИЯ
16
50
410
420
430
440
FOR M=1 TO
FOR N-l TO _
IF PCTR(M,N)=1 THEN IF
ELSE GOR(M,N)=1:
FLAG=1: EL&E IF FLAG=1
NEXT N.M
FOR N=1 TO 50
ПО ЕГО КОНТУРУ (ВОССТАНОВЛЕНИЕ ИСХОДНОГО
ИЗОБРАЖЕНИЯ)
FLAG=1 THEN FLAG=0:GOR(M,N)-1
THEN GOR(M,N)=1: ELSE GOR(M,N)=0
FOR M=1 TO 16
IF PCTR(M,N)=1 THEN IF FLAG=1 THEN FLAG=0:
VERT(M,b))=l ELSE VERT(M,N) = 1: FLAG=1:
ELSE ifr FLAG-1 THEN VERt(M,N)=1 : ELSE VERT(M,N)=0
NEXT M,N
450
100
460
470
480
490
500
510
520
530
540
FOR M=1 TO 16
FOR N=1 TO 50
IF GOR(M,N)=1 THEN IF VERT(M,N)=1 THEN PCTR(M,N)=1
ELSE PCTR(M,N}=0
IF PCTR(M.N)=1 THEN
ST$=ST$+Mt)$
NEXT N
PRINT STS
NEXT M
END
ELSE PCTR(M,N)=l
ELSE PCTR(M.N)=0
tutpkj ELSE MD$="
ST$:
1000
1010
1020
1030
1040
1050
1060
1070
1080
1090
1100
1110
1120
изо
1140
1150
1160
1170
1180
1190
1200
1210
1220
1230
1240
1250
1260
1270
1280
1290
1300
1310
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
о
о
о
о
о
о
1
о
о
о
о
о
о
о
о
о
о
о
о
о
о
1
о
1
о
1
о
о
о
о
о
о
0
О
О
О
1
1
1
1
О
1
О
1
О
О
О
О
О
о
о
1
о
1
о
1
о
1
о
1
о
о
1
о
о
о
1
1
1
1
о
1
о
1
о
1
о
1
о
о
о
1
о
1
о
1
о
1
о
1
о
1
о
1
1
о
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,0
1,1
1,0
1,1
1,0
1,1
1,1
1,1
1,1
1,1
1,1
1,1
0,0
1,1
0,0
1,1
0,0
1,1
0,0
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
0,0
1,1
0,0
1,1
0,0
1,1
1,1
1,1
1,1
1,1
1,1
1,1
0.0
1,1
0,0
1,1
0,0
1,1
0,0
1,1
1,1
1,1
1,1
1,1
1,1
1,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0
111,0,00,0,0,0,0,1,1,1,1,1,1,1
1,0,0,0,0.1,1,1,1,1,1,1,1,1,0,0,0
1,11,1,0,0,0,0,0,1,1,1,1,1,1,1,1
1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0
1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1
1,0,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0
0,0,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1
1,0,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0
0,0,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1
1,0,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0
0,0,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1
1,0,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0
4 4 ’ 4 00,0,0,1,1,1,0,0,0,0,0,1
1,1,1,0,0,0,0,0,1,1,1,0,0
00,0,0,1,1,1,0,0,0,0,0,1
0,1,1,1,1,1,1,1,1,1,1,0,0
00,0,0,0,1,1,1,1,1,1,1,1
0,0,0,0,0,0,0,0,1,1,1,0,0
10,0,0,0,0,0,0,0,0,0,0,1
00,0,0,0,0,0,0,1,1,1,0,0
11,0,0,0,0,0,0,0.0,0,0,1
0,0,0,0,0,0,0,0,1,1,1,0,0
1,1,0,0,0,0,0,0,0,0,0,0,1
0,0,0,0,0,0,0,0,1,1,1,0,0
1,1,0,0,0,0,0,0,0,0,0,0,1
1,1,1,0,0,0,0,0,1,1,1,0,0
10 0 0 1,1,1,0,0,0,0,0,1
0,1,1,1,0,0,0,1,1,1,0,0,0
0,0,0,0,0,1,1,1,0,0,0,1,1
0,0,1,1,1,1,1,1,1,0,0,0,0
1, 1,1,1
1,0,0,0
1,1,1,0
1,0,0,0
1,1,1,1
1,0,0,0
0,0,0,1
1,0,0,0
0,0,0,1
1,0,0,0
0,0,0,1
1,0,0,0
0,0,0,1
1,0,0,0
1,1,1,1
1,0,0,0
1,1,1,1
1,1,1,0
1,1,1,0
0,0
1,0
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,1
1,0
6,’ 6,’ 6,’ 6,’ 661,’ 11,’ 1,’ 1,’ 1,’ 1,0,0
***** ******* ******* *******
****** ********* ********* *********
******* *********** *********** ***********
** ***** *** *** *** *** *** ***
***** *** *** *** *** *** ***
***** *** *** *** *** *** ***
***** *** *** ********* *** ***
***** *** *** ******* *** ***
***** ********** ********* **********
***** *** ** ** ***
***** *★* *** *** ***
***** *** *** *** ***
***** *** *** *** ***
***** *** *** *********** *** ***
***** *** *** ********* *** ***
********* ******* ******* ******
***** ******* ******* *******
* * * * * * * *
** * * * * * * *
** * * * * * * * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * * * * * * * *
* * * * * * ********* * * * *
* * * * * * * * * * * *
* * ********** ********* **********
* * * * ** ** * *
* * * * * * ♦ * * *
* * * * * * * * * *
* * * * * * * * * *
* * *** * * *********** *** * *
* * *
*******
* * *
******
*
*********
*
*
*******
101
Рис» 3.10
? 3?
£££>£?
х— чо
♦PROCESS F(I) LINE 0PT(2);
SLAVA:PROC(MA ГМ) OPTIONS REORDER;
DCL BUF CHAR(80),
SYM(80) CHAR(80),
MACR(100,2) FIXED(16) INIT((200)1),
Ml(100) CHAR(31) INITC (100) ((31) " ) ) ,
OBJC100) CHAR(80) INIT((100)((80) " )) ,
RELC100) OHAR(80) INIT((100)((80) " )),
RUL(100) CHAR(1600)INIT((100)((1600) " )),
DATAU00) FIXED(IS) I NIT((100)0),
POISKU00) FIXED(16) INIT((100)0),
FU00.100) BIT(l) INIT((10000)’0'B),
VECTU00) FIXFD(2) INIT((100)1),
DIR(11,2) CHAR(10) INIT('INPUT ',’BBOH','PRINT', 'ПЕЧАТЬ','CLEAR','ОЧИСТКА', 'OBJECT','OB" EKT' , 'RELATION' , 'ОТНОШЕНИЯ','ROLL','ПРАВИЛА', 'DATA','ДАННЫЕ','FIND', 'HABTH'.’EKD'.'BCE', 'STOP','ОСТАНОВ','MACRO','МАКРО
(SUBSTR,
INDEX) BUILTIN,
N,12,IH,L,1B,
19,Il,I,K9,
(SUS IN,SYSPRINT) FILE;
GET EDIT(OBJ(1))(А(вИ))J
IF ОВД(1)='РУСС' THEN IH=2;
ELSE IHMJ
L,M=0+N,11 = 1;12=1;
ON CONV GOTO ere;
CONTINUE:
PUT SKIP EDIT('ВВОДИТЕ КОМАНДУ')(A);GET EDIT(BUF)(A(80));
CALL SCAN(BUF,SYM);
SELECT(SYMd));
WHEN(DIR(1,IH))DO;BR;SELECT(SYM(2));
WHEN(DIR(4,IH))DO;
IF SY‘4(3)=DIR(11, IH) THEN DO;
macr(ii,i)=L+1;
MACR(11,2)=L+SUBSTR(SYM(8),1,INDEX(SYM(5), ' '));
M1(U)=8YM(4);
11=11+1;
END;
ELSE DO;
IF SYM(3)*1=(80) r 'THEN DO;OBJ(SYM( 3))=SYM(4);
goto continue;
END;
END;
AL:PUT SKIP EDIT( 'ВВОДИТЕ ОБ"ЕКТЫ') (A);
GET EDIT(BUF)(A<80))JCALL SCAN(BUF,SYM);
DO 1 = 1 BY 1 W4ILE(SYM(I)л=(80)' ');
IF SYM(I)=DIR(9,IR) THEN DO;L=L+I-1;GO TO CONTINUE;END;
OBJ(L+1)=SYM(I);
END;L=L+I-1;GOTO AL;
END;
WHEN(0IR(5,IH)) DO;
BL:PUT EDIT('ВВОДИТЕ ОТНОИЁНИЯ')(A);
GET EDIT(BUF)(a(80))JCALL SCAN(BUF.SYM)J
DO 1=1 BY 1 WHlLE(SYM(I)-»=(80)' ');
IF SYM(I)=DIR(9,IH) THEN DO;M=M+I-1;GOTO CONTINUE;END J
REL(h+I)=8YM(I);
END;M=M+1-1;GO TO BL;
103
END;
WHEN(DIR(6,IH)) DO;PUT SKIP EDIT('ВВОДИТЕ ПРАВИЛА')(A);
GET EDIT(BUF)(A(80));
IF BUF=DIR(9,IH) THEN GO TO CONTINUE;
I=INDEX(BUF,'=')J
19 = INDEXCRUL(N),' ');
IF 19=1 THEN
IF 1=0 THEN RUL(N)=SUBSTR(BUF,1,INDEX(BUF,' '));
ELSE DO;
VECTCN)=SUBSTR(BUF,I+1,3);
RUL(N)=SUBSTR(BUF,1,1-1);N = N + 1;END;
ELSE
IF 1=0 THEN RUL(N)=SUBSTR(RUL(N),1,19-1)
! !SUBSTRCBUF,1,I NDEX(BUF,' '));
ELSE DO;
VECTCN)=SUBSTR(BUF,I+1,3);
RUL(N)=SUBSTR(RUL(N),1,19-1)!!
SUBSTRCBUF,1,1-1):N=N+1;END;
GOTO CL;
END;
OTHER GOTO ERE;
END BR;
END;
WHEN(DIR(2,IH)) VR:DO:DR:SELECTCSYM(2));
WHENCDIR(4,IH))DO;
X1:DO 1 = 1 BY WHI LE(OBJ( I )“’=(80) ' ');
IF SYM( 3 ) ”’= ( 80 ) ' '8SYM(3)"’=I THEN GOTO E;
X3:DO 19=1 TO 100;
IF MACR(19,1)<=I8MACR(19,2)>=I THEN GOTO V;
END X3;G0T0 Vl;
V:PUT SKIP LIST(SUBSTRCMl(I 9),1,I ND EX(OBJ( I) , ' ')+!),
SUBSTR(OBJ(I),1,INDEX(OBJ(I),' ')+!), I ) ;
GOTO E;
V1:PUT SKIP LIST(SUBSTRCOBJ( I),1,
к INDEX(OBJCI),' ')+!),!);
E:END Xi;
END;
WHEN(DIR(5,IH))DO:DO 1=1 BY 1 WHI LE( REL( I )’’=(80) ' ');
IF SYM( 3 ) “’=( 80 ) ' '8SYM(3)’*=I THEN GOTO El;
PUT SKIP LIST(SUBSTR(REL(I),1,INDEX(REL(I)<' ')+!),!);
El:END;
END;
WHEN(D I R( 6 , I H)) DO ; DO 1 = 1 BY 1 WHILE( RUL ( I ) "’=( 1 800) ' ');
IF SYM(3)“’=(80) ' '8SYM(3)’’=I THEN GOTO E2 ;
PUT SKIP LIST(SUBSTRCRUL(I),1,I ND EX(RUL(I),' ') + !),
VECTCI));
£2:END;
END;
OTHER DOjGOTO ERE;END;
END DR;
END VR;
WHENCDIRC3,IH))DO;OBJ,REL,Ml=(80)' ':L,M=0;Il,I2,N=1;
MACR=1;RUL=(1600)' ';END;
WHEN(DIR(7,IH))DO;K9 = l;GOT:GET ED IT(BUF)(A(80));
CALL SCANCBUF,SYM);
DO 18 = 1 BY 1 WHILECSYMC I8)”1=(80)' ');
IF SYMC18)=DIR(9,IH) THEN GOTO LDV;
DO 19=1 BY 1 WH I LE( OB J( I 9 )’’=(80 ) ' ');
IF OBJ(I9)=SYM(18) THEN GOTO AH;
END;
AH:DATAC18) = 19;
104
END;
GOTO GOT;
LDV:END;
WHEN(DIR(8,IH))DO;K9=l;DLG-:GET EDIT(BUF)(A(80)) ;
CALL SCAN(BUF,SYM);
DO 18 = 1 BY 1 ILE (S YM( 18) “’= (80 ) r ');
IF SYM(T8)=DIR(9,IH) THEN GOTO WP;
DO 19 = 1 BY 1 WHI LE(OB J( I 9) "•=( 80 ) ' ');
IF OBJ(I9)=SYM(18) THEN DO;GOT0 AVHjEND;
END;
AVH:POISK(18)=I9;
END;
GOTO DLG;
WPiGOTO exec;
END;
WHEN(DIR(10,IH)) GOTO 0;
OTHER GOTO ERE;
END;
GOTO CONTINUE;
EXECJDO 18=1 BY 1 WHILE(RUL(I8)n=(1600)' ');
K9=l;
LABElDO I9=K9 BY 1 WHILE(OBJ( I9)-»=(80)' ');
IF INDEX(RUL(18),SUBSTR(OBJ(19),1,INDEX(OBJ(19),' ')-l))“l=0
THEN GOTO rla;
END;
GOTO DE;
RLA:F(I8,I9)='1'B;K9=I9+1;GOTO LABE;
DE:END;
PUT SKIP ED*IT( ((F( 19,18) DO 18=1 TO 10)DO 19=1 TO 10))
((10)((10)B(3),SKIP));
CALL ALFA(F,DATA,POIJK);
goto continue;
ERE:PUT('ОШИБКА ВО ВХОДНОМ ТЕКСТЕ')(A);
GOTO CONTINUE;
ALFA:PROC(A,В,C);
DCL A(*,*> BIT(1),
B(*) FIXED(IB), >
C(* ) FIXEDU6);
RETURN;
END; •
SCAN!PROCtBUF,SYM);
DCL BUF VAR CHAR(80),SYM(*) CHAR(80),X CHAR(80);
SYM=(80)' ';
BUF=BUF!!' ';
DO 1=1 TO 80;IF SUBSTR(BUF,I,1)='.'!SUBSTR(BUF;I,1)='.'
THEN SUBSTR(BUF,I,1) = ' ';END;
DO 1=1 TO 80 WHILE(BUF“>=*’ ');
A:DO WHILE(INDEX(BUF,' ')=1!BUF=' ');
BUF=SUBSTR(BUF,2);
END a;
SYM(I)=SUBSTR(BUF,1,INDEX(BUF,' '));
BUF=SUBSTR(BUF,INDEXCBUF,' '));
END;
RETURN;
END SCAN;
0:; .
END SLAVA;
Рис. 3.11
. 8. Зак. 5901 t05
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
• 160
170
180
190
200
210
220'
230
240
250
260
• 270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
42Ю
430
440
450
460
470
480
490
’программа распознавания объектов по их признакам (свойствам)
М^13-^-9?ЫШ3)’ Р$(9)’ РВ0(13)
F1-1J- N-У • KbOlUXUL _ __. Л -г _
FOR 1=1 ТО 9: --
FOR 1=1 ТО 13
FOR 1=1 ТО 9: -
S=0: FOR 1=1 ТО
IF S=0 ----
IF S=1 __
‘ P=-l: FOR J=1 TO N
R=0
FOR 1 = 1 TO M
IF F(J,I)=1 AND PBO(I)=1 THEN R=R+1
NEXT I
IF R < S-R THEN RR=R ELSE RR=S-R
IF RR > P THEN K=J: P=RR
NEXT J
PRINT "Объекту X соответствует свойство " :K
PRINT ">";Р$(К);"<";ТАВ(35);"(Д/Н) INPUT А$
IF А$="Д" THEN ЙЬ=О ELSE NL=1
FOR 1=1 ТО И
•IF F(K,I)=NL THEN PBO(I)=0 ,
NEXT I
GOTO 70
PRINT “аналогов нет"
FOR 1=1 TO M
IF PBO(I)=1 THEN 300
NEXT I
PRINT "аналог - ”;O$(I)
END
’ Г 0,1 1 -матрица
DATA 1,0,1,0,0,0,0.0
DATA 0 1,0,1,0,0,1,0
DATA 0,0,0,0 4 * Л -
DATA 0,0,0,0
DATA 1,1,1,1
DATA 0,0,1,0
DATA 11,0,0
DATA 1,0,1,1
DATA 0,1,0,0
’ объекты :
DATA КЗШ1 .СЗШ2.КЗЦ1 ,C31 ,Ж4Ц2,С4Ц1
DATA Х32,14Ц1,^ЗШ2,д4Ш1,К41,дЗЦ1
’ признаки (свойства)
DATA "цвет красный ","цвет синий","цвет желтый"
DATA "состоит из 4 частей", "состоит из 3 частей"
DATA "имеет цилиндрические детали","имеет
DATA "весом отЗ до 10 кг","весом от 10 до
FOR J=1 TO 13: READ F(I,J): NEXT J: NEXT I
READ 0$(I): PBO(I)=1: ЙЕХТ I
READ P$(I): NEXT I
...____’О M; S=S+PBO(I): NEXT I
THEN 250
THEN 270
unin. и, и
DATA 1,1
1,1,0
1,1,1
0,0,0
1,0,1
0,1,0
0,1,1
1,0,0
1
0
1
0
0
0
1
0,1,0,1
0,0,1,0
10 0,0
1,0,1,1
O', 1, Q, 0
1,0,0,0
0,1,1,0
1,0,1,1
01,0,0
0
1
0
0
1
1
0
1
0
шаровидные детали
30 кг”
RUN
Объекту X соответствует
>состоит из 4 частей<
Объекту X соответствует
свойство
------ ------------, свойство
>цвет желтый <
Объекту X соответствует свойство
>имеет цилиндрические детали<
Объекту X соответствует двойство
>весом от 3 до 10 кг<
аналог - Ж4Ц2
₽К:
Объекту X соответствует свойство
>состоит из 4 частей<
Объекту X соответствует свойство
>цвет красный<
Объекту X соответствует свойство
>имеет цилиндрические детали<
Объекту X соответствует свойство
>весом от 3 до 10 кг<
аналог - КЗШ1
БЭЙСИК:
£Д/Н)
&Д/Н)
|д/Н>
(Д/Н)
(Д/Н)
£ДЛП
£Д/Н)
(Д/Н)
? д
?'д
? Д
? Н
? Н
? Д
? н
? д
RUN
Объекту X соответствует свойство
>состоит из 4 частей<
Объекту X соответствует свойство
>цвет красный<
Объекту X соответствует свойство
>весом от 3 до 10 кг<
£Д/Н) ? н
£Д/Н) ? н
(Д/Н) ? н
106
program prim22;
const
Объекту х соответствует
>цвет синий < X
аналог - СЗШ2
БЭЙСИК:
RUN
Объекту X соответствует
>состоит из 4 частей<
Объекту X соответствует
>цвет красный<
Объекту X соответствует _____
>имеет цилиндрические детали<
аналог - КЗЦ1
БЭЙСИК:
свойство
свойство
свойство
свойство
2
(Д/Н) ? Д
4
£Д/Н) ? Н
£Д/Н) ? Д-
(Д/Н) ?,Д
Н=9:
М=15;
OBJ .'array Г1: М1 of string[4]=
( ’КЗШ1*,ЬСЗШ2’,’КЗЦ1’,FC3I ’
__’Ж32 ’,’Ж4Ц1’,’КЗШ2* ’С4Ш1’
PRI: array [1..N1 of string[30]
( ’ЦВеТ КраСНЫЙ*,’ЦВеТ СИНИЙ’, цйсг дслгыл .
“Й* , ’состоит из 3 частей’,
(
F:
Ж4Ш1’.’С4Ц1*,
C3U1’J;
цвет к рас ный*,7 цвет” синий7 J, ’ цвет желтый ’ .
состоит из 4 частей’,’состоит из 3 частей’,
имеет цилиндрические детали’,’имеет шаровидные детали*,
arrayГ1..N
^’^’Г,0’,0
0,1.0
0,0,1
1,0,1
лиш1 ,
Ж32 ’,’Ж4Ц1
о!о,о
ОгО’,1
.„г------ детали’,’имеет шаровидны
до 10 кг’.’весом от 10 до 3Q кг');
1..Ml of 0..1-
0,0,0,1,0,1,0),
О
1
О
О
О
1 .’ojojo
);
var i,s, j, k, г, rr,p,nl*. integer;
PBO: arrayfl..M] of integer
ch:char;
function Summ :integer;
var i,sum:integer;
begin
?um:=0;
or i:=l to N do
л sum:ssum+PBO[i];
Summ:
end; {функции Sumi? } ;
•egin ^главца^программа}
while SurnmM do
begin
p:=-l; s:=Sunan ;
for j:=l to N do
begin
for 1:=1 to M do
if (F[j,i]=l) and (PBO[i]=l)
then r:=succ(r);
if. r<s-r
if rr>p .
then begin
k:=j; p:=rr
end
end; writeln(* объекту X соответствует свойство
write(PRI[kJ:30, (д/н)?’);
repeat
,k:2);
until ch in С’Д*,’Д’,'Н*,’н’];
writein(ch):
if ch in riS-A-J
then nl:=0
else nl:sl;
for i:=l to M do
if F[k,i]=nl then PBO[i]:=0
107
end;
if Summ =0 . 4
then write(’ аналогов нет*),
else begin
while not (PBO[i]=l) do
i:-succ(i);
write (* аналог - ’,OBJ[i])
end• '
end. {программы}
Рис. 3.12
DIM F(7j13),PBA(13),Pl(13),BBA(13),A$(13),P$(7),C(13)
DIM CC(i5),ЙЕТ$?2)
N=7: M=13: RESTORE „ ,
FOR - —- ’ ' — “
FOR
10
20
30
40
60. FOR 1=1 TO M: PBATlpO?'
70 FOR 1=1 TO N: READ P$£I)
80 INPUT "СКОЛЬКО НЕИЗВЕСТН
90 U=l: GOSUB 450
100------ ------ -------- ..
110
120
' 130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
330
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
N: FOR J=1 TO M: READ F(I,J): NEXT J: NEXT I
M: READ A$(I): NEXT I
“ PBAII1=O: Pl^=0: BBA(I)=0: C(I)=0: NEXT I
:тных ";NU.
PRINT"PRINT' "ЗАДАЧА : ":PRINT "ДАНО
FOR 1=1 TO M: IF PBA(I)?1 THEN PRINT
1=1
1 = 1
TO
TO
";A$(I);
PRINT "ЦЕЛЬ: УСТАНОВИТЬ, КАКОЕ ИЗДЕЛИЕ МОЖНО СОБРАТЬ"
PRINT
FF=0
’ИСХОДНЫЕ ДАННЫЕ ДЛЯ ПОДПРОГРАММЫ ГЕНЕРАЦИИ СОЧЕТАНИЙ
NC=2: МС=1: SETS(1)="И1": SET$(2)="H2"
FOR 1=1 ТО МС: CC(I)=I: NEXT I
’ ПРОВЕРКА СГЕНЕРИРОВАННОГО ВАРИАНТА
FOR 1 = 1 ТО “ — — т
FOR 1=1 ТО
NEXT Д
GOSUB 320
IF FLAGP=0 THEN 280
PRINT "МОЖНО СОБРАТЬ ИЗДЁЛИЕ ";SET$(СС(1)): FF=1
’ ВСЕ ВАРИАНТЫ СГЕНЕРИРОВАЛИ ?,
IF FLFGCO1 THEN GOSUB 790: GOTO 210
IF FF=0 THEN PRINT "ЗАДАЧА HE РЕШАЕТСЯ, НЕТ ТАКИХ ИЗДЕЛИЙ "
END
’ПРОГРАММА ПЛАНИРОВЩИКА, ПРЯМОЙ ХОД
L=0: FLAG1=-1
FOR J=1 TO N: S=0: FOR 1=1 TO M
IF F(J,I)=1 AND PBA(I)<>1 THEN S=S+1: B=I
NEXT I
IF SOI THEN 390
IF PBA(B)=-1 THEN L=1
PBA(B)=1: BBA(B)=J: FLAG1=1
IF LO1 THEN 416
GOSUB 550: IF S=0 THEN FLAGP=1: RETURN ’ПРОВЕРКА УДАЧНАЯ
NEXT J
IF FLAG1=1 THEN 320
FLAGP=0: ’ПРОВЕРКА НЕУДАЧНАЯ
RETURN
PRINT "ВВОДИТЕ - "
FOR K=1 TO NU
INPUT ">":M$: MM=0
FOR 1=1 Тб M
IF A$(I)=M$ THEN MM=I
NEXT I к • .
IF MM=0 THEN PRINT "ПдвТ.ВВОД GOTO 470
PBA(MM)=U: P1(MM)=U
NEXT К
RETURN
S=0: FOR 1=1 TO M
IF PBA(I)=-1 THEN S=S+1
NEXT I
RETURN
’ P'l]
DATA 1,1,-,-,____________
DATA 0,0,0,0,0,1,1,0,0,0,1
DATA 0,0,0,1,0,0,0,0,0/0,1
DATA 0,0,1,1,0,0,0,1,0,0,0
DATA 0,0,0,1,1,0,0,0,1,0,0
DATA...............------
DATA
’ОБЪЕКТЫ
________ J ВАННОГО ВАРИАНТА
M: PBA(I)=P1(I): NEXT I
M: IF SET$(CC(1))=A$(I) THEN PBA(I)=-1
МАТРИЦА
,0,0,0,0,1,0,0,0,0
0,0,0,1,1,0,0,0,1
0
0
0,0,0,0,0,0,1,1,1,0
0,0,0,0,l,0,0,0,l,0
0,0
0,0
1,0
0,0
0,0
0,0
0,1
108
рАТАА^1^2,ДЗ,Д4,Д5,Д6,У1,У2,УЗ,У4,У5,И1,И2
DATA " 1. СОЕДИНИТЬ Д1 И ~ --------- “
DATA " 2. СОЕДИНИТЬ У1 И
DATA " 3...............
DATA " 4.
DATA " 5.
DATA " 6........ ~ .. .
DATA " 7. СОЕДИНИТЬ У4 И Д6, ПОЛУЧИТЬ
’ПРОГРАММА ГЕНЕРАЦИИ СОЧЕТАНИЙ
’ПО М ЭЛЕМЕНТОВ ИЗ N
FOR IC=MC ТО 1 STEP -1
IF СС( IC) ONC-MC+IC THEN 830
NEXT IC
------- ------- ’КОНЕЦ ГЕНЕРАЦИИ
680
690
700
710
720
730
740
750
760
770
780
790
810 NEXf'tc"..... ’
820 FLAGC=0: RETURN ’КОНЕЦ ГЕНЕРАЦИИ
830 CC(IC)=CC(IC)+1
840 FOR JC=IC+1 TO MC: CC(JC)=CC(JC-1)+l: NEXT JC
850 FLAGC=1: RETURN ’ГЕНЕРАЦИЯ ЕЩЕ HE ЗАКОНЧИЛАСЬ
10 ]
20 1
30 ]
40 1
50 1
во :
70 1
во ;
90 I
100
110
120
130
- 140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
430
490
500
510
520
530
540
550
560
570
580
590
600
610
620
СОЕДИНИТЬ
СОЕДИНИТЬ
СОЕДИНИТЬ
СОЕДИНИТЬ
'2
12, ПОЛУЧИТЬ
;6, ПОЛУЧИТЬ
[4, ПОЛУЧИТЬ
.4, ПОЛУЧИТЬ
5, ПОЛУЧИТЬ
>3, ПОЛУЧИТЬ
У1"
У5"
И1"
У2"
УЗ”
У4"
И2"
’ГЕНЕРАЦИЯ ЕЩЕ HE ЗАКОНЧИЛАСЬ
DIM F^7^13)&PBA^13),P1(13),BBA(13),A$(13),P$(7),C(13)
FOR 1=1 TO NT FOR\j=l TO M: READ F(I,J): NEXT J: NEXT I
FOR 1=1 TO M:READ A$(I):PBA(I)=0:Pl(t)=0:BBA(I)=0:C(I)=i
FOR 1=1 TO N: READ P$(I): NEXT I
INPUT “СКОЛЬКО ИЗВЕСТНЫХ " ; NU
U=l: GOSUB 470
INPUT "СКОЛЬКО НЕИЗВЕСТНЫХ ";NU
U=-l: GOSUB 470
I PRINT: PRINT "ЗАДАЧА: ": PRINT "ДАНО":
* FOR 1=1 TO M: IF PBA(I)=1 THEN PRINT A
I NEXT I
I PRINT: PRINT "НАЙТИ
i FOR 1=1 TO M: IF PBA(lJ=-l THEN PRINT " ”;A$(I);
I NEXT I: PRINT
। L=0: FLAG1=-1
I FOR J=1 TO N: S=Q: FOR 1=1 M
I IF F(J,I)=1 AND PBA(I)O1 THEN S=S+1: B=I
I IFXS<>1 THEN 230
I IF PBA(B)=-1 THEN L=1
I PBA(B)=1: BBA(B)=J: FLAG1=1
> IF L<>1 THEN 250
I GOSUB 570: IF S=0 THEN 290.
I NEXT J
I IF FLAG1=1 THEN 160
> PRINT "НЕВОЗМОЖНО РЕШИТЬ ЗАДАЧУ"
I END
I U=0
> FOR 1=1 TO M: PBA(I)=P1(I): NEXT I
I FLAGl=0
) FOR 1=1 TO M: IF PBA(I)<>-1 THEN 380
» FLAG1=1: PBA(I)=1: J=BBA(I): P1(I)=1
I FOR K=1 TO M
) IF F(J,K)=1 AND PBA(K)=0 THEN Pl(K)=rl
J NEXT К
) U=U+1: C(U)=I
I NEXT I
) IF FLAG1=1 THEN 300
> FOR 1=1 TO U: P=C(I)
) PRINT "НЕИЗВ. ”;A$(P)
I H=BBA(P): PRINT PS(H)
) NEXT 1
I PRINT
) PRINT "ВЫВОД ОКОНЧЕН"
1 END
) PRINT "ВВОДИТЕ - "
) FOR K=1 TO NU
) INPUT M$: MM=0
I FOR 1=1 Тб M
) IF A$(I)=M$ THEN MM=I
I NEXT I
k IF MM=O THEN PRINT "ПОВТ.ВВОД ": GOTO 490
PBA^MM)=U: P1(MM)=U
RETURN
S=0: TOR 1=1 TO M
IF РЙА(1)=-1 THEN- S=S+1
NEXT I
RETURN
’ £0,13 - МАТРИЦА
DATA 1,1,0,0,0,0,1,0,0,0,0,0,0
ИЗ ПРАВИЛА "
A$(I);
: NEXT I
109
630
640
650
660
670
680
690
700
710
720
730
740
750
760
770
780
DATA 0,0,0,0,0,1,1,0,0,0,1,0,0
DATA 0,0,0,1,0,0,0,0,0,0,1,1,0
DATA 0,0,1,1,0,0,0,1,0,0,0,0,0
DATA 0,0,01,1,0,0,0,1,0,0,0,0
DATA 0,0,0,0,0,0,0,1,1,1,0,0,0
DATA 0,0,0,0,0,1,0,0,0,1,0,0,1
* ОБЪЕКТЫ *
DATA Д1,Д2,ДЗ,Д4,Д5,Д6,У1,У2,УЗ,У4,У5,И1,И2
’ ПРАВИЛА .. '
---- - J СОЕДИНИТЬ л vi
СОЕДИНИТЬ
СОЕДИНИТЬ
СОЕДИНИТЬ
СОЕДИНИТЬ
СОЕДИНИТЬ
СОЕДИНИТЬ
DATA " 1.
DATA ’’ 2.
DATA," 3.
DATA " 4.
DATA " 5.
DATA " 6.
DATA " 7.
У5
У4
И
И
и
и
и
и
и
Д2, ПОЛУЧИТЬ У1"
Д6, ПОЛУЧИТЬ У5“
Д4, ПОЛУЧИТЬ.И1"
Д4, ПОЛУЧИТЬ У2"
Д5, ПОЛУЧИТЬ УЗ"
УЗ, ПОЛУЧИТЬ У4"
Д6, ПОЛУЧИТЬ И2"
ПОЛУЧИТЬ У2"
СКОЛЬКО ИЗВЕСТНЫХ 4
ВВОДИТЕ -
а
СКОЛЬКО НЕИЗВЕСТНЫХ 1
ВВОДИТЕ -
>И1
(В ”2 " “
«НЕИЗВ. И1 ИЗ ПРАВИЛА
3. СОЕДИНИТЬ У5 И Д4,
НЕИЗВ. У5 ИЗ ПРАВИЛА
2. СОЕДИНИТЬ У1 И Д6,
НЕИЗВ. У1 ИЗ ПРАВИЛА
1. СОЕДИНИТЬ Д1 и Д2,
ВЫВОД ОКОНЧЕН
ПОЛУЧИТЬ И1
ПОЛУЧИТЬ У5
ПОЛУЧИТЬ У1
Рис. 3.13
program sort?
const max=1000; {максимальная размерность массива}
type
date=record {тип date определяется пользователем}
rl:real;
im:real;
end:
dim=array[l..max] of date;
var
al,a2: dim;
n,i : integer;
function comp(x,y: date):integer; {сравнение X и Y 1:>,-1:<»0:=.}
begin
if x.rl>y.rl then comp:=l
else comp:=-l; • . .
if x.rl=y.rl then comp:=0;
end;
procedure swap(var x,y:date); {обмен X и Y}
var t:date;
begin
end;
procedure quicksort(n: integer’; var a:dim); {сортировка"дробленией"}
const m=9; {последовательности длины < m выгоднее
сортировать прямым включением}
110
type, pointer=*stek;
stek=record
left,right:integer;
ptr:pointer;
end;
var
top,ntop :pointer; i
J.i,1,r,k,:integer;
flag :boolean;
procedure sis(l,r:integer); {сортировка прямым включением}
var b:date;
j:integer;
begin
tor j:=l+l to r do begin
>b)=l) and (i>=l) do begin
a[i^l1:=a{ij;
e&r'1;
a[i+l]:=b;
end;
end;
begin
{ n - количество элементов в массиве, n<=max}
{ аГ1] .. a[n] - сортируемый массив}
new(top); {заглушка стека}
top".left:=0:
top".right:-0; >
top*.ptr:=nil;
new(ntop^ {инициализация стека}
ntop".right:=n;.
ntop".ptr:=top;
< top:=nxop;
while nor (top74 .ptr=nil) do begin
1:=topA.left:
r:=top".right;
top:=top*.ptr;
whjle^r-l>=m do begin
^iag:=false;
’ repeat
while (compCafi],a[j])<=0) and (i<J) do j:=j-l;
if i=J then fiag:=true
else begin
swap(a[i] , a[ JI); j.
while(comp(a[ 1] ,a[ j j )<=0) and (i<j) do i:=i+l;
if i=j then flag:=true
else swap(a[i],a[j])
end ,
until flag=true;
new(ntop) j
if r-i<=i-l then begin
ntop".left:=i+l;
ntop*.right:=r;
ntop*.ptr:=top;
top:=ntop;
r;=i-l
end
else begin
ntop .left:=1:
ntop*.right:=i-l;
ntop*.ptr:=top;
top:=ntop;
l:=i+l
end
end:
sisfl,r);
end;
end;
procedure heapsort(n:integer;var a:dim): {сортировка
Построением пирамиды }
var j,i,n/: integer; 4
procedure heap(3,m:integer; var a:dim);
{постановка j-го элемента в пирамиде}
Ill 4
<0) or (comp(a[j],a[2*j+l])<0)) do
>0 then begin
begin л ,
while (m>=2*j+l) and
( (cotopW j] . a{2*
if comp(af2*jl,a[2*j+
swap(a[j]> a[2*jJ);
J:=2*j
end
else, begin x
swap(a[j],a[2*j+l]);
j:=2*j+i;
if (m=2*j) and (comp(a(j],a[2*j])<0) then swap(a[j],a[2*j])
end;
begin
m:=n tm - текущая размерность пирамиды}
for j:=i downto 1 do heap(j,m,a);
while m> = l do begin
swap(a[l],a[m]);
m:=m-l;
heap(l,m,a)
end;
end;
begin {ввод исходных данных}
writeln(’введите размер массива:);
readln(n);
writein(’исходный массив: );
writein; , . , »
for i:=l to n do beein
al[i].rl:=random*1000; .
al[iJ.im:=randpm*1000: ,
write(al[i].rl:4:0, ,,al[i].im.4•0,
if i mod 5 =0 then writein
end;
a2:=al;
quicksort(n,al);
writelnf’ Сортировка дроблением: отсортированный массив’);
writein; , .
for i i = l to n do beein . ,
write(al[i].rl:4:0,’ ,al[1].im:4:0, ),
if i mod 5 =0 then writein
end;
heapsort(n,a2);
writelnf’ Сортировка пирамиды: отсортированный массив’);
writein; •
for i:=l to n do begin , ЛГ., x л Л , ч.
write(a2(i].rl:4:U, ,a2[i].im:4•0, ),
if i mod 5 =0 then writein
end
end.
Сортировка массива данных
Введите рвзмер массива:
40
исходный массив:
0 31 861 203 273 672 319 162 372 426
82 475 71 841 60 - 293 917 368 775 328
698 844 718 307 163 329 466 247 826 . 279
482 149 .874 287 773 976 493 •888 827 20
141 144 501 22 593 10 774 651 770 708
558 206 681 593 955 644 998 ,244 676 296
86 772 495 882 510 573 953 685 339 8
705 989 774 750 198 144 914 784 589 865
Сортировка дроблением: отсортированный массив
0 31 60 293 71* 841 82 475 86 772
141 144 163 329 198 . 144 273 672 319 162
339 8 372 426 466 47 482 149 888
495 882 501 22 510 573 558 206 Зле 865
593 10 676 296 681 593 698 844 705 989
112
*718
775
914
307
328
784
770
826
917
708
279
368
774
861
955
750
203
644
774
874
998
244
Сортировка пирамиды:
отсортированный массив
Рис. 3.14
82
273
482
361
955
475
672
149
206
844
750
203
644
Задача для дальнейшего исследования
Рассмотрим некоторую функцию f, позволяющую нуме-
ровать все пары (Х1,Х2) из натурального ряда, а также
функции fi(Y) и f2<Y), которые по номеру Y пары
(Х1.Х2) дают её компоненты XI и Х2. В этом случае
граф' может быть представлен в виде вектора размернос-
ти М, где М - число рёбер в графе.
В качестве функции f можно использовать:
1) пеановскую функцию:
f(XI,Х2)=(Х1+Х2)(Х1+Х2+1)/2+Х1
XI Х2 1.
0 1 2 3 1
0 0 1 3 6 { . . . ।
1. 2 4 7
2 5 • в 8
3 9 . . .
2) N - функцию:
f(XI,X2)=N(X1-1)+X2 ,
где N - число вершин графа.
XI Х2
1 2 3 N
1 1 2 3 N
2 N+1 N+2 N+3 2N _____
9 9 9 ...
N. (N-DN+1 (N-DN+2 N*N
Разработать алгоритмы и программы решения различных
комбинаторных задач для случая машинного представления
графа в.предложенной Форме.
. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
1. Адельсон-Вельский Г. М., Диниц Б. А.,: Карзанов 4. В. Потоковые алгоритмы. М.:
Наука, 1975.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгорит-
мов. М.: Мир, 1979.
3. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.
4. Берж К. Теория графов и ее применение. М.: Изд-во иностр, лит.,1962.
З.БертзиссА. Структуры данных. М.: Статистика, 1974.
6. Ван Тассел Д. Стиль, разработка, эффективность и испытание программ. М.: Мир,
1981.
1. Вирт Н. Систематическое программирование. Введение. М.: Мир, 1977.
Ъ. ВиртН. Алгоритмы + структуры данных •« пррграммы. М.: Мир, 1986.
9. Гарднер М. Математические головоломки и развлечения. М.: Мир, 1971.
10. Грин Д, КнутД. Математические методы анализа алгоритмов. М.: Мир, 1987.
И. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир,
1981.
12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир,
1982.
13. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985.
14. Замбицкий Д. К., Лозовану Д. Д. Алгоритмы решения оптимизационных задач на
сетях. Кишинев: Штиинца, 1983.
15. Зыков А. А. Основы теории графов. М.: Наука, 1987.
16. Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. М.:
Наука, 1986. . ,
17. Кнут Д. Искусство программирования для ЭВМ. Т. 1.: Основные алгоритмы. М.:
Мир, 1976.
18. Липский В. Комбинаторика для программистов. М.: Мир, 1988. v
19. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.
20. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.
21. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.
22. Нивергельт Ю., Фаррар Дж., Рейнголд Э. Машинный подход к решению математиче-
ских задач. М.: Мир, 1977.
23. Оре О. Теория графов; М.: Наука, 1968.
24. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.
25. Плесневич Г. С., СапарЪв М. С. Алгоритмы в теории графов. - Ашхабад: Ылым,
1981.
26. Рейнголд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.
М.: Мир, 1980.
27. Робертс Ф. С. Дискретные математические модели с приложениями к социальным,
. биологическим и экологическим задачам. М.: Мир, 1986.
28. Рыбников К. А. Введение в комбинаторный анализ. М.: Изд-во МГУ, 1972.
114
29. Свами М., Тхуласирайан К. Графы, сети и алгоритмы. М.: Мир, 1984.'
30. Соболь И. М., Статникдв Р. Б. Выбор оптимальных параметров в задачах со многими
критериями. М.: Наука, 1981.
31. Солтан П. С., Замбицкий Д. К., Присакару К. Ф. Экстремальные задачи на графах
и алгоритм их решения. Кишинев: Штиинца, 1973.
132. Тараканов В. Б. Комбинаторные задачи и (0,1) -матрицы. М.: Наука, 1985.
33. Тыугу Э. X. Концептуальное программирование. М., 1984.
34. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.
35. Уззерелл Ч. Этюды для программистов. М.: Мир, 1982.
36. Форд Л. Р., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.
37. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычис-
лений. М.: Мир, 1980. *
38. Холл М. Комбинаторика. М.: Мир, 1970.
39. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.
40. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.
ОГЛАВЛЕНИЕ
Предисловие............................................................ 3
Глава 1. Структура данных.................................................. 5
1.1. Стеки............................................................ 5
1.2. Очереди........................................................ 7
1.3. Связанные списки................................................ 9
1.4. N-дольный граф................................................... 12
Г лава 2. Алгоритмы генерации комбинаторных конфигураций J................ 34
2.1. Система /п подмножеств множества Е = {вр в2—er3.................. 34
2.2. Размещение элементов из множества Е по к ....................... 38
2.3. Сочетания элементов из Е по к ................................... 43
2.4. Поиск с возвращением............................................ 46
2.5. Случайный поиск.................................................. 50
Глава 3. Примеры комбинаторных задач.... ................................. 73
Рекомендуемая литература................................................ 114
Учебно-методическое издание
Корженевич Юрий Владимирович
КОМБИНАТОРНЫЕ ЗАДАЧИ:
Олимпиады по программированию
Заведующая редакцией Л. Ф. Берниковская
Редактор А. В. Новикова
Младший редактор О. В. Сермяжка
Художник Д, А. Милованов
Художественный редактор С. В. Валенок
Технические редакторы В. П. Безбородова, Т. К. Романович
Корректор Ю. А. Оверченко
ИБ№1449
Подписано в печать 10.08.89. AT 0634J3. Формат 60x84/16. Бумага книжно-журнальная. Офсетная печать.
Гарнитура Пресс Роман. Усл. печ. л. Б,97. Усл. кр.-отт. 7,08. Уч.-изд. л. 8,1. Тираж 25000 эка. Заказ
Цена 45 к.
Издательство „Университетское” Государственного комитета БССР по делам издательств, полиграфии
и книжной торговли. 220048, Минск, проспект Машерова, 11
Отвечатано с оригинала-макета издательства „Университетское” в типографии ,„Победа”. 222310, Моло*
дечно, ул. Тавлая, 11.
Корженевич Ю. В.
К 66 Комбинаторные задачи: Олимпиады по программированию:
Учеб.-метод. пособие. Мн.: Университетское, 1989. - 116 с.: ил.
ISBN 5-7855-0251-8.
В книге рассмотрены базисные операции для работы со структурами данных:
стеками, очередями, связанными списками, N-дольными графами. Приведены алго-
ритмы и программы генерации основных комбинаторных конфигураций. Рассмотре-
на схема поиска с возвращением, случайный поиск, алгоритмы сортировки. Представ-
лены программы решения целого ряда занимательных задач студенческих олимпиад:
формирование ряда Фарея, восемь ферзей, ханойская башня, генерация кольца Вир-
та и т. д.
Для широкого круга читателей, интересующихся проблемами информатики.
К
1602100000 — 072
М317(Ю)—89
39-89
ББК 22.174
45 к.