Решение задачи с прикладным содержанием с применением программирования на языке высокого уровня

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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кубанский государственный университет»

Факультет математики и компьютерных наук

Кафедра вычислительной математики и информатики

КУРСОВАЯ РАБОТА

Решение задачи с прикладным содержанием с применением программирования на языке высокого уровня

Работу выполнил Чабанец Антон Владимирович

Группа 26В2

Руководитель работы Д.Г. Сокол

Краснодар 2013

Содержание

Введение

1. Анализ условия задачи и выработка подхода к ее решению

2. Пошаговая разработка алгоритма

3. Код программы

Заключение

Список использованных источников

Введение

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

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

Цель работы определила следующие задачи исследования:

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

2. Выбрать наиболее подходящие представления для входных, выходных и промежуточных данных.

3. На основе выбранного подхода разработать алгоритм.

4. Описать алгоритм на языке программирования.

5. Составить тестовые примеры для отладки и демонстрации возможностей программы.

1. Анализ условия задачи и выработка подхода к ее решению

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

По условию исходными параметрами являются количество точек и их координаты в двумерном пространстве. В первую очередь необходимо организовать перебор троек точек из заданного множества. Порядок вершин в треугольнике не важен, но, чтобы сократить количество рассчитываемых наборов и не учитывать повторяющиеся наборы, упорядочим вершины. Перебор для первой вершины А возможен только с 1 до n-2 (если n-2 точка является первой вершиной, тогда n-1 - второй, а n - третьей), для второй вершины В перебор возможен со следующей координаты после выбранной в качестве А до n-1, для третьей вершины С - со следующей координаты после выбранной в качестве после В до n. Таким образом, мы сможем перебрать все возможные не повторяющиеся наборы из трех точек заданного множества. Необходимо проверить, не принадлежат ли выбранные точки одной прямой, так как в этом случае треугольника не существует и задача не имеет смысла. Три заданные точки принадлежат одной прямой, если выполняется условие:

Или



Перепишем условие проверки в подходящем для программирования виде:

(x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1) = 0.

2. Пошаговая разработка алгоритма

Алгоритм разделим на три основные части: ввод данных, решение задачи и вывод результата. Входными данными являются количество и координаты точек множества.

Выходными данными для алгоритма являются минимальный радиус окружности и точки центра.

Необходимые промежуточные данные: sa, sb, sc - промежуточные переменные для вычисления центра окружности, minr,minx0,miny0 - переменные для сравнения, нахождения и вывода минимального радиуса и точек центра.

Перебор троек точек осуществляется с помощью трех последовательных вложенных циклов for:

for i:=1 to n-2 do

for j:=i+1 to n-1 do

for k:=j+1 to n do

begin

end;

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



if ((x[3]-x[1])*(y[2]-y[1]))-((y[3]-y[1])*(x[2]-x[1])) <>0

Вычисляем длины сторон с помощью формул:

Находим полупериметр по формуле:

И по формуле Герона вычисляем площадь:

В алгоритме это выглядит так:

a:=sqrt(((x[j]-x[k])*(x[j]-x[k]))+((y[j]-y[k])*(y[j]-y[k])));

b:=sqrt(((x[k]-x[i])*(x[k]-x[i]))+((y[k]-y[i])*(y[k]-y[i])));

c:=sqrt(((x[j]-x[i])*(x[j]-x[i]))+((y[j]-y[i])*(y[j]-y[i])));

p:=(a+b+c)/2;

s:=sqrt(p*(p-a)*(p-b)*(p-c));

После вычисления площади, нужно с помощью оператора if проверить, что она не отрицательная.

IF s>0 THEN

BEGIN

sa:=((a*a)/(8*s*s));

sB:=((b*b)/(8*s*s));

sc:=((c*c)/(8*s*s));

x0:=(sa*(x[i]-x[j])*x[i])+(sb*(x[j]-x[i])*x[j])+(sc*(x[k]-x[i])*x[k]);

y0:=(sa*(y[i]-y[k])*y[i])+(sb*(y[j]-y[k])*y[j])+(sc*(y[k]-y[j])*y[k]);

r:=((x0-x[i])*(x0-x[i]))+((y0-y[i])*(y0-y[i]));

IF r<minr THEN

BEGIN

minr:=r;

minx0:=x0;

miny0:=y0;

END;

END;

Нахождение центра окружности:

Пусть радиус-векторы вершин треугольника, -- радиус-вектор центра описанной окружности. Тогда:

где

При этом - длины сторон треугольника, противоположных вершинам .

sa:=((a*a)/(8*s*s));

sB:=((b*b)/(8*s*s));

sc:=((c*c)/(8*s*s));

x0:=(sa*(x[i]-x[j])*x[i])+(sb*(x[j]-x[i])*x[j])+(sc*(x[k]-x[i])*x[k]);

y0:=(sa*(y[i]-y[k])*y[i])+(sb*(y[j]-y[k])*y[j])+(sc*(y[k]-y[j])*y[k]);

r:=((x0-x[i])*(x0-x[i]))+((y0-y[i])*(y0-y[i]));

Радиус вычисляем по формуле:

,

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

Выполняем главное условие нашего алгоритма, сравнивая найденный радиус с нашим минимальным радиусом r min. Если найденный радиус меньше rmin, значит присваиваем r min найденный радиус. Соответственно точки центра окружности этого радиуса также записываем в minX0, minY0.

minr:=r;

minx0:=x0;

miny0:=y0;

3. Код программы

PROGRAM Kursovaya;

USES crt;

VAR x,y:ARRAY[1..1000] OF REAL;

a, b, c, x0, y0, s, p, r, sa, sb, sc:REAL;

n, i, j, min, k:INTEGER;

f:TEXT;

minr, minx0, miny0:double;

BEGIN

CLRSCR;

minr:=9999;

minx0:=9999;

miny0:=9999;

ASSIGN(f,'File.txt');

RESET(f);

n:=0;

WHILE NOT SEEKEOF(f) DO

BEGIN

n:=n+1;

READLN(f,x[n],y[n]);

END;

FOR i:=1 TO n-2 DO

FOR j:=i+1 TO n-1 DO

FOR k:=j+1 TO n DO

BEGIN

if ((x[3]-x[1])*(y[2]-y[1]))-((y[3]-y[1])*(x[2]-x[1])) <>0 then

begin

a:=sqrt(((x[j]-x[k])*(x[j]-x[k]))+((y[j]-y[k])*(y[j]-y[k])));

b:=sqrt(((x[k]-x[i])*(x[k]-x[i]))+((y[k]-y[i])*(y[k]-y[i])));

c:=sqrt(((x[j]-x[i])*(x[j]-x[i]))+((y[j]-y[i])*(y[j]-y[i])));

p:=(a+b+c)/2;

s:=sqrt(p*(p-a)*(p-b)*(p-c));

IF s>0 THEN

BEGIN

sa:=((a*a)/(8*s*s));

sB:=((b*b)/(8*s*s));

sc:=((c*c)/(8*s*s));

x0:=(sa*(x[i]-x[j])*x[i])+(sb*(x[j]-x[i])*x[j])+(sc*(x[k]-x[i])*x[k]);

y0:=(sa*(y[i]-y[k])*y[i])+(sb*(y[j]-y[k])*y[j])+(sc*(y[k]-y[j])*y[k]);

r:=((x0-x[i])*(x0-x[i]))+((y0-y[i])*(y0-y[i]));

IF r<minr THEN

BEGIN

minr:=r;

minx0:=x0;

miny0:=y0;

END;

END;

END;

END;

minr:=sqrt(minr);

CLOSE(f);

WRITELN(minr:8:20);

WRITELN('Tochki centra = ', minx0:8:3,' ', miny0:8:3);

READKEY;

END.



Заключение

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

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

компьютерный программирование рascal прикладной

Список использованных источников

1. Абрамян М.Э., Михалкович С. С. Основы программирования на языке Паскаль: Скалярные типы данных, управляющие операторы, процедуры и функции. - Ростов-на-Дону. - ООО «ЦВВР». - 2004.

2. Абрамян М.Э. Практикум по программированию на языке Паскаль: Массивы, строки, файлы, рекурсия, указатели. - Ростов-на-Дону. - ООО «ЦВВР». - 2004.

3. Выгодский М.Я. Справочник по высшей математике. - АСТ. Астрель. - 2006.

4. Ильин В.А., Позняк Э.Г. Аналитическая геометрия. - М.: ФИЗМАТЛИТ. - 2002.

5. Касьянов В.Н., Сабельфельд В.К. Сборник задач по практикуму на ЭВМ. - М.: Наука. - 1986.

6. Рубанцев В. RVGames.de Занимательные уроки с паскалем, или PascalABC.NET для начинающих. - Я + R. - 2012.

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

...