Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Формализация задачи

Глава 2. Алгоритм определения наиболее длинной общей подпоследовательности

Глава 3. Программная реализация алгоритма LCS на языке программирования

3.1 Выбор языка программирования

3.2 Реализация алгоритма на языке Pascal

Глава 4. Производительность и быстродействие

Заключение

Список использованной литературы

Приложение

Введение

В настоящее время для организации учебного процесса в средних и высших учебных заведениях применяются системы автоматизированного тестирования. Это в большей степени относится к урокам информатики. В частности, такие системы используются в школе на уроках контроля и проверки знаний, лабораторных работах, на факультативах и внутренних олимпиадах по информатике. Если же рассматривать применение систем автоматизированного тестирования (САТ) в высших учебных заведениях, то здесь оно распространяется на все дисциплины, связанные с программированием. Особенно активно применяются САТ как во внутривузовских, так и в республиканских и международных олимпиадах по программированию. Особенно можно отметить применение САТ в командном чемпионате мира по программированию (International Collegiate Programming Contest), который проводится по правилам ACM.

Рассмотрим упрощенный принцип работы типичной системы автоматизированного тестирования.

САТ обычно располагается на отдельном компьютере (сетевом сервере) и состоит из двух частей: модуля, отвечающего за веб-интерфейс и тестирующего модуля. Модуль, отвечающий за веб-интерфейс, позволяет пользователю обмениваться данными с САТ.

Таким образом, к функциям САТ можно отнести следующие:

1. Прием у пользователя решенной задачи на языке программирования и дальнейшая передача ее тестирующему модулю.

2. Сообщение пользователю результатов работы данной программы. Если она работает неправильно, то данный модуль отображает причину, по которой задача не засчитывается. Это может быть, например, превышение лимита времени, неправильный результат или ошибка компиляции.

3. Сохранение результатов решений всех пользователей, обеспечение удобного просмотра результатов учебного курса или олимпиады для пользователей и организаторов. (Например, вывод таблицы результатов и т.д.)

Тестирующий модуль представляет собой программу, которая, приняв решение на языке программирования, компилирует его и проверяет на некотором наборе тестов.

Однако, стоит отметить, что у САТ есть один существенный недостаток. Он состоит в том, что пользователи, если нет должного контроля, а его проблематично, а порой невозможно организовать, могут обмениваться готовыми правильными решениями (текстами программ). Это нарушает принцип самостоятельности и делает проблематичным объективное оценивание отдельных пользователей САТ. На олимпиадах отсутствие контроля позволяет отдельным пользователям (командам) занимать места, на которые они претендовать при обычных обстоятельствах не смогли бы. И эта проблема очень актуальна, т.к. и сам автор был свидетелем такой несправедливости.

На мировых соревнованиях имеются системы контроля, позволяющие отсеивать повторяющиеся решения, однако механизм их работы остается в секрете. Один из вариантов - ручная проверка решений на идентичность. Однако в тех случаях, когда число заданий или пользователей достаточно велико, такой подход является весьма сложным, медленным и кропотливым.

На лабораторных или контрольных работах с использованием САТ модуль, который бы отсеивал повторяющиеся или частично совпадающие решения и сообщал о них преподавателю (учителю), явился бы незаменимым средством для борьбы с плагиатом и подлогом решений.

Он позволил бы без отрыва от учебного процесса проводить преподавателю лабораторные работы и контрольные мероприятия, а студентам (учащимся) - получать объективные оценки знаний. В данной курсовой работе будет предпринята попытка создать данный модуль, а затем проверить его в САТ.

Итак, целью данной курсовой работы является исследование возможностей использования алгоритма поиска максимальной подпоследовательности (Longest Common Subsequence) для оценки степени совпадения решений задач в САТ.

Задачи курсовой работы:

1. Изучение алгоритма LCS.

2. Программная реализация алгоритма.

3. Оценка эффективности работы алгоритма.

4. Апробация результатов в составе системы автоматизированного тестирования решений задач по информатике.

Глава 1. Формализация задачи

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

При анализе поставленной проблемы был отмечен тот факт, что задача определения степени идентичности двух текстовых файлов может быть сведена к задаче поиска максимальной общей подпоследовательности для двух последовательностей.

Прямо сравнивать два при этом файла не рационально. В частности, можно добавить в программу пустые строки, пробелы, комментарии, и тогда процент совпадения станет намного меньшим, кроме того, смена регистра символов также окажет влияние повлиять на степень совпадения. Но ведь решения могут полностью совпадать. Очевидное решение данной проблемы заключается в том, что перед поиском максимальной подпоследовательности необходимо определенным образом преобразовать исходные файлы.

В частности, если из текста программы удалить пробелы, комментарии, переводы строк и привести все символы к одному регистру (проще всего к верхнему) то это позволит более точно определить степень совпадения. Сравнение преобразованных таким образом файлов даст результаты, гораздо более близкие к искомой величине.

Следовательно, поставленная задача разбивается на две подзадачи:

1. Преобразование текста программы в последовательность символов в верхнем регистре без пробелов, символов перевода строки, комментариев.

2. Нахождение максимальной подпоследовательности для двух полученных последовательностей.

Начнем со второй части задачи. Существует несколько разных способов определения подобия двух строк. Один из наиболее простых и часто встречающихся способов использует символьные строки и их подпоследовательности. Допустим, имеется строка X = x₁x₂x₃x₄...x_n-1.

Определение: Подпоследовательностью строки X будет любая строка, имеющая вид x_ix_i2...x_ik, где i_j < i_j + 1; т.е. это набор символов, необязательно расположенных подряд, но, тем не менее, существующих в Х.

Например, строка AAAG является подстрокой CGATAATTGAGA. Заметим, что понятие подпоследовательности строки отличается от определения подстроки. В подстроке все символы обязательно расположены подряд.

Задача нахождения наиболее длинной общей подпоследовательности известна в англоязычной литературе под названием Longest Common Subsequence (LCS). Она состоит в том, чтобы из двух строк символов

X = x₁x₂x₃x₄...x_n-1

Y = y₁y₂y₃y₄...y_m-1

некоторого алфавита определить наиболее длинную строку S, являющуюся наиболее длинной подпоследовательностью обеих строк X и Y.

Одним из вариантов решения этой задачи является перебор всех подпоследовательностей в Х и выбор самой длинной из них, одновременно являющейся подпоследовательностью в Y. Поскольку каждый символ в X либо находится в подпоследовательности, либо нет, существует потенциально 2ⁿ различных подпоследовательностей Х, каждая из которых требует О(m) времени для определения, является ли она подпоследовательностью в Y. Таким образом, силовой алгоритм соответствует экспоненциальному алгоритму, выполняющемуся за O(2ⁿm) времени, что явно не эффективно. Ниже будет рассмотрен динамический метод решения задачи поиска наиболее длинной общей подпоследовательности, работающий намного быстрее.

Методика динамического программирования используется в первую очередь для оптимизационных задач, когда требуется определить наилучший способ выполнения некоторого действия. Зачастую количество разных способов выполнения такого действия экспоненциально, поэтому примитивный поиск недопустим. В таких случаях можно применить технологию динамического программирования, если задача содержит определенное количество структур, которые могут быть использованы. Такая структура включает три следующих компонента.

Простая подзадача: общая оптимизированная задача должна иметь возможность разбиения на подзадачи. Более того, должен существовать простой способ обозначения подзадач всего несколькими индексами типа i, j, k и т.п.

Оптимизация подзадачи: оптимальным решением общей задачи должна стать комбинация оптимальных решений подзадач. Вряд ли возможно найти оптимальное решение всей задачи, содержащее субоптимальные подзадачи.

Наложение подзадач: оптимальные решения не связанных между собой подзадач могут сами содержать общие подзадачи.

Перечислив основные составляющие технологии динамического программирования, рассмотрим их применение для поиска максимальной подпоследовательности.

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

Напомним, что для решения задачи имеется две строки X и Y. Т.к. X и Y состоят из символов, имеется естественное множество индексов, с помощью которых можно определить подзадачи - индексы в строке X и в строке Y.

Определим подзадачи таким образом, чтобы использовать при вычислениях значения L[i,j], применяемого для хранения длины наиболее длинной строки, являющейся подпоследовательностью обеих X = x₁x₂x₃x₄...x_n-1 и Y = y₁y₂y₃y₄...y_m-1. Это позволит переопределить L[i,j] для оптимального решения подзадачи, что зависит от ситуации, которая может быть следующей (см. рис. 1).

Размещено на http://www.allbest.ru/

При работе алгоритма возможны два случая наиболее длинной общей подпоследовательности: а) x_i=y_j и б) x_i?y_j. Заметим, что алгоритм сохраняет только значения L[i,j], а не совпадения.

· x_i=y_j. В этом случае имеется совпадение последнего символа в X[0…i] и последнего символа Y[0…j]. Будем считать, что этот символ принадлежит максимальной общей из подпоследовательностей X[0…i] и Y[0…j]. Для доказательства предположим, что это утверждение неверно. В то же время, для X и Y существует некоторая наиболее длинная общая подпоследовательность x_ix_i2...x_ik= y_jy_j2...y_jk. Если x_ik=x_i или y_jk=y_j, то подпоследовательность удлиняется добавлением x_i в ее конец. Таким образом, наиболее длинная общая подпоследовательность в X[0…i] и Y[0…j] будет заканчиваться на x_i.Следовательно, устанавливаем

, если x_i=y_j.

· x_i?y_j. В этом случае невозможно получить общую подпоследовательность из x_i и y_j. То есть можно получить общую подпоследовательность, заканчивающуюся на x_i или на y_j, или (возможно) ни ту, ни другую, но никак не обе. Следовательно, устанавливаем

, если x_i?y_j.

Чтобы оба эти уравнения имели смысл даже при i=0 и j=0, полагаем L[i,-1]=0, при i=0,1,…,n-1 и L[-1,j]=0, при j=0,1,…,m-1.

Такое определение для L[i,j] отвечает требованиям оптимизации подзадачи, так как невозможно получить наиболее длинную общую подпоследовательность, не имея наиболее длинной подпоследовательности для данной подзадачи. К тому же здесь применяется наложение подзадач, так как решение подзадачи L[i,j] может использоваться и в других задачах (а именно, задачах L[i+1,j] L[i,j+1] L[i+1,j+1]).

Глава 2. Алгоритм определения наиболее длинной общей подпоследовательности

Превращение описанного определения L[i,j] в алгоритм представляется достаточно простым и наглядным.

Создается массив размера [-1..n+1,-1..m+1], L для пограничных случаев, когда i=0 и j=0. То есть L[i,-1]=0, при i=0,1,…,n-1 и L[-1,j]=0, при j=0,1,…,m-1 (при этом порядок несколько нарушается, поскольку сроки и столбцы в L должны индексироваться с 0). Затем итеративно определяем значения L до тех пор, пока не получим L[n-1,m-1], длину наибольшей общей подпоследовательности X и Y. Псевдокод такого подхода в динамическом программировании для решения задачи поиска наиболее длинной общей подпоследовательности приведен ниже (стрелка влево означает присваивание).

Для i от -1 до n-1 выполнять L[i,-1]<0 Конец_для

Для j от 0 до m-1 выполнять L[-1,j]<0 Конец_для

Для i от 0 до n-1 выполнять

Для j от 0 до m-1 выполнять

Если x_i=y_i то

L[i,j]< L[i-1,j-1]+1

Иначе

L[i,j]< max(L[i-1,j],L[i,j-1])

Конец_если

Конец_для

Конец_для

После работы данного алгоритма с помощью L можно построить искомую последовательность, но так как задачей является только определить степень подобия, то, скорее всего, хранить весь массив L не нужно. Нетрудно заметить, что для получения очередного значения L[i,j] необходимо знать только содержимое текущей и предыдущей строк массива L, поэтому алгоритм можно модифицировать. Будем использовать не двумерный массив, а два одномерных: текущая строка и предыдущая строка. Это позволяет для двух последовательностей по 10000 элементов расходовать не 10⁸ байт, а всего лишь 20000 байт. Это существенно сокращает расход памяти.

Для i от -1 до n-1 выполнять

L1[i]<0

L2[i]<0

Конец_для

Для j от 0 до m-1 выполнять

Для i от 0 до n-1 выполнять

Для j от 0 до m-1 выполнять

Если x_i=y_i то

L2[j]< L1[j-1]+1

Иначе

L2[j]< max(L1[j],L2[j-1])

Конец_если

L1<L2

Если i?n-1 то

Для k от -1 до n-1 выполнять

L2[k]<0

Конец_для

Конец_если

Конец_для

Конец_для

Первая часть задачи решается довольно легко. Здесь необходимо преобразовать тексты двух программ в две последовательности символов(X и Y) по следующему правилу: “все символы приводятся в верхний регистр, удаляются пробелы, символы перевода строки, комментарии”. Таким образом, входные данные представляют собой два файла, а выходные - две строки. Приведем алгоритм в псевдокоде для обработки одного такого файла (второй файл обрабатывается аналогично).

Пока не конец файла выполнять

Считать очередной символ из файла;

Приводим его к верхнему регистру;

Если текущий символ «{» то

Пока текущий символ не «}» выполнять

Считать очередной символ из файла;

Конец_пока

Считываем очередной символ из файла;

Приводим его к верхнему регистру;

Конец_если

Если символ не «пробел», не «символ перевода строки» то

Добавить данный символ к последовательности

Конец_если

Конец_пока

Сравниваемые программы написаны в кодировке OEM, поэтому перевод строки обозначается сочетанием символов #13#10, а пробел - #32.

Глава 3. Программная реализация алгоритма LCS на языке программирования

3.1 Выбор языка программирования

В предыдущей главе был рассмотрен алгоритм LCS и написан в псевдокоде алгоритм решения поставленной задачи. Данная глава посвящена обоснованию выбора языка программирования и программной реализации рассмотренного в предыдущей главе алгоритма. Итоговая программа должна представлять собой консольное приложение для Win32, ориентирована на использование в составе системы автоматизированного тестирования (САТ).

Для реализации данного алгоритма был выбран язык программирования Pascal. Причина такого выбора заключается в том, что он был изначально разработан в учебных целях, прост и эффективен. Тем не менее, поскольку данное приложение предназначено для работы под управлением операционной системы Microsoft Windows Advanced Server 2003 - в NT-совместимой операционной системе, а разработанное на языке Pasсal приложение предназначено для MS DOS, таким образом, при работе программы в Windows его производительность существенно снизится. Поэтому было решено программы выполнять на Pascal, а затем откомпилировать программу в Delphi for Microsoft Win32. Это позволило, с одной стороны, не уходить от простого и эффективного языка программирования Pascal, и в то же время создать Win32-совместимое консольное приложение, которое способно работать в составе САТ без ухудшения ее производительности.

3.2 Реализация алгоритма на языке Pascal

Перевод программы из псевдокода на язык программирования подразумевает довольно глубокие знания данного языка. Вот еще одна причина, по которой был выбран язык Pascal. Поскольку первый вариант алгоритма LCS заведомо более требователен к ресурсам, для программной реализации был избран второй вариант. Поскольку данная программа работает только с файлами и строками, никакие вспомогательные модули, за исключением модуля System, в ней не использовались. Это значительно упростило написание программы. Рассмотрим базовые процедуры и функции, которые использовались при написании программы.

Процедуры read и write используются для ввода и вывода данных.

Fillchar - процедура, которая заполняет заданную область памяти определенными значениями (типа byte или char). В данном случае, она заполняет нулями массивы l1, l2 при инициализации программы, а затем на каждом шаге работы алгоритма LCS заполняет нулями массив l2.

Eof - функция, которая определяет, достигнут ли конец файла.

Upcase - функция, приводящая символ к верхнему регистру.

Assign - процедура, предназначенная для связывания файловой переменной с файлом на диске.

Reset - процедура, открывающая файл для чтения.

Rewrite - процедура, открывающая файл для записи. Если файла не существует, то она создает его.

Close - процедура, закрывающая открытый файл.

InputFile - пользовательская процедура. Данная процедура преобразует файл в последовательность (строку), которая не содержит пробелов, символов перевода строки и комментариев к программе (текста заключенного в фигурные скобки).

Max - пользовательская процедура. Данная процедура добавлена в программу, т.к. в языке Паскаль нет встроенной процедуры нахождения максимального значения. То есть данная процедура для двух элементов типа Longint находит и передает максимальный.

Min - пользовательская процедура. Аналогична предыдущей процедуре, за исключением того, что данная находит не максимальный, а минимальный элемент.

Рассмотрим более детально структуру программы и основные моменты ее реализации.

В скобках указаны операторы, процедуры и функции, с помощью которых реализовывался алгоритм на языке Pascal.

Сначала открываются входные файлы (два) для чтения (assign, reset), они считываются и преобразовываются в строки, используя процедуру Iputfile. В процедуре Iputfile файл считывается посимвольно (While not eof, read), а затем на каждом шаге символ приводится к верхнему регистру. Затем следует проверка на равенство символу “{“. Если (If) равенство выполняется, то это значит, что начался комментарий. Следовательно, далее считываются подряд все символы, пока (While) не встречается символ “}”. Если (If) текущий символ равен символу “}”, то это означает, что комментарий закончился. Проверяется (If) не является ли текущий символ пробелом или символом перевода строки. Если он таким не является, то символ добавляется к последовательности (строке).

