Непейвода Н.Н. Программирование. Раздел 4

Непейвода Н.Н. Программирование. Страница 443

§ 10.2. ЗАДАЧА ПОДСЧЕТА ДЛИН СЛОВ ТЕКСТА И ЗАДАНИЕ КОНЕЧ­НОГО АВТОМАТА 10.2.1. Постановка задачи и первичный анализ

Пусть требуется решить следующую задачу. Словом называется любая непустая последовательность букв латинского алфавита (для простоты — только строчных букв). Перепечатать из входной последовательности сим­волов все слова в следующем виде: <слово><длина словахконец строки печати>

Эту довольно простую задачу можно решать поразному. Ближайшая цель — построить решение, исходя из представления вычислительного про­цесса набором состояний с переходами.

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

Здесь уже сделаны неявные предположения об алгоритме:

слово рассматривается как вложенный во входную последовательность поток;

обработка слова будет происходить по схеме с инициализацией, вклю­чающей генерацию первого элемента потокаслова.

Можно считать, что эти предположения выяснены в результате анализа за­дачи и что они вытекают из сопоставления разных вариантов обработки. Из этих предположений следует, что в данном случае задача чисто автоматная, и поэтому построение диаграммы переходов и конечного автомата — одно и то же.

10.2.2. Построение графа состояний

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

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета &quot;Ангара-А5В&quot; в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие &quot;Крокодилы&quot;

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама