Модельная задача Задание массивов. Машинный ноль

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

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

Прямая линия, проходящая через две точки, определяется уравнением

= . (2)

Прямая делит плоскость на две части и по разные стороны прямой выражение уравнения (2), как функция x и y, становится неравенством того или иного знака. Множество точек на плоскости задается массивами X и Y координат этих точек. Для каждой пары точек из множества нужно найти количество точек выше и ниже прямой, определяемой данной парой точек и найти прямую с минимальной разницей.

Псевдокод

Задать количество точек N и массивы их координат X и Y.

Задать и обнулить счетчик разности для прямой - (xl1, yl1, xl2, yl2, Nl), где xl1, yl1, xl2, yl2- координаты точек, задающих прямую, а Nl искомая разность.

xl1, yl1, xl2, yl2 =0; Nl = N.

Цикл по парам точек множества

Count1, Count2 = 0 ‘Счетчики положения точек относительно прямой.

Цикл по точкам (x, y) множества

Если f(x, y) >0 То ‘f – вычисляется из (2)

Count1= Count1 + 1 ‘По одну сторону прямой

Иначе

Count2= Count2 + 1 ‘По другую сторону прямой

Все Если

Все цикл по точкам множества

Если | Count1 - Count2| < Nl То

Присвоить координаты точек текущей прямой счетчику разности,

Nl = | Count1 - Count2|

Все Если

Все цикл по парам точек

Программа

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Program4._1

{

class Program

{

static void Main(string[] args)

{

int N;

int[] X = new int[1000]; //объявление массива, как унаследованного от базового класса Array

int[] Y = new int[1000];

int x11, y11, x12, y12, N1;

int I, J, K;

int Count1, Count2, F, mDiff;

Console.Write("Enter N: "); // Ввод числа N - размерности массива

N = Convert.ToInt32(Console.ReadLine());

x11 = 0; y11 = 0; x12 = 0; y12 = 0; N1 = N; // Обнулить счетчик разности

for (I=0; I<N; I++)

{

Console.Write("Enter X" + (I + 1) + ": ");

X[I] = Convert.ToInt32(Console.ReadLine());

Console.Write("Enter Y" + (I + 1) + ": ");

Y[I] = Convert.ToInt32(Console.ReadLine());

}

for (I=1; I<N; I++)

for (J=I+1; I<=N; I++) // Цикл по парам точек

{

Count1 = 0; Count2 = 0;

for (K=0; K<N; K++)

{

// Подсчет разности левой и правой частей выражения (2)

F = (X[K] - X[I]) * (Y[J] - Y[I]) - (Y[K] - Y[I]) * (X[J] - X[I]);

// В машине нет точного нуля

if (F>0)

Count1++;

if (F<0)

Count2++;

}

mDiff = Math.Abs(Count1 - Count2);

if (mDiff<N1)

{

x11 = X[I];

y11 = Y[I];

x12 = X[J];

y12 = Y[J];

N1 = mDiff; // Задать счетчик разности

}

}

Console.WriteLine();

Console.WriteLine("Result:");

Console.WriteLine("x0=" + x11 + " y0=" + y11);

Console.WriteLine("x1=" + x12 + " y1=" + y12);

Console.WriteLine("Diff = " + N1);

Console.ReadKey();

}

}

}

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

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

Для определения координат центра окружности, проходящей через 3 точки нужно:

Провести две прямые через данные три точки

· Найти координаты центров отрезков, соединяющих точки

· Провести через центральные точки две прямые, перпендикулярно исходным прямым. (Прямая с уравнением (y-y₀ ) = - 1/p(x-x₀) проходит через точку с координатами (x₀ , y₀ ) перпендикулярно линии у = px.).

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

Перебор всех окружностей обеспечивает цикл по тройкам точек (см. программу задачи 23).

Псевдокод

Цикл по тройкам точек ‘Перебор окружностей

Определить радиус и центр окружности

Обнулить локальный счетчик

Цикл по точкам множества

Если точка лежит на расстоянии радиуса до центра ТО

Увеличить локальный счетчик

Все Если

Все цикл по точкам множества

Если локальный счетчик больше, То

Запомнить окружность

Все Если

Все цикл по тройкам

22. Определить радиус и центр окружности, на которой лежит наибольшее число точек заданного на плоскости множества точек.

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

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

25. Во множестве точек на плоскости найти пару точек с максимальным расстоянием между ними.

26. Расстояние между двумя множествами точек – это расстояние между наиболее близко расположенными точками этих множеств. Найти расстояние между двумя заданными множествами точек на плоскости.

