Fișierul bac.txt conține un șir de cel mult un milion de numere naturale din intervalul [0,102], separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă există cel puțin o pereche formată din termeni ai șirului aflat în fișier, x și y (y-x≥2), astfel încât să nu existe niciun termen al șirului care să aparțină intervalului (x,y). Dacă nu există nicio astfel de pereche, se afișează pe ecran mesajul NU. Pentru verificarea proprietății cerute, utilizați un algoritm eficient din punctul de vedere al timpului de executare. Exemplu: dacă fișierul conține numerele 5 9 0 8 10 11 12 13 15 14 6 7 40 10 0 0 5 41 95 7 atunci pe ecran se afișează mesajul DA deoarece intervalele (0,5), (15,40) sau (41,95) au proprietatea cerută.(Bac 2015)
Răspunsuri la întrebare
Răspuns 1 — cu array:
var
lista: array[0..102] of Boolean;
fisier: Text;
i, numar: Byte;
gaura, rezultat: Boolean;
begin
for i := 0 to 102 do begin
lista[i] := False;
end;
Assign(fisier, 'bac.txt');
Reset(fisier);
while not Eof(fisier) do begin
Read(fisier, numar);
lista[numar] := True;
end;
Close(fisier);
numar := 255;
gaura := False;
rezultat := False;
for i := 0 to 102 do begin
if lista[i] then begin
if (numar <> 255) and (i - numar >= 2) and gaura then begin
WriteLn('Gaură între ', numar, ' și ', i); { doar pentru verificare }
rezultat := True;
end;
numar := i;
gaura := False;
end else begin
gaura := True;
end;
end;
if rezultat then begin
WriteLn('DA');
end else begin
WriteLn('NU');
end;
end.
Răspuns 2 — cu set:
var
multime: set of 0..102;
fisier: Text;
i, j, numar: Byte;
rezultat: Boolean;
begin
multime := [];
Assign(fisier, 'bac.txt');
Reset(fisier);
while not Eof(fisier) do begin
Read(fisier, numar);
Include(multime, numar)
end;
Close(fisier);
rezultat := False;
numar := 255;
for i := 102 downto 0 do begin
if i in multime then begin
numar := i;
break;
end;
end;
if numar <> 255 then begin
for i := 0 to numar - 1 do begin
if i in multime then begin
for j := i + 1 to numar - 1 do begin
if not (j in multime) then begin
rezultat := True;
break;
end;
end;
break;
end;
end;
end;
if rezultat then begin
WriteLn('DA');
end else begin
WriteLn('NU');
end;
end.
Explicație:
- Menţionarea milionului de numere este doar intimidare: în intervalul 0..102 oricum n-o să fie mai mult de 103 numere. Cum nu se cere analiză cantitativă, putem procesa doar valori unice.
- Un milion de numere sunt totuși multe dacă la citirea fiecăruia trebuie să verificăm toate cele deja existente dacă noul număr a fost deja întâlnit sau nu. Așa că e mai eficient să folosim un set. (Nu mă întreba de ce, dar am ales să folosesc array de Boolean în loc de set.)
- Ar fi de ajuns să cauţi primul și ultimul True în lista și dacă între ele este un False, ai o gaură. (Din ceva motiv am avut impresia că se iau în considerare doar găuri mai mari, de asta e verificarea mai complexă.)
- Ulterior am implementat și cu set. N-a ieșit cu nimic mai simplu.