Далее с помощью процедуры Fillchar инициализируются начальные значения переменных, то есть заполняются нулями массивы l1, l2. Данные прочитаны, теперь можно перейти непосредственно к реализации алгоритма LCS.

Алгоритм реализован с помощью двух вложенных циклов For. Затем проверяются на равенство текущие символы (If) и по алгоритму, описанному выше (второй вариант алгоритма LCS):

Если они равны (If), то L2[j]<L1[j-1]+1.

Иначе L2[j]<max(L1[j],L2[j-1]).

Далее массив l2 сохраняется в массиве l1, и заполняется нулями. Заполняется он, только если текущая строка не является последней. Это реализация сделано, чтобы избавиться от двумерного массива. То есть хранятся только текущая (l2) и предыдущая строки (l1).

После выполнения алгоритма LCS необходимо получить результат, степень совпадения исходных файлов в процентах, и вывести их в файл вывода. Для этого длину максимальной подпоследовательности делим на длину меньшего файла (Min). Открываем для записи файл вывода (assign, rewrite) и записываем в него полученный результат (полный текст программы см. в Приложении).

Глава 4. Производительность и быстродействие

тестирование алгоритм подпоследовательность

Время выполнения алгоритма LCS достаточно легко рассчитывается, поскольку он управляется двумя вложенными циклами: внешний выполняет n итераций, а внутренний - m. Поскольку на выполнение каждого условия Если и каждого присваивания требуется порядка О(1) операций, алгоритм имеет вычислительную сложность порядка O(mn). Таким образом, методика динамического программирования может применяться в задачах поиска наиболее длинной общей подпоследовательности, значительно повышая производительность по сравнению с силовым решением этой задачи за экспоненциальное время.

Как уже было упомянуто, данная программа будет использоваться в составе САТ. Основное требование, накладываемое на данное приложение - его быстродействие. Для определения быстродействия были подготовлены 8 файлов различного размера, которые содержали текст программ на языке Pascal. Далее для проверки каждый из файлов был продублирован, а после этого в каждый файл случайным образом были внесены изменения. Это было сделано, чтобы внести некоторые отличия в содержимое тестовых файлов. Их размеры занесены в таблицу (см. Таблицу 4.1.). Программа, откомпилированная компилятором Pascal 7.1, работала достаточно долго. Уже на файлах, близких к 5 Кб, она показывала не очень хорошие результаты. Время затрачиваемое на анализ двух файлов превышало 5 с. Поэтому тестирование проводилось с использованием программы, откомпилированной в Delphi.

Таблица 4.1 Размер тестовых файлов

№ тесового файла	Размер файла, байт
1	520
2	930
3	3050
4	5700
5	7850
6	10500
7	13000
8	14200

Для определения времени выполнения программы необходимо засекать время начала и окончания ее работы. С этой целью в программу были добавлены необходимые переменные и команды:

time1,time2:TDateTime; - в раздел описаний переменных

time1:=time(); - в начало программы

time2:=time(); - в конец программы перед закрытием файла вывода

writeln((time2-time1)*(24*60*60*1000):0:6);

Тестирование на каждом тесте повторялось по два раза, после чего в качестве результата тестирования выбиралось среднее значение. В данных тестах использовались файлы с текстами программ, которые имеют степень совпадения 92-98%. Результаты тестирования представлены в таблице 4.2.

Таблица 4.2 Зависимость времени выполнения программы от размера файла

№	Размер, байт	Время выполнения, мс
1	520	16
2	930	31
3	3050	63
4	5700	203
5	7850	328
6	10500	800
7	13000	1390
8	14200	1719

График зависимости времени сравнения двух файлов от их размера изображен на рис 4.1.



Из результатов тестирования видно, что программа работает довольно быстро, 2 файла размером по 14 Кб она обработала менее чем за 2 секунды. Учитывая то, что файлы, с которыми предполагается работать программе, редко будут превышать 1 Кб, данные результаты являются хорошими. Однако, следует отметить, что в данном случае проверялись файлы с большой степенью совпадения (92-98%). Для полноты эксперимента проверить время выполнения программы на полностью идентичных файлах и на полностью различных. Для решения этой задачи было сгенерировано два файла. Первый содержал 10240 единиц, второй - 10240 двоек. В первом случае проверялось время выполнения двух одинаковых файлов, во втором - двух разных. Первое тестирование прошло за 0,7 с, а второе за 1 с. Т.е. время увеличилось примерно в 1,4 раза. Это связано с тем, что во втором случае процедура поиска максимального элемента выполняется на каждом проходе цикла. Поэтому операций сравнения при полностью различных файлах производится в 2 раза больше. К этому можно добавить также и еще один вход в функцию, хотя в первом случае производится операция сложения, а во втором нет.

