Навигатор > Программирование и Информатика > Курсовые работы > Технология программирования...

Технология программирования

	Скачать курсовую: Технология программирования

План курсового проекта

Введение

1.Содержание и этапы выполнения

2.Технический проект

3.Общие требования

Приложение 1. Геометрический редактор плоских деталей

Приложение 2. Система триангуляции многоугольных областей

Приложение 3. Система минимизации пути режущего инструмента при раскрое

Приложение 4. Структура данных файла геометрической информации

Приложение 5. Интерактивный корректировщик текста

Приложение 6. Интерактивный форматировщик текста

Литература

ВВЕДЕНИЕ

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

В соответствии с рабочей программой дисциплины курсовая работа выполняется в течение второго и третьего семестров в процессе проведения лабораторных занятий, связанных с разработкой программного обеспечения конкретной проблемы, а также в период вычислительной практики (табл.1). Проблемы, разрабатываемые на лабораторных занятиях и в ходе курсового проектирования, представлены в приложениях в виде постановки задачи и отдельных частей технического задания согласно ГОСТ 19.201-78.

Таблица 1 Перечень лабораторных работ и отрабатываемых на них вопросов

----T-----------------------T----------------------------------------¬
¦   ¦ Наименование лаб.раб. ¦     Отрабатываемые  вопросы            ¦
+---+-----------------------+---T------------------------------------+
¦ 1 ¦Использование абстрак- ¦ 1 ¦Разработка спецификаций типов данных¦
¦   ¦ций в разработке прог- ¦   ¦для многооконного интерфейса        ¦
¦   ¦раммного обеспечения   +---+------------------------------------+
¦   ¦                       ¦ 2 ¦Разработка спецификаций типов данных¦
¦   ¦                       ¦   ¦для заданной проблемы               ¦
¦   ¦                       +---+------------------------------------+
¦   ¦                       ¦ 3 ¦Разработка спецификации алгоритма   ¦
¦   ¦                       ¦   ¦проблемы                            ¦
+---+-----------------------+---+------------------------------------+
¦ 2 ¦Анализ требований на   ¦ 1 ¦Анализ требований из методических   ¦
¦   ¦программное обеспечение¦   ¦указаний на лабораторный практикум  ¦
+---+-----------------------+---+------------------------------------+
¦ 3 ¦Разработка спецификаций¦ 1 ¦Разработка функциональной специфика-¦
¦   ¦на программное обеспе- ¦   ¦ции программы                       ¦
¦   ¦чение                  ¦   ¦                                    ¦
+---+-----------------------+---+------------------------------------+
¦ 4 ¦Проектирование програм-¦ 1 ¦Уточнение спецификаций типов данных ¦
¦   ¦много обеспечения      +---+------------------------------------+
¦   ¦                       ¦ 2 ¦Разработка модульной структуры      ¦
+---+-----------------------+---+------------------------------------+
¦ 5 ¦Программирование       ¦ 1 ¦Программирование модулей            ¦
¦   ¦                       +---+------------------------------------+
¦   ¦                       ¦ 2 ¦Компоновка всей программы           ¦
+---+-----------------------+---+------------------------------------+
¦ 6 ¦Тестирование и отладка ¦ 1 ¦Индивидуальное тестирование модулей ¦
¦   ¦программного обеспече- +---+------------------------------------+
¦   ¦ния                    ¦ 2 ¦Интегральное тестирование программы ¦
+---+-----------------------+---+------------------------------------+
¦ 7 ¦Сопровождение програм- ¦ 1 ¦Адаптация программы                 ¦
¦   ¦много обеспечения      +---+------------------------------------+
¦   ¦                       ¦ 2 ¦Усовершенствование программы        ¦
+---+-----------------------+---+------------------------------------+
¦ 8 ¦Разработка программной ¦ 1 ¦Техническое задание                 ¦
¦   ¦документации           +---+------------------------------------+
¦   ¦                       ¦ 2 ¦Программа и методика испытаний      ¦
¦   ¦                       +---+------------------------------------+
¦   ¦                       ¦ 3 ¦Программная документация согласно   ¦
¦   ¦                       +---+------------------------------------+
¦   ¦                       ¦ 4 ¦техническому заданию                ¦
L---+-----------------------+---+-------------------------------------

