Tipuri de algoritmi. Tip liniar de algoritmi

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ă să înțeleagă măcar cum sună în rusă. Începătorii învață să scrie cod direct în C++ sau php, folosind multe biblioteci și nici măcar nu înțeleg cum ce creează sunete în limba lor maternă. Algoritmizarea se ocupa cu clarificarea si aducerea la inteles a acestui „ceva”.

Algoritmizare

Majoritatea exemplelor de algoritmi din informatică, chiar și din universități, sunt studiate la un nivel mediocru. Este o practică obișnuită să scrieți la nesfârșit cod din ce în ce mai complex. Încercările programatorilor fără experiență de a începe imediat să scrie programe într-un limbaj de programare pot fi comparate cu munca unui jurnalist care, după ce abia stăpânește 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 munca mai întâi în limba maternă, să o editați, să verificați dacă există erori și, în final, să o traduceți în limba dorită.

Avantajul acestei abordări constă în principal în faptul că dezvoltatorul va fi angajat în traducere doar 25% din timp, în timp ce atunci când scrie un program într-o limbă nouă, va petrece 100% lucrând cu o limbă necunoscută. În același timp, se va găsi în condiții înghesuite și nu va putea efectua o verificare bună pentru erori și nu va putea revizui proiectul.

Algoritmizarea ajută, la implementarea unui proiect pe un computer, să descrie procesul de soluție într-un limbaj nativ și ușor de înțeles sub forma unei diagrame de algoritmi interconectați, să analizeze idei și să obțină cel mai de înaltă calitate și cel mai bine gândit cod care va fi mai rezistent la erori și va funcționa mai eficient.

Conceptul de algoritm

Un computer nu poate rezolva probleme, poate efectua doar acțiuni simple în ordinea specificată. — Dar calculatorul? - tu intrebi. De asemenea, 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, el trebuie să fie antrenat să rezolve ecuații patratice. Acest lucru se întâmplă conform următoarei scheme:

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

Apoi va fi posibil să se dea executantului 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 de specialitate, atunci al treilea pas este dificil.

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

• determinați datele inițiale (variabila și coeficienții ecuației pătratice);
• împărțiți procesul de soluție în componente unic cunoscute pentru executant (formule discriminante și găsirea rădăcinilor);
• indicați ordinea pașilor (mai întâi calculaț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 mulțimii numerelor reale).

Setul descris de pași în sens general este un algoritm. Astfel, un algoritm poate fi înțeles ca o metodă de rezolvare a unei sarcini, scrisă folosind anumite reguli care permit o înțelegere fără ambiguitate 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

Discretenie. Procesul de rezolvare a unei probleme constă întotdeauna în acțiuni strict separate unele de altele, numite pași, care au o anumită ordine de execuție.

Certitudine. Fiecare pas trebuie să fie clar și lipsit de ambiguitate atât ca semnificație, cât și ca cheia acțiunii care urmează să fie efectuată.

Eficacitatea. Algoritmul ar trebui să dea un rezultat. În acest caz, numărul de pași poate fi de mii sau milioane, dar trebuie 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ă înțelegeți capacitățile acestora. Să luăm mai întâi în considerare 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, 10 5, caracteristica lor este invariabilitatea pe toată durata funcționării programului. Variabilele își schimbă valoarea în timpul execuției 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 denumire simbolică ca și pentru variabilele numerice: nume, oraș etc. Diferența dintre ele este în principal în memoria computerului alocată pentru stocarea unei astfel de variabile.

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

1. Citiți date de la dispozitivele de intrare (tastatură, mouse, fișiere).
2. Calcularea 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, către interfața de rețea).
4. Trecerea între etapele programului.
5. Comparația a două valori (mai mare, mai mică, egală).

Acestea sunt operațiunile 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 formulelor 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 o modalitate 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 vechimea în muncă, scris folosind un limbaj algoritmic.

alg salarii (int ST, real ZP) arg ST res ZP start if ST< 5 то zp = 150 иначе если ST <= 15 то ZP = 180 иначе ZP = 180 + (ST - 15)*10 конец

Limbajul algoritmic poate fi numit o formă mai strictă de notație în comparație cu cea verbală. Se folosește un set limitat de cuvinte și construcțiile acestora, precum și formatarea cu indentări. Dezavantajul formei verbale și al limbajului algoritmic este deteriorarea clarității algoritmului cu creșterea dimensiunii acestuia. Prin urmare, aceste metode pot fi folosite doar pentru a transmite semnificația unor algoritmi mici.

Tipuri de algoritm

Există o mare varietate de algoritmi proiectaț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 extremelor 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 fi împărțit în mai multe tipuri. Să luăm în considerare aceste tipuri de algoritmi cu exemple.

• liniară (calcularea rezultatului adunării sau înmulțirii, 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 de remarcat faptul că într-o serie de literatură există și un al patrulea tip - recursiv. Dar nu are o denumire specială în notația schematică și se implementează 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 sursa datelor.
2. Alege o soluție.
3. Împărțiț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ă a pașilor.
5. Ieșirea rezultatelor calculului.
6. Indicați trecerea 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. Acestea 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 funcționarea corectă, ținând cont de: numere pozitive, negative, întregi și reale, valori zero etc.

Creierul uman rămâne principalul instrument de verificare a acurateței unui algoritm. Desigur, este permisă utilizarea altor instrumente informatice pentru a automatiza verificarea, dar într-un fel sau altul, este o persoană care pregătește teste ș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 rezolvarea repetată a unui anumit tip de problemă.

Algoritmi liniari

Linear 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 cușcă termică suplimentară care ar trebui folosită pentru a schimba animalele.

Algoritmi de bifurcare

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 casetă în formă de romb, în ​​interiorul căreia este indicată o condiție, iar pe lateralele acesteia sunt ramuri de selecție în funcție de condiția adevărată sau falsă. Algoritmul de ramificare și exemple de aplicare a acestuia pot fi găsite peste tot. În programare, acesta este un construct tipic dacă-altfel 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 se repetă aceiași pași de mai multe ori, în care doar valoarea unei anumite variabile, peste care se fac calcule, se poate modifica. Tipurile de algoritm de looping ș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 greșeli.
2. Blocul pentru calcularea rezultatelor. Acesta este corpul principal al buclei.
3. Verificarea stării de sfârșit a procesului ciclic. Dacă uitați să specificați condiția în care trebuie să se încheie bucla, algoritmul va rula pe termen nelimitat.
4. Schimbarea variabilelor. Acest bloc intră în vigoare după verificarea condiției de terminare dacă a fost falsă. Dacă uiț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, precondiție și parametru.

Să construim un algoritm ciclic folosind exemplul de găsire a factorialului numărului N.

Alte tipuri de algoritmi

Există o serie de alți algoritmi care diferă în clasificare sau origine.

• 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ă justificare matematică riguroasă.
• Algoritmi genetici. Aplicați ideile biologice în munca lor.

Algoritmii pot fi simpli, complecși, dar toți au caracteristici comune. Prin aceste caracteristici se obișnuiește să distingem trei tipuri de algoritmi, cu care ne vom familiariza.

În algoritmi, comenzile sunt scrise una după alta într-o anumită ordine. Ele nu sunt neapărat efectuate în secvența înregistrată. Pot exista referiri interne la diferite echipe.

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

Orez. 1. Joc de societate ()

Cunoscutul joc „Monopoly” sau „Manager” este un model mai complex de execuție a algoritmului (Fig. 2).

Orez. 2. Jocul „Monopoly” ()

Diferența esențială a acestui joc față de simpla execuție a algoritmului este că scopul final al participanților nu este parcurgerea traseului, ci acumularea de bani prin intermediul anumitor 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 l-au jucat cel puțin o dată (Fig. 4).

Orez. 4. Jocul „Monopoly” ()

La momentul începerii, jucătorii au o sumă egală de numerar. Aruncând zarurile și mișcându-și jetoanele pe terenul de joc în buclă, aceștia dobândesc o mulțime de imobile de culori diferite. Odată ajuns pe site-ul achiziționat 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 dimensiunea contractului de închiriere. Scopul a tot ceea ce se întâmplă este banal - distrugerea tuturor rivalilor.

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-a inventat despre comerțul imobiliar.

Orez. 5. Charles Darrow ()

După ce au descoperit 52 de greșeli de design în jocul de masă, frații Parker l-au refuzat pe inventator. 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 le scăpau din nas, Parker Brothers a dobândit în grabă drepturile asupra Monopoly, iar în anul următor a devenit cel mai bine vândut joc de societate din Statele Unite, iar Darrow a fost întruchiparea vie a visului american.

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

Î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. Îmbunătățită de ideile sale, în ianuarie 1904 Maggie a primit un brevet pentru jocul de societate The Landlord’s Game, care, atât ca reguli, cât și ca aspect, seamănă cu actualul „Monopol”. Se crede că „Jocul proprietarului terenului” avea două variante ale regulilor: după ce au jucat un joc conform legilor fiscale actuale, jucătorii au trecut la modelul propus de George - și se presupune că s-au convins de avantajele necesare. . Astfel, jocul nu a fost 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 Crize: mii de șomeri s-au bucurat să se imagineze ca niște 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 multe decenii și-a asumat faima de unicul inventator al „Monopolului”.

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

Orez. 6. Joc „Manager” ()

Având în vedere recenta regândire a rolului lui Darrow în crearea monopolului și expirarea drepturilor de autor, astfel de companii nu vor fi trimise în judecată. Chiar dacă presupunem că Elizabeth Maggie nu a existat în lume, regulile „Monopoly” au trecut cu mult timp în urmă în domeniul public. Cu toate acestea, Hasbro păstrează încă o parte din brevet cu 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 întrerupătorul 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 reprezentat după cum urmează:

(diagrama bloc (Fig. 7.) vezi la sfârșitul rezumatului)

Situațiile în care succesiunea acțiunilor necesare este cunoscută dinainte sunt extrem de rare. În viață, de multe ori trebuie să iei o decizie în funcție de situația actuală. Dacă plouă, luăm o umbrelă și ne punem o haină de ploaie; dacă este cald, purtați haine ușoare. Există și condiții de selecție mai complexe. În unele cazuri, soarta unei persoane depinde de decizia aleasă.

Logica de luare a deciziilor poate fi descrisă după cum urmează:

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

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

DACA ai bani, ATUNCI cumpara paine, NU o cumperi ALTA.

DACĂ azi vei fi în centru, apelează-mă, ALLTĂ nu.

DACA lectiile sunt invatate, ATUNCI iesi la o plimbare, ALLT invata lectiile.

In unele cazuri<действия 2>poate fi absent. Acest lucru se poate datora atât evidentității 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), cât și absenței necesității acesteia.

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

