Теория множеств

Анотація

Даний дипломний проект присвячена розв’язанню основоположної задачі теорії множин, розв’язання якої необхідне для доведення теорем вищої математики. Дана програма розроблена в середовищі Delphi 7 на мові програмування Delphi.

Робота викладена на 52 сторінках друкованого тексту з 27 рисунками, 7 таблицями та 4 додатками.

Аннотация Даный дипломный проект посвящен решению основоположной задачи теории множеств, решение которой необходимо для доведения теорем высшей математики. Данная программа разработана в среде Delphi 7 на языке программирования Delphi.

Работа изложена на 52 страницах печатного текста с 27 рисунками, 7 таблицами и 4 приложениями.

Abstract

This term paper is sanctified to the decision of fundamental task of theory of sets, the decision of which is needed for proving of theorems of higher mathematics. This program is worked out in the environment of Delphi 7 in programming of Delphi language. Work is expounded on 52 pages of the printed text with 27 pictures, 7 tables and 4 apendixes.

A term paper is written with Russian.

Содержание Введение

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

1.1 Анализ предметной области

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

2. Проект программы

2.1 Эскизный проект

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

2.3 Рабочий проект

3. Результаты разработки

Выводы

Приложение

Целью данной работы является решение следующей задачи: проверить в заданном множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

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

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

1.1 Анализ предметной области

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

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

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

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

Наглядно обосновать и проверить для заданного множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB. Задачу решить для нескольких множеств. Представить результаты на экране.

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

2. Проект программы

2.1 Эскизный проект

Определение входных данных

Программе необходимы следующие входные данные:

имя файла исходных данных. Задано в программе data.txt.

Количество элементов множества и координаты точек множества. Вводятся из файла или вручную с клавиатуры пользователем. Каждой точек присваивается порядковый номер.

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

Определение выходных данных

На экран выводятся координаты точек множества, каждая координата в отдельной ячейке. Для каждой точки выводится порядковый номер. Для каждой точки выводится номер точки с которой они образуют искомую прямую. Если прямая не может быть образовано выводится знак «-» .

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

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

Контекстная диаграмма

Рис. 2.1- Контекстная диаграмма

Таблица 2.1. Словарь данных контекстной диаграммы

Диаграмма состояний

Рис. 2.2- Диаграмма состояний

Таблица 2.2. Словарь данных диаграммы состояний

Условия перехода

После запуска программы доступно состояние Ввод данных (0).

Разработка интерфейса

Состояние 0. Ввод данных.

Рис. 2.3-Интерфейс состояния 0.

1. ввод координат точек из файла и переход в состояние 1;

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

3. Вызов справки;

4. Выход из программы

Состояние 1. Поиск

Рис. 2.4-Интерфейс состояния 1.

При нажатии на кнопку Найти (2) выполняется поиск для каждой точки введенной в таблице исходных данных (1) точки, удовлетворяющей постановке задачи. После поиска переход в состояние 2.

В таблице (1) доступно редактирование элементов

Состояние 2. Выбор действия

Рис. 2.5-Интерфейс состояния 2.

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

При нажатии кнопки «Изображение» в правой части экрана согласно координатам прорисовываются точки множества.

Состояние 3. Изображение

Рис. 2.6-Интерфейс состояния 3.

В поле (2) вводится номер точки (номер см. в таблице слева).

По нажатию кнопки (3) прорисовывается прямая (1). В поле справа от (2) выводит номер второй точки для построения прямой.

Логическая модель данных

Рис. 2.7 — Схема данных

На рис. 2.7 показаны основные блоки хранения данных и перемещение данных между ними.

Описание элементов

Файл data. txt

множество теорема математика программирование

Здесь

(N) — количество строк матрицы

(x_i; y_j) — координаты точки

Массив координат точек — одномерный массив размерностью 100, каждый элемент которого содержит координату точки.