Допускается проведение лабораторных занятий и разработка курсовой работы группой до 5 человек.

1.Содержание и этапы выполнения

Курсовая работа должна включать оттестированное программное обеспечение, соответствующее техническому заданию, и пояснительную записку, включающую:

- техническое задание (ГОСТ 19.201-78);
- технический проект;
- программу и методику испытаний (ГОСТ 19.301-79),

а также программную документацию:

- тексты программ (ГОСТ 19.401-78);
- описание программы (ГОСТ 19.404-78);
- пояснительная записка (ГОСТ 19.404-79);
- описание применения (ГОСТ 19.502-78);
- руководство системного программиста (ГОСТ 19.503-79);
- руководство программиста (ГОСТ 19.504-79);
- руководство оператора (ГОСТ 19.505-79),

состав которой определяется руководителем курсового проектирования и указывается в техническом задании.

Таблица 2 Этапы и сроки выполнения курсовой работы

------------------------------------------T--------------------------¬
¦ Этапы выполнения                        ¦          Сроки           ¦
+-----------------------------------------+--------------------------+
¦ Технический проект                      ¦ 15-17 недели II семестра ¦
+-----------------------------------------+--------------------------+
¦ Утверждение технического задания и      ¦   4 неделя III семестра  ¦
¦ программы и методики испытаний          ¦                          ¦
+-----------------------------------------+--------------------------+
¦ Приемка программного обеспечения        ¦ 12-14 недели III семестра¦
+-----------------------------------------+--------------------------+
¦ Защита курсовой работы                  ¦ 15-17 недели III семестра¦
L-----------------------------------------+---------------------------

2.ТЕХНИЧЕСКИЙ ПРОЕКТ

Согласно ГОСТ 19.102-77 "Стадии разработки" технический проект предполагает выполнение следующих работ: уточнение струтуры входных и выходных данных; разработку алгоритма решения задачи; определение формы представления входных и выходных данных; определение семантики и синтаксиса языка; разработку структуры программы; окончательное определение конфигурации технических средств.

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

3.ОБЩИЕ ТРЕБОВАНИЯ

Разрабатываемое ПО должно работать в многооконном графическом режиме и поддерживать работу как клавиатуры, так и манипулятора типа "мышь". Рекомендации по разработке графического пользовательского интерфейса приведены в [1].

Программная документация, входящая в состав курсовой работы, должна соответствовать требованиям Единой системы программной документации (ЕСПД) [2]. В [1] приводятся выдержки из основных стандартов ЕСПД.

ПРИЛОЖЕНИЕ 1 ГЕОМЕТРИЧЕСКИЙ РЕДАКТОР ПЛОСКИХ ДЕТАЛЕЙ

Постановка задачи

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

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

<ДЕТАЛЬ>..................:=<список контуров>
<список контуров>.........:=<наружный контур>
:=<наружный контур><список внутренних
контуров>
<КОНТУР>..................:=<замкнутый список ребер>
<СЕГМЕНТ>.................:=<ребро>
:=<разомкнутый список ребер>
<РЕБРО>...................:=<две граничные точки>
<ГРАНИЧНАЯ ТОЧКА>.........:=<две координаты>
<список ребер>............:=<последовательность непересекающихся ребер,
в котором любые два соседних в
последовательности ребра имеют общую
граничную точку>
<замкнутый список ребер>..:=<кольцевой список ребер>
<разомкнутый список ребер>:=<линейный список ребер>

К основным функциям редактирования можно отнести следующие [3]:

- перенос объекта изображения в другое место. Это действие связано с выполнением поступательного движения;