DACĂ s-a numit încărcătură, atunci urcă-te în spate.

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

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

Să înfățișăm sub forma unei organigrame succesiunea acțiunilor unui elev de clasa a VI-a care a uitat cheile apartamentului, pe care și-l închipuie astfel: „Dacă mama e acasă, atunci voi veni și mă voi așeza să fac. tema mea. Dacă mama nu este acasă, atunci voi merge să joc fotbal cu prietenii mei până vine mama. Dacă nu sunt prieteni pe stradă, voi merge pe leagăn până vine mama mea.”

(diagrama bloc (Fig. 8.) vezi sfârșitul rezumatului)

Condiții necesare și suficiente

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

Un exemplu de condiție prealabilă ar fi:

Pentru a deveni medic, trebuie să completezi o diplomă de medicină.

Condiția de a avea studii medicale este necesară pentru a lucra ca medic, dar nu este suficientă. Într-adevăr, nu toți absolvenții de medicină devin doctori.

Un exemplu de condiție suficientă ar fi:

Pentru a vă răcori, porniți doar aerul condiționat.

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

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

Pentru ca vara sa vina, este necesar si suficient ca primavara sa se incheie.

Î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 precum logica matematică. În plus, ele 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 o anumită condiție stabilită anterior este îndeplinită.

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

1. Luați un măr.

2. Vezi dacă este putred.

3. Dacă este putred - aruncați-l, dacă nu - transferați-l în 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 succesiuni de acțiuni se repetă în timp ce o anumită condiție prestabilită este îndeplinită, se numește ciclu (repetiție).

Se apelează situația în care execuția buclei nu se termină niciodată buclă.

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

Să luăm în considerare algoritmul ceasului cu alarmă de pe 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, schema sa bloc arată astfel: (diagrama bloc (Fig. 9.) vezi la sfârșitul rezumatului)

Î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ă.

Sita lui Eratosthenes

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

Un număr natural se numește prim dacă este are doar doi divizori: unu și numărul însuși. Restul numerelor sunt chemate constitutiv... În plus, 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 prime mai mici decât un anumit număr. NS:

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

2. șterge 1;

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

4. Trimiteți toate numerele care sunt multipli ai numărului subliniat la pasul anterior;

5. dacă lista conține numere nemarcate, atunci treceți la pasul 3, în caz contrar 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 le vom sublinia pe cele două. Tăiați toate numerele pare.

Deoarece nu toate numerele sunt marcate, subliniază 3. Acum taie toate numerele care sunt divizibile cu 3.

Deoarece nu toate numerele sunt marcate, subliniați 5. Acum tăiați 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.

Obținem 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. Bossova L.L. Informatică și TIC: manual pentru clasa a VI-a. - M .: BINOM. Laboratorul de cunoștințe, 2012.

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

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

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

2. Portalul de internet „Knowledge Hypermarket” ()

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

Teme pentru acasă

1. §3.4 (Bosova L.L. Informatica si TIC: Manual pentru clasa a VI-a).

2. Pagina 81 sarcini 2, 6 (Bosova L.L. Informatica si TIC: Manual pentru clasa a VI-a).

3. Pagina 82 sarcina 9, 11, 13, 14 (Bosova L.L. Informatica si TIC: Manual pentru clasa a VI-a).

4. * Pagina 83 sarcina 15 (Bosova L.L. Informatica si TIC: Manual pentru clasa a VI-a).

Principalul proprietăți algoritm sunt:

1.

2.

3.

4.

·liniar;

· Ramificare;

· ciclic.

Liniar

Ramificare

ciclic

Structura programului în Pascal.

Pascal Este o limbă care predă acuratețea și claritatea (secțiunile programului nu pot fi schimbate, este necesar să se reprezinte clar activitatea programului etc.). De aceea este necesar să cunoaștem și să înțelegem clar structura unui program Pascal.

PROGRAM denumirea programului;
(în litere engleze, un cuvânt. Vrei mai profund? Atunci trebuie să folosești regulile pentru scrierea identificatorilor)

UTILIZĂRI biblioteci de plug-in (module);
(funcții suplimentare, acestea pot fi conectate la programul din această linie)

ETICHETA lista de etichete;
(de la un loc al programului „sari” în altul)

CONST secțiune care descrie constante;
(valori constante, nu pot fi modificate)

TIP descrierea tipurilor de variabile; (tip)

VAR definirea variabilelor globale;
(descrierea tuturor variabilelor care pot fi modificate în program)

DEFINIREA PROCEDURILOR;

DEFINIREA FUNCȚIILOR;

blocul principal al programului

Aproape fiecare linie este urmată de un „ ; ". Acest semn indică faptul că linia este terminată. Semnul" ; „nu este plasat după cuvântul de serviciu ÎNCEPEși ultimul SFÂRȘIT.(care înseamnă sfârșitul programului) urmat de un punct.

3.Operator condiționat, operator de alegere. Operații logice în Pascal, tabele de adevăr, legile de bază ale algebrei logice.
Operatori condiționali

IF [expresie booleană] Apoi [instrucțiunea 1]; Else [operatorul 2];

Instrucțiunea IF funcționează după cum urmează: mai întâi, rezultatul unei expresii booleene este verificat. Dacă rezultatul este TRUE, atunci [statement_1] după cuvântul cheie Then este executat și [statement_2] este omis. Dacă rezultatul este FALS, atunci [statement_1] este omis și [statement_2] este executat.

FOR [cycle_parameter]: = [n_z_p_ts] To [k_z_p_ts] Do [operator];

FOR, To, Do - cuvinte de serviciu. [cycle_parameter] este un parametru de ciclu. [n_z_p_ts] - valoarea inițială a parametrului ciclului. [k_z_p_ts] - valoarea finală a parametrului ciclului. [operator] este un operator arbitrar.