Таблица вывода множества — элемент интерфейса, служит для вывода, хранения и редактирования координат точек множества, их номеров и результатов решения.

Номер точки A — порядковый номер точки в таблице вывода, соответствует индексу точки в массиве координат. Это индекс первой точки для построения прямой.

Номер точки B — порядковый номер точки в таблице вывода, соответствует индексу точки в массиве координат. Это индекс второй точки для построения прямой.

Поле ввода точки A — Элемент интерфейса, куда пользователь вводит номер точки, для которой он хочет построить прямую.

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

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

Физическая модель данных

Рис. 2.8 Физическая модель данных

На рис. 2.8 показано физическая модель данных программы.

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

t :real [1.100] - переменная типа одномерный массив, размером 100 каждый элемент которого является составным типом данных, включает две переменные x, y целого типа, для работы с координатами точек множества.;

i:integer — индекс первой точки для построения прямой в массиве. t

j:integer — индекс второй точки для построения прямой в массиве. t

EditPointNumber — переменная типа поле ввода строки для ввода номера точки.

Point2 — переменная типа поле ввода строки для вывода номера точки, является недоступным для редактирования пользователем.

Диаграмма потоков данных 1-го уровня

Рис. 2.7 — Диаграмма потоков данных 1-го уровня

Таблица 2.3. Словарь данных DFD 1 уровня

Спецификация процессов

1. Ввод данных.

Входные данные: количество точек, координаты точек

Выходные данные: координаты точек

Функциональное назначение: Считывание содержимого файла data.txt. Сначала считывается первое значение — количество точек. Потом в цикле по строкам значения координат в массив t. И выводится в таблицу sg на экран.

Условие выполнения: команда пользователя, наличие файла data. txt, корректный формат файла.

2. Поиск.

Входные данные: массив t

Выходные данные: для каждой точки номера точек, образующих искомую прямую;

Функциональное назначение:

В цикле для каждого элемента I массива t выполняется построение прямой с оставшимися точками массива. Для каждой прямой определяется количество точек r лежащих с одной стороны. Если количество этих точек равно 0 или N — 2, то искомая точка j найдена и поиск останавливается. (N — общее количество точек множества, 2 — количество точек на прямой).

Номер точки j выводится в четвертый столбец и Iтую строку таблицу Sg.

Условие выполнения: команда пользователя, наличие в таблице вывода sg координат хотя бы трех точек.

3. Построить множество

Входные данные: координаты точек множества (массив t)

Выходные данные: изображение точек на экране в соответствии с координатами.

Функциональное назначение: перевод координат точек в экранные и вывод на экран кружочков с соответствующим номером в позиции согласно координате.

Условия выполнения: команда пользователя, наличие в массиве координаты хотя бы одной точки.

4. Построить прямую

Входные данные: номер точки I (первая точка прямой)

Выходные данные: номер точки j (вторая точка прямой). Изображение прямой на экране.

Функциональное назначение: Вывод номера второй точки в поле вывода Point2. Значение определяется из таблицы вывода sg — четвертый столбец, I-тая строка.

Координаты точек I и j из массива t переводятся в экранные и соединяются прямой на экране.

Условия выполнения: наличие точки с номером I, существование для нее точки с которой она образует искомую прямую (соответствующей записи в таблице вывода).

Диаграмма потоков данных 2-го уровня

Согласно спецификации процесса Поиск в диаграмме потоков данных 1-го уровня, этот процесс является сложным и требует декомпозиции.

Рис. 2.8 — Диаграмма потоков данных 2-го уровня

Таблица 2.4. Словарь данных DFD 2 уровня

Спецификация процессов

1. Поиск.

Входные данные: I, j — номера точек

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

Условие выполнения: наличие координат хотя бы трех точек.

2. Прямая.

Входные данные: массив t, I, jмассив координат точек, номера точек

Выходные данные: a, b — коэффициенты прямой.

Функциональное назначение:

Определение коэффициентов уравнения прямой

y=ax+b.

a:=; b:=

При a=1, b=x_i

При a=0, b=y_i

3. Знак

Входные данные: a, b, k — коэффициенты уравнения прямой, номер точки множества

Выходные данные: знак — разница между левой и правой частью уравнения прямой для k-той точки.

Функциональное назначение: znak=;

Условия выполнения:

2.3 Рабочий проект

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

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

Спецификация модулей

Модуль Lib

Содержит:

-Описание введенных типов

const n=100; - максимально допустимое количество точек множества

type tochka = recordтип составной тип координат точки

x, y: real; координаты по осям абсцисс и ординат

end;

mnogina = array [1.n] of tochka; - тип для множества точек

-Глобальные переменные

var t: mnogina; - массив координат точек множества

nt:integer; - количество точек множества

sx, sy: integer; - отступы в области прорисовки множества от краев

Xmin, Xmax, Ymin, Ymax, Mx, My: real; - граничные значения координат точек множества, коэффициенты перевода реальных координат в экранные.

Модуль Unit1

Функциональное Назначение: поиск для каждой точки множества точек согласно постановки задачи. Содержит основные функции:

praymaya. Соответствует процессу Определение коэффициентов прямой. (см. Технический проект) Входные данные: i, j: integer (индексы элементов массиве t)

Выходные данные: a, b: real (коэфициенты уравнения прямой для данной пары точек). Алгоритм:

Если t[i]. x = t[j]. x то

a:=1;b:=-t[i]. x

иначе если t[i]. y = t[j]. y то

a=0; b=t[i]. y

иначе

a=(t[i].y-t[j].y)/(t[i].x-t[j].x);

b=(t[j].y*t[i].x-t[i].y*t[j].x)/(t[i].x-t[j].x);

Текст процедуры:

procedure pryamaya (i, j: integer;var a, b: real);

begin

if t[i]. x=t[j].x then

begin

a:=1;b:=-t[i]. x

end

else

if t[i]. y=t[j].y then

begin

a:=0;b:=t[i]. y

end

else

begin

a:=(t[i].y-t[j].y)/(t[i].x-t[j].x);

b:=(t[j].y*t[i].x-t[i].y*t[j].x)/(t[i].x-t[j].x);

end;

end;

Тестирование модуля:

Используется метод «Эквивалентное разбиение»

Тест 1. Координаты точек разлычны

1 0

0 1

Результат

A=-1 b=1

Тест 2 Координаты точек равны по ординате

1 0

0 0

Результат

A= 0 b=0

Тест 3. Координаты равны по аобсциссе

1 1

1 0

Результат

a=1 b=-1

Функция Search.

Входные данные: t (см. описание глобальных переменных) Выходные данные sg. cells[3, i] - четвертый столбец таблицы вывода, содержит номера точек для построения прямой.

Алгоритм Алгоритм процедуры Poisk

Текст модуля

procedure pryamaya (i, j: integer;var a, b: real);

begin

if t[i]. x=t[j].x then

begin

a:=1;b:=t[i]. x

end

else

if t[i]. y=t[j].y then

begin

a:=0;b:=t[i]. y

end

else

begin

a:=(t[i].y-t[j].y)/(t[i].x-t[j].x);

b:=(t[j].y*t[i].x-t[i].y*t[j].x)/(t[i].x-t[j].x);

end;

end;

function znak (a, b: real;k, i, j:integer):real;

begin

znak:=t[k]. y-a*t[k].x-b;

end;

procedure poisk (i, j: integer;var r: integer);

var k: integer;

a, b: real;

begin

pryamaya (i, j, a, b);

r:=0;

for k:=1 to nt do

if (k<>i)and (k<>j) then

if znak (a, b, k, i, j)>=0 then r:=r+1;

end;

procedure TForm1. SearchClick (Sender: TObject);

var i, j, r:integer;

begin

