Tipuri de algoritmi de informatică. Structuri algoritmice (tipuri de algoritmi). Mod verbal de scriere a algoritmilor

Se numește algoritmul prezentat în Figura 12 algoritm de precondiție ciclică, deoarece starea este verificată la începutul buclei sau la intrarea în buclă. > X la intrarea în buclă. Dacă condiția este îndeplinită, atunci mergeți la blocul 4, altfel la blocul 6.

Al patrulea bloc calculează valoarea variabilei la eu= eu+1 .

Al cincilea bloc afișează rezultatul:

Valoare variabilă la,

eu.

Exemplu : Faceți o diagramă bloc a unui exemplu (Figura 12), verificând starea ieșirii din buclă. În acest exemplu, condiția sarcinii nu se modifică, iar rezultatul este același, dar organigrama va fi diferită.

Soluţie : În acest caz, se verifică condiția ieșirii din buclă: y<=x ... În această condiție, bucla nu este executată. Starea din diagrama bloc trebuie mutată la sfârșitul ciclului, după ce a fost tipărită. Ciclul este executat atâta timp cât este îndeplinită condiția y> x.

Algoritmul, dacă condiția este transferată la sfârșitul ciclului, se numește algoritm buclă cu postcondiție... Algoritmul pentru această problemă este prezentat în Fig. 13.

Al doilea bloc introduce y=30 , X=4 .

Al treilea bloc calculează valoarea variabilei la , se numără numărul de cicluri finalizate eu= eu+1 .

Al patrulea bloc afișează rezultatul:

Valoare variabilă la,

Numărul de cicluri efectuate eu.

Al cincilea bloc verifică starea y <= X pentru a ieși din buclă. Dacă condiția este îndeplinită, atunci trecerea la blocul 6, în caz contrar, la blocul 3 și ciclul se repetă.

Fig. 13. Algoritm buclă postcondiționată

Întrebări de control

1. Conceptul de algoritm.

2. Tipuri de algoritmi.

3. Structuri algoritmice de bază.

4. Blocurile principale ale algoritmului grafic.

5. Structura algoritmică liniară. Exemplu.

6. Ramificare. Exemplu.

7. Structuri algoritmice ciclice. Exemplu.

În practică, următoarele forme de prezentare a algoritmilor sunt cele mai frecvente:

· Verbal (înregistrări în limbaj natural);

· Grafic (imagini din simboluri grafice);

· Pseudocoduri (descrieri semi-formalizate ale algoritmilor într-un limbaj algoritmic condițional, incluzând atât elemente ale limbajului de programare, cât și fraze ale limbajului natural, notație matematică general acceptată etc.);

· Software (texte în limbaje de programare).

Mod verbalÎnregistrările algoritmice sunt o descriere a etapelor secvențiale ale procesării datelor. Algoritmul este setat în formă liberă în limbaj natural. De exemplu. Scrieți algoritmul pentru găsirea celui mai mare divizor comun (GCD) dintre două numere naturale.

Algoritmul poate fi după cum urmează:

· Setați două numere;

Dacă numerele sunt egale, atunci luați oricare dintre ele ca răspuns și opriți-vă la

în caz contrar, continuați executarea algoritmului;

· Determinați numărul mai mare;

· Înlocuiți numărul mai mare cu diferența dintre numărul mai mare și cel mai mic;

· Repetați algoritmul de la pasul 2.

Algoritmul descris este aplicabil oricărui număr natural și ar trebui să ducă la soluționarea problemei.

Mod verbal nu este utilizat pe scară largă din următoarele motive:

· Asemenea descrieri nu sunt strict formalizate;

· Suferă de verbozitatea înregistrărilor;

· Permiteți ambiguitatea în interpretarea reglementărilor individuale.

Mod grafic prezentarea algoritmilor este mai compactă și mai intuitivă în comparație cu cea verbală.

Această reprezentare grafică se numește schema algoritmică sau diagramă bloc.

Într-o prezentare grafică, algoritmul este descris ca o succesiune de blocuri funcționale interconectate, fiecare dintre ele corespunzând executării uneia sau mai multor acțiuni.

În diagrama bloc, fiecare tip de acțiune (introducerea datelor inițiale, calculul valorilor expresiei, verificarea condițiilor, controlul repetării acțiunilor, finalizarea procesării etc.) corespunde unei figuri geometrice reprezentate ca un simbol bloc. Simbolurile bloc sunt conectate prin linii de tranziție care determină ordinea executării acțiunilor.

1) Bloc start-end

Elementul afișează ieșirea către mediul extern și intrarea din mediul extern (cea mai obișnuită utilizare este începutul și sfârșitul unui program). Acțiunea corespunzătoare este înregistrată în interiorul figurii.

2) Bloc de acțiune

Efectuarea uneia sau mai multor operațiuni, prelucrarea datelor de orice fel (schimbarea valorii datelor, forma de prezentare, locația). În interiorul figurii, operațiile în sine sunt scrise direct, de exemplu, operația de atribuire: a = 10 * b + c

3) Bloc logic

Afișează o soluție sau o funcție de tip comutator cu o intrare și două sau mai multe ieșiri alternative, dintre care numai una poate fi selectată după evaluarea condițiilor definite în acest element. Intrarea într-un element este indicată printr-o linie, de obicei intrând în vârful superior al elementului. Dacă există două sau trei ieșiri, atunci de obicei fiecare ieșire este indicată de o linie care iese din vârfurile rămase (laterale și inferioare). Dacă există mai mult de trei ieșiri, atunci acestea ar trebui să fie afișate ca o linie care iese din partea de sus (mai des de jos) a elementului, care apoi se ramifică. Rezultatele corespunzătoare ale calculului pot fi scrise lângă liniile care reprezintă aceste căi. Exemple de soluții: în general - comparație (trei ieșiri:>,<, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).

Conversia datelor într-un formular adecvat pentru procesare (intrare) sau afișarea rezultatelor procesării (ieșire). Acest simbol nu definește un suport de date (simboluri specifice sunt utilizate pentru a indica tipul de suport de date).

Tipuri de algoritmi

Un algoritm de ramificare este un algoritm care conține cel puțin o condiție, ca urmare a verificării căreia se poate efectua împărțirea în mai multe ramuri paralele ale algoritmului.

Algoritmul liniar este un set de comenzi (instrucțiuni) executate secvențial în timp una după alta.

Algoritm ciclic - un algoritm care asigură repetarea multiplă a aceleiași acțiuni (aceleași operații) pe date sursă noi. Majoritatea metodelor de calcul, enumerarea opțiunilor sunt reduse la algoritmi ciclici. Un ciclu de program este o secvență de comenzi (serie, corp de buclă) care pot fi executate de mai multe ori (pentru date inițiale noi) până la îndeplinirea unei anumite condiții.

Programarea înseamnă a scrie ceva folosind limbajul necunoscut al altcuiva. Odată cu dezvoltarea acestei zone de cunoaștere, dezvoltatorii au mers și mai departe și au învățat să scrie „ceva” fără a înțelege nici măcar cum sună în limba rusă. Începătorii învață să scrie cod direct în C ++ sau php, folosind multe biblioteci și nici măcar nu înțeleg cum sună ceea ce creează în limba lor maternă. Algoritmarea se ocupă cu clarificarea și aducerea la înțelegere a acestui „ceva”.

Algoritmizare

Majoritatea exemplelor de algoritmi în informatică, chiar și în universități, sunt studiate la un nivel mediocru. Este o practică obișnuită să scrii la nesfârșit coduri din ce în ce mai complexe. Încercările programatorilor fără experiență de a începe să scrie programe imediat într-un limbaj de programare pot fi comparate cu munca unui jurnalist care, abia stăpânind elementele de bază ale unei limbi străine, scrie un articol pentru o revistă. Puteți evita o astfel de problemă dacă începeți să vă înregistrați mai întâi munca în limba maternă, să o editați, să verificați erorile și, în cele din urmă, să o traduceți în limba necesară.

Avantajul acestei abordări constă în principal în faptul că dezvoltatorul va fi implicat în traducere doar 25% din timp, în timp ce atunci când scrie un program într-o limbă nouă, va cheltui 100% pentru lucrul cu un limbaj necunoscut. În același timp, se va regăsi în condiții înguste și nu va putea efectua o bună verificare a erorilor și nu va putea revizui proiectul.

Algoritmarea ajută, atunci când implementați un proiect pe un computer, să descrieți procesul soluției într-un limbaj nativ și ușor de înțeles sub forma unei diagrame de algoritmi interconectați, să analizați ideile și să obțineți cel mai înalt cod de înaltă calitate și bine gândit care va fi mai rezistent la erori și va funcționa mai eficient.

Conceptul de algoritm

Computerul nu poate rezolva probleme, poate efectua doar acțiuni simple în ordinea specificată. - Dar calculatorul? - tu intrebi. Și el este rodul muncii programatorilor care au creat un program care folosește anumiți algoritmi pentru a obține rezultatele dorite. Să luăm în considerare o situație abstractă. Ce ar trebui să faceți dacă vi se cere să găsiți rădăcinile trinomului pătratic al unei persoane care nu este familiarizată cu metodele de rezolvare a ecuațiilor?

Evident, trebuie să fie instruit pentru a rezolva ecuațiile pătratice. Acest lucru se întâmplă în conformitate cu următoarea schemă:

1. Alegeți o soluție.
2. Studiați toate detaliile metodei alese.
3. Explicați primelor două puncte viitorului interpret într-un limbaj pe care îl înțelege.

Apoi, va fi posibil să acordați interpretului sarcini pentru a rezolva ecuația pătratică. Și dacă primii doi pași sunt simpli și simpli - toate soluțiile sunt descrise în literatura relevantă, atunci al treilea pas este dificil.

Cum vă puteți asigura că ideile folosite în rezolvarea problemei vor fi percepute de interpret în același mod în care îl înțelegeți? Aici ne apropiem de conceptul de algoritm. Practica arată că, pentru a explica în mod corect ceva cuiva, trebuie parcurși următorii pași:

• determinați datele inițiale (variabile și coeficienți ai ecuației pătratice);
• descompune procesul soluției în componente unice cunoscute pentru interpret (formule discriminante și găsirea rădăcinilor);
• indicați ordinea pașilor (calculați mai întâi discriminantul, apoi rădăcinile);
• stabiliți condiția în care soluția este considerată completă (verificați rădăcinile găsite înlocuindu-le în ecuație în locul variabilelor);
• indicați exact care ar trebui să fie rezultatul soluției (rădăcinile aparțin setului de numere reale).

Setul de pași descriși în sens general este un algoritm. Astfel, un algoritm poate fi înțeles ca un mod de rezolvare a unei sarcini, scris folosind anumite reguli care permit o înțelegere fără echivoc a acțiunilor efectuate și a ordinii acestora. Algoritmii și exemplele de sarcini vor fi discutate mai detaliat mai jos.

Proprietățile de bază ale algoritmului

Discreție. Procesul de rezolvare a unei probleme constă întotdeauna în acțiuni strict separate una de alta, numite pași, care au un anumit ordin de execuție.

Certitudine. Fiecare pas ar trebui să fie clar și lipsit de ambiguitate atât în ​​sens, cât și în cheia acțiunii care trebuie efectuată.

Eficacitate. Algoritmul ar trebui să dea un rezultat. În acest caz, numărul de pași poate fi în mii sau milioane, dar ar trebui să conducă întotdeauna la un rezultat.

Caracter de masă. Orice algoritm dezvoltat pentru a rezolva o problemă trebuie să fie aplicabil tuturor problemelor de acest tip pentru toate datele de intrare valide.

Capacitățile computerului

Pentru crearea corectă a algoritmilor pentru computere, este important să le înțelegem capacitățile. Să luăm în considerare mai întâi cantitățile cu care funcționează computerul. În general, ele pot fi împărțite în numerice și text, constante și variabile.

Numerele constante înseamnă toate numerele: 3,15, 100, 105, caracteristica lor este invariabilitatea pe toată durata funcționării programului. Variabilele își schimbă valoarea în timpul executării codului și sunt de obicei notate cu litere: x, y, max, min etc.

Variabilele text, precum cele numerice, pot fi constante sau variabile. În primul caz, este doar text: „bine”, „a și b”, etc. În al doilea, este aceeași desemnare simbolică ca și pentru variabilele numerice: nume, oraș etc. Diferența dintre ele este în principal în memoria calculatorului alocată pentru stocarea unei astfel de variabile.

Operații pe care computerul este capabil să le efectueze:

1. Citiți datele de pe dispozitivele de intrare (tastatură, mouse, fișiere).
2. Calculul valorilor folosind funcții matematice: adunare, scădere, sin, cos, ln etc. - fiecare limbaj de programare are propriul set de funcții încorporate.
3. Ieșire de date (pe ecran, pe hârtie, pe interfața de rețea).
4. Tranziția între etapele programului.
5. Compararea a două valori (mai mare, mai mică, egală).

Acestea sunt operațiile de bază pe care le pot efectua majoritatea limbajelor de programare.

Metode de descriere a algoritmilor

Verbal. Acesta este cel mai simplu mod. O rețetă culinară este un exemplu în acest sens. Este permisă utilizarea unor formule matematice simple.

Grafic. Descriere folosind diagrame. Acesta este un mod special de a scrie algoritmi folosind un fel de limbaj algoritmic general acceptat - forme și blocuri care au o semnificație specifică: un dreptunghi este o acțiune simplă, un paralelogram oblic este o intrare / ieșire, un romb este o condiție etc.

Folosind un limbaj algoritmic. Similar cu cel grafic, este și un mod special de scriere a algoritmului. Există multe limbaje algoritmice disponibile. Regulile lor nu sunt stricte, altfel ar fi un limbaj de programare. Luați în considerare un exemplu de algoritm pentru calcularea salariilor în funcție de durata serviciului, scris folosind un limbaj algoritmic.

Salariile Alg (int ST, ZP real) arg ST res ZP începe dacă ST

Limbajul algoritmic poate fi numit o formă de notație mai strictă în comparație cu una verbală. Se utilizează un set limitat de cuvinte și construcțiile lor, precum și formatarea cu indentări. Dezavantajul formei verbale și al limbajului algoritmic este claritatea deteriorării algoritmului, cu o creștere a dimensiunii sale. Prin urmare, aceste metode pot fi utilizate numai pentru a transmite semnificația unor algoritmi mici.

Tipuri de algoritmi

Există o mare varietate de algoritmi concepuți pentru a rezolva o mare varietate de probleme. De exemplu, orice manual de matematică superioară conține sute de algoritmi: rezolvarea unui sistem de ecuații liniare, găsirea extrema unei funcții, calcularea unei integrale etc. Cu toate acestea, la o examinare detaliată a structurii lor, se dovedește că toți algoritmii pot să fie împărțit în mai multe tipuri. Să luăm în considerare aceste tipuri de algoritmi cu exemple.

• liniar (calculul rezultatului adunării sau multiplicării, schimbului de valori ale mai multor variabile);
• ramificare (determinarea celui mai mare dintre mai multe numere);
• ciclic (sortarea unui tablou, calcularea unui factorial).

Acestea sunt tipuri de bază. De asemenea, este demn de remarcat faptul că într-o serie de literaturi există și un al patrulea tip - recursiv. Dar nu are o denumire specială în notația schematică și este implementată prin cele de bază.

Mai multe detalii despre fiecare algoritm de calcul cu exemple vor fi descrise mai jos.

Principii de algoritmizare

1. Determinați datele sursă.
2. Alegeți o soluție.
3. Divizați metoda selectată în pași pe baza capacităților computerului (limbaj de programare).
4. Executați algoritmul sub forma unei diagrame, definind o ordine clară de pași.
5. Rezultatul rezultatelor calculului.
6. Indicați tranziția la ieșirea circuitului.

Depanarea algoritmului

Omul face greșeli și asta este un fapt. Parametrul principal al oricărui algoritm ar trebui să fie corectitudinea activității sale. Depanarea este procesul de identificare și corectare a erorilor dintr-un algoritm. Pentru aceasta, se ia un anumit set de date inițiale, numite date de testare. Ele sunt, de regulă, tot felul de tipuri de date sursă. De exemplu, dacă un număr este furnizat la intrare, atunci algoritmul trebuie verificat pentru o funcționare corectă, luând în considerare: numerele pozitive, negative, întregi și reale, valori zero etc.

Creierul uman rămâne principalul instrument pentru verificarea acurateței unui algoritm. Desigur, este permisă utilizarea altor instrumente informatice pentru automatizarea verificării, dar într-un fel sau altul, este o persoană care pregătește testele și analizează rezultatele. În acest caz, apare întrebarea, de ce avem nevoie de un algoritm dacă o persoană face totul singur? Apoi, sarcina principală a algoritmului este soluția repetată a unui anumit tip de problemă.

Algoritmi liniari

Liniar este un algoritm în care pașii sunt secvențiali unul după altul. Orice algoritm care nu conține ramuri și bucle este liniar. Luați în considerare un exemplu de algoritm care rezolvă următoarea problemă: un lup și un iepure stau în două celule, trebuie să le schimbați.

Cheia pentru rezolvarea acestei probleme este o colivie de temperatură suplimentară care ar trebui utilizată pentru schimbul de animale.

Algoritmi de furcare

După cum sugerează și numele, algoritmul are mai multe ramuri. Esența lucrării este de a selecta una dintre opțiunile posibile pentru procesul de calcul, în funcție de orice condiții. Ramificarea schematică este reprezentată de o cutie în formă de diamant, în interiorul căreia este indicată starea, iar pe părțile laterale ale acesteia există ramuri de selecție în funcție de starea adevărată sau falsă. Algoritmul de ramificare și exemple de aplicare a acestuia pot fi găsite peste tot. În programare, aceasta este o construcție tipică if-else care se găsește în aproape orice limbaj.

Să dăm un exemplu de algoritm pentru rezolvarea problemei găsirii celui mai mare dintre trei numere.

Algoritm ciclic

Un algoritm ciclic este un algoritm în care aceiași pași sunt repetați de multe ori, în care numai valoarea unei anumite variabile, peste care se fac calcule, se poate schimba. Tipurile algoritmului de buclă și un exemplu vor fi discutate mai jos, dar deocamdată vom enumera pașii principali pentru construirea unei bucle.

1. Atribuirea unei valori inițiale variabilelor. Fără această condiție, bucla va eșua cel mai probabil sau va face erori.
2. Unitatea pentru calcularea rezultatelor. Acesta este corpul principal al buclei.
3. Verificarea stării la sfârșitul procesului ciclic. Dacă uitați să specificați condiția în care ar trebui să se încheie bucla, algoritmul va rula la nesfârșit.
4. Schimbarea variabilelor. Acest bloc intră în vigoare după verificarea stării de reziliere dacă a fost falsă. Dacă uitați de acest bloc, atunci ciclul va efectua o acțiune pentru totdeauna și nu se va finaliza niciodată. Prin urmare, este important ca variabilele să sufere unele modificări la fiecare iterație a buclei.

Există mai multe tipuri de algoritmi de buclă: cu postcondiție, condiție prealabilă și parametru.

Să construim un algoritm ciclic folosind exemplul găsirii factorialului numărului N.

Alte tipuri de algoritmi

Există o serie de alți algoritmi care diferă în ceea ce privește clasificarea sau originea.

• Algoritmi mecanici. De exemplu, funcționarea unui motor cu ardere internă sau a unei linii de asamblare.
• Algoritmi probabilistici. Munca lor se bazează pe teoria probabilității și statistica matematică.
• Algoritmi euristici. Folosiți considerații practice în munca lor, fără o justificare matematică riguroasă.
• Algoritmi genetici. Aplicați idei biologice în munca lor.

Algoritmii pot fi simpli, complexi, dar toate au caracteristici comune. Conform acestor caracteristici, este obișnuit să distingem trei tipuri de algoritmi, cu care vom face cunoștință.

În algoritmi, comenzile sunt scrise una după alta într-o ordine specifică. Nu sunt neapărat efectuate în secvența înregistrată. Pot exista referințe interne la diferite echipe.

În general, executarea comenzilor conform algoritmului amintește oarecum de jocurile de societate în care participanții se aruncă pe rând pe zaruri și merg pe câmpuri. Mai mult decât atât, în margini pot exista comentarii în stilul: „Du-te înapoi cu 2 celule” sau „Mergeți cu 5 celule înainte” (Fig. 1).

Orez. 1. Joc de societate ()

Binecunoscutul joc „Monopoly” sau „Manager” este un model mai complex al execuției algoritmului (Fig. 2).

Orez. 2. Jocul „Monopoly” ()

Diferența esențială dintre acest joc și simpla execuție a algoritmului este că scopul final al participanților nu este de a parcurge calea, ci de a acumula bani prin anumite acțiuni.

În funcție de ordinea executării comenzii, se pot distinge trei tipuri de algoritmi:

Algoritmi liniari;

Algoritmi de ramificare;

Algoritmi de repetare.

"Monopol"

Monopoly este unul dintre cele mai populare jocuri de societate. Regulile sale sunt destul de simple și de înțeles pentru toți cei care au jucat-o cel puțin o dată (Fig. 4).

Orez. 4. Jocul „Monopol” ()

În momentul începerii, jucătorii au o sumă egală de bani. Aruncând zaruri și mutându-și jetoanele pe terenul de joc în buclă, dobândesc o mulțime de bunuri imobiliare de culori diferite. Odată ajuns pe site-ul dobândit de inamic, jucătorul este obligat să plătească chiria stabilită. După ce a cumpărat toate parcelele din același grup de culori, participantul poate construi case și hoteluri pe ele, ceea ce mărește mărimea contractului de închiriere. Scopul a tot ceea ce se întâmplă este banal - să distrugă toți rivalii.

Potrivit unor surse oficiale - Parker Brothers, care produce Monopoly din 1935 până în prezent - legendarul joc de masă s-a născut în felul următor. În 1934, un inginer șomer Charles Darrow (Fig. 5) a invitat biroul de mai sus să lanseze un joc pe care îl inventase despre tranzacționarea imobiliară.

Orez. 5. Charles Darrow ()

După ce au descoperit 52 de greșeli de proiectare în jocul de societate, frații Parker au refuzat inventatorul. El, cu un spirit antreprenorial pur american, a mers la tipografie, a comandat 5 mii de exemplare ale jocului și le-a vândut destul de repede. Dându-și seama că profiturile scăpau din nas, Parker Brothers a dobândit în grabă drepturile la Monopoly, iar în anul următor a devenit cel mai bine vândut joc de societate din Statele Unite și Darrow - întruchiparea vie a visului american.

Cu toate acestea, în același timp, există și jocuri anterioare cunoscute care amintesc izbitor de „Monopol”. Se pare că Darrow a fost doar primul care s-a grăbit și a primit un brevet pentru distracția „populară”? Da și nu. Investigațiile din ultimii ani au arătat lumina asupra misterului din spatele originilor Monopolului.

În a doua jumătate a secolului al XIX-lea, economistul politic Henry George a trăit și a lucrat în Statele Unite. El a propus înlocuirea tuturor taxelor cu un singur impozit - pe teren. Impregnată de ideile sale, în ianuarie 1904 Maggie a primit un brevet pentru jocul de masă The Landlord’s Game, care, atât din punct de vedere al regulilor, cât și al aspectului, seamănă cu actualul „Monopol”. Se crede că „Jocul proprietarului terenului” avea două variante ale regulilor: jucând un joc în conformitate cu legile fiscale actuale, jucătorii au trecut la modelul propus de George - și se presupune că s-au convins de avantajele sale necesare . Astfel, jocul nu era divertisment, ci un instrument de luptă ideologică.

Nu a venit la producția de masă, dar The Landlord’s Game s-a răspândit treptat în America de Nord în copii artizanale. Creșterea interesului pentru jocul de societate a căzut în anii Marii Depresii: mii de șomeri s-au bucurat să se imagineze ca pe pungi de bani, cel puțin la masa de jocuri de noroc. Apariția unui om întreprinzător precum Charles Darrow a durat câteva luni - și a venit, timp de mai multe decenii, asumându-și faima singurului inventator al „Monopolului”.

Au fost, desigur, cei care au considerat necesar să smulgă o piesă de la deținătorii drepturilor de autor. Monopolurile fără licență au inundat China. Și în țara noastră au fost și sunt produse rânduri subțiri de clone - „Broker”, „Cooperativă”, „Manager” (Fig. 6) ...

Orez. 6. Jocul "Manager" ()

Având în vedere recențierea regândirii rolului lui Darrow în crearea Monopolului și expirarea drepturilor de autor, astfel de companii nu vor fi trimise în judecată. Chiar dacă presupunem că nu exista Elizabeth Maggie în lume, regulile „Monopolului” au trecut cu mult timp în domeniul public. Cu toate acestea, Hasbro păstrează încă o parte din brevet la el: designul jetoanelor, designul grafic, succesiunea celulelor pe terenul de joc.

Un algoritm în care comenzile sunt executate în ordinea în care sunt scrise, adică secvențial una după alta, se numește liniar.

Orez. 3. Bec ()

De exemplu, următorul algoritm pentru înlocuirea unui bec ars este liniar (Fig. 3):

1. opriți comutatorul luminii;

2. Deșurubați becul ars;

3. înșurubați un bec nou;

4. Porniți comutatorul pentru a verifica dacă lumina este aprinsă.

