Основные разделы


Алгоритмы подпрограмм

Основой алгоритма, приведенного в п.4.2.1 является подпрограмма GetSubSeq. Ее блок-схема представлена на рис.4.3 Переменная М содержит исходное множество двоичных векторов. Sample - содержит начальный вектор, Lst2 - список, к которому будет добавлена полученная субпоследовательность. List3 и List4 - два вспомогательных списка, которые создаются в операторе 2 и существуют все время выполнения подпрограммы. List3, после выполнения подпрограммы, будет содержать искомую субпоследовательность, List4 предназначен для хранения результатов выполнения подпрограммы GetByMask.

В результате выполнения блока 2, в List3 находится начальный вектор. В блоке 3 вызывается подпрограмма GetMask, которая на основе списка List3 получает маску, используемую для нахождения следующего вектора субпоследовательности (удовлетворяющего выражению (2.2)). Найденная маска помещается в переменную Mask.

В блоке 4 вызывается подпрограмма GetByMask, которой в качестве входных параметров передаются М и Mask. Данная подпрограмма отыскивает все векторы в М, отвечающие заданной маске, и сохраняет их в список List4.

В блоке 5 используется свойство Count переменной List4. Оно содержит количество векторов, которое содержит список. Если List4. Count = 0, т.е. не найдено ни одного вектора, то на этом нахождение текущей субпоследовательности завершается. Найденная субпоследовательность, которая содержится в List3, присоединяется к списку Lst2 (блок 8). В этом же блоке происходит освобождение памяти, занимаемой объектами List3 и List4.

Если же в результате выполнения блока 4 был найден хотя бы один вектор, то нахождение субпоследовательности продолжается в цикле. Подпрограмма SelectVector, вызываемая в блоке 6, позволяет выбрать наиболее подходящий из возможных векторов (из List4), и сохраняет его в переменной V, после чего V присоединяется к List3 (блок 7). В этом же блоке все неиспользованные векторы возвращаются в исходный список М. Далее выполняется следующая итерация цикла.

Далее рассмотрим алгоритм функционирования подпрограммы GetMask. Исходными данными для работы является List - это список, который передается в подпрограмму из вызвавшей программы, на его основе строится маска. Результат работы подпрограммы возвращается через переменную Result. Строковые переменные Subl и Sub2 используются для выделения и сравнения частей векторов. На i-м шаге внешнего цикла Subl содержит подстроку, состоящую из трех элементов последнего вектора из списка List, стоящих в позициях i-1, i, i+l Sub2 содержит те же три элемента j-гo вектора:

Subl = List [List. Count-ll [i-1] + List [List. Count-1] [i] + List [List. Count - l] [i+l];= List [j] [i-1] + List [j] [i] + List [j] [i+1],

где '+' обозначает конкатенацию строк.

Если в подпрограмму передан пустой список, это вызовет ошибку, для исключения такой ситуации выполняется проверка, если возникла ошибочная ситуация, подпрограмма посылает 'сообщение об ошибке' вызвавшей программе и завершает работу. Символ '*' в маске означает незафиксированный разряд, т.е. при проверке соответствия вектора маске (в подпрограмме GetByMask) такой разряд не сравнивается.

На рис.4.4 приведена блок-схема подпрограммы GetByMask, которая по заданной маске Mask, извлекает векторы из списка L1 и добавляет эти векторы в список L2, который и является результатом ее выполнения. Переменная j - это счетчик строк, a i - позиций (разрядов). При достижении j значения, соответствующего количеству строк в L1, подпрограмма завершается (блок 4). При достижении значения i>n (т.е. пройдена вся строка), текущий вектор заносится в список L2, происходит переход к следующему вектору и переустановка i. Соответствие вектора маске проверяется в блоке 6 поразрядно, при первом несоответствии происходит переход к следующему вектору и переустановка i (блоки 9 и 8 соответственно).

Подпрограмма SelectVector, блок-схема алгоритма которой приведена на рис.4.5, необходима для того, чтобы выбрать наиболее подходящий из всех векторов, которые могут быть присоединены к субпоследовательности на данном шаге. Переменные LI, L2 - списки, содержащие строящуюся субпоследовательность и векторы, которые могут быть присоединены к ней на данном шаге соответственно; переменная V содержит выбранный вектор после завершения работы подпрограммы. Переменная i - счетчик строк, j - содержит значение номера выбранного вектора в L2. Здесь также используется функция GetFreeColCount, которая подсчитывает количество символов '*' в аргументе.

Прочитайте еще и эти статьи:

Проектирование цифровой многофункциональной телемеханической системы ТУ-ТС-ТИ
В настоящее время имеется острая необходимость в автоматизации различных сфер нашей жизни. В связи с этим возникает необходимость применения средств автоматизации и вычислительной техники. Современное развитие техники, электроники и вычислительн ...

Сотовые сети стандарта СDMA
Как известно, наиболее прогрессивная часть человечества ныне стоит на пороге вступления в эру глобального информационного общества и соответствующего коренного улучшения телекоммуникационного обслуживания населения. И достигнуто э ...

© Copyright 2020 | www.techattribute.ru