Главная » Pascal, Исходники, Разное » Нахождение максимального кол-ва точек прямой размещенной на отрезке AB
Ноя
28

Нахождение максимального кол-ва точек прямой размещенной на отрезке AB

Задана прямая из N элементов. Найти максимальное количество точек, которые могли бы строго разместится на отрезке длиною L заданой прямой.

[sourcecode highlight=»62″ language=»css»]
uses Crt;
const
n = 10; { количество элементов в массиве }

var
A: Array[1..n] of Integer; { наша прямая из N элементов }
i, j, q, qMax: Byte;
Exch: Boolean;
Temp: Integer;
l, ls: Word;

begin
ClrScr; Randomize;
for i:=1 to n do { инициализация массива }
begin
A[i]:=Random(50);
Write(A[i]:3);
end; Writeln;

Exch:=True; j:=1; { сортировка массива }
While Exch do
begin
Exch:=False;
for i:=1 to n-j do
if A[i] > A[i+1] then
begin
Temp:=A[i];
A[i]:=A[i+1];
A[i+1]:=Temp;
Exch:=True;
end;
Inc(j);
end;

for i:=1 to n do { вывод отсортированного массива }
Write(A[i]:3);

Writeln;
Readln(l); { ввод длины отрезка L }
qMax:=1; i:=0;

{ нахождение максимального числа точек (элементов массива),
которые могут строго находится на заданом отрезке L }
Repeat
Inc(i);
q:=1; ls:=0;





for j:=i to n-1 do
begin
ls:=ls+A[j+1]-(A[j]);
if l > ls then Inc(q)
else
begin
ls:=0;
q:=1;
end;
if q > qMax then qMax:=q;
end;
Until n-1 <= i;
Writeln;
Write(qMax); { вывод максимального числа точек }
end.
{ prepared special for www.kpeople.ru by AlexeyJava }
[/sourcecode]

Точками в данной программе выступают элементы массива заданной длины N, а их координатами — элементы массива; поэтому мы и сортируем массив по-возрастанию, что было его легче просматривать. А теперь более конкретно о логике этой программы: перем. q будет подсчитывать точки которые могут быть строго помещены в отрезок длиною L, т.е. помещены так чтобы L был больше расстояния между первой и последней точкой помещенной в отрезок, т.е. переменной Ls, значить L > Ls.
На начале qMax:=1 и в цикле q:=1 потому что, даже если L будет задано нулем, одна точка в отрезке все равно сможет поместится. Вложенный цикл используется для того чтобы искать разные комбинации точек помещенных в прямую и находить соответствуещее qMax для всей последовательности.
Рассмотрим пример:

  • Случайно сгенегированная последовательность: 12 24 26 36 35 12 40 49 9 13
  • Отсортированная последовательность: 9 12 12 13 24 26 35 36 40 49
  • Вводим от любую длину отрезка L например: 15
  • Получаем  максимальное число точек qMax: 5   [ т.е.  12 12 13 24 26 , а не 9 12 12 13 24,  где q = 4 ]


Понравилась статья? Сделай приятно ее автору, поделись с друзьями:


Хотите получать обновления данного блога на EMail?

Введите адрес Почтового Ящика:




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