Rezumat: Un algoritm este un concept de bază pentru cei care doresc să înceapă programarea în orice limbaj de programare. Orice problemă poate fi formalizată algoritmic. Pentru a înțelege de unde să începeți, să examinăm principalele tipuri de algoritmi. Scopul acestei prelegeri este familiarizarea studenților cu conceptul de algoritm; arată că un astfel de lucru abstract, ca algoritm, ne înconjoară în viața de zi cu zi.
Există mai multe definiții ale conceptului algoritmului. Iată cele două cele mai comune.
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.
În general, prima definiție nu transmite sensul complet al conceptului de algoritm. Cuvântul "secvență" folosit aici îngustează acest concept, deoarece Acțiunile nu trebuie neapărat să urmeze unii pe alții - pot fi repetate sau pot conține o condiție.
- Discretă (din discretus latină -. Împărțit, intermitent) - acest algoritm partiționarea pe o serie de acțiuni individuale finalizate (etape).
- Determinism (din latina determinare a -. Certitudinea, precizie) - orice acțiune a algoritmului ar trebui să fie definite în mod strict și clar în fiecare caz. De exemplu, direcțiile de algoritm pentru a reciproc, dacă este cazul, pentru a opri autobuze de diferite rute, algoritmul trebuie să specifice un anumit număr de traseu 5. În plus, trebuie să specificați numărul exact de opriri care trebuie să conducă, să zicem, trei.
- Finiteness - fiecare acțiune în izolare și algoritmul în ansamblu ar trebui să poată fi finalizate.
- Masa - același algoritm poate fi folosit cu diferite date inițiale.
- Eficacitate - algoritmul ar trebui să conducă la o soluție fiabilă.
Scopul principal al algoritmizării este compilarea algoritmilor pentru un calculator cu o soluție suplimentară a problemei pe un computer.
- Orice dispozitiv achiziționat în magazin este furnizat cu o instrucțiune pentru utilizarea acestuia. Această instrucțiune este un algoritm pentru funcționarea corectă a dispozitivului.
- Fiecare șofer trebuie să cunoască regulile drumului. Regulile drumului reglementează în mod neechivoc comportamentul fiecărui participant în mișcare. Cunoscând aceste reguli, șoferul trebuie să acționeze conform unui anumit algoritm.
- Producția masivă a autovehiculelor a devenit posibilă numai atunci când ordinea de asamblare a mașinii pe linia de asamblare a fost gândită. O anumită ordine de asamblare a mașinilor este un set de acțiuni care conduc la o mașină.
Există mai multe moduri de a scrie algoritmi. În practică, cele mai comune forme de reprezentare a algoritmilor sunt:
- verbal (înregistrare în limbaj natural);
- Pseudocod (semiformalized descrie algoritmi de limbaj de programare convențional, incluzând atât elemente de limbaj de programare și fraza limbaj natural, notațiile matematice convenționale și colab.);
- Grafic (imagini din simboluri grafice - diagramă bloc);
- Program (texte în limbaje de programare - cod de program).
Să analizăm în detaliu fiecare variantă a algoritmilor de înregistrare prin exemplul următoarei probleme. Este necesar să se găsească un coeficient de două numere.
Modul verbal al algoritmilor de înregistrare este o descriere a etapelor succesive ale procesării datelor. Algoritmul este dat într-o declarație arbitrară în limba naturală. Răspunsul este dat persoanei care efectuează comenzile conform înregistrării verbale.
Exemplu de intrare verbală:
- setați două numere care sunt divizibile și divizibile;
- verificați dacă divizorul este zero;
- dacă divizorul nu este zero, atunci găsiți coeficientul, scrieți-l înapoi;
- dacă divizorul este zero, atunci ca răspuns la scrierea "nu există nicio soluție".
Metoda verbală nu este folosită pe scară largă, deoarece astfel de descrieri nu sunt strict formalizabile; suferă de verbozitatea înregistrărilor; permite ambiguitatea în interpretarea prescripțiilor individuale.
Iată structurile de control pseudocode de bază din Tabel. 1.1.
Tabelul 1.1. Structuri de control pseudocode de bază
În acest exemplu, se folosesc trei variabile: dividend, divizor și coeficient. Divizibilul și divizorul sunt specificate de executor prin numere arbitrare. Un coeficient este considerat numai dacă divizorul nu este zero.
Implementarea grafică a algoritmului este o diagramă grafică. Diagrama bloc constă din blocuri de o anumită formă, conectate prin săgeți. Răspunsul este dat persoanei care execută comenzile în conformitate cu diagrama. Pentru mai multe detalii privind diagramele, consultați Lectura 2.
O implementare software a unui algoritm este un program de calculator scris în unele limbi de programare algoritmică, de exemplu: C ++, Pascal, Basic, etc. Programul constă din comenzi dintr-un limbaj de programare specific. Rețineți că aceeași diagramă bloc poate fi implementată în diferite limbi de programare. Răspunsul este un computer, nu o persoană. Pentru mai multe informații despre programarea în limba de programare C ++, consultați Lectura 3.
Există trei tipuri principale de algoritmi:
- algoritmul liniar,
- algoritmul de ramificare,
- algoritmul ciclic.
Un algoritm liniar este un algoritm în care acțiunile sunt efectuate o dată și strict secvențial.
Cel mai simplu exemplu de implementare a unui algoritm liniar este modul de acasă la universitate.
Modul verbal de scriere a acestui algoritm:
- să părăsească universitatea pentru oprire;
- așteptați autobuzul potrivit;
- treci pe autobuzul potrivit;
- plătiți pentru călătorie;
- ieșiți la oprirea necesară;
- ajungeți în casă.
Evident, acest exemplu se referă la un algoritm liniar, deoarece toate acțiunile se urmează unul pe altul, fără condiții și repetiții.
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ă.
Exemplul de mai sus al unui pseudocod pentru găsirea unui număr special de două se aplică și unui algoritm de ramificare.
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.
Pentru mai multe detalii despre algoritmi liniari, ramificați și ciclici, consultați Lectura 2.
Rezultatele rezumate
Orice sarcină poate fi împărțită în acțiuni elementare. Pentru orice problemă matematică sau situație din viață, puteți crea un algoritm pentru rezolvare. Algoritmul poate fi descris verbal, pseudocod, grafic sau programabil. Sarcina este întotdeauna rezolvată folosind tipurile de bază ale algoritmului - liniar, ramificat sau ciclic.
- Ce este un algoritm?
- Care este problema algoritmizării?
- Care sunt proprietățile algoritmului?
- Ce tipuri de algoritmi există?
exerciții
- Faceți algoritmi pentru o campanie din magazin pentru mere. Utilizați algoritmi liniari și ramificați. Implementați-le verbal.
- Alcătuiți un algoritm pentru găsirea rădăcinilor unei ecuații patratice prin intermediul discriminatorului. Utilizați un algoritm de ramificare. Implementați-l cu un pseudocod.