Программирование и основы алгоритмизации
Министерство
образования и науки Российской Федерации
Санкт-Петербургский
государственный электротехнический университет "ЛЭТИ"
Кафедра:
КСУ
Курсовая
работа
"Программирование
и основы алгоритмизации"
Студент: Моисеева
О.И.
Группа: 1491
Преподаватель:
Ветчинкин А. С.
Санкт-Петербург,
2012 год
Постановка задачи и математическая модель задачи
математический модель
программа пользователь
Постановка задачи:
1. Ввод данных должен осуществляться из файла о
наборе точек и с клавиатуры координаты уравнений прямой.
2. Результаты расчета должны выводиться в
виде таблиц на экран и в файл, сохраняясь на жёстком диске.
. Процедуры расчета расстояния 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>*file1;*file2;vnutri_ili_snaruji
(float Ax, float Bx, float Cx, float Dx, float Ay, float By, float Cy, float
Dy, float x, float y)
{vnutri=0, z=0;y1, y2, y3,
y4;massiv[4];Kbc, Bbc, Kcd, Bcd, Kad, Bad, Kab, Bab;
Kbc=(By-Cy)/(Bx-Cx+0.0001); //коэффициенты в
ур-ие прямой
Bbc=By-Kbc*Bx;=(Dy-Cy)/(Dx-Cx+0.0001);=Cy-Kcd*Cx;=(Dy-Ay)/(Dx-Ax+0.0001);=Ay-Kad*Ax;=(By-Ay)/(Bx-Ax+0.0001);
Bab=Ay-Kab*Ax;=Kab*x+Bab; //Находим точки
пересечения со сторонами
многогранника=Kbc*x+Bbc;=Kcd*x+Bcd;=Kad*x+Bad;((y1>Ay && y1<By)
|| (y1<Ay && y1>By)) //Подсчёт точек пересечения параллельной
прямой
{[z]=y1;++;
}((y2>Cy && y2<By) ||
(y2<Cy && y2>By))
{[z]=y2;++;
}((y3>Cy && y3<Dy) ||
(y3<Cy && y3>Dy))
{[z]=y3;++;
}((y4>Ay && y4<Dy) ||
(y4<Ay && y4>Dy))
{[z]=y4;++;
}(z==2) //Проверка условия внутри многоугольника
{(y<massiv[0] &&
y>massiv[1]) vnutri=1;(y>massiv[0] && y<massiv[1]) vnutri=1;
}(vnutri);
}rasstoyanie (float x, float y,
float k, float b)
{d;=(fabs(k*x-y+b)/sqrt(k*k+1));
//рассчёт расстояния от точки до прямой(d);
}sortirovka(float
Sort[], float D3[250][6], int n)//Использование метода простого перебора
{i=0,k=0,nomer, j, j3=0, i3;max,
perv;temp, temp1, temp2, temp3, temp4, temp5;
do
//Сортировка значений r
{=Sort[i];
nomer=i;
{(Sort[i+1]>max)
nomer=i+1;(Sort[i+1]>max) max=Sort[i+1];++;
}(i<n-1);=Sort[k];[k]=max;[nomer]=perv;++;=k;
}(k<n-1);
for(j=0;j<n;j++)
//Подстановка строк по значению r
{(i3=0;i3<n;i3++)
{(Sort[j]==D3[i3][j3+5])
{=D3[j][j3];=D3[j][j3+1];=D3[j][j3+2];=D3[j][j3+3];=D3[j][j3+4];=D3[j][j3+5];[j][j3]=D3[i3][j3];[j][j3+1]=D3[i3][j3+1];[j][j3+2]=D3[i3][j3+2];[j][j3+3]=D3[i3][j3+3];[j][j3+4]=D3[i3][j3+4];[j][j3+5]=D3[i3][j3+5];[i3][j3]=temp;[i3][j3+1]=temp1;[i3][j3+2]=temp2;[i3][j3+3]=temp3;[i3][j3+4]=temp4;[i3][j3+5]=temp5;;
}
}
}(0);
}vyvod(float Massiv[250][6], int stroki,
int stolbcy)
{i,j,k;
if(stolbcy==6)
{=1;
}
{=0;
{((i%20)==0)
{();
}(j=k; j<stolbcy; j++)
{(stolbcy)
{6:
{(j)
{1:("D2=");;2:("D1=");;3:("x=");;4:("y=");;5:("d=");;
};
}3:
{(j)
{0:("D1=");;1:("x=");;2:("y=");;
};
}4:
{(j)
{0:("D2=");;1:("D1=");;2:("x=");;3:("y=");;
};
}
}("%1.1f
",Massiv[i][j]);(file2, "%1.1f ",Massiv[i][j]);
}("\n");(file2,"\n");
}
}MENU(int flag) //основное меню
{("cls"); //очистка экрана("\nMenu:\n");
//вывод меню(flag>1)
printf("1. Vvod na4al'nyh dannyh - ok!");printf("1. Vvod
na4al'nyh dannyh");(flag>2) printf("\n2. Ras4et -
ok!");printf("\n2. Ras4et");(flag>3) printf("\n3. Vyvod
rezul'tatov - ok!");printf("\n3. Vyvod rezul'tatov");("\n4.
Vyhod");("\n\nVvedite N punkta: ");
return
0;
}main()
//описание переменных
{
int
vyhod=0;Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;D1[250][6], D2[250][6], D3[250][6];i,j,vnutri,
n,N1,N2,N3,i1,j1,i2,j2,i3,j3;r,R;Sort[250];x, y;k, b, x1, x2, y1, y2;stroki,
stolbcy;str[128], key, key2;flag=1;w[1];(vyhod==0)
{(flag);=getchar();(w,
"%d", flag);(key=='4')
{=1;;
}(key>w[0])
{=5;("\nO6ibka! Dlya vyhoda
nazhmite 4 ili dla vvoda dannix nazhmite 1");
}(key)
{'1': //ввод данных
{("\nVvedem koordinati
mnogougol'nika.");("\nVvedite koordinatu A:\n");("%f
%f", &Ax, &Ay);("\nVvedite koordinatu B:\n");("%f %f",
&Bx, &By);("\nVvedite koordinatu C:\n");("%f %f",
&Cx, &Cy);("\nVvedite koordinatu D:\n");("%f %f",
&Dx, &Dy);("\nVvedite R:\n");("%f",
&R);("Vvedem 2 to4ki
pryamoj.");("\nPervaya:\n");("%f %f", &x1,
&y1);("\nVtoraya:\n");("%f %f", &x2,
&y2);++;();;
}'2': //расчет
{
k=(y2-y1)/(x2-x1+0.0001);
//составление ур-ий прямой=y2-k*x2;=1;=i1=n=0;
}=fopen("C:\\tochki.txt","rt");
// Открываем входной файл для чтения.(file1 == NULL) // Если файл не удалось
открыть...
{("Fajl
ne najden"); // выводим об этом сообщение.
return;
}{(NULL!=fgets(str,128,file1))
{++;
}(n>249) (n=250);(file1);
for
(i=0;i<n;i++) //формирование D1
{(file1,"%f
%f",&x,&y);(x>=0 && x<=12 && y>=0
&& y<=15)
{[i1][j1]=N1;[i1][j1+1]=x;[i1][j1+2]=y;++;++;
}
}(file1); //закрытие файла=N3=1;=i2=j2=i3=j3=0;(i1=0;
i1<N1-1; i1++)
{=vnutri_ili_snaruji (Ax, Bx, Cx,
Dx, Ay, By, Cy, Dy, D1[i1][j1+1], D1[i1][j1+2]);
if
(vnutri==0) //формирование D2
{[i2][j2]=N2;
D2[i2][j2+1]=D1[i1][j1];[i2][j2+2]=D1[i1][j1+1];[i2][j2+3]=D1[i1][j1+2];=rasstoyanie
(D2[i2][j2+2], D2[i2][j2+3], k,b); //формирование D3(r<=R)
{[i3][j3]=N3;[i3][j3+1]=D2[i2][j2];[i3][j3+2]=D2[i2][j2+1];[i3][j3+3]=D2[i2][j2+2];[i3][j3+4]=D2[i2][j2+3];[i3][j3+5]=r;[j]=r;++;++;++;
}++;
i2++;
}
}=N3-1;(Sort,
D3, N3); //сортировка по значению r
printf("\nPoschitano!\n");++;();
break;
}'3':
//вывод результата
{
file2=fopen("C:\\rezultat.txt",
"at");("\nKakoi massiv vyvesti? D1 - najmite 1, D2 - 2, D3 - 3,
vse - 4:\n");=getchar();=getchar();(key2=='1')
{=N1-1;=3;(file2, "\nVse to4ki
v zadannoj oblasti:\n");("\nVse to4ki v zadannoj
oblasti:\n");(D1,stroki,stolbcy);
}(key2=='2')
{=N2-1;=4;(file2, "\n\nTo4ki
VNE mnogougol'nika:\n");("\n\nTo4ki VNE
mnogougol'nika:\n");(D2,stroki,stolbcy);
}(key2=='3')
{=N3;=6;(file2, "\n\nTo4ki VNE
mnogougol'nika i r<=R:\n");("\n\nTo4ki VNE mnogougol'nika i
r<=R:\n");(D3,stroki,stolbcy);
}(key2=='4')
{=N1-1;=3;(file2, "\nVse to4ki
v zadannoj oblasti:\n");("\nVse to4ki v zadannoj
oblasti:\n");(D1,stroki,stolbcy);=N2-1;=4;(file2, "\n\nTo4ki VNE
mnogougol'nika:\n");("\n\nTo4ki VNE
mnogougol'nika:\n");(D2,stroki,stolbcy);=N3;=6;(file2, "\n\nTo4ki VNE
mnogougol'nika i r<=R:\n");("\n\nTo4ki VNE mnogougol'nika i
r<=R:\n");(D3,stroki,stolbcy);
}++;
fclose(file2);();;
{
printf("\nProgramma vypolnena.
\n");=1;++;();;
}
default: //любая другая клавиша
{();;
}
}
} }
Выводы
В
данной курсовой работе использовались двумерные массивы, в которые записывалась
вся информация о точках используемых в процессе работы программы.
Кроме
того, была продемонстрирована работа с файлами данных для ввода и вывода
данных.
Так
же были написаны функции для решения конкретных задач, что позволило сделать
программу более логичной и понятной.