Àëãîðèòì Åâêëèäà
Íàèáîëüøèé îáùèé äåëèòåëü
Ðàññìîòðèì ñëåäóþùóþ çàäà÷ó: òðåáóåòñÿ ñîñòàâèòü ïðîãðàììó îïðåäåëåíèÿ íàèáîëüøåãî îáùåãî äåëèòåëÿ (ÍÎÄ) äâóõ íàòóðàëüíûõ ÷èñåë.
Âñïîìíèì ìàòåìàòèêó. Íàèáîëüøèé îáùèé äåëèòåëü äâóõ íàòóðàëüíûõ ÷èñåë - ýòî ñàìîå áîëüøîå íàòóðàëüíîå ÷èñëî, íà êîòîðîå îíè äåëÿòñÿ íàöåëî. Íàïðèìåð, ó ÷èñåë 12 è 18 èìåþòñÿ îáùèå äåëèòåëè: 2, 3, 6. Íàèáîëüøèì îáùèì äåëèòåëåì ÿâëÿåòñÿ ÷èñëî 6. Ýòî çàïèñûâàåòñÿ òàê:
ÍÎÄ(12, 18) = 6.
Îáîçíà÷èì èñõîäíûå äàííûå êàê Ì u N. Ïîñòàíîâêà çàäà÷è âûãëÿäèò ñëåäóþùèì îáðàçîì:
Äàíî: Ì, N
Íàéòè: ÍÎÄ(Ì, N).
 äàííîì ñëó÷àå êàêîé-òî äîïîëíèòåëüíîé ìàòåìàòè÷åñêîé ôîðìàëèçàöèè íå òðåáóåòñÿ. Ñàìà ïîñòàíîâêà çàäà÷è íîñèò ôîðìàëüíûé ìàòåìàòè÷åñêèé õàðàêòåð. Íå ñóùåñòâóåò ôîðìóëû äëÿ âû÷èñëåíèÿ ÍÎÄ(Ì, N) ïî çíà÷åíèÿì Ì è N. Íî çàòî äîñòàòî÷íî äàâíî, çàäîëãî äî ïîÿâëåíèÿ ÝÂÌ, áûë èçâåñòåí àëãîðèòìè÷åñêèé ñïîñîá ðåøåíèÿ ýòîé çàäà÷è. Íàçûâàåòñÿ îí àëãîðèòìîì Åâêëèäà.
Èäåÿ àëãîðèòìà Åâêëèäà
Èäåÿ ýòîãî àëãîðèòìà îñíîâàíà íà òîì ñâîéñòâå, ÷òî åñëè M>N, òî
ÍÎÄ(Ì, N) = ÍÎÄ(Ì - N, N).
Èíà÷å ãîâîðÿ, ÍÎÄ äâóõ íàòóðàëüíûõ ÷èñåë ðàâåí ÍÎÄ èõ ïîëîæèòåëüíîé ðàçíîñòè (ìîäóëÿ èõ ðàçíîñòè) è ìåíüøåãî ÷èñëà.
Ëåãêî äîêàçàòü ýòî ñâîéñòâî. Ïóñòü Ê - îáùèé äåëèòåëü Ì u N (M> N). Ýòî çíà÷èò, ÷òî Ì = mÊ, N = nÊ, ãäå m, n - íàòóðàëüíûå ÷èñëà, ïðè÷åì m > n. Òîãäà Ì - N = Ê(m - n), îòêóäà ñëåäóåò, ÷òî Ê - äåëèòåëü ÷èñëà Ì - N. Çíà÷èò, âñå îáùèå äåëèòåëè ÷èñåë Ì è N ÿâëÿþòñÿ äåëèòåëÿìè èõ ðàçíîñòè Ì - N, â òîì ÷èñëå è íàèáîëüøèé îáùèé äåëèòåëü.
Âòîðîå î÷åâèäíîå ñâîéñòâî:
ÍÎÄ(Ì, Ì) = Ì.
Äëÿ "ðó÷íîãî" ñ÷åòà àëãîðèòì Åâêëèäà âûãëÿäèò òàê:
1) åñëè ÷èñëà ðàâíû, òî âçÿòü ëþáîå èç íèõ â êà÷åñòâå îòâåòà, â ïðîòèâíîì ñëó÷àå ïðîäîëæèòü âûïîëíåíèå àëãîðèòìà;
2) çàìåíèòü áîëüøåå ÷èñëî ðàçíîñòüþ áîëüøåãî è ìåíüøåãî èç ÷èñåë;
3) âåðíóòüñÿ ê âûïîëíåíèþ ï. 1.
Ðàññìîòðèì ýòîò àëãîðèòì íà ïðèìåðå Ì=32, N=24:
Ïîëó÷èëè: ÍÎÄ(32, 24) =ÍÎÄ(8, 8) = 8, ÷òî âåðíî.
Îïèñàíèå àëãîðèòìà Åâêëèäà áëîê-ñõåìîé
Íà ðèñ. 3.12 ïðèâåäåíà áëîê-ñõåìà àëãîðèòìà Åâêëèäà.
 |