- копирование объекта изображения в другом месте. Функция копирования подобна функции переноса, но при этом положение копируемого объекта не изменяется;

- поворот объекта. Это преобразование вращения, при котором объект поворачивается на заданный угол относительно исходной ориентации;

- зеркальное отображение объекта. Выполняется относительно заданной плоскости;

- уничтожение объекта изображения. Эта функция вызывает удаление выбранного объекта изображения с экрана;

- изменение масштаба. Выбранный объект изображения можно увеличить или уменьшить с заданными масштабными коэффициентами по координатным осям.

Многие из операций редактирования связаны с двумерными преобразованиями графических объектов. Геометрические преобразования на плоскости используются для перемещения и модификации объектов.

Преобразования представлены в матричной форме с использованием однородных координат. Декартовы координаты точки (x,y) на плоскости заменятся ее однородными координатами (x,y,1).

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

К основным (элементарным) преобразованиям на плоскости относятся следующие [4]:

- преобразование переноса на вектор Т (tx,ty);
- преобразование поворота относительно начала координат на угол al;
- преобразование масштаба на вектор Е (ex,ey),
- преобразования зеркальной симметрии относительно координатных осей.

Матрицы основных двумерных геометрических преобразований

---------------------------------------------------------------------¬
¦                                                                    ¦
¦           ¦ 1   0   0 ¦                ¦ cos(al)  sin(al)  0 ¦     ¦
¦    M(T) = ¦ 0   1   0 ¦     M(R(al)) = ¦-sin(al)  cos(al)  0 ¦     ¦
¦           ¦ tx  ty  1 ¦                ¦    0        0     1 ¦     ¦
¦                                                                    ¦
¦                                                                    ¦
¦        ¦ ex   0  0 ¦             ¦-1  0  0 ¦            ¦ 1  0  0 ¦¦
¦ M(E) = ¦  0  ey  0 ¦   M(S(x)) = ¦ 0  1  0 ¦  M(S(y)) = ¦ 0 -1  0 ¦¦
¦        ¦  0   0  1 ¦             ¦ 0  0  1 ¦            ¦ 0  0  1 ¦¦
¦                                                                    ¦
L---------------------------------------------------------------------

Преобразование вектора P(x,y,1) в вектор P'(x',y',1) производится умножением вектора-строки на матрицу M соответствующего преобразования

                         ¦ a  b  c ¦
P' = P*M = ¦ x  y  1 ¦ * ¦ d  e  f ¦ = ¦(ax+dy+g) (bx+ey+h) (cx+fy+i)¦,
                         ¦ g  h  i ¦

где выражения (ax+dy+g) и (bx+ey+h) соответствуют компонентам x' и y'вектора P'.

Рассмотрим получение матрицы сложного преобразования, осуществляющего поворот на угол al относительно произвольной точки A (xa,ya).

Матрица этого преобразования может быть получено с помощью последовательности элементарных преобразований:

- перенос на вектор (-xa,-ya) для совмещения центра вращения с началом координат;
- поворот на угол al относительно начала координат;
- обратный перенос на вектор (xa,ya).

Суммарная матрица преобразования в данном случае будет получена из выражения

         ¦ 1   0   0 ¦   ¦ cos(al)  sin(al)  0 ¦   ¦  1   0  0 ¦
     M = ¦ 0   1   0 ¦ * ¦-sin(al)  cos(al)  0 ¦ * ¦  0   1  0 ¦
         ¦-xa -ya  1 ¦   ¦    0        0     1 ¦   ¦ xa  ya  1 ¦

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

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

Выходная информация должна формироваться в виде файла геометрической информации (Приложение 4). Если в такой файл выводится информация о размещении, то первой деталью должен быть прямоугольник, внутри которого расположены детали.

Естественно, что файл геометрической информации может использоваться редактором в качестве входной информации.

Техническое задание

ВВЕДЕНИЕ

Наименование - геометрический редактор плоских деталей (далее просто редактор).

