КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Перечисление последовательностей фиксированной длины
Тип Абстрактные типы данных. Приближённые к реальности, но отсутствующие в данном языке программирования типы данных, называются абстрактными. «Программы = алгоритмы (процедуры) + структуры данных» Н. Вирт Идею нисходящего проектирования – многошаговый процесс создания (или выбора существующих) специализированных математических языков описания задач (подзадач) – мы ранее применяли к структурам управления. Применение к структурам данных – этот процесс был, как правило, одношаговый. При решении действительно сложных задач процесс нисходящего проектирования продолжается и на выбор промежуточных структур данных, то есть в целом на создание промежуточных абстрактных типов.
Задача о раскраске. Выяснить, можно ли данную карту правильно раскрасить данным количеством цветов. Если да, то предъявить все возможные раскраски. Раскраска правильная, если никакие две соседние страны не окрашены в один цвет. Делаем первые выводы относительно определения типа данных. 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=a1,…,an b=b1,…,bn a<b «ai0<bi0, где i0 – наименьший символ i такой, что ai¹bi и "i<i0 ai=bi
Procedure Следующая ({var Раскраска: tРаскраска;var Кончились:boolean}); {Выдаёт раскраску, следующую за данной, кладёт «Кончились» в true, если таковой нет} var i:tСтраны; c:tЦвет;
Дата добавления: 2014-01-05; Просмотров: 452; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |