| §2.3 Proiectarea algoritmilor

Lecția 15
§2.3 Proiectarea algoritmilor

2.3.1. Construcția secvențială a algoritmului

Exista diverse metode proiectarea (dezvoltarea, construcția) algoritmilor. Ne vom familiariza cu unul dintre ele - metoda de construcție secvențială (rafinare) a algoritmului. Cunoscută altfel ca metoda de dezvoltare de sus în jos, de sus în jos sau incrementală.

Procesul de construcție secvențială a algoritmului este următorul.

La primul pas, credem că avem în fața noastră un interpret perfect care „știe totul și poate face totul”. Prin urmare, este suficient să determinați datele și rezultatele inițiale ale algoritmului și să prezentați algoritmul în sine sub forma unei singure prescripții - o declarație de problemă (Fig. 2.4).

Orez. 2.4. Algoritm liniar, care este rezultatul primei etape de detaliere a sarcinii

Dacă executantul nu este instruit să execute o anumită instrucțiune, atunci este necesar să prezinte această instrucțiune sub forma unui set de instrucțiuni (comenzi) mai simple. Pentru aceasta:

Sarcina este împărțită în mai multe părți, fiecare dintre acestea fiind mai simplă decât întreaga sarcină;
soluția fiecărei părți a problemei este formulată într-o comandă separată, care poate depăși, de asemenea, cadrul sistemului de comandă al executantului;
Dacă algoritmul conține instrucțiuni care depășesc capacitățile interpretului, astfel de instrucțiuni sunt din nou prezentate ca un set de instrucțiuni și mai simple.

Procesul continuă până când toate instrucțiunile sunt clare pentru executant.

Combinând instrucțiunile primite într-un singur set de comenzi executate într-o anumită secvență, obținem algoritmul necesar pentru rezolvarea problemei inițiale.

2.3.2. Dezvoltarea unui algoritm folosind metoda de rafinare secvențială pentru performerul Robot

Sunteți deja familiarizat cu robotul interpret. Funcționează pe un câmp în carouri, între celulele căruia pot fi pereți.

Sistem de comandă pentru performerul robotului:

Puteți utiliza mai multe comenzi într-o singură condiție folosind operatii logiceȘI, SAU, NU.

Se știe că Robotul se află undeva pe coridorul orizontal. Niciuna dintre celulele coridorului nu este vopsită.

Să creăm un algoritm sub controlul căruia Robotul va picta peste toate celulele acestui coridor și va reveni la poziția inițială.

Să prezentăm planul de acțiune al Robotului cu următorii pași (module) extinși:

Detaliem fiecare dintre cele cinci module.

1. Pentru a picta toate celulele coridorului situat în stânga Robotului, vom ordona Robotului să pășească spre stânga și să execute ciclul - BYE:

stânga
nts pentru moment perete de deasupra Și vopsea peste fundul peretelui; stânga
kts

Sub controlul acestui algoritm, Robotul va picta toate celulele coridorului situat în stânga acestuia și va ajunge într-o celulă din stânga coridorului.

2. Folosiți comanda din dreapta pentru a întoarce robotul pe coridor. Sarcina noastră este să readucem robotul în celula sa originală. Această celulă este prima celulă neumplută situată în dreapta Robotului. Prin urmare, atâta timp cât celula ocupată de Robot este umbrită, o vom muta spre dreapta.

dreapta
nts pentru moment celula este umbrită la dreapta
kts

Sub controlul acestui algoritm, Robotul va ajunge în celula originală.

3. După ce a executat comanda din dreapta, Robotul va trece de celula originală și va ocupa o celulă în dreapta celei originale. Acum puteți picta peste celulele coridorului situate în dreapta celei originale.

dreapta
nts pentru moment perete de deasupra Și vopsea peste fundul peretelui; dreapta
kts

4. Deoarece, după ce a finalizat algoritmul anterior, Robotul s-a aflat în dreapta coridorului, îl vom întoarce în coridor cu comanda din stânga. Revenirea la celula originală este asigurată de următorul algoritm:

stânga
nts pentru moment celula este umbrită la stânga
kts

5. La comanda de pictare, Robotul pictează celula originală. Programul complet de control al robotului arată astfel:

2.3.3. Algoritmi auxiliari

La construirea de noi algoritmi apar adesea situații când locuri diferite algoritmul necesită aceeași secvență de pași de prelucrare a datelor. Pentru o astfel de secvență de pași, este creat un algoritm separat, numit algoritm auxiliar. Algoritmii dezvoltați anterior pentru a rezolva alte probleme pot fi folosiți ca auxiliari.

Un algoritm auxiliar este un algoritm care este utilizat în întregime ca parte a altui algoritm.

Exemplul 1. În mediul KuMir, vom crea un algoritm pentru interpretul Robot, sub controlul căruia va desena un model:

Poziția de pornire Lucrarea este marcată cu un asterisc. Algoritmul folosește algoritmul auxiliar al figurii.

La reprezentarea algoritmilor folosind diagrame de flux, pentru a indica comanda de apelare a unui algoritm auxiliar, se folosește un bloc „proces predefinit” (Fig. 2.5), în interiorul căruia este scris numele (numele) algoritmului auxiliar, după care parametrii - intrare datele și rezultatele - sunt enumerate în paranteze.

Orez. 2.5. Blocați „proces predefinit”

Algoritmul auxiliar face structura algoritmului mai ușor de înțeles.

Exemplul 2. Să ne amintim algoritmul de calcul al gradului cu un exponent natural y = a n. Diagrama bloc relevantă:

O putere cu un exponent întreg y = a x, unde x este un număr întreg, a ≠ 0 se calculează după cum urmează:

În intrarea de mai sus, calculul unui grad cu exponent natural apare de două ori. Prin urmare, algoritmul pentru calcularea unui grad cu un exponent întreg poate include un apel la un algoritm auxiliar pentru calcularea unui grad cu un exponent natural. Diagrama bloc relevantă:

Algoritmul prezentat în diagrama bloc este cel principal în raport cu algoritmul auxiliar numit în ea.

Parametrii algoritmului auxiliar utilizați sunt valorile a, n, y. Aceștia sunt parametri formali, sunt utilizați pentru a descrie algoritmul. Când se accesează în mod specific un algoritm auxiliar, parametrii formali sunt înlocuiți cu parametrii actuali, adică exact acele valori pentru care se va executa algoritmul auxiliar. Tipurile, numărul și ordinea parametrilor formali și reali trebuie să se potrivească.

Comanda de apelare a algoritmului auxiliar este executată după cum urmează (Fig. 2.6):

1) datele formale de intrare ale algoritmului auxiliar sunt înlocuite cu valorile datelor reale de intrare specificate în comanda de apelare a algoritmului auxiliar;
2) pentru datele de intrare date se execută comenzile algoritmului auxiliar;
3) rezultatele obţinute sunt atribuite variabilelor cu denumirea rezultatelor efective;
4) se realizează trecerea la următoarea comandă a algoritmului principal.

Orez. 2.6. Schema pentru executarea unei comenzi pentru apelarea unui algoritm auxiliar

Un algoritm care conține direct sau indirect o referință la sine ca algoritm auxiliar se numește recursiv.

Să ne uităm la câteva exemple de algoritmi recursivi.

Exemplul 3. Algoritm de calcul al gradului cu exponent natural n pentru oricare numar realși poate fi reprezentat în formă recursivă:

Numărul a la puterea n ( gradul al n-lea numerele a) nu sunt altceva decât produsul unui n-1 a; la rândul său, a n-1 = a n-2 a etc.

Exemplul 4. Algoritm recursiv este baza solutie eficienta Puzzle-uri Turnul din Hanoi.