Parametrul buclă trebuie să fie o variabilă de tip ordinal. Valorile de început și de sfârșit ale parametrului buclei trebuie să fie de același tip cu parametrul buclei.

WHILE [condiție] Do [operator];

WHILE, Do - cuvinte de serviciu. [condiție] este o expresie de tip boolean. [operator] este un operator obișnuit.

Instrucțiunea While funcționează după cum urmează: mai întâi, rezultatul condiției booleene este verificat. Dacă rezultatul este adevărat, atunci se execută instrucțiunea, după care condiția este returnată la test cu noua valoare a parametrilor în expresia logică a condiției. Dacă rezultatul este fals, atunci bucla este încheiată.

REPEAT [loop-body]; PÂNĂ [condiție];

Instrucțiunea REPEAT funcționează după cum urmează: mai întâi sunt executate instrucțiunile corpului buclei, după care rezultatul este verificat pentru condiția logică. Dacă rezultatul este fals, atunci se efectuează o revenire la execuția operatorilor următorului corp de buclă. Dacă rezultatul este adevărat, atunci declarația iese.

Operare logică ȘI

Operația logică AND se realizează cu doi biți, să-i numim a și b. Rezultatul executării operației logice AND va fi egal cu 1 dacă a și b sunt egali cu 1, iar în toate celelalte (alte) cazuri, rezultatul va fi egal cu 0. Să ne uităm la tabelul de adevăr al operației logice și .

A	b	a & b

Tipuri de date.

Ordinal:

întregi; Joc de inteligență; Simbolic; Numerabil; Interval;

Real:

Structurat:

tablouri; Siruri de caractere; Seturi; intrări; Dosare;

Indicatori

6. Matrice. Definiție, descriere, alocare și utilizare a memoriei.
O matrice este un tip de date structurate cu un număr fix de elemente și are același tip.

Proprietate:

toate elementele matricei sunt de același tip;

tabloul are un singur nume pentru toate elementele;

accesul la un anumit element al matricei se realizează prin index(i).

7.Proceduri și funcții. Antet și corp de proceduri și funcții, clasificarea parametrilor. Proceduri și funcții de apelare, particularitățile utilizării lor.

Subrutină este o parte a programului, concepută ca o structură sintactică separată și prevăzută cu un nume. „Apelarea” unei subrutine, de ex. execuția acțiunilor specificate într-o subrutină sub formă de instrucțiuni poate fi efectuată la un moment dat în program prin specificarea numelui acestei subrutine. Pe lângă specificarea unei secvențe de acțiuni, orice subrutină poate conține o descriere a unui anumit set local obiecte - constante, tipuri, variabile etc. Aceste obiecte sunt pentru organizarea acțiunilor într-o subrutină și au sens (adică disponibile sau vizibile) numai înăuntru această subrutină

Mecanismul subrutinelor în limbajul Turbo Pascal este implementat sub formă de proceduri și funcții. Au aproape aceeași structură, același sens, dar diferă ca scop și metodă de invocare.

Proceduri servesc la stabilirea unei secvențe de acțiuni care vizează schimbarea externului în raport cu mediul programului. Procedura se apelează prin specificarea numelui acesteia la locul programului unde se așteaptă execuția operatorilor specificati în procedură.

Funcții servesc, în primul rând, la determinarea algoritmului de calcul al unei anumite valori (tip simplu). În consecință, un apel de funcție este unul dintre operanzii validi ai unei expresii, notând în ea valoarea pe care funcția o calculează ("returns").

PROCEDURĂ ProcedureName (FormalParametersList);
ETICHETA
Enumerarea etichetelor în corpul procedurii
CONST
Descrierea constantelor locale
TIP
Descrierea tipurilor locale
VAR
Descrierea variabilelor locale
ÎNCEPE
Procedura corporală
SFÂRȘIT.

Conceptul de algoritm. Proprietăți, metode de descriere. Tipuri de algoritmi.

Un algoritm este o instrucțiune exactă și ușor de înțeles pentru executant pentru a efectua o secvență de acțiuni menite să rezolve problema.

Principalul proprietăți algoritm sunt:

1. determinism (certitudine). Presupune obținerea unui rezultat neechivoc al procesului de calcul cu datele inițiale date. Datorită acestei proprietăți, procesul de executare a algoritmului este de natură mecanică;

2. eficacitate. Indică prezența unor astfel de date inițiale pentru care procesul de calcul implementat conform unui algoritm dat trebuie să se oprească după un număr finit de pași și să returneze rezultatul dorit;

3. caracter de masă. Această proprietate presupune că algoritmul ar trebui să fie potrivit pentru rezolvarea tuturor problemelor de acest tip;

4. discretie. Înseamnă dezmembrarea procesului de calcul determinat de algoritm în etape separate, posibilitatea căreia executantul (calculatorul) o poate realiza este fără îndoială.

Cu toată varietatea de algoritmi pentru rezolvarea problemelor, trei tipuri principale de procese de calcul pot fi distinse în ei:

·liniar;

· Ramificare;

· ciclic.

Liniar se numește proces de calcul în care toate etapele rezolvării unei probleme sunt efectuate în ordinea firească a înregistrării acestor etape.

Ramificare se numeste un astfel de proces de calcul in care alegerea directiei de prelucrare a informatiei depinde de datele initiale sau intermediare (de rezultatele verificarii indeplinirii unei conditii logice).

Un ciclu este o secțiune de calcule repetate în mod repetat. Se numește un proces de calcul care conține unul sau mai multe cicluri ciclic... După numărul de execuții, ciclurile sunt împărțite în cicluri cu un anumit număr (predeterminat) de repetări și cicluri cu un număr nedefinit de repetări.

Ţintă : Pentru a familiariza elevii cu elementele de bază ale algoritmizării.

Întrebări de studiu:

1. Algoritmul și proprietățile acestuia. Metode de scriere a algoritmilor.

2. Principalele tipuri de algoritmi. Diagrame bloc ale algoritmilor tipici.

După ce a studiat acest subiect, studentul trebuie:

Știi:

· Proprietăţile algoritmului;

· Blocuri pentru constructii de circuite;

· Tipuri de bază de algoritmi;

A fi capabil să :

· Construiți algoritmi în funcție de starea problemei;

Conceptul de algoritm

Conceptul de algoritm este unul dintre conceptele fundamentale ale informaticii, care s-a conturat istoric într-o disciplină independentă „teoria algoritmilor”, apropiată de o altă disciplină „logica matematică”. Pe de altă parte, disciplina „teoria algoritmilor” poate fi considerată intermediară între două discipline: matematică și informatică, aferente secțiunii de programare.

Algoritmizarea se referă la metodele generale ale informaticii, are o mare importanță în rezolvarea problemelor complexe. Înainte de a scrie un program pentru rezolvarea unei probleme pe un computer, este necesar să revizuiți succesiunea de acțiuni care trebuie efectuate pentru a rezolva corect problema luată în considerare.

Un algoritm este o secvență de operații aritmetice, logice și alte operațiuni care trebuie efectuate pe un computer.

Pentru a obține rezultatul corect, algoritmul trebuie proiectat astfel încât atunci când este executat, toate comenzile să fie interpretate fără ambiguitate. Prin urmare, există cerințe obligatorii care trebuie luate în considerare la compilarea algoritmilor. Cerințele sunt formulate ca proprietăți.

Algoritmul trebuie să fie întotdeauna eficient, să aibă proprietatea de repetabilitate și trebuie să fie proiectat pentru un anumit interpret. În tehnologie, un astfel de interpret este un computer. Pentru a asigura posibilitatea implementării pe un computer, algoritmul trebuie descris în limbajul unui computer care este de înțeles, adică într-un limbaj de mașină. Cu toate acestea, înainte de a prezenta un algoritm într-un limbaj ușor de înțeles de calculator (limbaj de mașină), este necesar să scrieți un program folosind un limbaj de programare algoritmică.

Algoritmul poate fi reprezentat în diferite moduri, în special:

1) verbal (descriere verbală);

2) tabular;

3) sub forma unei diagrame bloc;

4) în limbaj algoritmic.