Folosind o diagramă bloc, acest algoritm poate fi descris după cum urmează:

(diagramă (Fig. 7.) vezi la sfârșitul sinopsisului)

Situațiile în care secvența acțiunilor necesare este cunoscută în avans sunt extrem de rare. În viață, trebuie să luați adesea o decizie în funcție de situația actuală. Dacă plouă, luăm o umbrelă și ne îmbrăcăm un impermeabil; dacă este cald, purtați haine ușoare. Există, de asemenea, condiții de selecție mai complexe. În unele cazuri, soarta unei persoane depinde de decizia aleasă.

Logica decizională poate fi descrisă după cum urmează:

DACĂ<условие>, ATUNCI<действия 1>,

IN CAZ CONTRAR<действия 2>

DACĂ aveți bani, ATUNCI cumpărați pâine, NU o cumpărați ALTĂ.

DACĂ veți fi în centru astăzi, atunci formați-mă, ELSE nu.

DACĂ lecțiile sunt învățate, atunci merg la plimbare, ALTE învață lecțiile.

In unele cazuri<действия 2>poate lipsi. Acest lucru se poate datora atât evidenței sale (ca, de exemplu, în primul exemplu - este clar că, dacă nu aveți bani, atunci pur și simplu nu puteți cumpăra pâine), și lipsa de nevoie pentru aceasta.

DACĂ<условие>, ATUNCI<действия 1>

DACĂ el s-a numit o sarcină, apoi urcă în spate.

DACĂ vrei să fii sănătos, atunci temperează-te.

O formă de organizare a acțiunilor în care, în funcție de îndeplinirea sau neîndeplinirea unei anumite condiții, se efectuează una sau alta secvență de acțiuni, se numește ramificare.

Haideți să descriem sub forma unei diagrame succesiunea acțiunilor unui elev de clasa a VI-a care a uitat cheile apartamentului, pe care și le imaginează după cum urmează: „Dacă mama mea este acasă, atunci voi veni și mă așez să fac tema mea. Dacă mama nu este acasă, atunci voi merge la fotbal cu prietenii mei până când va veni mama. Dacă nu sunt prieteni pe stradă, voi merge pe leagăn până când va veni mama. "

(diagramă bloc (Fig. 8.) vezi la sfârșitul sinopsisului)

Condiții necesare și suficiente

Am discutat deja cu dvs. că există condiții necesare și suficiente.

Un exemplu de condiție prealabilă ar fi:

Pentru a deveni medic, trebuie să obțineți o diplomă medicală.

Condiția de a avea o educație medicală este necesară pentru a lucra ca medic, dar nu este suficientă. Într-adevăr, nu toți absolvenții de medicină devin medici.

Un exemplu de condiție suficientă ar fi:

Pentru a vă răcori, pur și simplu porniți aparatul de aer condiționat.

Această condiție este suficientă: dacă porniți aparatul de aer condiționat, acesta devine cu adevărat mai răcoros. Cu toate acestea, această condiție nu este necesară, deoarece pentru a atinge acest obiectiv, puteți porni ventilatorul, puteți deschide o fereastră etc.

Desigur, există condiții necesare și suficiente în același timp (astfel de condiții sunt numite echivalează cu). De exemplu:

Pentru ca vara să vină, este necesar și suficient ca primăvara să se termine.

Într-adevăr, dacă primăvara s-a terminat, atunci vine vara, iar dacă primăvara nu s-a terminat, atunci vara nu poate veni. Adică condițiile pentru sfârșitul primăverii și începutul verii sunt echivalente.

Conceptele de condiții necesare, suficiente și echivalente sunt foarte importante într-o astfel de ramură a matematicii ca logica matematică. În plus, sunt foarte frecvente în demonstrarea diferitelor teoreme.

În practică, există adesea sarcini în care una sau mai multe acțiuni trebuie repetate de mai multe ori, în timp ce unele condiții stabilite anterior sunt îndeplinite.

De exemplu, dacă trebuie să sortați o cutie de mere pentru a le separa pe cele putrede de cele coapte, atunci trebuie să repetăm ​​pașii următori:

1. Ia un măr.

2. Vezi dacă este putred.

3. Dacă este putred - aruncați-l, dacă nu - transferați-l într-o altă cutie.

Este necesar să efectuați acest set de acțiuni până când merele din cutie se epuizează.