Jocul interactiv „Towers of Hanoi” (195747) vă va ajuta să vă amintiți condițiile și algoritmul pentru rezolvarea puzzle-ului (http://sc.edu.ru/).

Exemplul 5. Să luăm în considerare algoritmul de construcție figură geometrică, care se numește fulgul de zăpadă Koch. Pasul procedurii de construcție este înlocuirea treimii mijlocii a fiecărui segment existent cu două noi de aceeași lungime, așa cum se arată în figură:

Cu fiecare pas, silueta devine din ce în ce mai bizară. Limita fulgului de zăpadă Koch este poziția curbei după finalizarea unui număr infinit de pași.

CEL MAI IMPORTANT

Una dintre principalele metode de construire a algoritmilor este metoda de construire a algoritmului secvenţial. Esența sa este că: problema inițială este împărțită în mai multe părți, fiecare dintre acestea fiind mai simplă decât întreaga problemă, iar soluția fiecărei părți este formulată într-o echipă separată; Dacă se obțin comenzi care depășesc capacitățile interpretului, atunci acestea sunt prezentate sub forma unui set de instrucțiuni și mai simple. Procesul continuă până când toate instrucțiunile sunt clare pentru executant.

Algoritm auxiliar- un algoritm folosit în întregime ca parte a altui algoritm.

Se numește un algoritm care conține direct sau indirect o referință la sine ca algoritm auxiliar recursiv.

Întrebări și sarcini

1. Citiți materialele de prezentare pentru paragraful conținut în aplicație electronică la manual. Prezentarea completează informațiile conținute în textul paragrafului?

2. De ce atunci când te hotărăști sarcină complexă Este dificil să specifici totul deodată acțiunile necesare? Discutați această întrebare în grup.

3. Care este metoda de rafinare secvențială la construirea unui algoritm?

4. Care este legătura dintre metoda de construire a algoritmului secvențial și procese precum scrierea unui eseu sau pregătirea pentru o excursie de mai multe zile?

5. Înălțimea fiecăruia dintre ele este cunoscută n elevii clasei 9A și m elevii clasei 9B. Descrieți în blocuri mari un algoritm pentru compararea înălțimii medii a elevilor din aceste clase.

6. Într-un rând de zece celule în dreapta Robotului, unele celule sunt umbrite. Ultima celulă pictată poate fi adiacentă unui perete. Scrieți un algoritm care umbrește celulele deasupra și sub fiecare celulă umbrită. Verificați algoritmul în următoarele cazuri:

7. De ce sunt necesari algoritmi auxiliari?

8. Descrieți procesul de executare a unei comenzi pentru a apela un algoritm auxiliar în algoritmul principal.

9. Ați întâlnit ideea parametrilor formali și faptici în timp ce studiați matematica și fizica? Dă un exemplu.

10. Ce algoritmi se numesc recursivi? Dați un exemplu de recursivitate din viață.

11. Creați algoritmi sub controlul cărora Robotul va picta peste celulele indicate. Dacă este necesar, utilizați un algoritm auxiliar.

Robotul operează pe un câmp dreptunghiular în carouri. Între unele celule ale câmpului pot exista pereți. Unele celule pot fi vopsite peste (Fig. 3.11).

Robotul ocupă exact o celulă a câmpului. Prin comenzi sus, jos, stânga și dreapta, Robotul se deplasează în celula adiacentă în direcția indicată. Dacă există un perete în cale, are loc o defecțiune - este afișat un mesaj care spune că este imposibil să executați următoarea comandă.

La comanda de a picta, Robotul pictează celula în care se află. Dacă celula a fost deja vopsită, aceasta va fi vopsită din nou, deși nu vor apărea modificări vizibile.

Este important de reținut că Robotul poate executa doar comenzi scrise corect. De exemplu, dacă notați în loc de comandă, Robotul nu va înțelege această intrare și va raporta imediat o eroare.

Amintiți-vă ce erori în înregistrarea comenzilor sunt numite. Ce alte greșeli ar trebui evitate la dezvoltarea algoritmilor?

Exemplu de algoritm de control al robotului

Hai să scriem program, efectuând că Robotul va desena un meadru de cinci ture pe câmpul în carouri (Fig. 3.12).

Programul ar putea arăta astfel:

REPEȚI DE 5 ORI
dreapta
vopsea peste; stânga
vopsea peste; stânga
vopsea peste; sus
vopsea peste; sus
vopsea peste; dreapta; vopsea peste
dreapta; dreapta; dreapta
jos; jos
Sfârşit

Aici am folosit construcția de repetiție, deoarece fragmentele complet identice sunt repetate de 5 ori în figură. La înregistrarea corpului cicluși am scris mai multe comenzi pe o singură linie, separate prin punct și virgulă.

Dacă oficializați procedura ca o buclă, atunci programul principal se va dovedi a fi foarte scurt.

Algoritm auxiliar:
viraj PERC
START
dreapta
vopsea peste; stânga
vopsea peste; stânga
vopsea peste; sus
vopsea peste; sus
vopsea peste; dreapta; vopsea peste
dreapta; dreapta; dreapta
jos; jos
Sfârşit

Algoritm de bază:
REPEȚI DE 5 ORI
întoarce
Sfârşit

Sugerați versiunea dvs. a unui program pentru desenarea unui meandre.

Ciclul „adio”.

Acum să încercăm să scriem un program pentru a rezolva o problemă foarte simplă: colorați toate celulele din dreapta Robotului (Fig. 3.13).

Cu toate acestea, exact câte celule ar trebui vopsite nu este specificat. Ce se știe este că:

1) există un zid în dreapta la o distanţă necunoscută;
2) celulele trebuie vopsite până când robotul se apropie de perete.

Să profităm de faptul că Robotul poate analiza și raporta situația din jurul său, verificând următoarele condiții simple:

liber pe dreapta
lăsat liber
liber deasupra
liber de jos
pictat peste

Este clar că atâta timp cât condiția din dreapta este îndeplinită în mod liber, trebuie să executați comenzile:

dreapta
vopsea peste

Pentru a proiecta astfel de secvențe de acțiuni, se folosește o construcție specială a limbajului algoritmic - ciclul „în timp ce”.

ÎN CARE dreptul este liber să FAC
dreapta
vopsea peste
Sfârşit

ÎN vedere generala Bucla „while” este scrisă astfel:

PA<условие>DO
<тело цикла (последовательность команд)>
Sfârşit

Diagrama bloc a ciclului „while” are forma prezentată în Fig. 3.14.

Când efectuează acest ciclu, executantul repetă următoarele acțiuni:

1) verifică condiția scrisă după cuvântul funcție BYE;

2) dacă condiția nu este îndeplinită (robotul a răspuns „Nu”), atunci execuția ciclului este încheiată, iar Robotul începe să execute comenzile scrise după cuvântul de serviciu END. Dacă condiția este îndeplinită (robotul a răspuns „Da”), atunci robotul execută corpul buclei și verifică din nou condiția.

Să scriem un program, executând care Robotul va desena un meandru pe un câmp în carouri (Fig. 3.12), al cărui număr de spire depinde de poziția peretelui din dreapta.

O viraj meandre se potrivește pe un câmp în carouri dacă există 1 celulă între celula ocupată de Robot și peretele din dreapta.

ÎN CARE dreptul este liber să FAC
dreapta
vopsea peste; stânga
vopsea peste; stânga
vopsea peste; sus
vopsea peste; sus
umbra la dreapta; vopsea peste
dreapta; dreapta; dreapta
jos; jos
Sfârşit

Depinzând de pozitia de pornire Corpul buclei nu poate fi executat nici măcar o dată. Această situație nu este un refuz.

Gândiți-vă la care ar trebui să fie poziția de pornire a robotului în programul de desenare a meandrelor, astfel încât corpul buclei să nu fie executat niciodată.

Din cauza erorilor logice făcute la compilarea algoritmului, poate apărea o situație de buclă. Aceasta înseamnă că condiția va fi întotdeauna îndeplinită și bucla while nu se va finaliza niciodată.

Luați în considerare următorul exemplu:

ÎN CARE dreptul este liber să FAC
dreapta; stânga
Sfârşit

Ce se va întâmpla dacă nu există niciun zid în dreapta Robotului?

Condiția dintr-o buclă while este verificată numai înainte ca corpul buclei să fie executat, dar nu în timpul executării acesteia.

Luați în considerare ce s-ar întâmpla dacă robotul ar începe să execute programul nostru de desenare a meandrelor cu o buclă „while” în următoarea poziție de pornire:

Ce au în comun buclele „repeat n times” și „bye”? Care sunt diferențele dintre ele? Sunt necesare două constructe pentru a descrie acțiuni repetitive?

Condiții simple și compuse

În bucla „while”, pot fi utilizate nu numai condiții simple, ci și compuse.

O stare compusă este formată din unul sau mai multe conditii simpleși cuvinte funcționale ȘI, SAU, NU.

Să considerăm condiția compusă A și B, unde A, B sunt condiții simple. Condițiile A și B sunt îndeplinite atunci când fiecare dintre cele două condiții simple incluse în ea este îndeplinită.

Fie A o condiție simplă la dreapta liber, B o condiție simplă la dreapta liber. Să luăm în considerare în detaliu verificarea stării compuse A și B - libere de sus. (Fig. 3.15).

În cazul în care a, condiția A este îndeplinită (liber în partea de sus), condiția B este îndeplinită (liber în dreapta). Condiția compusă A și B (liber în sus și liber în dreapta) este de asemenea îndeplinită.

În cazul b, condiția A este îndeplinită, condiția B nu este îndeplinită. Condiția compusă A și B nu este îndeplinită.

În cazul c, condiția A nu este îndeplinită, condiția B este îndeplinită. Condiția compusă A și B nu este îndeplinită.

În cazul d, condiția A nu este satisfăcută, condiția B nu este îndeplinită.

Este necesar să se verifice condiția B într-o condiție compusă AIV dacă condiția A nu este îndeplinită?

Condiția compusă A SAU B este îndeplinită atunci când cel puțin una dintre cele două condiții simple incluse în aceasta este îndeplinită.

Să luăm în considerare verificarea condiției compuse A SAU B - liber deasupra SAU liber în dreapta (vezi Fig. 3.15).

În cazul în care a, condiția A este îndeplinită (liber în partea de sus), condiția B este îndeplinită (liber în dreapta). Condiția compusă A SAU B (liber deasupra SAU liberă pe dreapta) este îndeplinită.

În cazul b, condiția A este satisfăcută, condiția B nu este îndeplinită.

În cazul c, condiția A nu este îndeplinită, condiția B este îndeplinită.

În cazul d, condiția A nu este satisfăcută, condiția B nu este îndeplinită.

Ar trebui verificată condiția B în starea compusă A SAU B dacă condiția A este îndeplinită?

Condiția compusă NOT A este satisfăcută atunci când condiția A nu este îndeplinită.

Fie A - o condiție simplă să fie umbrită. Să luăm în considerare verificarea condiției compuse NU A (Fig. 3.16).

În cazul în care a, condiția A este îndeplinită, condiția NOT A (NEUmbriată) nu este îndeplinită.

În cazul b, condiția A nu este îndeplinită, condiția NOT A (NEUmbriată) este îndeplinită.

Să ne uităm la un exemplu de utilizare a unei condiții compuse.

Se știe că Robotul se află undeva pe coridorul vertical. Niciuna dintre celulele coridorului nu este vopsită.

Să compunem, sub controlul căruia Robotul va picta peste toate celulele acestui coridor și va reveni la poziția inițială.

Deoarece Robotul va trebui doar să picteze peste celulele coridorului, trebuie să-l „învățăm” să le recunoască. Cum diferă celulele de coridor de toate celelalte celule de pe teren? Din fig. Figura 3.17 arată că fiecare celulă a coridorului din stânga și din dreapta este limitată de un perete.

Robotul este pe coridor în timp ce există un perete în stânga și un perete în dreapta. SKI-ul contractorului nostru nu prevede astfel de condiții. Există condiții opuse: stânga este liberă, dreapta este liberă. Folosim cuvântul funcție NOT:

perete în stânga -> NU liber în stânga
perete în dreapta -> NU liber în dreapta

Condiția necesară va lua forma:
NU în stânga este liber ȘI NU în dreapta este liber.

Să prezentăm planul de acțiune al Robotului în pași lărgiți (Fig. 3.18).

Pentru simplitate, să presupunem că există cel puțin o celulă fără pereți deasupra și dedesubtul coridorului (în caz contrar, va trebui să faceți verificări suplimentare liber sus, liber jos).

1. Pentru a picta toate celulele coridorului situat deasupra Robotului, vom ordona Robotului să urce și să execute ciclul „deocamdată”:

sus
DO
vopsea peste
sus
Sfârşit

Sub controlul acestui algoritm, Robotul va picta toate celulele coridorului situat deasupra lui și va ajunge pe celula de lângă marginea superioară a coridorului.

În ce poziție inițială a robotului nu va fi executat acest ciclu nici măcar o dată?

2. Folosind echipa de jos, întoarceți robotul pe coridor. Sarcina noastră este să-l readucem la punctul de plecare. Acest punct are doar unul semn distinctiv- nu este vopsit peste. Prin urmare, în timp ce celula ocupată de Robot este umbrită, o vom muta în jos:

jos
WHILE pictat peste DO
jos
Sfârşit

Sub controlul acestui algoritm, Robotul va ajunge în celula originală.

3. După executarea comenzii în jos, Robotul va trece de celula originală și va ocupa prima celulă situată sub cea originală. Acum puteți picta peste celulele de coridor situate sub cea originală:

jos
PÂNĂ stanga este liberă ȘI NU dreapta este liberă
DO
vopsea peste
jos
Sfârşit

Este posibil ca această buclă să nu fie executată nici măcar o dată?

4. Deoarece, după ce a finalizat algoritmul anterior, Robotul va fi sub coridor, cu comanda sus îl vom întoarce pe coridor. Revenirea la punctul de plecare este asigurată de algoritmul:

sus
WHILE pictat peste DO
sus
Sfârşit

5. La comanda vopsire, Robotul pictează punctul de pornire.

Programul complet de control al robotului arată astfel:

sus
PÂNĂ stanga este liberă ȘI NU dreapta este liberă
DO
vopsea peste
sus
Sfârşit
jos
WHILE pictat peste DO
jos
Sfârşit
jos
PÂNĂ stanga este liberă ȘI NU dreapta este liberă
DO
vopsea peste
jos
Sfârşit
sus
WHILE pictat peste DO
sus
Sfârşit
vopsea peste

Comanda de filială

Să reamintim că forma de organizare a acțiunilor în care, în funcție de îndeplinirea sau neîndeplinirea unei condiții, se realizează fie una, fie alta succesiune de acțiuni, se numește ramificare.

Ramificarea poate fi reprezentată grafic așa cum se arată în Fig. 3.19.

Pentru a organiza filiale în Robotul SKI există a echipa speciala DACĂ. Aspectul său general:

DACĂ<условие>ACEA<серия действий 1>
IN CAZ CONTRAR<серия действий 2>
Sfârşit

Cuvintele auxiliare DACA, ATUNCI, ALTRE au sensul obisnuit.

Între THEN și ELSE se scriu una sau mai multe acțiuni, constituind o serie de acțiuni 1. Între ELSE și END se plasează o serie de acțiuni 2. Cuvântul funcție ALLTĂ, împreună cu o serie de acțiuni 2, pot lipsi (an formă prescurtată de ramificare).

Acum lăsați Robotul să fie într-un coridor orizontal, a cărui limită inferioară este solidă, iar limita superioară are ieșiri (Fig. 3.20). Trebuie să ghidați robotul prin întregul coridor și să pictați peste celulele coridorului care nu au margini superioare.