Краткая характеристика - двумерный геометрический редактор с локальной базой сформированных контуров.

1.ОСНОВАНИЕ ДЛЯ РАЗРАБОТКИ

Задание преподавателя для проведения лабораторных занятий и выполнения курсовой работы.

2.НАЗНАЧЕНИЕ РАЗРАБОТКИ

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

3.ТРЕБОВАНИЯ К ПРОГРАММЕ

3.1.Требования к функциональным характеристикам

3.1.1.Редактор должен работать в многооконном графическом режиме и поддерживать работу как клавиатуры, так и манипулятора типа "мышь".

3.1.2.Пользователь, по своему желанию, должен иметь возможность установки масштабного поля для каждого окна.

3.1.3.В одном окне возможна работа с несколькими деталями.

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

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

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

3.1.5.Редактор должен обеспечивать расчет следующих характеристик:

- для точки:
- координаты в принятом масштабном поле;
- для ребра:
- длина;
- угол наклона;
- для детали (контура):
- периметр;
- площадь;
- положение центра масс;
- положение центра давления;
- момент инерции относительно произвольной точки.

3.1.6.Информация о сформированной детали может быть сохранена в локальной базе данных редактора.

3.1.7.Должен быть обеспечен графический просмотр базы данных с возможностью удаления из нее или копирования в активное окно указанной детали.

3.1.8.Информация о сформированной детали может быть сохранена в форме выходного файла следующей структуры:

3.1.9.Редактор должен уметь считывать геометрическую информацию из файла описанной структуры.

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

3.2.Требования к надежности

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

3.2.2.Программа должна обеспечивать контроль входной и выходной информации в форме файлов геометрической информации.

3.4.Требования к составу и параметрам технических средств

3.4.1.Программное обеспечение разрабатывается для персональной вычислительной техники типа не ниже IBM PC-386 со следующими характеристиками:

- объем ОЗУ не ниже 1 Mb;
- графический адаптер SVGA;
- манипулятор типа "мышь".

3.4.2.ЭВМ должна работать под управлением операционной системы не ниже чем MS-DOS 5.0.

3.5.Требования к информационной и программной совместимости

3.5.1.Требование информационной совместимости должно быть обеспечено работой с файлами геометрической информации определенной структуры в качестве входной и выходной информации.

ПРИЛОЖЕНИЕ 2 СИСТЕМА ТРИАНГУЛЯЦИИ МНОГОУГОЛЬНЫХ ОБЛАСТЕЙ

Постановка задачи

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

Многочисленные методы построения разбиений областей с геометрической точки зрения подразделяются на три основных класса [4,5]:

- построение разбиения, осуществляемого подходящим преобразованием отображения разбиения области с геометрически простой формой;

- построение разбиения, осуществляемого подходящим преобразованием уже существующего разбиения;

- прямое, элемент за элементом, построение разбиения, начиная с задания распределения точек в области или на границе.

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

Разрабатываемое ПО должно использовать файл геометрической информации (Приложение 4) в качестве входной информации об области разбиения.

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

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

Техническое задание

ВВЕДЕНИЕ

Наименование - система трангуляции многоугольных областей (далее просто триангулятор).

Краткая характеристика - двумерный триангулятор с локальной базой сформированных сеток деталей.

1.ОСНОВАНИЕ ДЛЯ РАЗРАБОТКИ

Задание преподавателя для проведения лабораторных занятий и выполнения курсовой работы.

2.НАЗНАЧЕНИЕ РАЗРАБОТКИ

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

3.ТРЕБОВАНИЯ К ПРОГРАММЕ

3.1.Требования к функциональным характеристикам

3.1.2.Пользователь, по своему желанию, должен иметь возможность установки масштабного поля для каждого окна.

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

3.1.4.Программа должна включать, по желанию пользователя, минимизацию разности номеров вершин треугольников.

3.1.5.Информация о сформированной сети треугольников может быть сохранена в локальной базе данных триангулятора.

3.1.6.Должен быть обеспечен графический просмотр базы данных с возможностью удаления из нее или копирования в активное окно указанного разбиения.

3.1.7.Информация о сформированном разбиении может быть сохранена в форме выходного файла геометрической информации следующей структуры:

3.1.8.Триангулятор может использовать в качестве входной информации файл геометрической информации о детали или об уже имеющемся разбиении.

3.1.9.Программа должна обеспечивать возможность просмотра выхоного файла.

3.2.Требования к надежности

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

3.4.Требования к составу и параметрам технических средств

- объем ОЗУ не ниже 1 Mb;
- графический адаптер SVGA;
- манипулятор типа "мышь".

3.4.2.ЭВМ должна работать под управлением операционной системы не ниже чем MS-DOS 5.0.

3.5.Требования к информационной и программной совместимости

ПРИЛОЖЕНИЕ 3 СИСТЕМА МИНИМИЗАЦИИ ПУТИ РЕЖУЩЕГО ИНСТРУМЕНТА ПРИ РАСКРОЕ

Постановка задачи

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

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

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

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

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

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

Техническое задание

ВВЕДЕНИЕ

Наименование - система минимизации пути режущего инструмента при раскрое листовых материалов (далее просто минимизатор).

Краткая характеристика - двумерный минимизатортор с локальной базой сформированных маршрутов резки.

1.ОСНОВАНИЕ ДЛЯ РАЗРАБОТКИ

Задание преподавателя для проведения лабораторных занятий и выполнения курсовой работы.

2.НАЗНАЧЕНИЕ РАЗРАБОТКИ

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

3.ТРЕБОВАНИЯ К ПРОГРАММЕ

3.1.Требования к функциональным характеристикам

3.1.2.Пользователь, по своему желанию, должен иметь возможность установки масштабного поля для каждого окна.

3.1.3.Минимизатор должен обеспечивать нахождение минимального пути с проходом только один раз через каждое ребро каждого многоугольного контура детали в области размещения.

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

3.1.5.Информация о размещении контуров и сформированном маршруте может быть сохранена в локальной базе данных минимизатора.

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

3.1.7.Информация о размещении и сформированном маршруте может быть выведена в форме файла геометрической информации следующей структуры:

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

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

3.1.10.Программа должна обеспечивать просмотр выходного файла.

3.2.Требования к надежности

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

3.4.Требования к составу и параметрам технических средств

- объем ОЗУ не ниже 1 Mb;
- графический адаптер SVGA;
- манипулятор типа "мышь".

3.4.2.ЭВМ должна работать под управлением операционной системы не ниже чем MS-DOS 5.0.

3.5.Требования к информационной и программной совместимости

ПРИЛОЖЕНИЕ 4 СТРУКТУРА ДАННЫХ ФАЙЛА ГЕОМЕТРИЧЕСКОЙ ИНФОРМАЦИИ

Файл должен иметь следующую структуру (см.рис):

- информационная часть;

- дескриптор деталей;

- дескриптор контуров;

- дескриптор ребер;

- дескриптор вершин;

Информационная часть должна содержать следующую информацию:

- количество деталей в соответствующем дескрипторе;

- количество контуров в соответствующем дескрипторе;

- количество ребер в соответствующем дескрипторе;

- количество вершин в соответствующем дескрипторе.

Каждая деталь должна быть представлена в своем дескрипторе:

- количеством контуров детали;

- списком контуров детали (номеров контуров в дескрипторе; первым всегда указывается номер наружного контура детали).

Каждый контур должен быть представлен в своем дескрипторе:

- количеством ребер контура;

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

Каждое ребро должно быть представлено в своем дескрипторе номерами начальной и конечной вершин в их дескрипторе.

Каждая вершина должна быть представлена в своем дескрипторе двумя координатами (x,y).

