Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 198

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 192 193 194 195 196 197 < 198 > 199 200 201 202 203 204 .. 316 >> Следующая

Мы начнем с примеров таких задач и иллюстрации техники решений в разных случаях. Затем разбирается теоретическая основа и следствия из нее, которе ну ны для применения на практике, а затем возврааемся к технике программирования и показваем различные реализации программирования от состояний.
Очень часто диаграммы переходов порождают структуру конечного автомата (см. определение A.4.1). В этих случаях программирование от состояний вне конкуренции по сравнени с другими стилями. о поро оно при-
560
10.1. ОСНОВНЫЕ СТРУКТУРЫ
561
менимо и тогда, когда диаграмма перехода соответствует более сло ной вычислительной модели. Словом, если сохраняется инвариант "Действия глобальны, условия локальны", то задачу уместно решать с помощью методов, основваихся на понятии диаграмм переходов и конечного автомата.
Есть много вариаций методов программирования от состояний. Более того, 'уместно' не всегда означает 'лучше всего'. Поэтому программирование от состояний удобно для показа на примерах того, как варьируются практические методы решения логически и математически вроде бы однородных задач. ебольое изменение в ресурсных ограничениях — и, хотя старые метод , как правило, оста тся уместными, но луче перейти к другим.
§10.1. ОСНОВНЫЕ СТРУКТУРЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
Информационное пространство всех блоков и процедур при программировании от состояний в первом прибли ении одно и то е: состояния системы, моделируемой совокупность программных действий. о на самом деле многие блоки либо процедуры работа т с подсистемами. одсистем , ввиду их автономности, могут иметь характеристики, прямо недоступные для общей системы, и в свою очередь могут иметь лишь ограниченный доступ к обему системному пространству даннх. Более того, подсистем могут обаться прямо, в обход иерархически выестояей системы (см. рис. 10.1). Таким образом, структура информационного пространства при программировании от состояний в общих чертах соответствует той, которая навязывается современными системами с развитой модульностью.1
§ 10.2. ЗАДАЧА ПОДСЧЕТА ДЛИН СЛОВ ТЕКСТА И ЗАДАНИЕ КОНЕЧНОГО АВТОМАТА
10.2.1. Постановка задачи и первичный анализ
усть требуется реить следуу задачу. Словом назвается лбая непустая последовательность букв латинского алфавита (для простоты —
1 Интересно, что необходимость развитых средств поддержки модуляризации программ первоначально провозглашалась для для структурного программирования, но оказалась прекрасно приспособлена к совсем другому стилю. Впрочем, в современных программах самый верхний (часто полуавтоматически генерируемый системами визуального программирования и поэтому обычно мало интересный для программистов) этаж структуры программ, как правило, записан именно в стиле программирования от состояний.
562
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
Система
Пояснения к картинке. Светло-серые области — традиционный общий контекст системы и подсистемы. Темно-серые иллюстрируют, что доступность может быть односторонней, и не только по иерерхии. О дна из систем может влиять на часть информационного пространства другой, а другая может лишь пассивно следить за тем, что натворил непокорный вассал, либо сбрендивий начальник, либо просто коллега. бласти, связанные двусторонними стрелками, иллстриру т прямое обение в
обход иерархии.
Рис. 10Л. Информационное пространство систем
10.2. ПОДСЧЕТ ДЛИН СЛОВ
563
только строчных букв). ерепечатать из входной последовательности символов все слова в следующем виде: <слово> - <длина слова><конец строки печати>
Эту довольно простую задачу можно решать по-разному. Ближайшая цель — построить реение, исходя из представления вчислительного процесса набором состояний с переходами.
Для решения задачи входную последовательность символов естественно считать потоком, читаемым слева направо, пока не закончится входная строка. ри чтении букв, небукв и конца строки действия, которе необходимо выполнять, различны. Кроме того, различны действия для первой буквы и для последуих букв слова.
Здесь уже сделаны неявные предположения об алгоритме:
• слово рассматривается как вложенный во входную последовательность поток;
• обработка слова будет происходить по схеме с инициализацией, включа-
ей генераци первого элемента потока-слова.
Можно считать, что эти предположения выяснены в результате анализа задачи, и что они вытекают из сопоставления разных вариантов обработки. Из этих предполо ений следует, что в данном случае задача чисто автоматная, и поэтому построение диаграммы переходов и конечного автомата — одно и то же.
10.2.2. Построение графа состояний
Решение, которое исходит из применения метода конечного автомата, требует, чтобы был определен набор состояний. Различные состояния выделятся преде всего из-за различия действий-реакций на чтение символов. Вот полный перечень вариантов таких действий:
1. Символ буква: инициализировать обработку слова
(счетчику длин слова присвоить единицу).
2. Символ буква: продолжить обработку слова
(счетчик длины слова увеличить на единицу).
Предыдущая << 1 .. 192 193 194 195 196 197 < 198 > 199 200 201 202 203 204 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100