Программирование и основы алгоритмизации

Министерство образования и науки Российской Федерации Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

Кафедра: КСУ Курсовая работа

" Программирование и основы алгоритмизации"

Студент: Моисеева О.И.

Группа: 1491

Преподаватель: Ветчинкин А. С.

Санкт-Петербург, 2012 год Постановка задачи и математическая модель задачи математический модель программа пользователь Постановка задачи:

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

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

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

Математическая модель:

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

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

Kbc и Bbc — угловой коэффициент и свободный член уравнения прямой, проведенной через вершины многоугольника B и С.

Аналогично этому: Kcd и Bcd, Kad и Bad, Kab и Bab.

Во избежание деления на ноль используется число 0.0001.

На точность вычислений оно не влияет, т.к. очень мало.

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

Используется формула: Она путем преобразований получена из стандартной математической формулы для вычисления расстояний.

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

Аналогично максимальные значения из оставшихся значений переносятся в ячейку 2,3…n…

#include «stdafx.h»

#include

#include

#include

#include

#include

#include

FILE *file1;

FILE *file2;

int vnutri_ili_snaruji (float Ax, float Bx, float Cx, float Dx, float Ay, float By, float Cy, float Dy, float x, float y)

{

int vnutri=0, z=0;

float y1, y2, y3, y4;

float massiv[4];

float Kbc, Bbc, Kcd, Bcd, Kad, Bad, Kab, Bab;

Kbc=(By-Cy)/(Bx-Cx+0.0001); //коэффициенты в ур-ие прямой

Bbc=By-Kbc*Bx;

Kcd=(Dy-Cy)/(Dx-Cx+0.0001);

Bcd=Cy-Kcd*Cx;

Kad=(Dy-Ay)/(Dx-Ax+0.0001);

Bad=Ay-Kad*Ax;

Kab=(By-Ay)/(Bx-Ax+0.0001);

Bab=Ay-Kab*Ax;

y1=Kab*x+Bab; //Находим точки пересечения со сторонами многогранника

y2=Kbc*x+Bbc;

y3=Kcd*x+Bcd;

y4=Kad*x+Bad;

if ((y1>Ay && y1By)) //Подсчёт точек пересечения параллельной прямой

{

massiv[z]=y1;

z++;

}

if ((y2>Cy && y2By))

{

massiv[z]=y2;

z++;

}

if ((y3>Cy && y3Dy))

{

massiv[z]=y3;

z++;

}

if ((y4>Ay && y4Dy))

{

massiv[z]=y4;

z++;

}

if (z==2) //Проверка условия внутри многоугольника

{

if (ymassiv[1]) vnutri=1;

if (y>massiv[0] && y

}

return (vnutri);

}

float rasstoyanie (float x, float y, float k, float b)

{

float d;

d=(fabs (k*x-y+b)/sqrt (k*k+1)); //рассчёт расстояния от точки до прямой

return (d);

}

float sortirovka (float Sort[], float D3[250][6], int n)//Использование метода простого перебора

{

int i=0,k=0,nomer, j, j3=0, i3;

float max, perv;

float temp, temp1, temp2, temp3, temp4, temp5;

do //Сортировка значений r

{

max=Sort[i];

nomer=i;

do

{

if (Sort[i+1]>max) nomer=i+1;

if (Sort[i+1]>max) max=Sort[i+1];

i++;

}

while (i

perv=Sort[k];

Sort[k]=max;

Sort[nomer]=perv;

k++;

i=k;

}

while (k

for (j=0;j

{

for (i3=0;i3

{

if (Sort[j]==D3[i3][j3+5])

{

temp=D3[j][j3];

temp1=D3[j][j3+1];

temp2=D3[j][j3+2];

temp3=D3[j][j3+3];

temp4=D3[j][j3+4];

temp5=D3[j][j3+5];

D3[j][j3]=D3[i3][j3];

D3[j][j3+1]=D3[i3][j3+1];

D3[j][j3+2]=D3[i3][j3+2];

D3[j][j3+3]=D3[i3][j3+3];

D3[j][j3+4]=D3[i3][j3+4];

D3[j][j3+5]=D3[i3][j3+5];

D3[i3][j3]=temp;

D3[i3][j3+1]=temp1;

D3[i3][j3+2]=temp2;

D3[i3][j3+3]=temp3;

D3[i3][j3+4]=temp4;

D3[i3][j3+5]=temp5;

break;

}

}

}

return (0);

}

void vyvod (float Massiv[250][6], int stroki, int stolbcy)

{

int i, j, k;

if (stolbcy==6)

{

k=1;

}

else

{

k=0;

}

for (i=0; i

{

if ((i%20)==0)

{

getch ();

}

for (j=k; j

{

switch (stolbcy)

{

case 6:

{

switch (j)

{

case 1:

printf («D2=»);

break;

case 2:

printf («D1=»);

break;

case 3:

printf («x=»);

break;

case 4:

printf («y=»);

break;

case 5:

printf («d=»);

break;

}

break;

}

case 3:

{

switch (j)

{

case 0:

printf («D1=»);

break;

case 1:

printf («x=»);

break;

case 2:

printf («y=»);

break;

}

break;

}

case 4:

{

switch (j)

{

case 0:

printf («D2=»);

break;

case 1:

printf («D1=»);

break;

case 2:

printf («x=»);

break;

case 3:

printf («y=»);

break;

}

break;

}

}

printf («%1.1f «, Massiv[i][j]);

fprintf (file2, «%1.1f «, Massiv[i][j]);

}

printf («n»);

fprintf (file2," n");

}

}

int MENU (int flag) //основное меню

{

system («cls»); //очистка экрана

printf («nMenu:n»); //вывод меню

if (flag>1) printf («1. Vvod na4al'nyh dannyh — ok!»);

else printf («1. Vvod na4al'nyh dannyh»);

if (flag>2) printf («n2. Ras4et — ok!»);

else printf («n2. Ras4et»);

if (flag>3) printf («n3. Vyvod rezul’tatov — ok!»);

else printf («n3. Vyvod rezul’tatov»);

printf («n4. Vyhod»);

printf («nnVvedite N punkta: «);

return 0;

}

void main () //описание переменных

{

int vyhod=0;

float Ax, Ay, Bx, By, Cx, Cy, Dx, Dy;

float D1[250][6], D2[250][6], D3[250][6];

int i, j, vnutri, n, N1, N2,N3,i1,j1,i2,j2,i3,j3;

float r, R;

float Sort[250];

float x, y;

float k, b, x1, x2, y1, y2;

int stroki, stolbcy;

char str[128], key, key2;

int flag=1;

char w[1];

while (vyhod==0)

{

MENU (flag);

key=getchar ();

sprintf (w, «%d», flag);

if (key=='4')

{

vyhod=1;

break;

}

if (key>w[0])

{

key=5;

printf («nO6ibka! Dlya vyhoda nazhmite 4 ili dla vvoda dannix nazhmite 1»);

}

switch (key)

{

case '1': //ввод данных

{

printf («nVvedem koordinati mnogougol’nika.»);

printf («nVvedite koordinatu A: n»);

scanf («%f %f», &Ax, &Ay);

printf («nVvedite koordinatu B: n»);

scanf («%f %f», &Bx, &By);

printf («nVvedite koordinatu C: n»);

scanf («%f %f», &Cx, &Cy);

printf («nVvedite koordinatu D: n»);

scanf («%f %f», &Dx, &Dy);

printf («nVvedite R: n»);

scanf («%f», &R);

printf («Vvedem 2 to4ki pryamoj.»);

printf («nPervaya:n»);

scanf («%f %f», &x1, &y1);

printf («nVtoraya:n»);

scanf («%f %f», &x2, &y2);

flag++;

getch ();

break;

}

case '2': //расчет

{

k=(y2-y1)/(x2-x1+0.0001); //составление ур-ий прямой

b=y2-k*x2;

N1=1;

j1=i1=n=0;

}

file1=fopen («C:\tochki.txt» ," rt"); // Открываем входной файл для чтения.

if (file1 == NULL) // Если файл не удалось открыть…

{

printf («Fajl ne najden»); // выводим об этом сообщение.

return;

}

else{

while (NULL≠fgets (str, 128, file1))

{

n++;

}

if (n>249) (n=250);

rewind (file1);

for (i=0;i

{

fscanf (file1," %f %f" ,&x,&y);

if (x>=0 && x<=12 && y>=0 && y<=15)

{

D1[i1][j1]=N1;

D1[i1][j1+1]=x;

D1[i1][j1+2]=y;

N1++;

i1++;

}

}

fclose (file1); //закрытие файла

N2=N3=1;

j=i2=j2=i3=j3=0;

for (i1=0; i1

{

vnutri=vnutri_ili_snaruji (Ax, Bx, Cx, Dx, Ay, By, Cy, Dy, D1[i1][j1+1], D1[i1][j1+2]);

if (vnutri==0) //формирование D2

{

D2[i2][j2]=N2;

D2[i2][j2+1]=D1[i1][j1];

D2[i2][j2+2]=D1[i1][j1+1];

D2[i2][j2+3]=D1[i1][j1+2];

r=rasstoyanie (D2[i2][j2+2], D2[i2][j2+3], k, b); //формирование D3

if (r<=R)

{

D3[i3][j3]=N3;

D3[i3][j3+1]=D2[i2][j2];

D3[i3][j3+2]=D2[i2][j2+1];

D3[i3][j3+3]=D2[i2][j2+2];

D3[i3][j3+4]=D2[i2][j2+3];

D3[i3][j3+5]=r;

Sort[j]=r;

j++;

i3++;

N3++;

}

N2++;

i2++;

}

}

N3=N3−1;

sortirovka (Sort, D3, N3); //сортировка по значению r

printf («nPoschitano!n»);

flag++;

getch ();

break;

}

case '3': //вывод результата

{

file2=fopen («C:\rezultat.txt», «at»);

printf («nKakoi massiv vyvesti? D1 — najmite 1, D2 — 2, D3 — 3, vse — 4: n»);

key2=getchar ();

key2=getchar ();

if (key2=='1')

{

stroki=N1−1;

stolbcy=3;

fprintf (file2, «nVse to4ki v zadannoj oblasti: n»);

printf («nVse to4ki v zadannoj oblasti: n»);

vyvod (D1,stroki, stolbcy);

}

if (key2=='2')

{

stroki=N2−1;

stolbcy=4;

fprintf (file2, «nnTo4ki VNE mnogougol’nika:n»);

printf («nnTo4ki VNE mnogougol’nika:n»);

vyvod (D2,stroki, stolbcy);

}

if (key2=='3')

{

stroki=N3;

stolbcy=6;

fprintf (file2, «nnTo4ki VNE mnogougol’nika i r<=R:n»);

printf («nnTo4ki VNE mnogougol’nika i r<=R:n»);

vyvod (D3,stroki, stolbcy);

}

if (key2=='4')

{

stroki=N1−1;

stolbcy=3;

fprintf (file2, «nVse to4ki v zadannoj oblasti: n»);

printf («nVse to4ki v zadannoj oblasti: n»);

vyvod (D1,stroki, stolbcy);

stroki=N2−1;

stolbcy=4;

fprintf (file2, «nnTo4ki VNE mnogougol’nika:n»);

printf («nnTo4ki VNE mnogougol’nika:n»);

vyvod (D2,stroki, stolbcy);

stroki=N3;

stolbcy=6;

fprintf (file2, «nnTo4ki VNE mnogougol’nika i r<=R:n»);

printf («nnTo4ki VNE mnogougol’nika i r<=R:n»);

vyvod (D3,stroki, stolbcy);

}

flag++;

fclose (file2);

getch ();

break;

}

case '4': //выход из программы

{

printf («nProgramma vypolnena. n»);

vyhod=1;

flag++;

getch ();

break;

}

default: //любая другая клавиша

{

getch ();

break;

}

} } }

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

Кроме того, была продемонстрирована работа с файлами данных для ввода и вывода данных.

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