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

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

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

Санкт-Петербургский государственный электротехнический университет "ЛЭТИ"

Кафедра: КСУ

Курсовая работа

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

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

Группа: 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<stdio.h>

#include<conio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

#include<ctype.h>

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 && y1<By) || (y1<Ay && y1>By)) //Подсчёт точек пересечения параллельной прямой

{

massiv[z]=y1;

z++;

}

if ((y2>Cy && y2<By) || (y2<Cy && y2>By))

{

massiv[z]=y2;

z++;

}

if ((y3>Cy && y3<Dy) || (y3<Cy && y3>Dy))

{

massiv[z]=y3;

z++;

}

if ((y4>Ay && y4<Dy) || (y4<Ay && y4>Dy))

{

massiv[z]=y4;

z++;

}

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

{

if (y<massiv[0] && y>massiv[1]) vnutri=1;

if (y>massiv[0] && y<massiv[1]) vnutri=1;

}

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<n-1);

perv=Sort[k];

Sort[k]=max;

Sort[nomer]=perv;

k++;

i=k;

}

while(k<n-1);

for(j=0;j<n;j++) //Подстановка строк по значению r

{

for(i3=0;i3<n;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<stroki; i++)

{

if((i%20)==0)

{

getch();

}

for(j=k; j<stolbcy; 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("\n\nVvedite 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<n;i++) //формирование D1

{

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<N1-1; 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, "\n\nTo4ki VNE mnogougol'nika:\n");

printf("\n\nTo4ki VNE mnogougol'nika:\n");

vyvod(D2,stroki,stolbcy);

}

if (key2=='3')

{

stroki=N3;

stolbcy=6;

fprintf(file2, "\n\nTo4ki VNE mnogougol'nika i r<=R:\n");

printf("\n\nTo4ki 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, "\n\nTo4ki VNE mnogougol'nika:\n");

printf("\n\nTo4ki VNE mnogougol'nika:\n");

vyvod(D2,stroki,stolbcy);

stroki=N3;

stolbcy=6;

fprintf(file2, "\n\nTo4ki VNE mnogougol'nika i r<=R:\n");

printf("\n\nTo4ki 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;

}

} } }



Выводы

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

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

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

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