Structuri de bază ale algoritmilor Să impunem câteva restricții asupra
structura diagramei flux.
Vom construi un algoritm folosind numai
trei fragmente dintr-un anumit
configuratii.
Să le numim structuri de bază
algoritmi.

Urmează prima structură de bază
constă dintr-un lanţ de blocuri fără
ramificații.

Ramificare

Da
Nu
stare

Un caz special de ramificare
stare

Ramificarea este folosită în cazurile în care
când trebuie să alegi unul dintre
două moduri de a rezolva problema.

Ciclu

Ciclul este utilizat în cazurile în care
pentru a rezolva problema este necesar
repeta aceleasi lucruri iar si iar
actiuni.

Bucla cu postcondiție

Buclă cu precondiție

Ciclu parametric

Ciclu parametric controlat
parametru.
Un parametru de buclă este o variabilă
care se schimbă monoton în ciclu,
iar criteriul de ieșire depinde de el
ciclu.

i:=in
Corp
ciclu
i:= i + di
Nu
Da
eu > ik

i:=in
i>ik
Corp
ciclu
i:=i+di

Proiectarea algoritmilor complexi

Metoda de proiectare a algoritmului de sus în jos

Metoda constă din următorii pași:
sarcina inițială este împărțită în subsarcini,
conectat printr-un algoritm;
acest algoritm este în curs de depanare;
fiecare subsarcină este considerată ca
sarcină;
procesul continuă până când
sarcina inițială nu va fi complet
rezolvat.

Exemplu

Având în vedere ecuația ax2 + bx + c = 0 și funcția
f(x).
Dacă o ecuație are două reale
rădăcinile x1 și x2, construiți un tabel de valori
funcţie pe segmentul format din n
puncte.

Algoritm de nivel superior
Introducerea a,b,c
Soluţie
ecuații
Nu
x1, x2
găsit
Da
Introduceți n
Constructii
mesele
Nicio soluție
STOP

Algoritm care implementează subproblema soluție
ecuație pătratică
d:=b2 – 4ac
Nu
D>0
Da
X1=(- b + √ d)/2/a
X2= (- b - √ d)/2/a

Algoritm pentru construirea unui tabel de valori
funcții
h=(x2-x1)/(n-1)
x = x1
i=1
Ieșire x, f(x)
x=x+h
i = i +1
Da
Nu
i>n

Astfel, soluția problemei
problema constă dintr-un algoritm superior
nivel și două subsarcini.
Algoritm care leagă subsarcini
Soluţie
ecuații
Constructii
tabele f(x)

Lățimea blocului px

Copiați acest cod și inserați-l pe site-ul dvs. web

Subtitrările diapozitivelor:

Algoritmi și structuri de date Literatură:

• D. Knut. Arta programarii computerelor. T. 1-3, M.: Mir, 1978, 1995 etc.
• N. Wirth. Algoritmi și structuri de date. M.: Mir, 1989.

Conceptul tipului de date

• Informaţii care trebuie procesat pe computer este abstractizare, afișând un fragment din lumea reală. Și anume, fragmentul care este subiectul problemei care se rezolvă. Pentru a o rezolva, mai întâi construim informativ, iar în cazul general matematic model domeniul studiat și se selectează unul existent sau se construiește unul nou algoritm rezolvarea problemei.

• Informații întotdeauna se materializează, este reprezentat sub formă mesaje. În general, un mesaj reprezintă unele înregistrat semnal fizic . Semnal- Asta modificarea în timp sau în spațiu a unui obiect, în special, un parametru al unei cantități fizice, de exemplu, inducția câmpului magnetic (când se stochează informații, mai precis mesaje pe medii magnetice) sau nivelul de tensiune din circuitul electric (în cipurile de procesor sau RAM).

• Discret un mesaj este o secvență semne(valori semnal) de la unii final alfabet(un set finit de valori ale parametrilor de semnal), în special, pentru un computer, aceasta este o secvență de caractere a alfabetului binar, adică o secvență de biți.

• Date computerizate acestea sunt mesaje discrete care sunt prezentate într-o formă utilizabilă de un computer, calculatorul de înțeles. Pentru un procesor de computer, orice date este nestructurat secvență de biți (uneori se folosește termenul curgere biți).

• Interpretarea specifică a acestei secvențe depinde de program, de forme de prezentare si structuri de date, care sunt selectate programator. Această alegere depinde în cele din urmă de problema rezolvată și de comoditatea de a efectua acțiuni asupra datelor.

• Sensuri imediate Acest neschimbată obiecte program care se reprezintă: numere (25, 1.34E-20), simboluri ('A', '!'), şiruri de caractere ('Introduceţi elemente de matrice');
• constante sunt nume atribuite anumitor valori (const pi=3.1415926).
• Variabile acestea sunt obiecte care pot lua o valoare, o pot salva fără modificare și o pot modifica atunci când sunt efectuate anumite acțiuni (var k:integer, x:real, a:array).
• Valori de expresie și funcție. Expresiile și funcțiile sunt reguli pentru calcularea valorilor scrise într-un anumit fel: k*x+ sqrt(x).

• Datele din programe includ:

• Tipul de date este cea mai importantă caracteristică, care definește:

• set de valori valide;
• multe operații care pot fi efectuate asupra unei valori;
• structura valorilor (scalar, vectorial etc.);
• o metodă de reprezentare automată a sensului.

• Pentru a afișa caracteristicile reprezentării pe computer a datelor de diferite naturi în informatică, disciplinele de calcul folosesc cele mai importante conceptul de tip de date.

• Tipul unei constante, variabile sau expresii poate fi determinat de aspect(din imagine) sau din descriere fără a efectua niciun calcul.
• Orice operație sau funcție necesită argumente și returnează un rezultat de un tip foarte specific. Tipurile de argumente și rezultatele operațiunilor sunt determinate după reguli bine definite ale limbajului.

• Principiile de bază ale conceptului de tip de date
• în limbaje de programare:

• Varietăți de tipuri și structuri de date

• Informatica foloseste un numar mare de diferite tipuri, diverse structuri de date, care sunt folosite pentru modelare obiectele întâlnite în problemele luate în considerare.

• Dacă structura unui anumit algoritm nu se schimbă în timpul execuției, atunci se ia în considerare o astfel de structură static , Structuri statice de date exista neschimbat pentru întreg timpul de execuție al algoritmului.

• Sens scalar(simplu, atomic) tipul prezentat netezi unul componentă (exemplu: timp, temperatură).

• Structuri dinamice sunt create, modificate și distruse după cum este necesar în orice moment în timpul executării algoritmului.

• Sens structurat(compozit) tipul prezentat Mai mult Cum unul componentă (exemplu: vector, matrice, tabel etc.).

• Există tipuri predefinite (predefinite) - standard și definite de program. Pentru standard tipurile din descrierea unui limbaj de programare definesc toate caracteristicile acestuia - un set de valori, un set de operații, structura și reprezentarea mașinii a unei valori. Pentru nou definit tipuri, limbajul oferă un mecanism pentru specificarea unui set de valori într-un program și a structurii valorii. De obicei, un nou tip este construit pe baza celor standard existente. Prin urmare, multe operații și reprezentarea mașinii a unor astfel de tipuri sunt fixate în descrierea limbii.

• tipuri scalare (simple, atomice):
• întreg;
• real;
• logic (boolean);
• simbolic;
• tipuri structurate (compozite):
• matrice;
• înregistrare;
• fisier(secventa);
• multitudine;
• tipul obiectului (clasei);
• toate combinațiile posibile de tipuri scalare și structurate;
• tip de referință.

• Tipuri statice (structuri de date)

• Cele mai frecvent utilizate tipuri scalare predefinite sunt: ​​întreg ( întreg), real ( real), simbolic ( char), boolean ( boolean).

• Valori întregi exacte. Exemple: 73, -98, 5, 19674.
• Reprezentarea mașinii: format punct fix. Intervalul de valori este determinat de lungimea câmpului. Operații: +, -, *, div, mod,=,<, и т.д.

• Tip întreg

• Aproximații non-întregi. Exemple: 0,195, -91,84, 5,0
• Reprezentarea mașinii: format virgulă mobilă. Intervalul și precizia valorilor sunt determinate de lungimea câmpului. Operații: +, -, *, /, =,<, и т.д.

• Tip real

• Caractere cu un singur text. Exemple: „a”, „!”, „5”.
• Reprezentarea mașinii: format ASCII. Setul de valori este determinat de tabelul de coduri și de capacitățile tastaturii. Operații: +, =,<, и т.д.

• Tip char

• Două valori booleene false și adevărate. Mai mult, fals
• Reprezentarea mașinii ─ valoarea zero și un bit: fals este codificat 0, adevărat ─ 1. Operații: , , , =,< и т.д.

• Tip boolean

• Mecanisme de bază pentru construirea de noi tipuri discrete scalare: enumerare, restricție. În definiție transferabil tipuri, o listă cu toate valorile posibile este fixă, multe operațiuni sunt definite în prealabil în limbă. În definiție limitat tipuri ca un set de valori valide este fix subset un set de valori de un tip discret, care în acest caz se numește tip de bază în raport cu cel definit.

• Există tipuri scalare discrete și continue. Sensuri multiple discret tip finit sau numărabil. Sensuri multiple continuu tip mai mult decât numărabil. Tipurile standard discrete includ întreg, caracter și logic. Tipurile standard continue includ reale.

• Tipurile structurate (compozite) se caracterizează prin: numărul și tipul posibil de componente valorice, precum și modul în care este accesată o componentă individuală a valorii.

• Structurile similare vectorilor și matricelor din informatică sunt de obicei numite matrice. Toate elementele matricei trebuie să fie acelasi lucru tip.

• Tip matrice sau obișnuit

• Pentru a accesa (a face referire la) un element de matrice individual, se folosesc un index sau mai mulți indecși (w; w; A). Indicii pot fi expresii ale căror valori pot varia în mod arbitrar în limitele predefinite. Prin urmare, ei spun că elementele de matrice au acces direct.

• Sunt numite structuri similare cu rândurile de tabel înregistrări. Componentele înregistrărilor sunt de obicei numite câmpuri. Pot fi diferite câmpuri (coloane de tabel). diferit tipuri. Pentru a accesa câmpurile individuale ale unei înregistrări, acestea sunt fixe și neschimbabile nume. De exemplu: Ziua Victoriei. Luna:= mai. Câmpurile pot fi selectate pentru procesare în orice ordine, astfel încât se spune că este accesul la componentele de înregistrare direct.

• Tip de înregistrare sau combinat

• Ziua Victoriei:

• Fișier (secvență)

• Structura principală de date care este utilizată pentru stocarea informațiilor pe dispozitive externe (discuri magnetice, benzi etc.) este fișiere sau secvente. Fișierul este considerat a fi întotdeauna pe dispozitivul extern. În acest caz, numărul de componente ale fișierului este necunoscut; toate componentele trebuie să fie de același tip. Acces la componente ─ consistent.

• Zborul lui Gagarin:

• Multe

• În multe probleme de matematică și de informare este nevoie de a utiliza direct sau indirect obiectul matematic principal seturi. Tipul de date corespunzător unei mulțimi este prin definiție structurat, deoarece în cazul general o mulțime poate consta din mai mult de un element și, în același timp, operațiunile trebuie efectuate cu toate elementele mulțimii ca un singur întreg. Numărul de elemente dintr-un set nu este determinat în prealabil, iar în timp se poate modifica. Toate elementele setului trebuie să fie de același tip. Acces la elementele individuale ale ansamblului Nu. Puteți afla doar dacă un element aparține unui set sau nu, puteți include un element în set sau îl excludeți din set. Sunt prevăzute și operații standard pe mulțimi: unire, intersecție, scădere etc.

• X1 X5 X4

• Structuri dinamice de date

• Date cu o structură dinamică în timp schimbari se structura, și nu doar numărul de elemente, cum ar fi fișierele sau secvențele. Structurile de date dinamice de bază sunt:

