журнал «Информатика и образование» - Информатика и образование 2010 №03

æåëàòåëüíî âûáèðàòü òàê, ÷òîáû áûëî ÿñíî, ðåøåíèå êàêîé çàäà÷è îïèñûâàåò äàííûé àëãîðèòì. Äëÿ âûäåëåíèÿ íàçâàíèÿ àëãîðèòìà ïåðåä íèì çàïèñûâàþò ñëóæåáíîå ñëîâî àëã (àëãîðèòì). Çà íàçâàíèåì àëãîðèòìà (îáû÷íî ñ íîâîé ñòðîêè) çàïèñûâàþò åãî êîìàíäû. Äëÿ óêàçàíèÿ íà÷àëà è êîíöà àëãîðèòìà åãî êîìàíäû
çàêëþ÷àþò â ïàðó ñëóæåáíûõ ñëîâ íà÷ (íà÷àëî) è êîí (êîíåö). Êîìàíäû çàïèñûâàþò ïîñëåäîâàòåëüíî.
Àëãîðèòì, â êîòîðîì äåéñòâèÿ âûïîëíÿþòñÿ ïîñëåäîâàòåëüíî îäíî çà äðóãèì,
íàçûâàåòñÿ ëèíåéíûì.
Ïðèìåð ëèíåéíîãî àëãîðèòìà:
íà÷
âïåðåä
âïðàâî
âïåðåä
âïåðåä
âëåâî
âïåðåä
êîí
Àëãîðèòìû, ïðè èñïîëíåíèè êîòîðûõ ïîðÿäîê ñëåäîâàíèÿ êîìàíä îïðåäåëÿåòñÿ
â çàâèñèìîñòè îò ðåçóëüòàòîâ ïðîâåðêè íåêîòîðûõ óñëîâèé, íàçûâàþò ðàçâåòâëÿþùèìèñÿ. Äëÿ èõ îïèñàíèÿ â àëãîðèòìè÷åñêîì ÿçûêå èñïîëüçóþò ñïåöèàëüíóþ
ñîñòàâíóþ êîìàíäó — êîìàíäó âåòâëåíèÿ.
Ïðèìåð ðàçâåòâëÿþùåãîñÿ àëãîðèòìà:
åñëè ñëåâà ñâîáîäíî òî
âëåâî
èíà÷å
âíèç
êîíåöåñëè
 óêàçàííîì ïðèìåðå ïðèâåäåíî ïîëíîå âåòâëåíèå, ò. å. âåòâëåíèå, èìåþùåå äâå
âåòâè — âåòâü ÄÀ (çàïèñûâàåòñÿ ïîñëå ñëîâà ÒÎ è âûïîëíÿåòñÿ, åñëè óñëîâèå èñòèííî) è âåòâü ÍÅÒ (çàïèñûâàåòñÿ ïîñëå ñëîâà ÈÍÀ×Å è âûïîëíÿåòñÿ, åñëè óñëîâèå
ëîæíî). Âîçìîæíî â àëãîðèòìå èñïîëüçîâàíèå òîëüêî îäíîé âåòâè ÄÀ, òîãäà âåòâëåíèå ìîæíî íàçâàòü íåïîëíûì.
Àëãîðèòìû, ïðè èñïîëíåíèè êîòîðûõ îòäåëüíûå êîìàíäû èëè ñåðèè êîìàíä
âûïîëíÿþòñÿ íåîäíîêðàòíî, íàçûâàþò öèêëè÷åñêèìè. Äëÿ îðãàíèçàöèè öèêëè÷åñêèõ àëãîðèòìîâ â àëãîðèòìè÷åñêîì ÿçûêå èñïîëüçóþò ñïåöèàëüíóþ ñîñòàâíóþ
êîìàíäó öèêëà.  øêîëüíîì àëãîðèòìè÷åñêîì ÿçûêå íö îáîçíà÷àåò «íà÷àëî öèêëà»,
à êö — «êîíåö öèêëà»; âñå êîìàíäû ìåæäó íö è êö — ýòî òåëî öèêëà, îíè âûïîëíÿþòñÿ íåñêîëüêî ðàç. Ðàçëè÷àþò öèêëû ñ ïàðàìåòðîì, ñ ïîñòóñëîâèåì è ïðåäóñëîâèåì.
Öèêë ñ ïàðàìåòðîì íà àëãîðèòìè÷åñêîì ÿçûêå ìîæåò âûãëÿäåòü ñëåäóþùèì
îáðàçîì:
íö äëÿ i îò 1 äî n
ñåðèÿ êîìàíä
êö
Ýòà çàïèñü îáîçíà÷àåò öèêë, â êîòîðîì ïåðåìåííàÿ i (îíà íàçûâàåòñÿ ïåðåìåííîé öèêëà) ïðèíèìàåò ïîñëåäîâàòåëüíî âñå çíà÷åíèÿ îò 1 äî n ñ øàãîì 1.

ÈÍÔÎÐÌÀÒÈÊÀ È ÎÁÐÀÇÎÂÀÍÈÅ, ¹ 3—2010

5

