Öåëü ðàáîòû: Ïîëó÷èòü íàâûêè îïèñàíèÿ ìåòîäà ðåøåíèÿ ìàòåìàòè÷åñêîé
ìîäåëè íà ïðèìåðå ðåøåíèÿ çàäà÷ àíàëèòè÷åñêîé ãåîìåòðèè.
Çàäàíèå: 1) Ñîãëàñíî
çàäàííîìó âàðèàíòó îïèñàòü ìåòîäû ðåøåíèÿ çàäà÷è.
2) Íà îñíîâå îïèñàííûõ
ìåòîäîâ ðàçðàáîòàòü ìàòåìàòè÷åñêóþ ìîäåëü.
Çàäà÷à: Çàäàíî ìíîæåñòâî
òî÷åê, íàéòè ïàðàìåòðû îêðóæíîñòè ìèíèìàëüíîãî ðàäèóñà, ïðîõîäÿùèå ÷åðåç òðè
òî÷êè ìíîæåñòâà.
Õîä ðàáîòû
²)Ìàòåìàòè÷åñêàÿ ïîñòàíîâêà çàäà÷è:
1) Íàéòè íàèìåíüøèé ðàäèóñ îêðóæíîñòè ïî ôîðìóëå: i :
= 1…n
D=
, ãäå ;
j : = 1… 2)D1,D2,D3- ðàäèóñû
îêðóæíîñòè;
3) X
Y
, X
Y
, X
Y
, X
Y
- êîîðäèíàòû òî÷åê ìíîæåñòâà;
4) D=
-ôîðìóëà íàõîæäåíèÿ ðàññòîÿíèÿ ìåæäó äâóìÿ òî÷êàìè;
5)
-ñèñòåìà óðàâíåíèÿ èëè
íåðàâåíñòâà;
6)
-ñîâîêóïíîñòü óðàâíåíèÿ
èëè íåðàâåíñòâà;
7)
-çíàê áîëüøå
-çíàê ìåíüøå
=-çíàê ðàâíî;
8) A, B, C, E- íåêîòîðûå òî÷êè ñ îïðåäåëåííûìè
êîîðäèíàòàìè
²²) Îïèñàíèå
ìåòîäîâ ðåøåíèÿ:
Ìåòîä 1. Ìåòîä
çàêëþ÷àåòñÿ â òîì , ÷òî áû íàéòè íàèìåíüøèé ðàäèóñ îêðóæíîñòè ñ ïîìîùüþ
ïîñëåäîâàòåëüíîãî ñîåäèíåíèÿ òî÷åê ñ îäíîé, à çàòåì ïðîäåëûâàíèÿ ýòîãî ñ êàæäîé
èç òî÷åê ìíîæåñòâà. Çàòåì, ñ ïîìîùüþ ôîðìóëû íàõîæäåíèÿ ðàññòîÿíèÿ ìåæäó äâóìÿ
òî÷êàìè
(D=
),íåîáõîäèìî âû÷èñëèòü äëèíû ïîëó÷èâøèõñÿ îòðåçêîâ.
Ïîñëå âû÷èñëåíèÿ îòðåçêè íåîáõîäèìî ñðàâíèòü ìåæäó ñîáîé.  ðåçóëüòàòå åñëè äâà
îòðåçêà, âûõîäÿùèå èç îäíîé òî÷êè, ðàâíû - ýòî è åñòü ðàäèóñû îêðóæíîñòè. Íî èç
óñëîâèÿ, ïîñòàâëåííûå çàäà÷åé, íåîáõîäèìî íàéòè ìèíèìàëüíûé ðàäèóñ îêðóæíîñòè
ïðîõîäÿùåé ÷åðåç òðè òî÷êè ìíîæåñòâà. Åñëè ïðè ñðàâíåíèè íåñêîëüêî ïàð
îäèíàêîâûõ îòðåçêîâ - íåîáõîäèìî íàéòè íàèìåíüøóþ ïàðó – ýòî è áóäåò
ìèíèìàëüíûé ðàäèóñ îêðóæíîñòè. (Ðèñ.¹1)
Ðèñ.¹1
Ìåòîä 2.Âòîðîé ìåòîä
çàêëþ÷àåòñÿ â òîì, ÷òî áû èñêàòü ìèíèìàëüíûé ðàäèóñ îêðóæíîñòè ïðè ïîìîùè
ñîåäèíåíèÿ ìíîæåñòâî òî÷åê ìåæäó ñîáîé, è â ðåçóëüòàòå ïîëó÷åíèå ìíîæåñòâî
ãåîìåòðè÷åñêèõ ôèãóð ( â äàííîì ñëó÷àå ãåîìåòðè÷åñêèå ôèãóðû – òðåóãîëüíèêè).
Çàòåì íåîáõîäèìî íàéòè ðàññòîÿíèå ñòîðîí òðåóãîëüíèêà. Äëÿ ýòîãî âîçüìåì
ôîðìóëó íàõîæäåíèÿ ðàññòîÿíèÿ ìåæäó äâóìÿ òî÷êàìè (D=
).  ñëó÷àè, åñëè ñòîðîíû âûõîäÿùèå èç îäíîé òî÷êè
ðàâíû – ýòî è åñòü ðàäèóñû îêðóæíîñòè, òàê êàê ÷åðåç ðàâíûå îòðåçêè, âûõîäÿùèå
èç îäíîé òî÷êè ìîæíî ïðîâåñòè îêðóæíîñòü ñ öåíòðîì òî÷êè ñîåäèíåíèÿ ýòèõ
îòðåçêîâ.  ñëó÷àå, åñëè â êîíå÷íîì ðåçóëüòàòå âû÷èñëåíèÿ íåñêîëüêî ðàâíûõ
ñòîðîí, âûõîäÿùèõ èç îäíîé òî÷êè, íåîáõîäèìî íàéòè ìèíèìàëüíûé ðàäèóñ
îêðóæíîñòè. Ìèíèìàëüíûì ðàäèóñîì áóäóò ñòîðîíû ñ íàèìåíüøåé äëèíîé (ðèñ.¹ 2).
²²²) Àíàëèç ìåòîäà ðåøåíèÿ:
Ïåðâûé ìåòîä áîëåå
ýôôåêòèâåí, ÷åì âòîðîé, òàê êàê òðåáóåò ìåíüøåå êîëè÷åñòâî àðèôìåòè÷åñêèõ
ðàñ÷åòîâ, è â ïàìÿòè áóäåò çàíèìàòü ìåíüøåå êîëè÷åñòâî ðåñóðñîâ.
²Y) Ôîðìàëèçàöèÿ âûáðàííîãî ìåòîäà:
1)
D1=
D2=
D3=
;
2)
Åñëè D1=D3, òî âûïîëíÿåòñÿ ïóíêò 3, èíà÷å ïóíêò 4;
3)
D1, D3 - ðàäèóñû îêðóæíîñòè;
4)
Åñëè D2=D3, òî âûïîëíÿåòñÿ ïóíêò 5, èíà÷å ïóíêò 6;
5)
D2, D3 – ðàäèóñû îêðóæíîñòè;
6)
Åñëè D1=D2 , òî âûïîëíÿåòñÿ ïóíêò 7, èíà÷å ïóíêò 8;
7)
D1, D2 – ðàäèóñû îêðóæíîñòè;
8)
Åñëè D1=D2 , è/èëè D2=D3, è/èëè D1=D3, òî âûïîëíÿåòñÿ
ïóíêò 9;
9)
 ñëó÷àè ïóíêòà 8