• obiect;
• listă liniară;
• copac;
• grafic.

• Într-o listă liniară, fiecare element este legat de cel dinainte. Pentru o listă liniară, știm care element este la începutul listei, care este la sfârșit și, de asemenea, care element este înaintea celui curent. Într-o listă liniară, puteți trece de la elementul curent la următorul doar folosind conexiuni specificate între elementele vecine.

• Lista liniară

• În general, se obține un lanț de elemente în care poți căuta, în care poți insera elemente sau le poți exclude.

• Multe alte tipuri de structuri dinamice sunt organizate pe baza unei liste liniare. Acesta este în special: inele, cozile, punțileŞi stive.

• Structura inelului

• Diferența dintre un inel și o listă liniară este că un inel are o legătură între ultimul element al listei și primul său element.

• Pentru o listă liniară și un inel, este posibil accesul la orice element al structurii. Pentru a face acest lucru, trebuie să treceți succesiv de la un element la altul. În multe situații din lumea reală, un astfel de acces absent. Puteți interacționa doar cu primul și ultimul element, sau numai cu unul dintre ele. Cozile, punțile și stivele sunt folosite pentru a modela astfel de obiecte.

• Structura cozii

• Sfârșitul cozii este disponibil pentru includere, iar începutul este disponibil pentru excludere (selectare). Elementul care a ajuns mai devreme în coadă și care este întreținut primul. Ei spun că o coadă este o structură cu disciplină de serviciu FIFO (Fîn primul rând eu n, Fîn primul rând O ut) ─ „primul care vine, primul care pleacă.”

• Structura punții

• Puntea are ambele capete disponibile, atât pentru includere, cât și pentru eșantionare. Astfel, putem spune că Dec ─ este coadă cu două sensuri.

• Structura stivei

• O stivă are doar un capăt al structurii disponibil pentru interacțiune: partea de sus a stivei. Atât includerea unui nou element pe stivă, cât și selecția ultimului element inclus anterior trec prin partea de sus a stivei. Astfel, articolul care a sosit ultimul este procesat primul. Ei spun că o stivă este o structură cu o disciplină de întreținere LIFO (L ast eu n, Fîn primul rând O ut) ─ „ultimul care a venit, primul care a plecat.”

• VĂ MULȚUMIM PENTRU ATENȚIE!

Algoritm și structuri algoritmice

Mosina A.Yu.

Algoritm este o secvență strict definită de acțiuni atunci când se rezolvă o problemă.

Algoritmul conține mai mulți pași.

Pasul algoritmului este fiecare acțiune individuală a algoritmului.

„Un algoritm este o procedură de acțiune.”

Executor testamentar este un obiect care efectuează un anumit set de acțiuni.

Artistul poate fi o persoană, un robot, un animal sau un computer.

Sistem de comandă a executorului (SCHI) este un set de comenzi pe care executantul le poate executa.

Mediul artistului – mediul în care operează interpretul.

• Dezvolta algoritmi: umani
• Algoritmii sunt executați de oameni și dispozitive - calculatoare, roboți, mașini-unelte, sateliți, aparate electrocasnice complexe, jucării pentru copii.
• Executantul rezolvă problema conform unui algoritm dat, urmând cu strictețe instrucțiunile (programul) fără să aprofundeze sau să discute de ce face acest lucru.

Exercita: Numiți executanții următoarelor tipuri de lucrări:

Curățarea gunoiului din curte

Predarea copiilor la scoala

Conducerea

Răspunsul este pe tablă

Gătitul

Imprimarea unui document pe o imprimantă

Limb– fiecare acțiune individuală și algoritmul în ansamblu trebuie să poată fi finalizate

Eficienţă– obţinerea rezultatelor într-un număr finit de paşi

Discretenie(discontinuitate, separație) – împărțirea algoritmului în pași

Determinism(certitudine, acuratețe) – fiecare acțiune trebuie definită strict și fără ambiguitate

Caracter de masă– utilizarea unui algoritm pentru a rezolva probleme similare

Proprietățile ALGORITMULUI