Singurul semn al unui coridor este prezența unei limite inferioare, adică îndeplinirea condiției NU de jos este liberă. Dacă condiția de mai sus este îndeplinită în mod liber, atunci celula trebuie vopsită peste, altfel nu este nevoie să o vopsiți. Similar cu cazul pictării unui coridor vertical, presupunem că există celule în stânga și dreapta coridorului orizontal. Diagrama bloc a algoritmului are forma prezentată în Fig. 3.21.

Program:

PÂNĂ de jos este liber să FAC
DACĂ partea superioară este liberă ATUNCI
vopsea peste
Sfârşit
dreapta
Sfârşit

Pe scurt despre principalul lucru

Robotul Performer acționează pe un câmp dreptunghiular în carouri. Între unele celule ale câmpului pot exista pereți. Unele celule pot fi vopsite peste. Robotul ocupă exact o celulă a câmpului.

Sistemul de comenzi executant este prezentat în următorul tabel:

Robotul poate efectua o buclă „repetată de n ori”.

Dacă nu se știe dinainte exact de câte ori trebuie executat corpul buclei, se folosește o construcție specială a limbajului algoritmic - bucla „while”.

În bucla „while”, pot fi utilizate nu numai condiții simple, ci și compuse. O condiție compusă este formată din una sau mai multe condiții simple și cuvinte auxiliare AND, OR, NOT.

Pentru a organiza ramuri, Robot SCI oferă o comandă IF specială.

Întrebări și sarcini

1. Dați toți algoritmii din trei comenzi care vor muta Robotul din poziția inițială în celula B.

Există un algoritm pentru această sarcină în care Robotul face: a) doi pași; b) patru trepte; c) cinci trepte; d) șapte trepte; e) 2001 trepte; e) 2006 paşi?

2. Petya a creat un algoritm care transferă Robotul din celula A în celula B prin pictarea unor celule. Ce ar trebui să facă Kolya cu acest algoritm pentru a obține un algoritm care transferă Robotul de la B la A și pictează aceleași celule?

3. Petya a compilat un algoritm, în timpul căruia Robotul a revenit la poziția inițială. Kolya a șters una dintre echipe. Când a executat algoritmul lui Kolya, robotul a revenit și el la poziția inițială. Ce echipă a șters Kolya?

4. Masha a venit cu un model pentru Robot. Kolya a șters exact jumătate din celulele colorate. Restabiliți desenul, știind că este simetric față de axa verticala. Scrieți un program pentru robot.

5. Scrieți un program prin care Robotul să poată ajunge la celula B în toate cele trei labirinturi.

6. Scrieți un program care să ajute robotul să ajungă la celula B.

7. Se cunosc doi algoritmi auxiliari ai Robotului:

Desenați ce se va întâmpla când robotul execută următorii algoritmi de bază:

8. Creați algoritmi sub controlul cărora Robotul va picta peste celulele indicate:

9. Se știe că undeva în dreapta Robotului se află un zid.

Creați un algoritm sub controlul căruia Robotul va picta un rând de celule până la perete și va reveni la poziția inițială.

10. Se știe că undeva în dreapta Robotului se află o celulă plină.

Creați un algoritm sub controlul căruia Robotul va picta un număr de celule până la celula vopsită și va reveni la poziția inițială.

11. Se știe că Robotul este situat lângă intrarea din stânga a coridorului orizontal.

12. Se știe că Robotul se află undeva pe coridorul orizontal. Niciuna dintre celulele coridorului nu este vopsită.

Creați un algoritm sub controlul căruia Robotul va picta toate celulele acestui coridor și va reveni la poziția inițială.

13. Într-un rând de zece celule în dreapta Robotului, unele celule sunt umbrite.

Scrieți un algoritm care pictează celulele:

a) sub fiecare celulă umbrită;
b) deasupra și sub fiecare celulă umbrită.

14. Ce se poate spune despre corectitudinea următorului fragment al algoritmului?

ÎN CÂT timp este pictat FĂ-O
DACA dreptul este liber ATUNCI
dreapta
vopsea peste
Sfârşit
Sfârşit

15 Scrieți un program prin care Robotul poate ajunge la celula B în toate cele trei labirinturi.

Robotul există într-un anumit mediu (un câmp dreptunghiular în carouri). Între unele celule ale câmpului pot exista pereți. Unele celule pot fi vopsite peste (Fig. 3.11).

Robotul ocupă exact o celulă a câmpului.

Prin comenzi sus, jos, stânga și dreapta, Robotul se deplasează în celula adiacentă în direcția indicată. Dacă există un perete în cale, are loc o defecțiune - este afișat un mesaj care spune că este imposibil să executați următoarea comandă.

La comanda de a picta, Robotul pictează celula în care se află. Dacă celula a fost deja vopsită, va fi vopsită din nou, deși nu modificări vizibile nu se va intampla.