O modalitate destul de comună de a reprezenta un algoritm este de a-l scrie într-un limbaj algoritmic, care, în cazul general, este un sistem de notație și reguli pentru o scriere uniformă și precisă a algoritmilor și execuția lor. Acest mod de reprezentare a algoritmului presupune scrierea lui sub forma unui program.

Program Este o înregistrare a unui algoritm într-un limbaj de programare care duce la rezultatul final într-un număr finit de pași.

Este de preferat să prezentați algoritmul sub forma unei diagrame bloc înainte de a scrie într-un limbaj algoritmic. Pentru a construi un algoritm sub forma unei diagrame bloc, trebuie să cunoașteți scopul fiecăruia dintre blocuri. Tabelul 13. enumeră tipurile de blocuri și scopul acestora.

Tabelul 13

		Scopul blocului	Un comentariu (blocul corespunde operatorului)
		Început sau sfârșit diagrame bloc
		Intrarea sau ieșirea datelor	intrare ieșire
		Proces (în special calcul)	sarcinile
		Modificator de ciclu

5.2. Tipuri de bază de algoritmi

Algoritmizarea acționează ca un set de anumite tehnici practice, abilități specifice specifice gândirii raționale în cadrul unor mijloace lingvistice date. Algoritmizarea calculelor presupune rezolvarea unei probleme sub forma unei secvențe de acțiuni, adică a unei soluții prezentate sub forma unei organigrame. Se pot distinge algoritmi tipici. Acestea includ: algoritmi liniari, algoritmi de ramificare, algoritmi ciclici.

Algoritmi liniari

Algoritmul liniar este cel mai simplu. Presupune executarea secvențială a operațiunilor. Nu există verificări condiționate sau repetitive în acest algoritm.

Exemplu : Calculați funcția z = (x-y) / x + y2.

Întocmește o diagramă de flux pentru calcularea unei funcții folosind un algoritm liniar. Valori variabile NS, la pot exista oricare, cu excepția zero, pentru a le introduce de la tastatură.

Rezolvare: Algoritmul liniar pentru calcularea funcției este dat sub forma unei diagrame bloc în Fig. 8. La executarea unui algoritm liniar, valorile variabilelor sunt introduse de la tastatură, înlocuite într-o funcție dată, rezultatul este calculat și apoi rezultatul este afișat.

Fig. 8. Algoritm liniar

Scopul blocurilor din diagrama din Fig. 8:

· Blocul 1 din diagramă servește drept început logic.

· Blocul 3 reprezintă operația aritmetică.

· Blocul 4 emite rezultatul.

· Blocul 5 din circuit servește ca terminație logică a circuitului.

Algoritmi de ramificare

Algoritmul de ramificare presupune verificarea condițiilor de alegere a unei soluții. În consecință, algoritmul va avea două ramuri pentru fiecare condiție.

În exemplu, se ia în considerare un algoritm de ramificare, unde, în funcție de condiție, este selectată una dintre soluțiile posibile. Algoritmul este prezentat sub forma unei diagrame bloc.

Exemplu : Când condiția este îndeplinită X>0 se calculeaza functia: z= ln X+ y, altfel, și anume, când x = 0 sau X<0 , funcția se calculează: z= X+ y2 .

Întocmește o organigramă pentru calcularea unei funcții folosind algoritmul de ramificare. Valori variabile NS, la pot fi oricare, introduceți-le de la tastatură.

Soluţie : Figura 9 prezintă un algoritm de ramificare, unde, în funcție de condiție, se execută una dintre ramuri. Un nou bloc 3 a apărut în diagramă, care verifică starea problemei. Restul blocurilor sunt familiare din algoritmul liniar.

https://pandia.ru/text/78/136/images/image008_57.gif "width =" 300 "height =" 360 src = ">

Fig. 9. Algoritmul de ramificare

Exemplu : Găsiți valoarea maximă a trei numere întregi diferite introduse de la tastatură. Întocmește o diagramă pentru rezolvarea problemei.

Soluţie : Acest algoritm presupune verificarea condiției. Pentru aceasta, oricare dintre cele trei variabile este selectată și comparată cu celelalte două. Dacă este mai mare, atunci căutarea numărului maxim s-a încheiat. Dacă condiția nu este îndeplinită, atunci cele două variabile rămase sunt comparate. Una dintre ele va fi maximă. Diagrama bloc pentru această sarcină este prezentată în Fig. 10.