íåîáõîäèìî ñðàâíèòü íà ìåíüøèé ðàäèóñ:
D1=D2 D1=D3 D2=D3
D1
D3 D1
D2 D2D1
D1
D3 D1
D2 D2D1
D2
D3
D3
D2 D3
D1
D2
D3 D3
D2D1 D3D1
10) Çàòåì íåîáõîäèìî ïîâòîðèòü ýòî ñ îñòàâøèìèñÿ òî÷êàìè ïîêà
íå ïåðåãåíèðèðóþòñÿ âñå òî÷êè.
Y². Ãåîìåòðè÷åñêîå ðåøåíèå
çàäà÷è
A= (-5;0);
B= (-3;2);
E= (0;1);
C= (-3;-2), òàê êàê D=
, îòñþäà
1)
AB=
AE=
AC=
Òàê êàê AB=AC, AB
AE, AC
AE, çíà÷èò À è ÀÑ- ðàäèóñû îêðóæíîñòè
ñ öåíòðîì â òî÷êå À.
2) ÀÂ=
ÅÂ=
ÑÂ=
Òàê êàê ÀÂ
ÅÂ, ÅÂ
ÑÂ, ÀÂ
ÑÂ, çíà÷èò ÀÂ, ÅÂ, ÑÂ- íå
ÿâëÿþòñÿ ðàäèóñàìè îêðóæíîñòè è òî÷êà Â- íå ÿâëÿåòñÿ öåíòðîì îêðóæíîñòè.
3) ÀÅ=
ÑÅ=
ÂÅ=
Òàê êàê ÀÅ
ÑÅ, ÑÅ
ÂÅ, ÀÅ
ÂÅ, çíà÷èò ÀÅ, ÑÅ, ÂÅ- íå
ÿâëÿþòñÿ ðàäèóñàìè îêðóæíîñòè è òî÷êà Å- íå ÿâëÿåòñÿ öåíòðîì îêðóæíîñòè.
4) ÀÑ=
ÅÑ=
ÑÂ=
Òàê êàê ÀÑ
ÅÑ, ÅÑ
ÑÂ, ÀÑ
ÑÂ, çíà÷èò ÀÑ, ÅÑ, ÑÂ- íå
ÿâëÿþòñÿ ðàäèóñàìè îêðóæíîñòè è òî÷êà Ñ- íå ÿâëÿåòñÿ öåíòðîì îêðóæíîñòè.
Èç äàííîãî ìíîæåñòâà
òî÷åê ìîæíî ïðîâåñòè òîëüêî îäíó îêðóæíîñòü ñ ìèíèìàëüíûì ðàäèóñîì, ïðîõîäÿùåé
÷åðåç òðè òî÷êè ìíîæåñòâà. Îòñþäà ñëåäóåò, ÷òî ìèíèìàëüíûì ðàäèóñîì ÿâëÿþòñÿ
îòðåçêè ÀÂ è ÀÑ.
Àëãîðèòì ðåàëèçàöèè:
âûïîëíÿòü
ââîä
n
ïîêà ((n>3) è (n<20))
äëÿ i:=1..m
Âûâîä
‘Ââåäèòå êîîðäèíàòû’,I,’-îé òî÷êè.’
Ââîä
D[i].x, D[i].y
Âûâîä
‘D[‘,i,’].x =’,D[i].x;
‘D[‘,i,’].y =’,D[i].y;
äëÿ i:=1..(n-3)
äëÿ k:=i+1..(n-2)
äëÿ l:=j+1..(n-1)
äëÿ j:=l+1...n
dk:= (D [i].x-D
[k].x)²+(D [i].y-D [k].y)²;
dl:= (D [i].x-D
[l].x)²+( D[i].y-D [l].y)² ;
dj= (D [j].x-D
[j].x)²+(D [j].y-D [j].y)² ;
Åñëè (dk=dl) èëè (dk=dj) òîãäà
Âûâîä
‘Òî÷êà ',i,'- ÿâëÿåòñÿ öåíòðîì
îêðóæíîñòè!'
针֌
Âûâîä
'Òî÷êà ',i,' íå ÿâëÿåòñÿ öåíòðîì îêðóæíîñòè!'
Åñëè (dk=dl) èëè (dj=dl) òîãäà
Âûâîä
' dl- âîçìîæíûé ðàäèóñ îêðóæíîñòè!'
针֌
Âûâîä
'dl-íå îáðàçóåò ðàäèóñ..'
Åñëè (dk=dj) èëè (dk=dl) òîãäà
Âûâîä
' dk- âîçìîæíûé ðàäèóñ îêðóæíîñòè!'
针֌
Âûâîä
'dk-íå
îáðàçóåò ðàäèóñ.. '
Åñëè (dj=dl) èëè (dj=dk) òîãäà
Âûâîä
' dj- âîçìîæíûé ðàäèóñ îêðóæíîñòè!’
针֌
Âûâîä
' dj-íå
îáðàçóåò ðàäèóñ’
åñëè (dk<dj)
è (dk=dl) òî
Âûâîä
' dk- Íàèìåíüøèé ðàäèóñ îêðóæíîñòè!'
Åñëè (dk<dl)
è (dk=dj) òî
Âûâîä
' dl-
Íàèìåíüøèé ðàäèóñ îêðóæíîñòè!'
Åñëè (dk=dj)
è (dl=dk) òîãäà
Âûâîä
' dk è dj è dl- Íàèìåíüøèé ðàäèóñ îêðóæíîñòè!'
Ëèñòèíã ïðîãðàììû:
Program alex;
uses crt;
Type Point = Record
x,y : real;
End;
pnt = Array [1..20] Of Point;
var
q, nstr,cstr:string;
c:char;
D:pnt;
l,n,i,k,j,code:integer;
di,dj,dk,dl,Dmin:real;
begin
clrscr;
writeln(' Äîíåöêèé ãîñóäàðñòâåííûé èíñòèòóò èñêóññòâåííîãî
èíòåëëåêòà');
writeln;
writeln;
gotoxy(40,6);
write('Êàôåäðà ïðîãðàìíîãî îáåñïå÷åíèÿ');
gotoxy(40,7);
writeln(' èíòåëëåêòóàëüíûõ ñèñòåì');
gotoxy(19,10);
writeln(' Ëàáîðàòîðíàÿ ðàáîòà #2');
writeln(' ïî êóðñó:"Àëãîðèòìèçàöèÿ âû÷èñëèòåëüíûõ
ïðîöåññîâ"');
writeln(' òåìà:"Ðàçðàáîòêà àëãîðèòìîâ è
ïðîãðàììû"');
gotoxy(60,20);
write('Âûïîëíèë:');
gotoxy(60,21);
write(‘');
gotoxy(60,22);
write();
writeln;
writeln;
writeln;
write('Íàæìèòå ëþáóþ êëàâèøó');
readkey;
clrscr;
writeln(' Çàäàíèå: Çàäàíî ìíîæåñòâî òî÷åê. Íàéòè ïàðàìåòðû îêðóæíîñòè');
writeln('ìèíèìàëüíîãî ðàäèóñà ïðîõîäÿùåé ÷åðåç òðè òî÷êè ìíîæåñòâà.');
gotoxy(1,25);
write('Íàæìèòå ëþáóþ êëàâèøó...');
readkey;
clrscr;
repeat
Writeln('Ââåäèòå êîëè÷åñòâî òî÷åê');
readln(nstr);
writeln;
val(nstr,n,code);
if (code<>0) then
begin
clrscr;
writeln('Ýòî íå ÷èñëî!
Ïîïðîáóéòå åùå ðàç.');
n:=5;
end;
if not( n in[3..20]) then
begin
clrscr;
code:=1;
writeln('×èñëî íå íàõîäèòñÿ â çàäàííîì äèàïàçîíå!
Ïîïðîáóéòå åùå ðàç')
end;
until (code=0);
clrscr;
for i:=1 to n do
begin
repeat
write('Ââåäèòå êîîðäèíàòó Õ ',i,'-îé òî÷êè: ');
readln(cstr);
val(cstr,D[i].x,code);
if (code<>0) then
begin
writeln('Ýòî íå ÷èñëî! Ïîïðîáóéòå åùå ðàç.');
continue
end;
clrscr;
if ((D[i].x>100) or (D[i].x<-100))
then
begin
clrscr;
writeln('Äèàïàçîí êîîðäèíàò òî÷åê îò -100 äî 100!');
code:=1;
continue
end;
until (code=0);
repeat
write('Ââåäèòå êîîðäèíàòó Y ',i,'-îé òî÷êè: ');
readln readln
val(cstr,D[i].y,code);
if (code<>0) then
begin
clrscr;
writeln('Ýòî íå ÷èñëî!
Ïîïðîáóéòå åùå ðàç.');
code:=1;
continue
end;
clrscr;
if ((D[i].y>100) or (D[i].y<-100))
then
begin
clrscr;
writeln('Äèàïàçîí êîîðäèíàò òî÷åê îò -100 äî 100!');
code:=1;
continue
end;
until (code=0);
end;
for i:=1 to n do
begin
writeln('D[',i,'].x=',D[i].x);
writeln('D[',i,'].y=',D[i].y);
end;
for i:= 1 to (n-3) do
for k:= i+1 to (n-2) do
for l:= k+1 to (n-1) do
for j:= l+1 to n do
begin
begin
begin
begin
dk:=Sqrt(Sqr(D[i].x-D[k].x)+Sqr(D[i].y-D[k].y));
dl:=Sqrt(Sqr(D[i].x-D[l].x)+Sqr(D[i].y-D[l].y));
dj:=Sqrt(Sqr(D[i].x-D[j].x)+Sqr(D[i].y-D[j].y));
Dmin:=dk;
begin
if (dk=dl) or
(dj=dl) then
writeln
('',dl:7:2,' dl-âîçìîæíûé ðàäèóñ îêðóæíîîñòè')
else
writeln ('dl-íå îáðàçóåò ðàäèóñ');
if (dk=dj) or
(dk=dl) then
writeln
('',dk:7:2,' dk-âîçìîæíûé ðàäèóñ îêðóæíîñòè')
else
writeln ('dk-íå îáðàçóåò ðàäèóñ');
if (dj=dl) or
(dj=dk) then
writeln
('',dj:7:2,' dj-âîçìîæíûé ðàäèóñ îêðóæíîñòè')
else
writeln ('dj-íå îáðàçóåò ðàäèóñ');
if (dk=dl) or
(dk=dj) then
writeln
('Òî÷êà ',i,' ÿâëÿåòñÿ öåíòðîì îêðóæíîñòè')
else
writeln ('Òî÷êà ',i,' íå ÿâëÿåòñÿ
öåíòðîì îêðóæíîñòè!');
end;
begin
if (dk<dj) and
(dk=dl) then
writeln ('dk
i dl-íàèìåíüøèé ðàäèóñ îêðóæíîñòè') ;
if (dk<dl) and
(dk=dj) then
writeln ('dk
i dj-íàèìåíüøèé ðàäèóñ îêðóæíîñòè');
if (dk=dj) and
(dk=dl) then
writeln ('dk
i dj i dl-íàèìåíüøèé ðàäèóñ îêðóæíîñòè');
end;
end;
end;
end;
end;
readLn;
end.
Ýêðàííûå ôîðìû:
Âûâîä:
 õîäå ëàáîðàòîðíîé
ðàáîòû ÿ èçó÷èë íàâûêè îïèñàíèÿ ìåòîäà ðåøåíèÿ ìàòåìàòè÷åñêîé ìîäåëè íà
ïðèìåðå ðåøåíèÿ çàäà÷ àíàëèòè÷åñêîé ãåîìåòðèè.