Robotul poate executa doar comenzi scrise corect. Dacă notați în loc de comanda down, Robotul nu va înțelege această intrare și va raporta imediat o eroare.

DESPRE
erori: 1 sintactic; 2. logic

Descrierile situațiilor sunt stocate în fișiere text format special(format.fil).

Actual- mediul în care se află Robotul acest moment(inclusiv informații despre poziția robotului).

Pornire- mediul în care Robotul este forțat să fie plasat la începutul execuției unui program folosind Robotul.

Procedura de operare:

1. 
   A stabilit mediu de pornire in functie de conditiile problemei:

2. Specificați Antreprenorul:

Meniul Inserare → Utilizare robot

3. Scrieți un algoritm pentru rezolvarea problemei.

4. Executați algoritmul (Meniu Execuție →Run continuu /F9)

Sistem de comandă pentru performer robot în sistemul KUMIR

Ciclu– organizarea repetării acțiunilor în timp ce o anumită condiție este adevărată .

Corpul buclei este un set de acțiuni repetabile.

Condiție - expresie logică (simplu sau complex (compozit))
Tipuri de cicluri:

1.Buclă „Repetați de n ori” 2. Buclă „Până”
nts de n ori nts pentru moment
. . Corpul buclei. . Corpul buclei
kts kts

Exemplu: nts pentru moment liber pe dreapta

Vedere generală a ciclului „Repetați de n ori”:

REPEȚI de n ORI

Sfârşit
kts

Vedere generală a ciclului „în timp”:

FĂ-O LA RED

Sfârşit
Condiții compozite format din una sau mai multe condiții și cuvinte funcționale simple ȘI, SAU, NU.

Fie A - gratuit deasupra,ÎN - liber pe dreapta, apoi condiția compusă A SI B- liber deasupra și liber pe dreapta.

Exemplu: Fie A o celulă colorată (condiție simplă).

P Verificarea stării compuse NU A:

a) A - finalizat, NU A (NEUmbriat) - nefinalizat.

b) A - necompletat, NOT A (NEUmbriat) - finalizat.

Ramificare - o formă de organizare a acțiunilor în care, în funcție de îndeplinirea sau neîndeplinirea unei condiții, se realizează fie una, fie alta succesiune de acțiuni.

Vedere generală a comenzii IF:

DACĂ ACEA IN CAZ CONTRAR

Sfârşit

În limbajul ICON:

Ramificare completă: Ramificare incompletă:
Dacă Acea Dacă Acea

in caz contrar

totul totul

Algoritm auxiliar- un algoritm care rezolvă o subsarcină a problemei principale.

În sistemul KUMIR, la sfârșit se scriu algoritmi auxiliari programul principal(după cuvântul oficial con), sunt chemate pentru execuție în programul principal după nume.

ÎN sondaje și sarcini

1. Dați toți algoritmii din trei comenzi care vor muta Robotul din poziția inițială în celula B.

Există un algoritm pentru această sarcină în care robotul face:

a) două etape; b) patru trepte; c) cinci trepte; d) șapte pași?

1. 
   Petya a compilat un algoritm care transferă Robotul de la celula A la celula B prin pictarea unor celule. Ce ar trebui să facă Kolya cu acest algoritm pentru a obține un algoritm care transferă Robotul de la B la A și pictează aceleași celule?

7. Sunt cunoscuți doi algoritmi roboti auxiliari

Desenați ce se va întâmpla când robotul execută următorii algoritmi de bază:

8. Creați algoritmi sub controlul cărora Robotul va picta peste celulele indicate:

10. Se știe că undeva în dreapta Robotului se află o celulă plină.

CU lăsați algoritmul sub controlul căruia Robotul va picta un număr de celule până la celula vopsită și va reveni la poziția inițială.

11. Se știe că Robotul este situat lângă intrarea din stânga a coridorului orizontal.

12. Se știe că Robotul se află undeva pe coridorul orizontal. Niciuna dintre celulele coridorului nu este vopsită.

Creați un algoritm sub controlul căruia Robotul va picta toate celulele acestui coridor și va reveni la poziția inițială.

CU lăsați algoritmul care pictează celulele:

a) sub fiecare celulă umbrită;

b) deasupra și sub fiecare celulă umbrită.

nts pentru moment celula este vopsită peste

DACĂ liber pe dreapta ACEA

dreapta; vopsea peste

La
ts

15. Scrieți un program prin care Robotul să poată ajunge la celula B în toate cele trei labirinturi.

Z

Realizări GIA

1. 
   Coridorul 1. Robotul este undeva pe coridorul vertical. Niciuna dintre celulele coridorului nu este vopsită. Creați un algoritm sub controlul căruia Robotul va picta toate celulele acestui coridor și va reveni la poziția inițială.