27. Задано множество точек M на плоскости. Определить, верно ли, что для каждой точки A M существует точка В M (A ≠ B) такая, что не существует двух точек множества M, лежащих по разные стороны от прямой AB.

См. решение задачи 23

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

29. Задано множество точек M в трехмерном пространстве. Найти такую из них, что шар заданного радиуса с центром в этой точке содержит максимальное число точек из M.

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

Для вычисления площади треугольника использовать формулу Герона.

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

X координата центра тяжести системы материальных точек вычисляется по формуле x_c= . Аналогично вычисляется y и z координаты.

32. Заданы два множества точек на плоскости. Построить пересечение и разность этих множеств.

33. Множество точек на плоскости назовем регулярным, если вместе с парой различных точек оно содержит и третью вершину правильного треугольника с вершинами в этих точках. Определить, регулярно ли заданное множество.

Координату вершины правильного треугольника можно вычислить по координатам двух других его вершин (неоднозначно).

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

См. задачу 24. Далее найти по трем сторонам площадь треугольника, вписанного в окружность.

35. На плоскости задано множество попарно различных прямых, коэффициентами k уравнения y=kx+b. Указать среди них ту прямую, которая имеет максимальное число пересечений с остальными прямыми.

Две прямые с неравными коэффициентами k уравнений пересекаются.

36. Задано множество прямых на плоскости (коэффициентами своих уравнений). Подсчитать количество точек пересечения этих прямых.

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

38. Задано множество точек на плоскости, не лежащих на одной прямой. Определить минимальное подмножество точек, после удаления которых остаются точки, лежащие на одной прямой.

Задача сводится к поиску прямой, на которой лежит максимальное количество точек.

39. Среди треугольников с вершинами в заданном множестве точек на плоскости указать такой, стороны которого содержат максимальное число точек заданного множества.

Если точки (x₀,y₀), (x₁,y₁), (x₂,y₂) лежат на одной прямой, то точка (x₀,y₀) лежит между двумя остальными, когда

(x₁-x₀) (x₂-x₀) < 0 и (y₁-y₀) (y₂-y₀) < 0. Доказать.

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

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

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

43. В трехмерном пространстве задано множество материальных точек. Каждая из точек с максимальной массой исчезает, теряя десятую часть своей массы и раздавая оставшуюся массу поровну всем остальным, более «легким» точкам. Определить суммарную массу множества точек в тот момент, когда все оставшиеся в ней точки имеют одинаковую массу.

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

Координаты точек не влияют на решение задачи. Определим точки массивом из их весов. Вопрос – что делать с исчезающими точками. Реально убирать нулевые элементы из массива хлопотно, можно ограничится проверкой величины массы и не обращать внимания на нулевые массы.

44. Найти ромб наибольшей площади с вершинами в заданном множестве точек на плоскости.

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

Для данной четверки точек нужно провести прямые (диагонали) через точки (1,3) и (2,4). Если прямые перпендикулярны, то нужно проверить точку их пересечения. Для ромба точка пересечения делит диагонали пополам (См. задачу 24).

45. На плоскости заданы множество точек и множество окружностей. Найти две такие различные точки из A, что проходящая через них прямая пересекается с максимальным количеством окружностей из B.

Окружности строить не нужно. Для анализа ситуации достаточно определить расстояние от центра окружности до прямой.

46. На плоскости задано n множеств по m точек в каждом. Среди точек первого множества найти такую точку, которая принадлежит наибольшему количеству множеств.m

Для решения задачи сформируйте два двумерных массива n m по каждой из координат. Для точек с координатами 1 m организуйте цикл поиска по множествам координат * m, * меняется от 2 до n.

47. Задано множество точек на плоскости. Выбрать из них четыре разные точки, которые являются вершинами квадрата наибольшего периметра.

Решается аналогично задаче 47, с учетом, что квадрат - частный случай ромба.

48. Из заданного множества точек на плоскости выбрать три разные точки A, B, C так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества.

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

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

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

Устроить цикл по парам точек. Точка принадлежит окружности данного радиуса, если находится на расстоянии меньшем радиуса.

Псевдокод

Цикл по I от 1 до N -1

M1 = количество точек в окружности I

Цикл по J от I + 1 до N

M2 = количество точек в окружности J

Если M1 = M2 То

Печать результата

End программы

Все Если

Все цикл по J

Все цикл по I

Печать – таких окружностей нет

Поиск по сайту: