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

 

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

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

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 214 215 216 217 218 219 < 220 > 221 222 223 224 225 226 .. 316 >> Следующая

Будем решать задачу, которая для каждого конкретного случая решается с помощью конечного автомата специального вида (как и всегда, выбор конкретного представления сильно влияет на сло ность и другие характеристи-
626
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
ки программ , и автоматическое применение ранее использованных представлений в других задачах не рекомендуется).
Пусть требуется подсчитать, сколько раз каждое из вводимых слов встречается в некотором больом файле (теперь слово — это лбая последовательность символов). «і, а2, ..., «n — вводимые слова; « = ¦ ¦ ¦ &кг — слово H апечатать: Число вхождений а1 = <Число 1>, Число вхождений а2 = <Число 2>,
Число вхождений an = <Число n>
где <Число k> — полное число вхождений слова ak в файл с учетом возмож-ного перекрытия слов (например, в строке "*МАМАМА{}" два вхождения слова "МАМА").
ля заданнх заранее слов легко построить граф, кадая верина которого представляет символ внутри слов. Его верины помечен символом.
з такой верин исходят две дуги: первая указывает на верину, к которой следует переходить, когда очередной читаемый символ совпадает с пометкой вершины, а вторая — на вершину, которая должна стать преемником данной в случае несовпадения. егко видеть, что это одна из форм представления конечного автомата, кадое состояние которого кодирует мно ество всех вер-
ин, связанных дугами второго вида, а состояния-преемники определя тся дугами первого вида исходного графа. Чтобы этот автомат работал, т.е. решал поставленную за-дачу нужно снабдить его действиями, которые сводятся к увеличени счетчиков, соответ-ствуих найденным словам, а так е определить начальное и конечное состояния. не будем заниматься переделкой исходного графа, поскольку такая его форма удобнее для интерпретации.
Если дуги первого вида изобраать стрелками, исходяими в горизонтальном на-правлении, дуги второго вида - вертикальными стрелками, а действия со счетчиками - соответствуими пометками при дугах, то, например, для мно ества слов
1) МАМА,
2) ,
3) ШИНА,
4) Т,
5)
10.6.
627
мо ет бть построен граф, показаннй на рис. 10.6.
На языке C++/C# структура, которая представляет граф, почти такой, как только что описаннй, мо ет быть изобра ена следуим образом:
собенность данной интерпретации таблицы в том, что она соответствует автоматам ура: действия ассоцииру тся с веринами, а не с дугами, с состояниями, а не с переходами. Верина, которой сопоставлено действие, не требует чтения очередного символа и его анализа. Вместо символьных пометок вершины-действия содержат числовые номера, идентифицирующие соответствующие счетчики (использовано размеченное объединение для того, чтоб отразить это соглаение). ри елании мо но считать, что действия приписаны только тем дугам, которые ведут из этих верин (специ-альне пометки этих дуг не ну ны).
Для нашего примера граф-автомат представляется следующей таблицей (переход 111, указывающий за пределы таблицы, использован для обозначения заверения просмотра файла):
1) МАМА, 2) МАШИНА, 3) ШИНА, 4) МАТ, 5) НА.
0. '\n' 111 1
1. М 2 15
2. А 3 0
3. М 4 6
4. А 5 0
5. <1> 3 -
6. Ш 7 14
7. И 8 0
8. Н 9 0
9. А 10 0
10. <2> 11 —
struct {
bool Tag; // поле признак
union {char Symb; // <- Tag = true int Num; // <- Tag = false
}; // имя объедине
int yes; // индекс перех
int no; // индекс перех
// поле признака текуего значения в union:
// имя объединения здесь не ну но // индекс перехода по совпадению // индекс перехода по несовпадению
} Table[];
628
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
'\n'
н—*
Рис. 10.6. ример конечного автомата для распознавания вхо дений слов
10.6. ПЕРЕХОД ОТ ДАННЫХ К КОНЕЧНОМУ АВТОМАТУ
629
11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21
Ш И Н
А Н
А
V
<3> <5> Т
<4>
12 1
14 1
16 17 18 11 20 12
0
0
19
0
0
0
0
0
рограмма интерпретации графа достаточно проста. ля данной задачи нет смсла использовать транслируий вариант реализации оперирования с таблицей (операторы Current_Reaction(); и Final_Reaction(); использованы для обозначения действий со счетчиками, например тех, которые приведены в комментариях):
Программа 10.6.1
s = getchar ();
i=1;
for (;;) {
if (Table[i].Tag) {
if (Table[i].Symb == s) {
i = Table[i].yes; // следующая строка if ( s != '\n')
else {
Current_Reaction(); // M[Table[i].Num]++ i = Table[i].yes; // следующая строка
}
}
Final_Reaction(); // Распечатка M
s = getchar (); else return;
}
else
i = Table[i].no; // следующая строка
}
630
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
В данном интерпретаторе структура данных не содержит описаний действий — они только идентифицируются значениями соответствующих полей таблицы, а потому нет противоречий двойной трактовки данных как информационных и операционнх единиц, т. е. нет тех проблем, которые бли отмечен ве для автомата, использованного для подсчета длин слов. Вано, что здесь достигается универсальность, независимость от таблицы для всех вариантов ввода слов.
Ничуть не сложнее решение, когда вместо таблицы-массива используется списочная структура. о суеству ничто, кроме доступа к даннм, которй мо но строго локализовать в соответствуих процедурах, не изменится.
Предыдущая << 1 .. 214 215 216 217 218 219 < 220 > 221 222 223 224 225 226 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100