множества N различных точек плоскости найти прямую, проходящую через начало координат и разделяющую это множество на два равномощных (или отличающихся на 1).
1.2. Краткое описание алгоритма решения задачи
В программе использована константа N=10, задающая количество точек плоскости множества.
Переменные, используемые в программе:
MnojTochek:array[1..3,1..N] типа real – массив, в котором для каждой точки плоскости из множества хранятся ее координаты и угол наклона (угол в радианах между положительной полуосью абсцисс и прямой, проходящей через начало координат и данную точку);
I,J типа integer – счетчики;
KolTochek типа integer – количество точек, для которых угол наклона лежит в промежутке [угол наклона исследуемой прямой; угол наклона исследуемой прямой + π];
X,Y типа real – координаты точки (не начало координат), через которую проходит исследуемая прямая;
Tmp типа real – вспомогательная переменная;
Fi типа real – значение в радианах угла наклона исследуемой прямой;
Razdeleno типа boolean – переменная, принимающая значение True, если прямая, проходящая через начало координат и разделяющая множество точек на два равномощных (или отличающихся на 1) найдена, и значение False в противном случае.
После определения переменных производится ввод координат точек множества и расчет угла наклона (по формуле выражения через координаты точки в прямоугольной системе координат координаты точки в полярной системе координат - угла φ).
Затем, с помощью пузырькового метода сортировки, производится сортировка точек в массиве по возрастанию угла наклона.
Далее осуществляется перебор всех точек множества в порядке их сортировки. При этом на каждом этапе перебора:
• рассчитывается угол наклона Fi искомой прямой (как полу сумма углов наклона текущей и следующей точек множества);
• производится подсчет количества точек, для которых угол наклона попадает в интервал [Fi;Fi+π];
• если количество попадаемых в указанный интервал точек составляет половину или половину ±1 множества точек (если количество точек нечетно), то перебор точек прекращается.
В конце программы производится расчет координаты второй точки, через которую проходит искомая прямая и в окне выполненной программы выводится заключение о работе программы.
После определения переменных производится ввод координат точек множества и расчет угла наклона (по формуле выражения через координаты точки в прямоугольной системе координат координаты точки в полярной системе координат - угла φ).
Затем, с помощью пузырькового метода сортировки, производится сотрировка точек в массиве по возрастанию угла наклона.
Далее осуществляется перебор всех точек множества в порядке их сортировки. При этом на каждом этапе перебора:
· расчитывается угол наклона Fi искомой прямой (как полусумма углов наклона текущей и следующей точек множества);
· производится подсчет количества точек, для которых угол наклона попадает в интервал [Fi;Fi+π];
· если количество попадаемых в указанный интервал точек составляет половину или половину ±1 множества точек (если количество точек нечетно), то перебор точек прекращается.
В конце программы производится расчет координаты второй точки, через которую проходит искомая прямая и в окне выполненной программы выводится заключение о работе программы.
1.3. Текст программы на алгоритмическом языке ABC Pascal
program zadacha_4_4;
uses crt;
const N=10;
var
MnojTochek:array[1..3,1..N] of real;
I,J,KolTochek:integer;
X,Y,Tmp,Fi:real;
Razdeleno:boolean;
begin
clrscr;
for I:=1 to N do
begin
write(‘Введите абсциссу',I,'-ой точки: ');
readln(MnojTochek[1,I]);
write(‘Введите ординату ',I,'-ой точки: ');
readln(MnojTochek[2,I]);
if (MnojTochek[1,I]>0) and (MnojTochek[2,I]>0) then
MnojTochek[3,I] := arctan(MnojTochek[2,I]/MnojTochek[1,I]);
if (MnojTochek[1,I]>0) and (MnojTochek[2,I]<0) then
MnojTochek[3,I] := arctan(MnojTochek[2,I]/MnojTochek[1,I])+2*Pi;
if (MnojTochek[1,I]<0) then
MnojTochek[3,I] := arctan(MnojTochek[2,I]/MnojTochek[1,I])+Pi;
if (MnojTochek[1,I]=0) and (MnojTochek[2,I]>0) then
MnojTochek[3,I] := Pi/2;
if (MnojTochek[1,I]=0) and (MnojTochek[2,I]<0) then
MnojTochek[3,I] := 3*Pi/2;
if (MnojTochek[1,I]=0) and (MnojTochek[2,I]=0) then
MnojTochek[3,I] := 0;
end;
for I:=1 to N-1 do
for J:=1 to N-I do
if (MnojTochek[3,J] > MnojTochek[3,J+1]) then
begin
Tmp:=MnojTochek[3,J+1];
MnojTochek[3,J+1]:=MnojTochek[3,J];
MnojTochek[3,J]:=Tmp;
end;
for I:=1 to N do
begin
KolTochek:=0;
if (I < N) then
Fi:=(MnojTochek[3,I]+MnojTochek[3,I+1])/2
else
Fi:=(MnojTochek[3,I]+MnojTochek[3,1])/2;
for J:=I+1 to N do
if MnojTochek[3,J]< Fi+Pi then
KolTochek:=KolTochek+1
else
J:=N+1;
if (((N mod 2=0) and (KolTochek=(N div 2))) or ((N mod 2<>0)
and (KolTochek >= (N div 2) - 1) and (KolTochek <= (N div 2) +1))) then
begin
I:=N+1;
Razdeleno:=True;
end;
end;
if Razdeleno then
begin
X:=1;
Y:=X*(SIN(Fi)/COS(Fi));
writeln(‘Заданное множество точек мощностью,N,’в отношении’, KolTochek,':',N-KolTochek);
writeln('Делит прямая, проходящая через начало координат[ 'X,',',Y,']');
end
else
writeln(‘Решение не найдено’);
end.
Задание 5.11
1.1. Постановка задачи
Игра "тараканьи бега на прямой" (делайте ставки, господа!).
1.2. Текст программы на алгоритмическом языке ABC Pascal.NET
В забегах будут принимать участие 6 тараканов, которые раскрашены в разные цвета:
uses
GraphABC, ABCButtons, ABCObjects, System.Media, Timers, System;
const
//число тараканов
N_TARAKAN=6;
//цветатараканов
COLOR_TARAKAN: array[1..N_TARAKAN] of Color = (Color.Red, Color.Yellow, Color.Blue, Color.Green, Color.SandyBrown, Color.LavenderBlush )
Переменные для хранения координат тараканов и их здоровья на момент старта:
var
//размеры окна
height, width: integer;
//элементы управления
lblTIme, lblWin: RectangleABC;
btnStart: ButtonABC;
_timer: Timer;
playSound:SoundPlayer;
//координатытараканов
x: array[1..N_TARAKAN] of real;
y: array[1..N_TARAKAN] of integer;
//здоровье тараканов
zdor: array[1..N_TARAKAN] of real;
tar: array[1..N_TARAKAN] of EllipseABC;
//время старта
startTime: DateTime;
//флажки начала и окончания забега
flgStart, flgFinish: boolean;
//координаты стартовой позиции
xStart:= 10;
yStart:= 60;
xFinish: integer;
// расстояние между дорожками по вертикали
dy:= 32;
//размеры тараканов
wTar:= 32;
hTar:= 16;
Время, прошедшее со старта выводим в метку lblTime в процедуре-обработчике таймера OnTick:
//отсчитываем время гонок
procedure OnTick;
begin
var t:= DateTime.Now - startTime;
var s:= 'Время: ' + t.Seconds.ToString() + '.' + t.Milliseconds.ToString() ;
lblTIme.Text:= s;
End;
Для точного подсчета времени используем свойство Now структуры записи DateTime.
В процедуре prepareсоздаем новых тараканов заданного цвета и размера. В нашей модели роль тараканов будут исполнять эллипсисы.
//готовим тараканов к старту
procedure prepare;
begin
//начинаемновыйзабег
flgFinish := false;
lblTime.Text:= 'Время 0';
For var i:= 1 to N_TARAKAN do begin
//цвет таракана
var clr:= COLOR_TARAKAN[i];
SetBrushColor(clr);
SetPenColor(clr)
//создаемновыхтараканов
//и расставляем их у стартовой черты
y[i]:= yStart + dy * (i-1);
x[i]:= xStart;
tar[i]:= new EllipseABC(Floor(x[i]), y[i], wTar, hTar, clr);
//здоровьетараканов
zdor[i]:= (PABCSystem.Random(30)+1)/100 + 1.2;
end;
//чертим линию старта
SetPenWidth(2);
SetPenColor(Color.Red);
Line(xStart+wTar,yStart, xStart+wTar, y[N_TARAKAN]+ hTar);
//чертим линию финиша
SetPenColor(Color.LightGreen);
xFinish:= width-wTar;
Line(xFinish, yStart, xFinish, y[N_TARAKAN]+ hTar);
//прячем информационное окно
lblWin.Visible:= false;
end;
//вычисляем новые координаты тараканов
procedure calcNewCoords;
begin
For var i:= 1 to N_TARAKAN do begin
//случайное перемещение
vardx:= (PABCSystem.Random(43)+1)/10 + 0.9;
//новое положение таракана на дистанции
x[i] := x[i] + dx*zdor[i];
end;
end;
procedure testFinish;
begin
var xEnd:=0.0;
var n:=0;
flgFinish:= false;
For var i:= 1 to N_TARAKAN do begin
if (x[i] >= xFinish-wTar) Then begin
flgFinish:= true;
_timer.Stop();
If (x[i] > xEnd) then begin
//определяем номер победителя
n:= i;
xEnd:= x[i];
End;
end;
end;
If (flgFinish= true) then begin
playSound.Play();
var s:= ' Победилтаракан # ' + n.ToString() + '!';
var t:= DateTime.Now - startTime;
s:= s + 'Его время: ' + t.Seconds.ToString() + '.' + t.Milliseconds.ToString();
flgStart:= false;
lblWin.Text:= s;
lblWin.Visible:= true;
//задержка
Sleep(6000);
//уничтожаем старых тараканов
For var i:= 1 to N_TARAKAN do
tar[i].Destroy;
//готовимся к новой игре
prepare();
btnStart.Visible:= true;
end;
end;
//игровойцикл
procedure game;
begin
While (not flgFinish) do begin
//Нажатакнопка "Начатьзабег!":
If not flgStart then exit;
//вычисляем новые координаты тараканов
calcNewCoords();
//и перемещаем их туда
For var i:= 1 to N_TARAKAN do
tar[i].MoveTo(Floor(x[i]), y[i]);
//устанавливаем скорость работы программы
Sleep(20);
//проверяем, не финишировал ли таракан
testFinish();
end;
end;
procedure btnStart_OnClick;
begin
btnStart.Visible:= false;
lblTime.Visible:= true;
//обнуляем время
lblTime.Text:= 'Время: ' + 0.ToString();
//запускаме таймер
_timer.Start();
//запускаем время старта по системным часам
startTime:= DateTime.Now;
//стреляем из стартового пистолета
flgStart:= True;
game();
end;
//ОСНОВНАЯПРОГРАММА
begin
SetWindowTitle('Òàðàêàíüè áåãà');
SetWindowWidth(640);
Window.Height:= 480;
Window.CenterOnScreen();
Window.IsFixedSize := true;
Window.Clear(RGB($2F,$4F,$4F));
height := Window.Height;
width := Window.Width;
//Кнопка
//Начатьзабег!
btnStart := new ButtonABC(10, Height-40, 120, 30, ‘Начатьзабег!!', clMoneyGreen
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.