Лекции Русакова (1021002), страница 29
Текст из файла (страница 29)
Найти все компоненты сильной связности.v1v2v3v4v5v100111v201110v301011v411010v5011012. Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e110100e201010e301100e400011e500110e601001e720000Вариант №911.Изобразитьориентированныйv1v2v3v4v5v101001v210100v311011v411000v500010граф,заданныйматрицейсмежности.Составитьинцидентности.
Построить матрицу достижимости. Найти все компоненты сильной связности.матрицу2. Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e110001e210001e310100e411000e500200e601001e701100270Вариант №921.Изобразитьориентированныйv1v2v3v4v5v101101v201000v310101v410100v511101граф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости. Найти все компоненты сильной связности.матрицу2.
Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e101001e200011e300101e410100e510100e610100e700200Вариант №931.Изобразитьориентированныйграф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости.
Найти все компоненты сильной связности.v1v2v3v4v5v101111v200010v301000v401011v510101матрицу2. Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e100101e200002e300011e410100e501010e600110e700101Вариант №942711.Изобразитьориентированныйграф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5v101011v210000v301110v411111v510001матрицу2.
Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e101001e210001e311000e401001e520000e601010e710001Вариант №951.Изобразитьориентированныйграф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5v100001v201100v300100v411100v510100матрицу2. Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости.
Найти все компоненты сильной связности.v1v2v3v4v5e100101e201001e302000e410010e510100e601010e710100Вариант №961.Изобразитьориентированныйграф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5v111100v200101272матрицуv310011v400110v5001102. Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности.
Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e100101e200002e300110e401001e501010e610100e710100Вариант №971.Изобразитьориентированныйграф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5v111110v201101v301001v400011v500110матрицу2.
Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e100101e200200e311000e410001e501010e611000e700011Вариант №981.Изобразитьориентированныйграф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости.
Найти все компоненты сильной связности.v1v2v3v4v5v111111v210001v300001v411100v500010273матрицу2. Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e101010e200011e301001e411000e501001e600002e701001Вариант №991.Изобразитьориентированныйv1v2v3v4v5v110011v201001v311001v400101v500010граф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости.
Найти все компоненты сильной связности.матрицу2. Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности. Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e100110e201001e302000e411000e511000e610100e700101Вариант №1001.Изобразитьориентированныйv1v2v3v4v5v111110v200100v300011v401111v501001граф,заданныйматрицейсмежности.Составитьинцидентности. Построить матрицу достижимости. Найти все компоненты сильной связности.матрицу2. Изобразить неориентированный граф, заданный матрицей инцидентности. Составить матрицусмежности.
Построить матрицу достижимости. Найти все компоненты сильной связности.v1v2v3v4v5e111000e201010274e300200e400101e501001e610100e710001Глава 9. Дополнительнаячасть:практическаяработа студентовПрактическое занятие №1. Работа с регулярнымивыражениями на основе PERL .9.01. Общие указания к выполнению практическойработы.Практические работы выполняются с использованием персональныхкомпьютеров.
Указания по технике безопасности совпадают с требованиями,предъявляемымикпользователюЭВМ.Другиеопасныефакторыотсутствуют.9.02. Цель работыОзнакомиться и научиться составлять регулярные выражения всинтаксисе языка PERL. Научиться применить полученные знания к задачепоиска текста по шаблону в файлах.9.03.
Теоретические сведения.8.03.1. Регулярные выражения (шаблоны).Определение.Регулярные выражения (англ. regular expressions, сокр. RegExp,RegEx) — это формальный язык поиска и осуществления манипуляций сподстроками в тексте, основанный на использовании метасимволов275(терминалов). По сути это строка-образец (англ. pattern, по-русски её частоназывают «шаблоном», «маской»), состоящая из символов (не терминалов),метасимволов (терминалов) и задающего правило поиска (продукций).Регулярные выражения или шаблоны (pattern) то же самое, что и regexpпроцедуры в Unix. Выражения и синтаксис заимствованы из свободнораспространяемых процедур V8 Генри Спенсера (Henry Spencer).В шаблонах используются следующие метасимволы (символыобозначающиегруппыдругихсимволов)частоназываемыеegrep-стандартом:¦ \ — считать следующий метасимвол как обычный символ.¦ ^ — начало строки¦ .
— один произвольный символ. Кроме “\ n” — конец строки.¦ $ — конец строки¦ | — альтернатива (или)¦ () — группировка¦ [] — класс символовМетасимволы имеют модификаторы (пишутся после метасимвола):¦ * — повторяется 0 или большее число раз¦ + — 1 или большее число раз¦ ? — 1 или 0 раз¦ {n} — точно n раз¦ {n,} — по меньшей мере n раз¦ {n,m} — не меньше n, но и не больше mВо все других случаях фигурные скобки считаются обычными (нетерминальными) символами.276Таким образом:“*” эквивалентна { 0,} ,“+” — { 1,} ,“?” — { 0,1} .n и m не могут быть больше 65536.По умолчанию действие метасимволов “жадно” (greedy). Совпадениераспространяется столько раз, сколько возможно, не учитывая результатдействия следующих метасимволов.
Если вы хотите “уменьшить ихаппетит”,тоиспользуйтесимвол“?”.Этонеизменяетзначениеметасимволов, просто уменьшает распространение.Таким образом:¦ *? — 0 и более¦ +? — 1 и более¦ ?? — 0 или 1 раз¦ { n} ? — точно n раз¦ { n,} ? — не меньше n раз¦ { n,m} ? — больше или равно n и меньше m разШаблоны работают так же, как и двойные кавычки (в С++, PERL),поэтому в них можно использовать “\” — символы (бэкслэш-символы):¦ \ t — символ табуляции¦ \ n — новая строка¦ \ r — перевод каретки¦ \ а — перевод формата¦ \ v — вертикальная табуляция¦ \ a — звонок277¦ \ e — escape¦ \ 033 — восьмеричная запись символа¦ \ x1A — шестнадцатеричная¦ \ c — control символ¦ \ l — нижний регистр следующего символа¦ \ u — верхний регистр¦ \ L — все символы в нижнем регистре до \ E¦ \ U — то же в верхнем регистре¦ \ E — ограничитель смены регистра¦ \ Q — отмена действия как метасимволаДополнительно в Perl добавлены следующие метасимволы:¦ \ w — алфавитно-цифровой или '_' символ¦ \ W — не алфавитно-цифровой или '_' символ¦ \ s — один пробел¦ \ S — один не пробел¦ \ d — одна цифра¦ \ D — одна не цифраОбратите внимание, что все это “один” символ.Для обозначения последовательности применяйте модификаторы.
Так:¦ \ w+ — слово¦ \ d+ — целое число¦ [+-]?\ d+ — целое со знаком¦ [+-]?\ d+\ .?\ d* — число с точкойКроме того существуют мнимые метасимволы. Обозначающие несуществующие символы в месте смены значения. Такие как:278¦ \ b — граница слова¦ \ B — не граница слова¦ \ A — начало строки¦ \ Z — конец строки¦ \ G — конец действия m//gГраница слова (\ b) — это мнимая точка между символами \ w и \ W.Внутри класса символов \ b обозначает символ backspace (стирания).Метасимволы \ A и \ Z — аналогичны “^” и “$”, но если начало строки “^” иконец строки “$” действуют для каждой строки в многострочной строке, то\A и \Z обозначают начало и конец всей многострочной строки. Если внутришаблона применяется группировка (круглые скобки), то номер подстрокигруппы обозначается как “\ цифра”.Заметьте, что за шаблоном в пределах выражения или блока эти группыобозначаются как “$цифра”.
Кроме этого существуют дополнительныепеременные:¦ $+ — обозначает последнее совпадение¦ $& — все совпадение¦ $` — все до совпадения¦ $' — все после совпаденияНапример:$s = "Один 1 два 2 и три 3";if ($s =~ /(\ d+)\ D+(\ d+)/){print "$1\ n";# Результат '1'print "$2\ n";# '2'print "$+\ n";# '2'print "$&\ n";# '1 два 2'print "$`\ n";# 'Один '279print "$'\ n";# ' и три 3'}8.03.2.
Правила регулярного выражения.1. Любой символ обозначает себя самого, если это не метасимвол. Есливам нужно отменить действие метасимвола, то поставьте перед ним “\”.2. Строка символов обозначает строку этих символов.3. Множество возможных символов (класс) заключается в квадратныескобки [], это значит, что в данном месте может стоять один из указанныхв скобках символов. Если первый символ в скобках это “^” — значит ниодин из указанных символов не может стоять в данном месте выражения.Внутри класса можно употреблять символ “-”, обозначающий диапазонсимволов. Например, a-z — один из малых букв латинского алфавита, 0-9— цифра.4. Все символы, включая специальные, можно обозначать с помощью “\”как в языке С.5. Альтернативныепоследовательностиразделяютсясимволом“|”Заметьте что внутри квадратных скобок это обычный символ.6.