Algoritmul - format din pasi (etape) este destinat rezolvarii unei categorii de probleme ; are caracteristici : generalitate, finitudine , claritate .
Se reprezinta algoritmii prin scheme logice , limbaj de programare , pseudocod, formalisme matematice .
Pseudocodul - este o descriere a algoritmului in limbaj natural cu cuvinte cheie precum : start , stop , daca , altfel , atunci , scrie, citeste , atribuie , pentru, cat timp , repeta , executa .
Transcrierea algoritmului daca sunt utilizate corect aceste cuvinte in cod sursa este foarte simplă . Există din perioada când se puneau bazele informaticii ca domeniu o teoremă cunoscută ca teoremă Bohm-Jacopini ce demonstrează că un algoritm se poate scrie doar cu structuri secvențiale , structura alternativa cât timp și structuri decizionale.
Structurile sunt liniare,decizionale,repetitive.
Structuri liniare(secventiale)
int i,j;
int main()
{
cout<< "i=";
cin>>i;
cout<< "j=";
cin>>j;
if(i=j)cout<<i;
else cout<<j; return 0;}
Programul citeste i si j si il afiseaza pe cel mai mare dintre i si j . Main e funcția principala , practic instrucțiunile sale se execută in ordinea în care apar .
Aceste programe sunt realizate pentru stilul de programare in care avem un singur fir de execuție și acela în logica execuției strict secvențiale după ordinea in care avem instructiunile în funcția Main .
În programele de rețea se lucrează de regulă cu fire multiple de executie - multithread.
Teste la clasa
S-a inlocuit instructiunea repetitiva cu test initial cu cea cu test final.
TEST VERIFICARE
EXEMPLU INT A[10];
IN C++ , editat si rulat in CODEBLOCKS cu compilator MINGW C++ :
#include <iostream>
using namespace std;
int n,i,j,a[10],x;
int main()
{
cout<<"sortarea e crescatoare-dati n ! " << endl;
cin>>n;
for(i=0;i<n;i++){ cout<<"a["<<i<<"]=";cin>>a[i];
for(j=0;j<i;j++) if(a[i]<a[j]){x=a[i];
a[i]=a[j];
a[j]=x;
}
}
cout<<endl<<"vectorul sortat este"<<endl;
for (i=0;i<n;i++) cout<<a[i]<<endl;
return 0;
}
Structuri liniare(secventiale)
- scrie cin>>
- citeste cout<<
- atribuie =
- instructiunea compusa { }
- Citirea se face de la tastatură când introducem valori ale variabilelor , din fișiere , din fluxuri de date ( eventual prin comunicație în rețea așa cum se întâmplă dacă se transmit datele unui formular web către un script php ). Scriptul citește datele formularului.
- Scrierea este realizata prin afișaj pe display , prin scriere în fișiere , transmiterea de date prin fluxuri de date , trimiterea unor date în diverse protocoale în rețea .
- Atribuirea are ca efect atribuirea valorii sau a unei evaluări a membrului din dreapta către cel din stânga .
Structuri decizionale (numite si structuri alternative sau selective)
daca conditie atunci instr; selectia simpla
daca conditie atunci instr1 altfel instr 2; selectia duala
În programe apare adesea selecția multiplă , dar aceasta este de fapt alcătuită din mai multe structuri selective simple si eventual duale. În C++ se operează cu instr switch(selector) { case val1 : instr 1 ; case val2:instr2; ...else instr ;}
În programe apare adesea selecția multiplă , dar aceasta este de fapt alcătuită din mai multe structuri selective simple si eventual duale. În C++ se operează cu instr switch(selector) { case val1 : instr 1 ; case val2:instr2; ...else instr ;}
#include<stdio.h>
#include<iostream.h>int i,j;
int main()
{
cout<< "i=";
cin>>i;
cout<< "j=";
cin>>j;
if(i=j)cout<<i;
else cout<<j; return 0;}
Programul citeste i si j si il afiseaza pe cel mai mare dintre i si j . Main e funcția principala , practic instrucțiunile sale se execută in ordinea în care apar .
Aceste programe sunt realizate pentru stilul de programare in care avem un singur fir de execuție și acela în logica execuției strict secvențiale după ordinea in care avem instructiunile în funcția Main .
În programele de rețea se lucrează de regulă cu fire multiple de executie - multithread.
Structurile repetitive
-structura repetitiva cu contor
pentru i de la val_initiala la valoare_finala executa
instr ;
instr ;
-structura repetitiva cu test initial
cat timp conditie executa instr ;
-structura repetitiva cu test final
repeta instr pana când conditie;
Test practic - REDACTATI programul CMMDC
#include<iostream.h>
int a[10],n,i,j;
int main()
{
cout<<"nr=";cin>>n;for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<n;i++)
while(a[i]!=a[i+1])
{if(a[i]>a[i+1]) a[i]=a[i] -a[i+1];
if (a[i]<a[i+1]) a[i+1]=a[i+1]-a[i];
}
cout<<a[n]<<" este cmmdc";
return 0 ;
}
EXPLICATIE Avem in n numarul de elemente -exemplu 3 . In ”vectorul” a vom introduce pe rand 7,21 si 42 -3 elemente si vom obtine pentru cmmdc valoarea 7.Elementele vectorului a sunt comparate doua cate 2 .Se scade din numarul mai mare numarul mai mic până când devin egale . Variabile sunt a,n,i,j.
INCERCATI SA SCRIETI ALGORTMUL IN PSEUDOCOD pentru programul de mai sus .
NOTIUNI TEORETICE NECESARE IN REALIZAREA ALGORITMILOR
%-operatia modulo ofera restul la impartirea intreaga
Teste la clasa
test1
Pentru itemul 1, scrieţi pe foaia de examen litera corespunzătoare răspunsului corect.
1. Variabila x este de tip real. Care dintre următoarele expresii C/C++ are valoarea 1 dacă şi
numai dacă numărul real memorat în variabila x aparţine intervalului (5,8]? (1p.)
a. (x<8) && (x>=5) b. (x<=8) || (x>5)
c. (x>8) || (x<=5) d. (x<=8) && (x>5)
Scrieţi răspunsul pentru fiecare dintre cerinţele următoare.
2. Se consideră algoritmul alăturat, descris în pseudocod.
citeşte n (număr natural)
z=0
p=1
┌cât timp n>0 execută
│ c=n%10
│ n=[n/10]
│┌dacă c%3=0 atunci
││ z=z+p*(9-c)
││ p=p*10
│└■
└■
scrie z
scrie z
S-a notat cu x%y restul împărţirii numărului întreg x la numărul
întreg nenul y şi cu [a] partea întreagă a numărului real a.
a) Scrieţi valoarea care se va afişa dacă se citeşte
n=103456. (3p.)
b) Scrieţi toate numere naturale impare, distincte, fiecare
având exact două cifre, care pot fi citite pentru variabila
n astfel încât să se afişeze valoarea 3. (2p.)
c) Scrieţi în pseudocod un algoritm, echivalent cu cel dat,
în care să se înlocuiască structura cât timp...execută
cu o structură repetitivă de alt tip. (2p.)
2p (of)
Rezolvare:
La 1 avem raspuns corect b si d
la 2 a) se face un tabel
Rezolvare:
La 1 avem raspuns corect b si d
la 2 a) se face un tabel
n
|
c
|
z
|
p
|
|
103456
|
6
|
0
|
1
|
|
10345
|
3
|
10
|
||
1034
|
5
|
|||
103
|
4
|
|||
3
|
63
|
100
|
||
10
|
0
|
963
|
1000
|
|
1
|
1
|
|||
0
|
Cel mai probabil afiseaza 963
2 b) pt n=16 observam
n
|
c
|
z
|
p
|
|
16
|
0
|
1
|
||
1
|
6
|
3
|
10
|
|
0
|
1
|
|||
presupunem ca daca prima cifra nu e diviz cu 3 dar ultima e 6 avem f probabil valorile
16,26,46,56,76,86
c) citeşte n (număr natural)
z=0
p=1
daca n>0 atunci
┌repeta
┌repeta
│ c=n%10
│ n=[n/10]
│┌dacă c%3=0 atunci
││ z=z+p*(9-c)
││ p=p*10
│└■
└■ pana cand(n=0)
scrie z
S-a inlocuit instructiunea repetitiva cu test initial cu cea cu test final.
Intrebari
1. Observati ca am inlocuit instr repetitiva cu test initial cu instr repetitiva cu test final !
TEST
De ce se pune inaintea instructiunii repetitive cu test final o instructiune conditionala cu exact aceeasi conditie ca in instr repetitiva cu test initial?
2.Mentionati numele variabilelor intalnite in algoritm
3.Mai sus avem doua modalitati diferite de reprezentare a algoritmilor . Care sunt ?
4.Ce inseamna % , &&, ||, [ ] in algoritmul de mai sus ?
TEST VERIFICARE
Pentru itemul 1, scrieţi pe caiet litera corespunzătoare răspunsului corect.
1. Care dintre următoarele expresii C/C++, are ca valoare cel mai mic dintre numerele
naturale nenule, cu cel mult 4 cifre fiecare, memorate în variabilele întregi x şi y? (4p.)
a. (x+y-abs(x-y))/2 b. x+y-abs(x-y)/2
c. (x+y+abs(x-y))/2 d. (x+y+abs(x+y))/2
Scrieţi pe caiet răspunsul pentru fiecare dintre cerinţele următoare.
2. Se consideră algoritmul alăturat, descris în pseudocod:
S-a notat cu [c] partea întreagă a numărului real c, iar cu a%b
restul împărţirii numărului întreg a la numărul întreg nenul b.
a) Scrieţi valoarea care se afişează, în urma executării
algoritmului, dacă se citeşte numărul 9321.
b) Scrieţi o valoare care poate fi citită pentru n astfel încât
să se afişeze valoarea 11.
c) Scrieţi în pseudocod un algoritm echivalent cu cel dat în
care să se înlocuiască structura cât timp ... execută
cu o structură repetitivă cu test final.
citeşte n (număr natural)
s=-1
┌cât timp n>0 execută
│┌dacă n%10>s atunci
││ s=n%10
││altfel
││ s=11
│└■
│ n=[n/10]
└■
scrie s
Rezolvare cerinta b
citeşte n (număr natural)
s=-1
┌cât timp n>0 execută
│┌dacă n%10>s atunci
││ s=n%10
││altfel
││ s=11
│└■
│ n=[n/10]
└■
scrie s
s=-1
┌cât timp n>0 execută
│┌dacă n%10>s atunci
││ s=n%10
││altfel
││ s=11
│└■
│ n=[n/10]
└■
scrie s
s=11
cerinta b
n=? 100,200,50,250………
n
|
s
|
100
|
-1
|
10
|
0
|
1
|
11
|
0
|
11
|
REZOLVARE la cerinta c
citeşte n (număr natural)
s=-1
s=-1
daca n>0 atunci
┌repeta
│┌dacă n%10>s atunci
││ s=n%10
││altfel
││ s=11
│└■
│ n=[n/10]
└■pana cand n<=0
scrie s
┌repeta
│┌dacă n%10>s atunci
││ s=n%10
││altfel
││ s=11
│└■
│ n=[n/10]
└■pana cand n<=0
scrie s
Tema : ce afiseaza pt n=321 ?
Algoritmi cu secvente numerice
sunt cei de sortare , cautare , extragere dintr-un sir a cifrelor impare , pare etc
1. Suma cifrelor impare ale unui numar n>0
#include<iostream.h>
int n,s;
void main()
{
s=0;
do {
cout<<"n=";cin>>n;
} while(n<=0);
while(n>0)
{
if((n%10)%2==1) s=s+n%10;
n=n/10;
}
cout<<"suma cif impare= "<<s;
}
VECTORII
- sunt alcatuiti dintr-o insiruire de elemente de acelasi fel
-elementele (fiecare in parte) sunt asociate unor indici
EXEMPLU INT A[10];
INDICII SUNT 0....9
Elementele sunt A[0]......A[9]
Evident A este vector!
2. Se cere un algoritm pentru a inversa un sir alfanumeric.
Obs . Avem nevoie sa declaram vectori .In fapt un sir e un vector de caractere.
E rezolvat si la TIC cu o pagina web data ca exemplu !!
Algoritmul(pseudocod)
declaram n,i intregi
s[20] ca sir de caractere ,c caracter
citeste s
n<--lungimea lui s //exista instructiune in C++pt lung. de sir
pentru i de la 0 la n/2
{ x=s[i];
s[i]=s[n-i-1];
s[n-i-1]=x;
}
scrie s ;
s[20] ca sir de caractere ,c caracter
citeste s
n<--lungimea lui s //exista instructiune in C++pt lung. de sir
pentru i de la 0 la n/2
{ x=s[i];
s[i]=s[n-i-1];
s[n-i-1]=x;
}
scrie s ;
In C++ in CODEBLOCKS :
#include <iostream>
#include<string.h>
using namespace std;
int n,i;
char s[20],x;
int main()
{
cout<<"s=";
cin>>s;
n=strlen(s);
cout<<n;
for(i=0;i<n/2;i++)
{ x=s[i];
s[i]=s[n-i-1];
s[n-i-1]=x;
}
cout<<"sir inv="<< s ;
return 0;
}
#include<string.h>
using namespace std;
int n,i;
char s[20],x;
int main()
{
cout<<"s=";
cin>>s;
n=strlen(s);
cout<<n;
for(i=0;i<n/2;i++)
{ x=s[i];
s[i]=s[n-i-1];
s[n-i-1]=x;
}
cout<<"sir inv="<< s ;
return 0;
}
3. SORTAREA UNUI SIR DE NUMERE (stocate într-un vector)
Algoritm pseudocod(bubblesort)
IMPORTANT! Indicii unui vector C++ se numerotează începând cu 0 .
IMPORTANT! Indicii unui vector C++ se numerotează începând cu 0 .
Declară a[10], n,i j,,x intregi
citeste n
pentru i de la 0 la n-1 { citeste a[i ]
pentru j de la 0 la i-1 daca a[i ]<a[j] atunci
{ x=a[i]
a[i]=a[j]
a[j ]=x;
}
}
}
pentru i de la 0 la n-1 scrie a[i]
IN C++ , editat si rulat in CODEBLOCKS cu compilator MINGW C++ :
#include <iostream>
using namespace std;
int n,i,j,a[10],x;
int main()
{
cout<<"sortarea e crescatoare-dati n ! " << endl;
cin>>n;
for(i=0;i<n;i++){ cout<<"a["<<i<<"]=";cin>>a[i];
for(j=0;j<i;j++) if(a[i]<a[j]){x=a[i];
a[i]=a[j];
a[j]=x;
}
}
cout<<endl<<"vectorul sortat este"<<endl;
for (i=0;i<n;i++) cout<<a[i]<<endl;
return 0;
}
Se cere ca tema :
- explicatii sub forma unui eseu de 10 propozitii
ALGORITMI simpli tratati in pseudocod si in limbajul C++
1. Se cere suma tuturor numerelor intregi din intervalul [a,b] , a<b cu a si b intregi
2. Se dau x si y . Se cere algoritm pentru calculul mediei aritmetice
Subiectul 2 ramane pt testare
REZOLVARE
1.
declara i, s, a si b intregi
citeste a si b
s=0
pentru i de la a la b s=s+i
scrie i
#include<iostream>
using namespace std;
int a, b , i , s;
int main ()
{
cin >>a>>b;
s=0;
for(i=a;i<=b;i++) s=s+i;
cout<<i;
return 0;
}