ПРИЛОЖЕНИЕ 5 ИНТЕРАКТИВНЫЙ КОРРЕКТИРОВЩИК ПРАВОПИСАНИЯ

Постановка задачи

Корректировщик правописания представляет собой программу, которая получает в качестве входных данных словарь и текстовый файл и исправляет затем в текстовом файле ошибки правописания. Программа работает, отыскивая каждое слово текстового файла в словаре. Если слово отсутствует в словаре, то оно может содержать или же не содержать ошибку. В обоих случаях программа отражает слово на экране с объемом окружающего текста, достаточным для того, чтобы показать контекст, в котором оно находится. Пользователь может предпринять несколько действий по исправлению ошибки: перепечатать неверно напечатанное слово, заставить программу ввести его без изменений и включить это слово в словарь. Результатом работы корректировщика является исправленный текст и, возможно, обновленный словарь.

Корректировщик правописания должен иметь достаточно эффективную реализацию по двум соображениям. Во-первых, программа выполняет большое количество вычислений, поэтому неэффективная реализация сделает ее непрактичной. Во-вторых, поскольку программа является интерактивной, работа пользователя за терминалом должна быть максимально облегчена. Основная проблема заключается в поиске слов в словаре. Эта операция выполняется для каждого слова во входном тексте. Для удовлетворения требования по эффективности нам необходим алгоритм просмотра, более быстрый, чем прстой линейный поиск в словаре. Примеры алгоритмов просмотра с приемлемой эффективностью есть (1) бинарный поиск по упорядоченному списку, (2) просмотр упорядоченного бинарного дерева и (3) хэширование.

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

Этот набор требований к программе является неполным. Для словаря может понадобиться дополнительная информация. Вы должны также принять решение о возможностях, предоставляемых программой, и так же подробно проанализировать обработку входных символов. Можно вывести ряд предположений: 1.Символьная обработка. Вы должны определить то, каким образом программа обращается с символами пунктуации, например с кавычками, со словами или акронимами, включающими цифры, дефисами, стандартными сокращениями ("и т.д.") и так далее. Например, вы можете рассматривать дефисы как ограничители, поскольку большинство слов с дефисами являются сочетаниями из нескольких распознаваемых подчастей.

2.Интерфейс с пользователем. Интерфейс с пользователем в интерактивной программе является весьма важной частью, которая должна быть тщательно продумана. Необходимо, чтобы программой можно было легко пользоваться. На этот счет имеются следующие соображения: а) возложите на пользователя указание имен для исходного и результирующего файлов - как для текста, так и для словаря; б) дайте возможность пользователю исправить несколько текстовых файлов без выхода из программы корректировщика; в) запрашивайте у пользователя ввод возможных правильных ответов при отображении неверно заданного слова; г) реализуйте команду help ("вспомогательная информация"), описывающую эффект каждого из вышеописанных ответов подробно.

ПРИЛОЖЕНИЕ 6 ИНТЕРАКТИВНЫЙ ФОРМАТИРОВЩИК ТЕКСТА

Постановка задачи

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

По умолчанию строка должна включать 70 символов, за исключением символа перевода строки, и 60 строк в странице. Пользователь должен иметь возможность переустановки этих значений.

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

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

Л И Т Е Р А Т У Р А

1.Курсовое проектирование. Методические указания для студентов специальности 220400. Электронная версия.

2.Единая система программной документации.- М.: Изд-во стандартов, 1985.- 128 с.

3.Гардан И., Люка М. Машинная графика и автоматизация конструирования.- М.: Мир, 1987.- 272 с.

4.Математика и САПР: В 2-х кн. Кн.1.- М.: Мир, 1988.- 204 с. Кн.2.М.: Мир, 1989.- 264 с.

5.Шикин Е.В., Боресков А.В., Зайцев А.А. Начала компьютерной графики.М.: ДИАЛОГ-МИФИ, 1993.- 138 с.

6.Липский В. Комбинаторика для программистов.- М.: Мир, 1988. 213 с.

Поиск