1. 
   LA
   Necesar

   Dat
   coridorul2. Robotul este situat în celula superioară a unui coridor vertical îngust. Lățimea coridorului este de o celulă, lungimea coridorului poate fi arbitrară.

Scrieți un algoritm pentru robot care pictează toate celulele din interiorul coridorului și readuce robotul în poziția inițială. De exemplu, pentru imaginea de mai sus, Robotul trebuie să picteze peste următoarele celule (vezi imaginea):

1. 
   Există un perete orizontal lung într-un câmp nesfârșit. Lungimea zidului este necunoscută. Robotul se află într-una dintre celulele chiar deasupra peretelui. Poziția inițială a robotului este, de asemenea, necunoscută. Una dintre pozițiile posibile:

Dat
Scrieți un algoritm pentru Robot care pictează toate celulele situate deasupra peretelui și adiacente acestuia, indiferent de dimensiunea peretelui și de poziția inițială a Robotului. De exemplu, pentru imaginea de mai sus, Robotul trebuie să picteze peste următoarele celule:

Poziția finală a robotului poate fi arbitrară. La executarea algoritmului, robotul nu trebuie distrus.

1. 
   Câmpul nesfârșit are un perete vertical lung. Lungimea zidului este necunoscută. Robotul se află într-una dintre cuștile situate direct în dreapta peretelui. Poziția inițială a robotului este, de asemenea, necunoscută. Una dintre pozițiile posibile ale robotului este prezentată în figură (robotul este desemnat prin litera „P”): Scrieți un algoritm care să lucreze care pictează toate celulele adiacente peretelui: în stânga, începând de la partea de sus nevopsită. unul și prin unul; in dreapta, incepand din partea de jos umbrita si printr-una. Robotul trebuie să picteze doar celule care satisfac această condiție. De exemplu, pentru imaginea de mai sus, robotul trebuie să completeze următoarele celule (vezi imaginea): Locația finală a robotului poate fi arbitrară. Algoritmul trebuie să rezolve problema pentru o dimensiune arbitrară a peretelui și orice poziție de pornire validă a robotului. La executarea algoritmului, robotul nu trebuie distrus.

Scrieți un algoritm pentru Robot care pictează toate celulele situate în stânga peretelui vertical și deasupra peretelui orizontal și adiacente acestora. Robotul trebuie să picteze numai celule care îndeplinesc această condiție. De exemplu, pentru imaginea de mai sus, Robotul trebuie să coloreze în următoarele celule (vezi imaginea).

N Scrieți un algoritm pentru Robot care pictează celulele adiacente peretelui, de sus și de jos, începând din stânga și din toate celelalte. Robotul trebuie să picteze numai celule care îndeplinesc această condiție. De exemplu, pentru figura dată a) Robotul trebuie să picteze peste următoarele celule (vezi figura b).

Poziția finală a robotului poate fi arbitrară. Algoritmul trebuie să rezolve problema pentru o dimensiune arbitrară a peretelui și orice poziție inițială acceptabilă a robotului.

1. 
   Câmpul nesfârșit are un perete vertical lung. Lungimea zidului este necunoscută. Robotul se află într-una dintre celulele situate direct în stânga peretelui. Poziția inițială a robotului este, de asemenea, necunoscută. Una dintre pozițiile posibile ale robotului este prezentată în figură (robotul este desemnat cu litera „P”):

• 
  in stanga totul;
• 
  in dreapta, incepand din partea de sus nevopsita si printr-una.

B
1102_GIA2011

Câmpul nesfârșit are doi pereți orizontali. Lungimea pereților este necunoscută. Distanța dintre pereți este necunoscută. Robotul este situat deasupra peretelui de jos într-o cușcă situată la marginea sa din stânga. Scrieți un algoritm pentru Robot care pictează toate celulele situate deasupra peretelui de jos și sub peretele de sus și adiacente acestora. Robotul trebuie să picteze numai celule care îndeplinesc această condiție. De exemplu, pentru imaginea de mai sus, robotul trebuie să picteze următoarele celule (vezi imaginea):

Locația finală a robotului poate fi arbitrară. Algoritmul trebuie să rezolve problema pentru o dimensiune arbitrară a câmpului și orice aranjare admisibilă a pereților în interiorul unui câmp dreptunghiular. La executarea algoritmului, robotul nu trebuie distrus.

ÎN
1103_GIA_2011

Scrieți un algoritm pentru Robot care pictează toate celulele situate deasupra peretelui orizontal și în dreapta peretelui vertical și adiacente acestora. Robotul trebuie să picteze numai celule care îndeplinesc această condiție. De exemplu, pentru imaginea de mai sus, Robotul trebuie să coloreze în următoarele celule (vezi imaginea).