Forma de organizare a acțiunilor, în care executarea aceleiași secvențe de acțiuni se repetă în timp ce se îndeplinește o anumită condiție prestabilită, se numește ciclu (repetare).

Se numește situația în care execuția buclei nu se termină niciodată buclare.

Ar trebui dezvoltate algoritmi pentru a evita astfel de situații.

Luați în considerare algoritmul pentru ceasul deșteptător de pe un telefon, care ar trebui să sune la 8:00 dimineața și apoi să sune la fiecare 10 minute până când este oprit.

În acest caz, diagrama sa blocată arată astfel: (diagrama bloc (Fig. 9.) vezi la sfârșitul sinopsisului)

În această lecție, am discutat trei tipuri de algoritmi - algoritmi liniari, algoritmi de ramificare și algoritmi repetitivi.

În lecția următoare, vom discuta despre cum să scriem algoritmi în practică.

Seta lui Eratostene

Să ne amintim definiția unui număr natural prim.

Un număr natural se numește prim dacă este are doar doi divizori: unul și numărul în sine. Restul numerelor sunt apelate constitutiv... Mai mult, numărul 1 nu este nici simplu, nici compus.

Exemple de numere prime: 2, 3, 5, 7.

Exemple de numere compuse: 4, 6, 8.

În secolul al III-lea î.Hr., matematicianul grec Eratos-phene a propus următorul algoritm pentru găsirea tuturor numerelor mai mici decât un număr dat NS:

1. scrieți toate numerele naturale de la 1 la n;

2. ștergeți 1;

3. subliniați cel mai mic dintre numerele nemarcate;

4. Tăiați toate numerele care sunt multipli ai numărului subliniat în pasul anterior;

5. dacă lista conține numere nemarcate, treceți la pasul 3, altfel toate numerele subliniate sunt prime.

Acesta este un algoritm ciclic. Când este executat, pașii 3-5 se repetă până când există numere nemarcate în lista originală.

Să luăm în considerare rezultatul acestui algoritm. Să scriem toate numerele prime de la 1 la 25.

Să scriem numerele de la 1 la 25.

Să ștergem 1. Acum vom sublinia cele două. Tăiați toate numerele pare.

Deoarece nu toate numerele sunt marcate, subliniați 3. Acum, tăiați toate numerele care sunt divizibile cu 3.

Deoarece nu toate numerele sunt marcate, subliniați 5. Acum răstoarne numărul 25.

Deoarece nu toate numerele sunt marcate, subliniem 7.

Nu puteți tăia nimic, dar nu toate numerele sunt marcate, așa că subliniem 11.

Nu puteți tăia nimic, dar nu toate numerele sunt marcate, așa că subliniem 13. Din nou, nu putem tăia nimic - subliniem 17, apoi 19 și 23.

Toate numerele sunt acum marcate.

Primim numere prime: 2, 3, 5, 7, 11, 13, 17, 19, 23.

Orez. 7.Schema bloc pentru schimbarea unui bec

Orez. 8. Organigrama acțiunilor elevului de clasa a VI-a

Orez. 9. Schema bloc a ceasului cu alarmă

Bibliografie

1. Bosova L.L. Informatică și TIC: manual pentru clasa a 6-a. - M.: BINOM. Laborator de cunoștințe, 2012.

2. Bosova L.L. Informatică: Caiet de lucru pentru clasa a 6-a. - M.: BINOM. Laborator de cunoștințe, 2010.

3. Bosova L.L., Bosova A.Yu. Lecții de informatică în clasele 5-6: Ghid metodologic. - M.: BINOM. Laborator de cunoștințe, 2010.

1. Portal internet „Rețeaua noastră” ()

2. Portalul Internet „Hypermarketul cunoștințelor” ()

3. Portalul de internet „kaz.docdat.com” ()

Teme pentru acasă

1. §3.4 (Bosova L.L. Informatică și TIC: Manual pentru clasa a 6-a).

2. Pagina 81 sarcini 2, 6 (Bosova L.L. Informatică și TIC: Manual pentru clasa a 6-a).

3. Pagina 82 sarcina 9, 11, 13, 14 (Bosova L.L. Informatică și TIC: Manual pentru clasa a 6-a).

4. * Pagina 83 sarcina 15 (Bosova L.L. Informatică și TIC: Manual pentru clasa a 6-a).