la efectuarea lucrărilor de laborator nr.1
pentru studenții de specialitate cu normă întreagă 010500 "Suport matematic și administrarea sistemelor informatice"
Recomandat de către departamentul "Informatică și software" BSTU (protocolul №4 din 15.02.10)
În acest LR elevii se familiarizează cu conceptul algoritmului, proprietățile și metodele de înregistrare. Formarea abilităților algoritmilor de înregistrare sub formă de diagrame bloc și diagrame Nassi-Schneiderman.
Scopul lucrării este de a studia metodele de bază ale algoritmilor de înregistrare. Pentru aceasta, studentul trebuie:
· Să studieze conceptul de algoritm și executor;
· Simboluri de studiu în diagrame bloc;
· Simboluri de studiu în scheme structurate;
Durata de lucru - 2 ore.
Algoritmul - o secvență de acțiuni clar definite, a căror implementare conduce la rezolvarea problemei. Algoritmul, scris în limba mașinii, este programul pentru rezolvarea problemei.
Un algoritm este un set de acțiuni care conduc la realizarea unui rezultat într-un număr finit de pași.
1. Discreența este împărțirea algoritmului într-o serie de acțiuni finalizate (pași) individuali.
2. Determinismul (din determinarea latină - certitudine, acuratețe) - orice acțiune a algoritmului trebuie definită strict și neechivoc în fiecare caz.
3. Finiteness - fiecare acțiune separată și algoritmul în ansamblu ar trebui să poată fi finalizat.
4. Massivitate - algoritmul ar trebui să fie aplicabil diferitelor seturi de date de intrare.
5. Eficacitate - algoritmul ar trebui să conducă la o soluție fiabilă.
Exemple de algoritmi pot fi:
Instrucțiuni pentru dispozitiv;
· Descrierea rutei, etc.
Există trei tipuri principale de algoritmi:
Un algoritm liniar este un algoritm în care acțiunile sunt efectuate o dată și strict secvențial.
Un exemplu de algoritm liniar poate fi o secvență de acțiuni atunci când se pregătește un sandwich. În acest caz, algoritmul va arăta astfel:
2. Tăiați pâinea;
3. răspândirea untului pe pâine;
4. Tăiați cârnații;
5. puneți cârnați pe pâine;
Toate acțiunile sunt efectuate secvențial unul după altul într-o anumită ordine și conduc la rezultatul final.
Un algoritm de ramificare este un algoritm în care, în funcție de condiție, se efectuează una sau cealaltă secvență de acțiuni.
Cel mai simplu exemplu de implementare a unui algoritm de ramificare - dacă plouă pe stradă, atunci trebuie să luați o umbrelă, altfel nu ar trebui să vă luați o umbrelă.
Un algoritm ciclic este un algoritm ale cărui comenzi sunt repetate de un anumit număr de ori la rând.
Cel mai simplu exemplu de implementare a unui algoritm ciclic este acela că, atunci când se citește o carte, se vor repeta aceleași acțiuni: citiți pagina, răsturnați-o etc.
Algoritmi ciclici de trei tipuri:
· Buclele cu contra-acțiunile din cadrul bucla sunt executate de un anumit număr de ori;
· Ciclu cu precondiție - înainte de fiecare nouă trecere a buclei, se verifică o anumită condiție, dacă este adevărată, acțiunile din interiorul bucla sunt executate, altfel buclele iese;
· Un ciclu cu o condiție ulterioară - la început, acțiunile sunt efectuate în bucla și numai atunci se efectuează verificarea condiției.
Formulare de înregistrare a algoritmilor:
· Verbală sau verbală (lingvistică, formală-verbală);
Pseudocod (limbi oficiale algoritmice);
o structurograme (scheme Nassi-Schneiderman);
Grafică (scheme).
De obicei, mai întâi (la nivel de idei), algoritmul descris în cuvinte, dar pe măsură ce se apropie de realizarea el devine o formă mai mult și mai formală și formularea unei limbi înțeleasă de către executorul (de exemplu, cod mașină).
Un exemplu de algoritm scris de cuvinte este dat mai devreme când se ia în considerare un algoritm liniar. Un exemplu de scriere a unui algoritm care utilizează pseudocodul este codul oricărui program din orice limbaj de programare (C ++, Pascal, Basic, etc.).
Metodele de înregistrare schematică a algoritmilor sunt discutate în detaliu mai jos.
Normele de executare a schemelor sunt stabilite de următoarele documente:
· GOST 19.701-90. Scheme de algoritmi, programe, date și sisteme. Legendele și regulile de execuție.
Aceste documente în special reglementează modalitățile de construire a schemelor și aspectul elementelor lor.
Elemente de bază ale schemelor de algoritmi
Elementul afișează intrarea din mediul extern sau din ieșirea din el (cea mai obișnuită aplicație fiind începutul și sfârșitul programului). În interiorul figurii se înregistrează o acțiune corespunzătoare.
Unitate de calcul (unitate de calcul)
Efectuarea uneia sau mai multor operațiuni, prelucrarea datelor de orice fel (modificarea valorii datelor, formularul de prezentare, locația). În interiorul figurii, operațiile în sine sunt scrise, de exemplu, operația de atribuire: a = 10 * b + c.
Bloc logic (bloc condiție)
Simbolul afișează executarea unui proces constând dintr-una sau mai multe operații, care este definită în altă parte a programului (în subrutină, modul). În interiorul simbolului, numele procesului și datele transferate acestuia sunt înregistrate. De exemplu, în programare, un apel de procedură sau funcție.
Conversia datelor într-o formă potrivită pentru procesarea (introducerea) sau afișarea rezultatelor procesării (ieșirii). Acest simbol nu definește suportul de date (simbolurile specifice sunt utilizate pentru a indica tipul de suport de date).
Simbolul este format din două porțiuni - respectiv, la începutul și la sfârșitul ciclului - operațiunilor efectuate în cadrul buclei, amplasat între ele. Condițiile ciclului și incrementului sunt scrise în interiorul caracterului de început sau sfârșit al buclă, în funcție de tipul de organizare a buclă. Adesea folosit simbolul condițiilor pentru imaginea sa în locul acestui simbol al diagramei bloc a ciclului, indicând în ea soluția, și una dintre liniile de ieșire scurte de mai sus în diagrama bloc (operații ciclu anterior).
Descrierea altor elemente de circuit poate fi găsită în GOST corespunzător (menționat mai sus).
Să luăm în considerare un exemplu de construire a unei diagrame bloc a unui algoritm pentru rezolvarea ecuației quadrate complete. În primul rând, scriem algoritmul în formă verbală:
5. Afișați ecuația pe ecran;
6. Calcularea discriminantului prin formula;
7. Dacă afișați un mesaj despre absența rădăcinilor și treceți la pasul 10, mergeți la pasul 8;
8. Dacă. calcula singura rădăcină a ecuației cu formula. afișați-o pe ecran și treceți la pasul 10. În caz contrar, mergeți la pasul 9.
9. Calculați rădăcinile ecuației prin formule
Afișați rezultatele pe ecran, treceți la pasul 10.
Atunci când se construiește o diagramă, se vor utiliza următoarele elemente:
1. Începutul și sfârșitul -
2. Intrări și ieșiri de date -
Secvența acțiunilor este stabilită de săgețile de control care leagă blocurile, iar comanda corespunzătoare este scrisă în elementele grafice.
Schema bloc a algoritmului este prezentată în Fig. 1.
Fig.1. Diagrama bloc a algoritmului pentru calcularea rădăcinilor ecuației patrate
Apoi, este luată în considerare un alt mod de înregistrare algoritm grafic - folosind diagrama Nassi-Schneiderman.
Diagrama Nassi-Schneiderman (grafice structurate)
Diagrama Nassi-Shneiderman - un mod grafic de prezentare algoritmi și programe structurate dezvoltate în 1972 de către absolvent american Ben Shneiderman și Isaac Nassi.
Diagramele Nassi-Schneiderman au mai multe avantaje față de diagramele bloc atunci când elaborează algoritmi și programe structurate:
· Înregistrările sunt mai compacte (în primul rând datorită lipsei săgeților dintre elemente).
· Respectarea garantată a principiilor programării structurate (utilizând diagrame bloc, puteți obține accidental un algoritm nestructurat dacă nu sunteți atent).
· Diagrame Nassi - Shneiderman este util pentru problema granularitate elementare, deoarece acestea, de asemenea, sunt construite pe principiul pas cu pas detaliu - inițial diagramă reprezintă un dreptunghi (problema originală), atunci este desenată o anumită structură de guvernare, în care există mai multe dreptunghiuri (subactivități ale problemei inițiale ), și mai mult cu fiecare dreptunghi (sub-sarcină) se poate face aceeași operație.