Лабораторные методы программирования

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ

НГТУ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

РАСЧЕТНО ГРАФИЧЕСКАЯ РАБОТА № 1

ПО ДИСЦИПЛИНЕ:

ЛАБОРАТОРНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ

ФПМИ

ГРУППА: ПМ-21

СТУДЕНТ: Воронов А.С.

ПРЕПОДАВАТЕЛЬ: Хиценко В. П.

НОВОСИБИРСК 2002 г.

1. Условие задачи

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

2. Анализ задачи

Дано: Множество точек {(x₁,y₁), (x₂,y₂),…,(x_n,y_n) | x,y Î R, n Î N} и два радиуса r₁, r₂ Î R

Результат: Координаты двух различных точек

Основные подзадачи:

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

2)  Расчет количества точек попадающих в окружности

3)  Нахождение двух окружностей с равным содержанием точек, разными центрами и радиусами

4)  Вывод координат центов этих окружностей

Метод решения:

Находим количество точек лежащих в окружности с радиусом r₁ и центрами в точках (x_i,y_i), iÎ[1..n]

Находим количество точек лежащих в окружности с радиусом r₂ и центрами в точках (x_i,y_i), iÎ[1..n]

Находим две окружности с различными центрами и радиусами, но с равным количеством содержащихся в них точек.

3. Структура данных

Множество точек {(x₁,y₁), (x₂,y₂),…,(x_n,y_n) | x,y Î R, n Î N} и два радиуса r₁, r₂ Î R

Центры двух искомых окружностей (a₁,b₁), (a₂,b₂) a₁,b₁,a₂,b₂

Множества T1₁…T1_n и T2₁…T2_n – множества содержащие количество точек лежащих в окружностях с радиусами r₁, r₂ и центрами в точках (x_n,y_n)

4. Алгоритм задачи

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

#include <stdio.h>

#include <conio.h>

#include <math.h>

#define n 5

void input (float X[n],float Y[n])   // Ввод координат

{

int k;

printf ("Введите пары координат точек (x,y)\nВсего %d",n);

printf (" штук\n");

k=0;

while (k<=n-1)

{

scanf ("%f%f",&X[k],&Y[k]);

k++;

}

}

void main ()

{

float X[n],Y[n],r1,r2,a,b;

int i,j,T1[n],T2[n],c;

clrscr ();

input (X,Y);

printf ("Введите длины двух радиусов\n");

scanf ("%f%f",&r1,&r2);

a=r1*r1;

b=r2*r2;

i=0;

j=0;

while (i<=n-1)

{  // 2

T1[i]=-1;

T2[i]=-1;

while (j<=n-1)

{  // 3

if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<=a) T1[i]++;

if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<=b) T2[i]++;

j++;

}  // 3

i++;

j=0;

}  // 2

i=0;

j=1;

a=0;

b=0;

while (i<=n-1)

{  // 4

while (j<=n-1)

{  // 5

if (T1[i]==T2[j])

{  // 6

if (T1[i]>a) {a=T1[i]; b=i; c=j;}

}  // 6

j++;

}  // 5

i++;

j=1+i;

}  // 4

printf ("Центры искомых окружностей в \n(%f",X[b]);

printf (",%f",Y[b]);

printf (") - центр 1-ой окружности с радиусом %f",r1);

printf ("\n (%f",X[c]);

printf (",%f",Y[c]);

printf (") - центр 2-ой окружности с радиусом %f",r2);

getch ();

}

6. Набор тестов

№ теста	1-ая точка	2-ая точка	3-ая точка	4-ая точка	5-ая точка	1-ый радиус	2-ой радиус	Центр 1-ой	Центр 2-ой
1	(1,2)	(2,2)	(3,3)	(3,1)	(3,-1)	1	2	(1,2)	(3,-1)
2	(2,2)	(2,3)	(-1,-1)	(-1.5,    -1.5)	(-1,-2)	1	2	(-1,-1)	(-1.5      -1.5)
3	(2,2)	(2,3)	(-1,-1)	(-1.5,      -1.5)	(-1,-2)	2	1	(-1,-1)	(-1.5,     -1.5)