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.
Niciun comentariu:
Trimiteți un comentariu