Ïðèìåð öèêëà ñ ïàðàìåòðîì:
íö äëÿ i îò 1 äî 5
c := Èçâëå÷ü(a, i)
b := Ñêëåèòü(b, c)
i := i – k
êö
Öèêë ñ ïðåäóñëîâèåì, èëè öèêë ÏÎÊÀ, — ýòî öèêë, â êîòîðîì óñëîâèå ïðîâåðÿåòñÿ ïåðåä âûïîëíåíèåì êîìàíä. Öèêë ìîæíî çàïèñàòü â ñëåäóþùåì âèäå:
ïîêà óñëîâèå
íö
ñåðèÿ êîìàíä
êö
Ïðèìåð öèêëà ñ ïðåäóñëîâèåì:
ïîêà i > 0
íö
c := Èçâëå÷ü(a, i)
b := Ñêëåèòü(b, c)
i := i – k
êö
Öèêë ñ ïîñòóñëîâèåì, èëè öèêë ÄÎ, — ýòî öèêë, â êîòîðîì óñëîâèå ïðîâåðÿåòñÿ
ïîñëå âûïîëíåíèÿ êîìàíäû. Öèêë ìîæíî çàïèñàòü â ñëåäóþùåì âèäå:
íö
ñåðèÿ êîìàíä
äî óñëîâèå
êö
Ïðèìåð öèêëà ñ ïîñòóñëîâèåì:
íö
c := Èçâëå÷ü(a, i)
b := Ñêëåèòü(b, c)
i := i – k
äî i > 0
êö
 àëãîðèòìàõ ìîãóò áûòü èñïîëüçîâàíû ðàçëè÷íûå òèïû äàííûõ: öåëûå ÷èñëà,
âåùåñòâåííûå ÷èñëà, ñèìâîëû, ñòðîêè è äð.
Îñíîâíûå îïåðàöèè ñ ÷èñëàìè áûëè ðàññìîòðåíû â ïåðâîé òåìå.
Îñíîâíûå îïåðàöèè ñ ñèìâîëüíûìè ñòðîêàìè: îïðåäåëåíèå äëèíû, âûäåëåíèå
ïîäñòðîêè, óäàëåíèå è âñòàâêà ñèìâîëîâ, «ñöåïêà» äâóõ ñòðîê â îäíó. Íàïðèìåð:
Äëèíà(à) — âîçâðàùàåò êîëè÷åñòâî ñèìâîëîâ â ñòðîêå à, òèï «öåëîå»;
Èçâëå÷ü(a, i) — âîçâðàùàåò i-é (ñëåâà) ñèìâîë â ñòðîêå à, òèï «ñòðîêà»;
Ñêëåèòü(a, b) — âîçâðàùàåò ñòðîêó, â êîòîðîé çàïèñàíû ñíà÷àëà âñå ñèìâîëû
ñòðîêè à, à çàòåì âñå ñèìâîëû ñòðîêè b, òèï «ñòðîêà».

Ïðèìåðû çàäàíèé
Ðåêîìåíäóåìîå âðåìÿ íà âûïîëíåíèå ïîäîáíûõ çàäàíèé — 1 ìèí.
Çàäà÷à 1 (çàäàíèå òèïà À18).
Èñïîëíèòåëü ×åðåïàøêà ïåðåìåùàåòñÿ íà ýêðàíå êîìïüþòåðà, îñòàâëÿÿ ñëåä
â âèäå ëèíèè. Â êàæäûé êîíêðåòíûé ìîìåíò èçâåñòíû ïîëîæåíèå èñïîëíèòåëÿ
è íàïðàâëåíèå åãî äâèæåíèÿ. Ó èñïîëíèòåëÿ ñóùåñòâóþò äâå êîìàíäû:
Âïåðåä n, âûçûâàþùàÿ ïåðåäâèæåíèå ×åðåïàøêè íà n øàãîâ â íàïðàâëåíèè
äâèæåíèÿ.

www.infojournal.ru

6

Íàïðàâî m, âûçûâàþùàÿ èçìåíåíèå äâèæåíèÿ íà m ãðàäóñîâ ïî ÷àñîâîé ñòðåëêå.
Âìåñòî n è m äîëæíû ñòîÿòü öåëûå ÷èñëà.
Çàïèñü:
Ïîâòîðè 5 [Êîìàíäà 1 Êîìàíäà 2]
îçíà÷àåò, ÷òî ïîñëåäîâàòåëüíîñòü êîìàíä â êâàäðàòíûõ ñêîáêàõ ïîâòîðèòñÿ 5 ðàç.
Êàêîå ÷èñëî íåîáõîäèìî çàïèñàòü âìåñòî n â ñëåäóþùåì àëãîðèòìå:
Ïîâòîðè 7 [Âïåðåä 40 Íàïðàâî n],
÷òîáû íà ýêðàíå ïîÿâèëñÿ ïðàâèëüíûé øåñòèóãîëüíèê?
Ðåøåíèå.
Ïðèìå÷àíèå. Çàäàíèÿ äàííîãî òèïà â ÊÈÌàõ ÅÃÝ èäóò ñ âûáîðîì îòâåòà. Ýòîò
ïðèìåð ïðèâåäåí áåç âàðèàíòîâ îòâåòîâ, ÷òîáû ó÷àùèåñÿ ìîãëè ïîëàãàòüñÿ íà ëîãèêó ðàññóæäåíèÿ.
Ñóììà óãëîâ ïðàâèëüíîãî --">