https://pandia.ru/text/78/136/images/image010_48.gif "width =" 492 "height =" 456 src = ">

Orez. 10. Schema bloc a căutării maximului

Algoritmi ciclici

Algoritmul ciclic prevede repetarea unei operații sau a mai multor operații, în funcție de starea problemei.

Algoritmii ciclici sunt de două tipuri:

1) cu un număr dat de cicluri sau cu un numărător de cicluri;

2) numărul de cicluri este necunoscut.

Exemplu : Într-o buclă, calculați valoarea funcției z = x * y cu condiţia ca una dintre variabile X modificări în fiecare ciclu cu unul, iar cealaltă variabilă la nu se modifică și poate fi orice număr întreg. Ca rezultat al executării buclei la valoarea inițială a variabilei x = 1 puteți obține tabla înmulțirii. Numărul de cicluri poate fi oricare. Întocmește o diagramă de flux pentru rezolvarea problemei.

Soluţie : În exemplu, numărul de cicluri este setat. În consecință, este selectat primul tip de algoritm de buclă. Algoritmul pentru această problemă este prezentat în Fig. unsprezece.

În al doilea bloc este introdus numărul de cicluri n și orice numere întregi NS, y .

Un nou bloc 3 a apărut în diagrama bloc, în care variabila i numără numărul de cicluri, crescând cu unul după fiecare ciclu până când contorul este egal cu i = n ... La i = n se va executa ultimul ciclu.

Al treilea bloc indică intervalul de modificare a contorului de cicluri (de la i = 1 inainte de i = n).

În al patrulea bloc, valorile variabilelor sunt modificate: z, X.

Al cincilea bloc afișează rezultatul. Al patrulea și al cincilea bloc se repetă în fiecare ciclu.

Fig. 11. Algoritm ciclic cu contor de cicluri

Acest tip de algoritmi de bucle este preferat atunci când este dat de numărul de bucle.

Dacă numărul de cicluri este necunoscut, atunci diagramele bloc ale algoritmilor ciclici pot fi prezentate sub forma figurilor 12, 13.

Exemplu : calculati y = y-X in timp ce y> X, dacă y=30 , X=4. Numărați numărul de cicluri executate, valoarea finală a unei variabile la ... Într-o buclă, scoateți valoarea unei variabile la, numărul de cicluri efectuate. Întocmește o diagramă pentru rezolvarea problemei.

Soluţie : În exemplu, numărul de cicluri este necunoscut. În consecință, este selectat al doilea tip de algoritm de buclă. Algoritmul pentru această problemă este prezentat în Fig. 12.

Starea este verificată la intrarea în buclă. Două blocuri sunt executate în corpul buclei:

1) y = y-x;i= i+1 ;

2) ieșirea valorilor variabilelor i, y.

Ciclul este executat atâta timp cât condiția este îndeplinită y> x... Cu condiția ca aceste variabile să fie egale y = x sau y ciclul se termină.

Algoritmul prezentat în Figura 12 este numit algoritmul 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, în caz contrar la blocul 6.

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

Al cincilea bloc afișează rezultatul:

Valoare variabilă la,

i.

Exemplu : Întocmește un exemplu de organigramă (Figura 12), verificând starea de ieșire a buclei. În acest exemplu, condiția sarcinii nu se schimbă, iar rezultatul este același, dar diagrama de flux va fi diferită.

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

Algoritmul, dacă condiția este transferată la sfârșitul ciclului, este apelat algoritm de 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 i= i+1 .

Al patrulea bloc afișează rezultatul:

Valoare variabilă la,

Numărul de cicluri finalizate i.

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

Fig. 13. Algoritm de buclă cu postcondiție

Întrebări de control

1. Conceptul de algoritm.

2. Tipuri de algoritmi.

3. Structuri algoritmice de bază.

4. Principalele blocuri ale algoritmului grafic.

5. Structura algoritmică liniară. Exemplu.

6. Ramificare. Exemplu.

7. Structuri algoritmice ciclice. Exemplu.