readFromGrid (nt, t);

for i:=1 to nt do

Form1.SG.Cells[3,i]: ='-';

for i:=1 to nt do

for j:=1 to nt do

if i<>j then

begin

poisk (i, j, r);

if (r=0)or (r=nt-2) then sg. Cells[3,i]: =floattostr (j);

end;

minmax ();

MakePicture.Enabled:=True;

end;

Тестирование методами «черного ящика»

Эквивалентное разбиение

1. задано две точки. Есть единственно возможная прямая, по обе стороны от которой нет точек.

Тест 1

Тест 2. Задано три точки Тест 3. Задано 4 точки Тест 4. Задано 5 точек Тест 4 доказывает что не для каждой точки множества можно найти такую точку, остальные точки множества будут лежать по одну сторону от прямой, проведенной через эти две точки.

Тестирование методами «белого ящика» фнкции Poisk

Метод покрытия всех условий/решений Условие

kI и kj

I — номер одной точки прямой

J — номер второй точки прямой

K — номер точки не лежащей на прямой.

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

Содержимое файла

I=1

J=2

K = 3, 4, 5

Условие

Znak (a, b, k)>0

Для проверки этого условия на ветке истина добавим вывод в файл всех K.

Таким образом должны быть веведены только номера точек, удовлетворяющих условию. Nt = 5.

Дано множество

1) 1 0

2) 0 1

3) -1 4

4) 5 2

5) 1 -3

I=1; j=2 => a =-1; b=1

K=3 znak =2; K=4 znak =7; K=5 znak =-3

Содержимое файла

3. Результаты разработки

Структура программы

Программа выполнена на объектно-ориентированном языке Delphi 7.0.Программа состоит из файлов: Unit1. pas, Unit2.pas., Picture. pas, lib. pas

Unit1.pas содержит код проверки предположения о том, что для заданного множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB

Unit2.pas содержит код панели с сообщением об ошибке.

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

Lib.pas — библиотечный файл, содержит описание введенных типов и глобальных переменных.

Все файлы объединены в проект Poisktochki.dpr. Логика программы очень проста. Система программирования уже содержит все необходимые компоненты (кнопки, поля ввода, панели и др.). Из них формируется интерфейс программного продукта. В разделе события выбирается, на какое действие должен реагировать компонент. Были дописаны реакции компонента на действия пользователя.

Назначение программы

Программа, позволяющая проверить для заданного множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

Выполняет следующие основные функции:

1) ввод данных о множестве точек из файла

2) вывод введенных данных на экран

3) ввод данных о множестве с клавиатуры

4) построение прямой AB для указанной точки A.

5) Поиск точек B_i для каждой точки множества A_i и вывод на экран

6) Визуализация точек множества на экране

Реализации процессов

Логика программы соответствует логике объектно-ориентированного программирования. Система программирования уже содержит все необходимые компоненты (кнопки, поля ввода, панели и др.). Из них формируется интерфейс программного продукта. В разделе события выбирается, на какое действие должен реагировать компонент. Пользователь только дописывает, как компонент реагирует на то или иное действие. Один компонент может реагировать на несколько действий. Например, при наведении на кнопку курсором мыши в строке состояния появляется функция, выполняемая кнопкой, а при нажатии курсором мыши на эту кнопку она совершает действие описываемое в строке состояния. При выборе пользователем компонента и события система сама создаёт процедуру с соответствующим названием.

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

Основные процедуры рассматриваются в Таблице 3.1.

Таблица 3.1. Функции процессов.

Тестирование программы

Программа и её модули были протестированы методами «чёрного ящика» — предположение об ошибке и эквивалентное разбиение и «Белого ящика» — покрытие всех условий/решений.

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

Программа соответствует требованиям Технического задания.

Выводы В результате дипломного проектирования были достигнуты цели заявленные во введении — решение задачи определения в заданном множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

