Probleme de căutare.
Dintre problemele simple de prelucrare a
tablourilor fac parte şi problemele de căutare într-un tablou a unuia sau mai
multor elemente cu o proprietate anumită. În problemele de căutare se folosesc
ciclurile, în cadrul cărora se parcurg tablourile şi se verifică condiţiile
cerute. La organizarea ciclurilor de căutare poate fi utilizată instrucţiunea
For care va permite parcurgerea întregului tablou şi instrucţiunile While-Do şi
Repeat-Until în cazul problemelor cînd căutarea trebuie întreruptă de îndată ce
elementul cu proprietatea cerută a fost găsit. Elevii întîmpină greutăţi în
cazul problemelor pentru care ciclul trebuie întrerupt de îndată ce elementul
cu proprietatea cerută a fost găsit, deaceea trebuie să se acorde atenţie modului
de organizare a întreruperii căutării.
1. Problema
Nr. 1. Fie dat tabloul A[1..N], N≤100, de numere reale.
Scrieţi un program care determină elementul maxim şi numărul de elemente
maxime.
Intrare:
numărul N şi elementele tabloului se citesc de la tastatură.
Ieşire: pe
ecran se afişează valoarea elementului maxim şi numărul de elemente maxime,
despărţite prin spaţiu.
Algoritmul: Folosim o variabilă Max în care
vom păstra valoarea elementului maxim şi Num pentru numărul de elemente maxime.
Iniţializăm Max cu valoarea primului element A[1], iar Num – cu 1, apoi
parcurgem elementele tabloului în cadrul
unui ciclu, începînd cu al doilea şi verificăm dacă elementul cercetat este egal cu elementul
maxim, la variabila contor Num se adună o unitate, dacă elementul cercetat mai
mare ca maximul curent, atunci elementul respectiv devine noul maxim, iar
variabila Num se iniţializează din nou cu 1.
Program Tablou_problema_nr1;
Uses CRT;
Type
Lin=Array[1..100] Of Real;
Var A:Lin;
Num, N,I:Byte;
Max:Real;
Begin
ClrScr;
Write(’Numarul de elemente=’);ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
Begin
Write(’introduceti elementul ’,I,’:’);ReadLn(A[I])
End;
Max:=A[1]; Num:=1;
For I:=2 To N Do
If A[I] >Max Then Begin
Max:=A[I]; Num:=1
End
Else If A[I]=Max
Then Inc(Num);
WriteLn(Max:7:2,’ ’,Num );
ReadLn End.
2. Problema
Nr. 2. Fie dat tabloul A[1..N], N≤100, de numere reale.
Scrieţi un program care determină indicele primului element pozitiv.
Intrare:
numărul N şi elementele tabloului se citesc de la tastatură.
Ieşire: pe
ecran se afişează indicele şi valoarea elementului cu indicele dat, despărţite
prin spaţiu, dacă aşa element există şi mesajul NU EXISTA în caz dacă nu există
nici un element pozitiv în tablou.
Algoritmul: Pentru a stabili dacă în tabloul dat există
măcar un element pozitiv, vom folosi o variabilă logică . Înainte de a începe
căutarea, iniţializăm această variabilă cu False. Parcurgem într-un ciclu
poziţiile elementelor i=1,...,N. Pentru fiecare valoare a lui i, testăm dacă
elementul A[i] este pozitiv: în caz afirmativ variabila logică primeşte
valoarea True şi întrerupem execuţia ciclului. Dacă pentru nici o valoare a lui
i nu este îndeplinită condiţia A[i]>0, atunci valoarea variabilei logice
rămîne False. La implementarea algoritmului de mai sus vom folosi instrucţiunea
While-Do pentru ca la găsirea primului număr pozitiv ciclul să fie întrerupt.
Program Tablou_problema_nr2;
Uses CRT;
Type
Lin=Array[1..100] Of Real;
Var A:Lin;
N,I:Byte;
V:Boolean;
Begin
ClrScr;
Write(’Numarul de elemente=’);ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
Begin
Write(’introduceti elementul ’,I,’:’);ReadLn(A[I])
End;
I:=0; V:=False;
Repeat
Inc(I);
If A[I]>0 Then V:=True
Until V Or (I=N);
If V Then WriteLn(I,’ ’,A[I]:7:2)
Else WriteLn(’ NU EXISTA’ );
ReadLn End.
3. Problema
Nr.3. Fie dat tabloul bidimensional A[1..N,1..N], N≤20,
elementele căruia sunt numere întregi.
Scrieţi un program care determină elementul ce se găseşte în fiecare linie.
Intrare:
numărul N şi elementele tabloului se citesc de la tastatură.
Ieşire: pe
ecran se afişează elementul, dacă aşa
element (elemente) exista şi mesajul NU EXISTA în caz dacă aşa element nu
există.
Algoritmul: Se parcurge într-un ciclu indicii
elementelor din prima linie şi pentru fiecare element se verifică dacă el se
conţine în toate celelalte linii. Dacă se conţine, valoarea lui se afişează la
ecran, în caz contrar se trece la următorul element. Vom utiliza o variabilă
logică care iniţial va primi valoarea True, adică aşa elemente nu există. Dacă
vom găsi măcar un element ce verifică condiţia dată, valoarea variabile se va
schimba în False.
Program Tablou_problema_nr3;
Uses CRT;
Type Tab=Array[1..20,1..20] Of Integer;
Var A:Tab;
N,I,K,J:Byte;
V,C, Control:Boolean;
Begin
ClrScr;
Write(’Introduceti dimensiunea tabloului: ’); ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
For K:=1 To N Do
Begin
Write(’A[’,I, ’, ’,K, ’]= ’); ReadLn(A[I,K])
End;
Control:=True;
For I:=1 To N Do
Begin V:=True;
For J:=2 To N Do
Begin C:=False;
For K:=1 To N Do
If A[1,I]=A[J,K] Then C:=True;
If Not C Then V:=False
End;
If V Then Begin
Control:=False;
WriteLn(A[1,I])
End
End;
If Control Then WriteLn(’NU EXISTA’);
ReadLn End.
4. Problema
Nr.4. Fie dat tabloul bidimensional A[1..N,1..N], N≤20,
elementele căruia sunt numere reale.
Scrieţi un program care determină perechea de elemente, diferenţa dintre care
este maximă.
Intrare:
numărul N şi elementele tabloului se citesc de la tastatură.
Ieşire: pe
ecran se afişează în două linii separate indicii elementelor ce corespund
condiţiilor din enunţul problemei, separate prin spaţiu. Primul număr va indica
numărul liniei, iar al doilea – numărul coloanei.
Algoritmul: Se calculează toate diferenţele
posibile dintre elementele tabloului şi se reţine valoarea maximă a acestor
diferenţe, inclusiv şi indicii elementelor pentru care este realizată această
diferenţă.
Program Tablou_problema_nr4;
Uses CRT;
Type Tab=Array[1..20,1..20] Of Real;
Var A:Tab;
N,I,K,J,L,B,Lin_1,Col_1,Lin_2,Col_2:Byte;
Dmax:Real;
Begin
ClrScr;
Write(’Introduceti dimensiunea tabloului: ’);
ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
For K:=1 To N Do
Begin
Write(’A[’,I, ’, ’,K, ’]= ’);
ReadLn(A[I,K])
End;
Dmax:=Abs(A[1,1]-A[1,2]);
Lin_1:=1; Col_1:=1;
Lin_2:=1; Col_2:=2;
For I:=1 To N Do
For K:=1 To N Do
For L:=I To N Do
Begin
If I<L Then B:=1 Else B:=K+1;
For J:=B To N Do
If Abs(A[I,K]-A[L,J])>Dmax Then Begin
Dmax:=Abs(A[I,K]-A[L,J]);
Lin_1:=I;
Col_1:=K;
Lin_2:=L; Col_2:=J
End
End;
WriteLn(Lin_1, ’ ’,Col_1);
WriteLn(Lin_2, ’ ’,Col_2);
ReadLn End.
Probleme de modificare.
Există probleme în cadrul cărora
tablourile sunt supuse unor schimbări. La aceste probleme trebuie să se ţină
cont de modul de execuţie a instrucţiunii de atribuire şi să nu se scape din
vedere faptul, că în urma atribuirii unei valori noi variabilei, valoarea
precedentă se pierde.
1. Problema
Nr. 2. Fie dat tabloul A[1..N], N≤100, de numere reale.
Scrieţi un program care interschimbă elementele vecine ale tabloului.
Intrare:
numărul N şi elementele tabloului se citesc de la tastatură.
Ieşire: pe
ecran se afişează elementele tabloului modificat, separate prin spaţiu.
Algoritmul: Parcurgem într-un ciclu poziţiile
elementelor i=1,3,...,N-1. Pentru fiecare valoare a lui i, înlocuim elementul
A[i] cu A[i+1].
Program Tablou_problema_nr1;
Uses CRT;
Type
Lin=Array[1..100] Of Real;
Var A:Lin;
N,I:Byte; C:Real;
Begin
ClrScr;
Write(’Numarul de elemente=’);ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
Begin
Write(’Elementul ’,I,’ este:’); ReadLn(A[I])
End;
ClrScr;
WriteLn(’Tabloul initial’);
For I:=1 To N Do Write(A[I]:7:2, ’ ’);
WriteLn;
I:=1;
While I<N Do Begin
C:=A[I]; A[I]:=A[I+1]; A[I+1]:=C;
Inc(I,2) End;
WriteLn(’Tabloul modificat’);
For I:=1 To N Do Write(A[I]:7:2, ’ ’);
WriteLn;
ReadLn End.
2. Problema
Nr. 2. Fie dat tabloul A[1..N], N≤100, de numere întregi.
Scrieţi un program care
efectuiază
deplasarea consecutivă a elementelor tabloului pozitive la început, negative –
la
sfîrşitul
tabloului fără a schimba ordinea lor din tabloul iniţial.
Intrare: numărul N
şi elementele tabloului se citesc de la tastatură.
Ieşire: pe
ecran se afişează elementele tabloului modificat, separate prin spaţiu.
Algoritmul:Parcurgem într-un ciclu poziţiile
elementelor i=1,2,...,N. Utilizăm o variabilă pentru poziţia unde a fost
transferat ultimul element pozitiv găsit, care iniţial se zerografiază. Pentru
fiecare valoare a lui i, testăm dacă elementul A[i] este pozitiv. Dacă
răspunsul este afirmativ, elementele negative amplasate în faţa lui le deplasăm
la dreapta cu o poziţie, mărim cu o unitate valoarea variabilei pentru poziţia ultimului element pozitiv
transferat, şi înscriem acest element la
poziţia indicată.
Program Tablou_problema_nr2;
Uses CRT;
Type
Lin=Array[1..100] Of Integer;
Var A:Lin;
N,I,K,P:Byte;C:Integer;
Begin
ClrScr; Write(’Numarul de elemente=’);ReadLn(N);
WriteLn(’Introduceti elementele tabloului’);
For I:=1 To N Do
Begin
Write(’Elementul ’,I,’ este:’); ReadLn(A[I])
End;
ClrScr;
WriteLn(’Tabloul initial’);
For I:=1 To N Do
Write(A[I], ’ ’); WriteLn;
P:=0;
For I:=1 To N Do
If A[I]>0 Then Begin
C:=A[I];
For K:=I-1 DownTo P+1 Do A[K+1]:=A[K];
Inc(P); A[P]:=C
End;
WriteLn(’Tabloul modificat’);
For I:=1 To N Do
Write(A[I], ’ ’);
ReadLn End.
3. Problema Nr. 3. Să
se transforme un număr natural din baza 10 în baza 2, memorînd cifrele binare într-un tablou unidimensional.
Intrare:
numărul N se citeşte de la tastatură.
Ieşire: pe
ecran se afişează elementele tabloului.
Algoritmul: Transformăm numărul dat din baza
10 în baza 2,memorînd cifrele binare într-un tablou unidimensional. Pentru a
afişa numărul în baza 2, trebuie să tipărim tabloul cifrelor binare în ordine
inversă: parcurgem într-un ciclu poziţiile elementelor în ordine inversă,
i=N,N-1,...,2,1, afişînd fiecare element. Algoritmul de transformare a unui
număr din baza 10 în baza 2 se bazează pe împărţirea repetată a unui deîmpărţit
la doi. Iniţial deîmpărţitul este chir numărul dat, apoi la fiecare pas cîtul
devine deîmpărţit pentru împărţirea următoare, algoritmul repetîndu-se pînă
cînd deîmpărţitul devine 0. Restul fiecărei împărţiri este o cifră binară (0
sau 1) iar numărul în baza 2 se obţine citind în ordine inversă cifrele binare
obţinute.
Program Tablou_problema_nr3;
Uses CRT;
Type Binar=0..1; Lin=Array[1..30] Of
Binar;
Var A:Lin;
K,I:Byte; N:Integer;
Begin
ClrScr; Write(’N=’); ReadLn(N); K:=0;
Repeat
Inc(K); A[K]:=N Mod 2; N:=N Div 2
Until N=0;
WriteLn(’Numarul in forma binara’);
For I:=K DownTo 1 Do Write(A[I]);
ReadLn
End.
4.Problema
Nr. 4. Fie dat tabloul bidimensional A[1..N,1..N], N≤20,
elementele căruia sunt numere întregi. Scrieţi un program care realizează
interschimbarea simetrică a elementelor tabloului în raport cu diagonala
secundară.
Intrare:
numărul N şi elementele tabloului se citesc de la tastatură.
Ieşire: pe
ecran se afişează tabloul modificat. Fiecare linie a tabloului se afişează
într-o linie separată. În linie elementele sunt separate prin spaţiu.
Algoritmul: Parcurgem elementele aflate deasupra diagonalei
secundare ( liniile i ale tabloului (i=1,2,...,N-1), iar pentru fiecare linie i
parcurgem numai coloanele j mai mici decît N-i+1, adică j=N-i+1,...,N) şi
schimbăm cu locul elementul respectiv cu cel ce se află sub diagonala secundară
prin intermediul unei variabile auxiliare.
Program Tablou_problema_nr4;
Uses CRT;
Type
Tab=Array[1..20,1..20] Of Integer;
Var A:Tab;
N,I,K:Byte; X:Integer;
Begin
ClrScr;
Write(’Introduceti nr. de linii si
coloane:’); ReadLn(N);
WriteLn(’Introduceti elementele
tabloului’);
For I:=1 To N Do
For K:=1 To N Do
Begin
Write(’A[’,I,’,’,K,’ ]=’); ReadLn(A[I,K])
End;
ClrScr; WriteLn(’Tabloul initial’);
For I:=1 To N Do
Begin
For K:=1 To N Do
Write(A[I,K]:5); WriteLn
End;
For I:=1 To N-1 Do
For K:=1 To N-I Do
Begin
X:=A[I,K]; A[I,K]:=X[N-K+1,N-I+1]; A[N-K+1,N-I+1]:=X
End;
WriteLn(’Tabloul modificat’);
For I:=1 To N Do
Begin
For K:=1 To N Do
Write(A[I,K]:5); WriteLn
End;
ReadLn End.
Rezultatele le transmiteti la adresa de e-mail: toloaca.svetlana@gmail.com
Elevii, care nu au calculatoare creaza un proiect la tema: Limbajul Pascal. Tipuri structurate de date.
Informatia teoretica o gasiti in manual si pe blog exemple de probleme-le scriem pe hîrtie, le fotografiem şi le plasăm în proiect. Succese!!!
Termen de realizare- 2 săptămâni. ( până la data -17.04.2020)
Sarcini pentru executare.
1. Este dat un tablou unidimensional A[1..N], N<=100 cu elemente intregi. Numarul de elemente si elementele tabloului se citesc de la tastatura.
a) Determinati valoarea maxima si numarul de elemente maxime printr-o singura parcurgere a tabloului.
b) Determinati primul numar par
c) Determinati ultimul numar pozitiv
d) Transferati elementele cu o pozitie la dreapta
2. Este dat un tablou patrat A[1..n,1..N], N<=20 cu elemente intregi.
a) Transpuneti tabloul simetric fata de diagonala principala.
b) Adaugati la fiecare element elementul diagonalei secundare din linia data.
c) Schimbati cu locul elementele din prima linie cu cele din ultima
d) Scimbati cu locul elementele din ultima coloana cu elementul maxim din linia data.
1. Este dat un tablou unidimensional A[1..N], N<=100 cu elemente intregi. Numarul de elemente si elementele tabloului se citesc de la tastatura.
a) Determinati valoarea maxima si numarul de elemente maxime printr-o singura parcurgere a tabloului.
b) Determinati primul numar par
c) Determinati ultimul numar pozitiv
d) Transferati elementele cu o pozitie la dreapta
2. Este dat un tablou patrat A[1..n,1..N], N<=20 cu elemente intregi.
a) Transpuneti tabloul simetric fata de diagonala principala.
b) Adaugati la fiecare element elementul diagonalei secundare din linia data.
c) Schimbati cu locul elementele din prima linie cu cele din ultima
d) Scimbati cu locul elementele din ultima coloana cu elementul maxim din linia data.
Rezultatele le transmiteti la adresa de e-mail: toloaca.svetlana@gmail.com
Elevii, care nu au calculatoare creaza un proiect la tema: Limbajul Pascal. Tipuri structurate de date.
Informatia teoretica o gasiti in manual si pe blog exemple de probleme-le scriem pe hîrtie, le fotografiem şi le plasăm în proiect. Succese!!!
Termen de realizare- 2 săptămâni. ( până la data -17.04.2020)
Niciun comentariu:
Trimiteți un comentariu