Clasificarea algoritmilor după forma de prezentare :

Verbal

Tabular

Grafic (diagrame bloc)

Software

Diagrama bloc – grafic performanţă algoritm sub forma unei secvențe de blocuri funcționale interconectate ( elemente grafice standard ), fiecare dintre acestea corespunde efectuării uneia sau mai multor acțiuni.

Convenții de bază în diagramele bloc

Simbol

Scopul blocului

Începutul sau sfârșitul algoritmului

Intrarea sau ieșirea datelor.

În interiorul blocului, datele sunt listate separate prin virgule.

Proces.

Matematica este scrisă în interiorul blocului. formule si operatii de prelucrare a datelor.

Verificarea stării.

Condițiile logice sunt scrise în interiorul blocului. Are două ieșiri Da (+) și Nu (-).

Direcţie.

Clasificarea algoritmilor dupa structura:

Linear (urmează)

Ramificat (ramură, alegere, alternativă)

Buclă (repetare)

Auxiliar

Combinate

Algoritm liniar

Algoritm liniar este un algoritm ai carui pasi sunt executati secvential unul dupa altul.

(Exemplu: algoritmul de colectare a portofoliului).

Structura de bază a algoritmului liniar:

Echipa seria 1

Echipa Seria 2

Echipa N seria

Sarcină

Calculați perimetrul unui triunghi arbitrar pe baza celor trei laturi ale sale.

Soluţie:

Etapa 1: Enunțarea problemei.

Datele inițiale: A, B, C – laturile unui triunghi arbitrar

Imprima: P – perimetrul triunghiului.

Etapa 2: Model matematic.

P=A+B+C

Etapa 3: Elaborarea unui algoritm

Început

Intră

Concluzie

Sfârşit

№ 1 ŞI folosind diagrama algoritmică , calculați valoarea funcției Y la X=2,

început

intrare: X

Z=8*X

• SOLUŢIE:

• X=2
• Z = 8 * 2 = 16
• Z = √16 = 4
• Z = 4 – 1 = 3
• Y = 3 * 2 = 6
• Y = 6 / 3 = 2

Z = Z - 1

Y=3*X

Y=Y/Z

ieșire: Y

• Algoritmii pot descrie procesele de transformare ale unei game largi de obiecte. Cuvântul „algoritm” în sine provine de la „algorithmi” - ortografia latină a numelui remarcabilului matematician al secolului al IX-lea al-Khwarizmi, care a formulat regulile pentru efectuarea operațiilor aritmetice.
• Algoritm- un set de comenzi care descriu ordinea acțiunilor executantului pentru a obține rezultatul rezolvării unei probleme într-un număr finit de acțiuni.

Proprietățile algoritmilor:

1. Discretență- algoritmul trebuie sa reprezinte procesul de rezolvare a unei probleme ca o executie secventiala a unor pasi simpli. În același timp fiecare pas al algoritmului necesită un timp finit pentru finalizare, adică transformarea datelor sursă în rezultate se realizează discret în timp.

2. Determinism (certitudine). În fiecare moment, următorul pas de lucru este determinat în mod unic de starea sistemului. Astfel, algoritmul produce același rezultat (răspuns) pentru aceleași date inițiale.

3. Claritate- algoritmul ar trebui să includă doar acele comenzi care sunt disponibile pentru executant și sunt incluse în sistemul său de comandă.

4. Completitudine (extremitate)- cu date inițiale corect specificate, algoritmul trebuie să își finalizeze munca și să producă un rezultat într-un număr finit de pași.

5. Caracter de masă (universalitate). Algoritmul trebuie să fie aplicabil diferitelor seturi de date de intrare.

6. Eficacitate- finalizarea algoritmului cu anumite rezultate.

Modalități de a scrie algoritmi:

1. Metoda de înregistrare verbală

Modul verbal de scriere a algoritmilor este o descriere a etapelor succesive de prelucrare a datelor. Algoritmul este specificat într-o prezentare arbitrară în limbaj natural .

Exemplu

Ca exemplu de mod verbal de a scrie un algoritm, luați în considerare un algoritm pentru găsirea ariei unui dreptunghi