Было выяснено что существуют точки, для которых данное утверждение не верно, как показано на рисунке ниже.

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

Задача решалась в несколько этапов:

§ Определение требований и постановка задачи;

§ Разработка Эскизного проекта;

§ Разработка Технического проекта;

§ Разработка рабочего проекта;

Все этапы полностью или частично задокументированы и представлены в настоящей пояснительной записке. Создана сопровождающая документация в составе:

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

§ Описание программы;

§ Программа и методика испытаний;

§ Руководство пользователя.

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

Приложение, А ТЕХНИЧЕСКОЕ ЗАДАНИЕ

1.

Введение

.

Полное наименование программного изделия: Программа, позволяющая проверить для заданного множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

Краткая характеристика области применения: решение задачи определения в заданном множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

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

2. Основания для разработки.

Условное обозначение программного изделия: Программа.

Документ: Задание на курсовую работу.

Утвердил: Суслов С.В.

Дата утверждения: 15.02.2010

Плановые сроки начала и окончания работы по созданию программного изделия:

начало: 15.02.2010

окончание: 31.05.2010

3. Назначение разработки.

Функциональное назначение: решение задачи определения в заданном множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

Эксплуатационное назначение: использование программного изделия для наглядного доказательства определения в заданном множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

4. Требования к программному изделию.

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

4.1.1. Требования к организации входных и выходных данных.

Входными данными для Программы являются:

количество точек множества (N);

координаты точек (x_i; y_i);

Точка A_i, для которой пользователь хочет построить прямую.

Входные данные Программа получает:

— из файла, где они располагаются следующим образом:

— пользователь вводит с клавиатуры

3) Выходными данными для Программы являются:

— координаты точки B для каждой точки A, если такая существует.

— визуализация точек множества на плоскости

— визуализация прямой AB, для заданной пользователем точки A.

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

Программа должна иметь следующие функции:

7) ввод данных о множестве точек из файла

8) вывод введенных данных на экран

9) ввод данных о множестве с клавиатуры

10) построение прямой AB для указанной точки A.

11) Поиск точек B_i для каждой точки множества A_i и вывод на экран

12) Визуализация точек множества на экране

4.1.3. Требования к интерфейсу

1) Интерфейс графический

2) Вывод множества в табличной форме с прорисовкой границ.

3) Вывод множества в графической форме

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

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

2) В случае ошибки при выполнении Программы выдать сообщение об ошибке и прекратить работу.

4.3. Условия эксплуатации.

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

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

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

Процессор: 1 ГГц и выше.

Оперативная память — минимум 256 Мб.

Дисплей. Необходим цветной или монохромный дисплей типа VGA, SVGA.

Наличие клавиатуры и манипулятора мышь.

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

Программа рассчитана для работы в среде Windows'7/Vista/XP.

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

Структура хранения информации определена в пункте 4.1.1.

4.6. Требования к маркировке и упаковке.

Маркировка и упаковка проектируемого программного продукта должны соответствовать всем стандартным требованиям, применяемым к маркировке, вариантам и способам упаковки.

4.7. Требования к транспортированию и хранению.

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

5. Требования к программной документации.

Полный пакет документов должен включать :

Пояснительная записка.

Описание программы.

Текст программы.

Методика испытаний.

Руководство пользователя.

6. Технико-экономические показатели.

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

7. Стадии и этапы разработки.

Техническое задание Плановые сроки начала и окончания работы:

Начало: 15.02.10

Окончание:3.03.10

Эскизный проект Плановые сроки начала и окончания работы:

Начало: 04.03.10

Окончание:1.04.10

Технический проект Плановые сроки начала и окончания работы:

Начало: 2.04.10

Окончание: 16.04.10

Рабочий проект Плановые сроки начала и окончания работы:

Начало: 16.04.10

Окончание: 30.05.10

7. Порядок контроля и приёмки.

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

Приемку программы производит руководитель проекта.