Таким образом, худший случай сравнительного анализа содержимого двух текстовых файлов будет при полностью различных файлах. Для подтверждения результата тестирование было произведено еще раз, но на этот раз размер файла был равен 14,5 Кб. Результаты оказались практически идентичными.

Другими словами, время работы программы в худшем случае можно получить из таблицы 4.2, содержащей время работы программы для "похожих" файлов, умножив соответствующие значения на 1.4.

Полученные в результате тестирования результаты для худшего и лучшего случаев представлены на рис 4.2.

Полученная программа обладает отличным быстродействием и должна полностью справляться с поставленной перед ней задачей. Даже если Размер анализируемых файлов составляет 1-2 Кб и их количество достаточно велико (15-20), то, тем не менее, все проверки то все проверки выполнятся за 1-2 с.

Тестирование данной программы было произведено на компьютере, который имеет не очень высокие на сегодняшний день характеристики: Частота процессора 2000 МГц, 512 Мб ОЗУ. Такой компьютер несложно найти в любом учебном заведении. В составе САТ она будет работать на более совершенном компьютере, поэтому полученные здесь результаты можно считать обоснованными.

Заключение

Итак, в данной курсовой исследована возможность использования алгоритма поиска максимальной подпоследовательности (Longest Common Subsequence) для оценки степени совпадения решений задач в САТ. Также было проведено подробное изучение и программная реализация самого алгоритма LCS. Довольно тщательно проведена оценка быстродействия не только теоретически, но и практически. При определении быстродействия были учтены как лучший, так и худший случай. Исходя из параметров быстродействия данной программы, было решено испробовать ее в составе САТ для проверки решений задач по информатике.

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

В дальнейшем планируется усовершенствовать программу таким образом, что выше перечисленные действия не смогут повлиять на степень совпадения решений. Также большое внимание уделяется тому, чтобы поддерживалась высокая производительность программы.

В данный момент ведется подготовка программы к использованию в составе САТ.

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

Список использованной литературы

1. Гудрич М. Т., Тамассия Р. Структуры данных и алгоритмы Java; Пер. с англ. А. М. Чернухо. - Мн.: Новое издание, 2003. - 671 с.

2. Фаронов В. В. Delphi 2005. Язык, среда, разработка приложений. - СПб.: Питер, 2005. - 560 с.

3. Федоров А. Borland Pascal в среде Windows. - Киев: Диалектика, 1993. - 656 с.

Приложение

Program LCS;

{$APPTYPE CONSOLE}

Uses

SysUtils;

{Четыре верхние строки отсутствуют в программе на Pascal-е}

Var

i,j,m,n:longInt;

a,b:array [0..15000] of char;

l1,l2:array [-1..15000] of integer;

c:char;

h:real;

Procedure Inputfile(Var a:array of char; var n:longint);

Begin

i:=0;

Fillchar(a,sizeof(a),#0);

While not eof(input) do begin

read(c); c:=upcase(c);

If c='{' then begin

while c<>'}' do read(c);

read(c);

c:=upcase(c);

end;

if (c<>#13)and(c<>#10)and(c<>' ') then begin

inc(i);

a[i]:=c;

end;

end;

n:=i+1;

end;

Function Max(x,y:integer):integer;

Begin

if x>y then max:=x else max:=y;

end;

Function Min(x,y:integer):integer;

Begin

if x<y then min:=x else min:=y;

end;

Begin

assign(input,'input1.txt');

Reset(input);

fillchar(l1,sizeof(l1),0);

fillchar(l2,sizeof(l2),0);

inputfile(a,n);

close(input);

assign(input,'input2.txt');

Reset(input);

inputfile(b,m);

close(input);

For i:=0 to n-1 do begin

for j:=0 to m-1 do begin

if a[i]=b[j] then l2[j]:=l1[j-1]+1

else l2[j]:=max(l1[j],l2[j-1]);

end;

l1:=l2;

if i<>n-1 then fillchar(l2,sizeof(l2),0);

end;

h:=(l2[m-1])/(min(m,n)/100);

assign(output,'output.txt');

Rewrite(output);

Writeln(h:0:0);

close(output);

End.

Размещено на Allbest.ru