Перечисление последовательностей фиксированной длины

Тип

Абстрактные типы данных.

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

«Программы = алгоритмы (процедуры) + структуры данных»

Н. Вирт

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

Задача о раскраске.

Выяснить, можно ли данную карту правильно раскрасить данным количеством цветов. Если да, то предъявить все возможные раскраски. Раскраска правильная, если никакие две соседние страны не окрашены в один цвет.

Делаем первые выводы относительно определения типа данных.

type tСтраны = 1..n; {Можно взять произвольный порядковый тип}

tКарта = array [tСтраны,tСтраны] of Boolean; {На этом типе обязана быть определена единственная функция}

var карта: tКарта;

m:cardinal;

можно: boolean;

раскраска:tРаскраска; {Определение типа откладываем до определения операций, которые нужны в алгоритме}

Function Правильная (раскраска: tРаскраска):boolean;

{правильная:="i,jÎtСтраны (соседи (i,j)(i<j) à раскраска(i) ¹ раскраска j)}

{Стрелка – логическая связь – «если, то»}

{правильная:= }

Begin

result:=true;

i:=первая страна;

while (i<=последняя страна) and (Result) do

begin

j:=succ(i);

while (j<=последняя страна) and Result do

begin

if соседи (i,j) then if раскраска (i) = раскраска (j) then Result:=false;

else j:=succ(j);

end;

i:=succ(i);

end;

end;

Begin

{Можно:=$ раскраска – tРаскраска - правильная}

можно:=false;

раскраска:=первая раскраска;

while not (конечная раскраска) do

begin

if (правильная раскраска) then

begin

можно:=true;

write (Правильная раскраска);

end;

раскраска:=следующая раскраска;

end;

End.

Мы отождествляем тип tКарта с функцией “Соседи”, задавая её в виде булевского массива. Не забудь переименовать в алгоритме Соседи на Карта!

tРаскраска: tСтранаàtЦвет

array[tСтрана] of tЦвет

Однако основной алгоритм требует, чтобы тип tРаскраска был порядковым. Нам необходима возможность перечислять раскраску.

n циклов дали бы нужный порядок, но мы не можем выразить такой оператор синтаксически, однако это даёт идею того, в каком порядке можно перебирать последовательности (конечные функции) – в словарном (лексикографическом).

a=a₁,…,a_n

b=b₁,…,b_n

a<b «a_i0<b_i0, где i₀ – наименьший символ i такой, что a_i¹b_i и "i<i₀ a_i=b_i

Procedure Следующая ({var Раскраска: tРаскраска;var Кончились:boolean});

{Выдаёт раскраску, следующую за данной, кладёт «Кончились» в true, если таковой нет}

var i:tСтраны; c:tЦвет;

Дата добавления: 2014-01-05