Приложение Б

Описание программы

Общие сведения

Наименование программы: Программа, позволяющая проверить для заданного множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB. Программное обеспечение, необходимое для функционирования программы: программа предназначена для работы в среде Windows'7/Vista/XP.

Функциональное назначение.

Функциональное назначение разработки: решение задачи определения в заданном множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

Описание логической структуры.

Программа выполнена на объектно-ориентированном языке Delphi 7.0.Программа состоит из файлов: Unit1. pas, Unit2.pas., Picture. pas, lib. pas

Unit1.pas содержит код проверки предположения о том, что для заданного множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB

Unit2.pas содержит код панели с сообщением об ошибке.

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

Lib.pas — библиотечный файл, содержит описание введенных типов и глобальных переменных.

Все файлы объединены в проект Poisktochki. dpr

Основные процедуры рассматриваются в Таблице 3.1.

Таблица 3.1. Функции процессов.

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

Процессор: 1 ГГц и выше.

Оперативная память — минимум 256 Мб.

Дисплей. Необходим цветной или монохромный дисплей типа VGA, SVGA. Наличие клавиатуры и манипулятора мышь.

Вызов и загрузка

Вызов Программы осуществляется посредством запуска файла poisktochki. exe

Входные данные

2 Входные данные

Входными данными для Программы являются:

количество точек множества (N);

координаты точек (x_i; y_i);

Точка A_i, для которой пользователь хочет построить прямую.

Входные данные Программа получает:

— из файла, где они располагаются следующим образом:

— пользователь вводит с клавиатуры

3 Выходные данные

Приложение В

Программа и методика испытаний

1 Объект испытаний

Программа, позволяющая проверить для заданного множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB

2 Цель испытаний

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

3 Требования к программе

13) ввод данных о множестве точек из файла

14) вывод введенных данных на экран

15) ввод данных о множестве с клавиатуры

16) построение прямой AB для указанной точки A.

17) Поиск точек B_i для каждой точки множества A_i и вывод на экран

18) Визуализация точек множества на экране

4 Средства и порядок испытаний

4.1 Технические средства Процессор: 1 ГГц и выше.

Оперативная память — минимум 256 Мб.

Дисплей. Необходим цветной или монохромный дисплей типа VGA, SVGA.

Наличие клавиатуры и манипулятора мышь.

4.2 Программные средства Операционная система Windows'7/Vista/XP

4.3 Порядок испытаний

1. Создать файл исходных данных как указано в и Приложении Б Инструкция пользователя

2. Запустить файл poisktochki.exe.

3. Следовать указаниям приведённых перед тестовыми заданиями для каждой функции.

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

5 Методы испытаний

1) ввод данных из файла и вывод данных на экран

Первоначальный вид окна программы

Содержимое файла data. txt

2 4

— 3 5

5 -4

— 2 1

Вид окна программы после нажатия кнопки «Ввести данные из файла»

2) Поиск точек B_i для каждой точки множества A_i и вывод на экран

Нажать кнопку «Найти»

Как видно из этого теста, не для всех точек множества AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB

3) Визуализация точек множества на экране

Нажать кнопку «Изображение»

4) построение прямой AB для указанной точки A.

Сначала построим прямую для точек для которых это возможно.

Например для первой точки.

Для второй точки

Теперь вводим номер точки 5 и нажимаем «Нарисовать пямую»

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

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

Программное изделие предполагается использовать для наглядного доказательства определения в заданном множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB

Пользователь должен иметь навыки работы с компьютером в операционной системе Windows.

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

1 Общие сведения о программе

Наименование программы: Программа, позволяющая проверить для заданного множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