unde S este aria dreptunghiului; a, b – lungimile laturilor sale.

Evident, a, b trebuie specificate în prealabil, altfel problema nu poate fi rezolvată.

Modalități de a scrie algoritmi

Modul verbal de scriere a algoritmului arată astfel:

• Începutul algoritmului.
• Setați valoarea numerică a laturii a.
• Setați valoarea numerică a laturii b.
• Calculați aria S a dreptunghiului folosind formula S=a*b.
• Emite rezultatul calculelor.
• Sfârșitul algoritmului.

Modalități de a scrie algoritmi

2. Metoda grafică

Când este prezentat grafic, algoritmul este reprezentat ca o secvență de blocuri funcționale interconectate, fiecare dintre acestea corespunzând execuției uneia sau mai multor acțiuni.

Această reprezentare grafică se numește diagramă de flux sau diagramă de flux. În organigramă, fiecărui tip de acțiune (introducerea datelor inițiale, calcularea valorilor expresiilor, verificarea condițiilor, controlul repetarea acțiunilor, finalizarea procesării etc.) corespunde unei figuri geometrice reprezentate ca simbol bloc. Simbolurile bloc sunt conectate prin linii de tranziție care determină ordinea în care sunt efectuate acțiunile. Următoarele sunt cele mai frecvent utilizate simboluri.

Modalități de a scrie algoritmi

Element de diagramă de flux

Nume

Bloc de calcul (bloc de calcul)

Acțiuni de calcul sau succesiune de acțiuni

Bloc logic (bloc de condiție)

Bloc de intrare/ieșire a datelor

Alegerea direcției de execuție a algoritmului în funcție de o anumită condiție

Denumirea generală a datelor de intrare (ieșire) (indiferent de mediul fizic)

Inceput (sfarsit)

Începutul sau sfârșitul unui algoritm, intrare sau ieșire într-o subrutină

Modalități de a scrie algoritmi

Element de diagramă de flux

Nume

Procesul utilizatorului (subrutină)

Calcul folosind un program standard sau subrutină

Bloc de modificare

Funcția efectuează acțiuni care modifică punctele (de exemplu, antetul buclei) ale algoritmului

Conector

Indicarea conexiunii prin linii întrerupte între fluxurile de informații

Modalități de a scrie algoritmi

Exemplu

Algoritm pentru calcularea ariei unui dreptunghi

Modalități de a scrie algoritmi

3. Pseudocoduri

descrieri semi-formalizate ale algoritmilor într-un limbaj algoritmic condiționat, incluzând atât elemente ale unui limbaj de programare, cât și fraze în limbaj natural, notații matematice general acceptate etc.

Nu există o definiție unică sau formală a pseudocodului, așa că sunt posibile diverse pseudocoduri, care diferă în setul de cuvinte funcționale și construcții de bază (de bază).

Modalități de a scrie algoritmi

Exemplu

• Început. Treci la punctul 2.
• Introducerea numerelor a și b. Treci la punctul 3.
• Calculați S=a*b. Treci la punctul 4.
• Concluzie S. Treceți la pasul 5.
• Sfârşit.

Modalități de a scrie algoritmi

4. Metoda software

Înregistrarea algoritmului în limbajul de programare selectat.

Exemplu

Writeln('');

Writeln(‘S=‘ , S);

Tipuri de algoritmi

1. Algoritm liniar

Acesta este un algoritm în care există doar o structură următoare.

Urmând- Aceasta este aranjarea acțiunilor una după alta.

Tipuri de algoritmi

2. Algoritm de ramificare (dacă... atunci... altfel...)

Acesta este un algoritm care are o structură de ramificare.

Ramificare- aceasta este alegerea actiunii in functie de indeplinirea unei conditii.

Tipuri de algoritmi

3. Algoritm ciclic

Acesta este un algoritm care are o structură în buclă.

Ciclu- Aceasta este repetarea repetată a oricărei acțiuni.

Tipuri de algoritmi

4. Algoritm combinat

Un algoritm care conține mai multe structuri simultan.