| Ðèñ. 3.12. Áëîê-ñõåìà àëãîðèòìà Åâêëèäà |
Ñòðóêòóðà àëãîðèòìà - öèêë-ïîêà ñ âëîæåííûì âåòâëåíèåì. Öèêë ïîâòîðÿåòñÿ, ïîêà çíà÷åíèÿ Ì è N íå ðàâíû äðóã äðóãó.  âåòâëåíèè áîëüøåå èç äâóõ çíà÷åíèé çàìåíÿåòñÿ íà èõ ðàçíîñòü.
À òåïåðü ïîñìîòðèòå íà òðàññèðîâî÷íóþ òàáëèöó àëãîðèòìà äëÿ èñõîäíûõ çíà÷åíèé Ì = 32, N = 24.
| Øàã |
Îïåðàöèÿ |
M |
N |
Óñëîâèå |
| 1 |
ââîä Ì |
32 |
|
|
| 2 |
ââîä N |
|
24 |
|
| 3 |
M ¹ N |
|
|
32 ¹ 24, äà |
| 4 |
M>N |
|
|
32>24, äà |
| 5 |
M:=M-N |
8 |
|
|
| 6 |
M ¹ N |
|
|
8 ¹ 24, äà |
| 7 |
M>N |
|
|
8>24, íåò |
| 8 |
N:=N-M |
|
16 |
|
| 9 |
M ¹ N |
|
|
8 ¹ 16, äà |
| 10 |
M>N |
|
|
8>16, íåò |
| 11 |
N:=N-M |
|
8 |
|
| 12 |
M ¹ N |
|
|
8 ¹ 8, íåò |
| 13 |
âûâîä M |
8 |
|
|
| 14 |
êîíåö |
|
|
|
 èòîãå ïîëó÷èëñÿ âåðíûé ðåçóëüòàò.
Ïðîãðàììà íà Àß è íà Ïàñêàëå
Çàïèøåì àëãîðèòì íà Àß è ïðîãðàììó íà Ïàñêàëå.
àëã Åâêëèä
öåë Ì, N
íà÷
âûâîä " Ââåäèòå Ì è N" ââîä Ì, N
ïîêà Ì N, ïîâòîðÿòü
íö
åñëè M>N
òî M:=M-N
èíà÷å N:=N-M
êâ
êö
âûâîä "ÍÎÄ=",Ì
êîí |
Program Evklid;
var M, N: integer;
begin
writeln('Ââåäèòå Ì è N');
readln(M, N);
while M<>N do
begin
if M>N
then M:=M-N
else N:=N-M
end;
write('Í0Ä=',Ì)
end.
|
Âîïðîñû è çàäàíèÿ
1. Âûïîëíèòå íà êîìïüþòåðå ïðîãðàììó Evklid. Ïðîòåñòèðóéòå åå íà çíà÷åíèÿõ Ì= 32, N = 24; Ì = 696, N = 234.
2. Ñîñòàâüòå ïðîãðàììó íàõîæäåíèÿ íàèáîëüøåãî îáùåãî äåëèòåëÿ òðåõ ÷èñåë, èñïîëüçóÿ ñëåäóþùóþ ôîðìóëó:
ÍÎÄ(À, B, Ñ) = ÍÎÄ(ÍÎÄ(À, Â), Ñ).
3. Ñîñòàâüòå ïðîãðàììó íàõîæäåíèÿ íàèìåíüøåãî îáùåãî êðàòíîãî (ÍÎÊ) äâóõ ÷èñåë, èñïîëüçóÿ ôîðìóëó:
À × Â = ÍÎÄ(À, Â) × ÍÎÊ(À, Â).
|