Функциональное назначение разработки: решение задачи определения в заданном множества точек M, верно ли, что для каждой точки AM существует точка B (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

Программное обеспечение, необходимое для функционирования программы: программа предназначена для работы в среде Windows XP/Vista/7.

2 Входные данные

Входными данными для Программы являются:

количество точек множества (N);

координаты точек (x_i; y_i);

Точка A_i, для которой пользователь хочет построить прямую.

Входные данные Программа получает:

— из файла, где они располагаются следующим образом:

— пользователь вводит с клавиатуры

3 Выходные данные

3 Работа с программой

Для запуска программы нужно запустить файл poisktochki.exe. Об успешном запуске свидетельствует появление окна (рис. 1.)

Рис. 1 — Главное окно программы

где

" Ввести данные из файла" - кнопка ввода данных из файла data.txt.

" Найти" - кнопка поиска точки B, для каждой точки AM, (AB), такая что не существует двух точек множества M, которые лежат по разные стороны от прямой AB.

" Изображение" - служит для ввода команды нарисовать точки множества в области под кнопкой. Становится доступна после выполнения поиска.

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

Таблица слева содержит в первом столбце номера точек множества, во втором координаты абсцисс точек множества, в третьем координаты ординат точек множества, в четвертый выводится номер точки b после поиска.

Приложение Д

ТЕКСТ ПРОГРАММЫ

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, Grids, lib;

type

TForm1 = class (TForm)

SG: TStringGrid;

OutPutFile: TButton;

Image1: TImage;

MakePicture: TButton;

Exit: TButton;

Help: TButton;

EnterPointNumber: TLabel;

EditPointNumber: TEdit;

Search: TButton;

PaintStr: TButton;

EditPoint2: TEdit;

procedure OutPutFileClick (Sender: TObject);

procedure SGEnter (Sender: TObject);

procedure SearchClick (Sender: TObject);

procedure ExitClick (Sender: TObject);

procedure MakePictureClick (Sender: TObject);

procedure PaintStrClick (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

uses picture, Unit2;

{$R *.dfm}

function XI (XW:real):integer; // перевод в Х-экранную кординату

begin XI:=Round ((XW-Xmin)*Mx+Sx/2) end;

function YI (YW:real):integer; // перевод в Y-экранную кординату

begin YI:=Round ((Ymax-YW)*My+Sy/2); end;

procedure TForm1. OutPutFileClick (Sender: TObject);

var f: textfile;

i:integer;

x, y: integer;

begin

assignfile (f,'data.txt');

reset (f);

readln (f, nt);

for i:=1 to nt do

begin

readln (f, x, y);

sg.Cells[0,i]: =floattostr (i);

sg.Cells[1,i]:=floattostr (x);

sg.Cells[2,i]:=floattostr (y);

end;

Search.Enabled:=True;

end;

procedure TForm1. SGEnter (Sender: TObject);

begin

sg.Cells[0,0]: ='№ точки';

sg.Cells[1,0]: ='X';

sg.Cells[2,0]:='Y';

sg.Cells[3,0]:='№ 2-й точки';

end;

procedure readFromGrid (var nt: integer; var t: mnogina);

var i, j: integer;

begin

i:=1; j:=1;nt:=0;

while (Form1.sg.cells[i, j]<>'')do

begin

nt:=nt+1;

t[j]. x:=strtofloat (Form1.sg.cells[i, j]);

t[j].y:=strtoFloat (Form1.sg.cells[i+1,j]);

j:=j+1;

end;

end;

procedure pryamaya (i, j: integer;var a, b: real);

begin

if t[i]. x=t[j].x then

begin

a:=1;b:=t[i]. x

end

else

if t[i]. y=t[j].y then

begin

a:=0;b:=t[i]. y

end

else

begin

a:=(t[i].y-t[j].y)/(t[i].x-t[j].x);

b:=(t[j].y*t[i].x-t[i].y*t[j].x)/(t[i].x-t[j].x);

end;

end;

function znak (a, b: real;k, i, j:integer):real;

begin

znak:=t[k]. y-a*t[k].x-b;

//(t[k].x-t[i].x)/(t[i].x-t[j].x)-(t[k].y-t[i].y)/(t[i].y-t[j].y)

end;

procedure poisk (i, j: integer;var r: integer);

var k: integer;

a, b: real;

begin

pryamaya (i, j, a, b);

r:=0;

for k:=1 to nt do

if (k<>i)and (k<>j) then

if znak (a, b, k, i, j)>=0 then r:=r+1;

end;

procedure TForm1. SearchClick (Sender: TObject);

var i, j, r:integer;

begin

readFromGrid (nt, t);

for i:=1 to nt do

Form1.SG.Cells[3,i]: ='-';

for i:=1 to nt do

for j:=1 to nt do

if i<>j then

begin

poisk (i, j, r);

if (r=0)or (r=nt-2) then sg. Cells[3,i]: =floattostr (j);

end;

//if (r>0)and (r

minmax ();

MakePicture.Enabled:=True;

end;

procedure TForm1. ExitClick (Sender: TObject);

begin

Halt;

end;

procedure TForm1. MakePictureClick (Sender: TObject);

var i: integer;

begin

Image1.Picture:=nil;

Image1.Canvas.Pen.Color:=clRed;

Image1.Canvas.Pen.Width:=2;

for i:=1 to nt do

begin

Image1.Canvas.Ellipse (XI (t[i]. x)-3,YI (t[i].y)-3,XI (t[i].x)+3,YI (t[i].y)+3);

Image1.Canvas.TextOut (XI (t[i].x)-10,YI (t[i].y)-10,sg.Cells[0,i]);

end;

Image1.Refresh;

PaintStr.Enabled:=true;

end;

procedure TForm1. PaintStrClick (Sender: TObject);

var i, j: integer;

begin

i:=strtoint (EditPointNumber.Text);

if (i>0)and (i<=nt) then

begin

Image1.Canvas.Pen.Color:=clBlue;

Image1.Canvas.pen.Width:=2;

if sg. Cells[3,i]<>'-' then

begin

editPoint2.Text:=sg.Cells[3,i];

j:=strtoint (sg.Cells[3,i]);

Image1.Canvas.MoveTo (XI (t[i].x), YI (t[i].y));

Image1.Canvas.LineTo (XI (t[j].x), YI (t[j].y));

end

else

begin

editPoint2.Text:='-';

Image1.Canvas.Ellipse (XI (t[i].x)-4,YI (t[i].y)-4,XI (t[i].x)+4,YI (t[i].y)+4);

end;

end

else

Form2.ShowModal ();

end;

end.

unit Picture;

interface

uses Classes, Graphics, lib, unit1;

procedure minmax ();

implementation

procedure SetWind (Xmin, Ymin, Xmax, Ymax: real);//вычисление коэффициентов для перевода в экранные координаты

begin

Sx:=50; Sy:=50;

Mx:=(Form1.Image1.Width-Sx)/(Xmax-Xmin);

My:=(Form1.Image1.Height-Sy)/(Ymax-Ymin);

end;

procedure minmax ();

var i: integer;

begin

Xmin:=t[1]. x;

Xmax:=t[1].x;

Ymin:=t[1].y;

Ymax:=t[1].y;

for i:=1 to nt do

begin

if Xmax < t[i]. x then Xmax:=t[i]. x else

if Xmin > t[i]. x then Xmin:=t[i]. x;

end;

for i:=1 to nt do

begin

if Ymax < t[i]. y then Ymax:=t[i]. y else

if Ymin > t[i]. y then Ymin:=t[i]. y;

end;

SetWind (Xmin, Ymin, Xmax, Ymax);

end;

end.

unit Lib;

interface

const n=100;

type tochka = record

x, y: real;

end;

mnogina = array [1.n] of tochka;

var t: mnogina;

nt:integer;

sx, sy: integer;

Xmin, Xmax, Ymin, Ymax, Mx, My: real;

implementation

end.