4037 - CautariLiniare

Sursa: 4037 - CautariLiniare

---

Cerinţa

Se dă un șir a[1], a[2], …, a[n] de numere întregi. Se dau de asemenea numerele întregi x și k. Să se determine:
a) Cea mai din stânga poziție p din șir cu a[p] = x
b) Cea mai din dreapta poziție q din șir cu a[q] = x
c) Poziția r a celei de-a k-a apariții a lui x în șir.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere întregi, separate prin enter, reprezentând elementele șirului. În final, de pe ultimele două linii, se citesc numerele x și k.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou va afișa, separate prin enter, valorile p, q și r. Dacă x nu apare în vector, atunci p și q vor fi egale cu 0, iar dacă x nu apare de cel puțin k ori, atunci r va fi 0. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• toate numerele citite la intrare sunt cuprinse între -1.000 și 1.000.
• n și k sunt numere naturale nenule

Exemple

Exemplul 1

Intrare

12

2

4

5

-7

2

3

2

5

7

2

3

4

2

3

Ieșire

Datele sunt introduse corect.

1

10

7

Explicație exemplul 1

Șirul a este 2, 4, 5, -7, 2, 3, 2, 5, 7, 2, 3, 4, x=2 și k=3.

Cea mai din stânga poziție a lui 2 este la poziția 1, cea mai din dreapta este la poziția 10, iar a treia apariție a lui 2 este la poziția 7.

Exemplul 2

Intrare

4

1

2

1

2

1

4

Ieșire

Datele sunt introduse corect.

1

3

0

Explicație exemplul 2

Șirul a este 1, 2, 1, 2, x=1 și k=4. Cea mai din stânga poziție a lui 1 este la poziția 1, cea mai din dreapta este la poziția 3, iar a patra apariție a lui 1 nu există, deoarece 1 apare doar de două ori în șir, deci se afișează 0.

Exemplul 3

Intrare

0

1

2

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 4037 CautariLiniare

def afis_cea_mai_stanga_poz_x_dreapta_poz_x_poz_apar_k_lui_x(a, n, k, x):

   p = q = contor = r = 0
   for i in range(n):
       if a[i] == x:
           p = i + 1
           break
   print(p)
   for i in range(n-1, 1, -1):
       if a[i] == x:
           q = i + 1
           break
   print(q)
   for i in range(n):
       if a[i] == x:
           contor += 1
       if contor == k and contor != 0:
           r = i + 1
           break
   print(r)

def citire_conform_restrictiilor(a, n, k):

   if n < 1 or k < 1:
       print("Datele nu corespund restricțiilor impuse.")
       exit()
   for element in a:
       if element >= 1000 or element < -1000:
           print("Datele nu corespund restricțiilor impuse.")
           exit()
   print("Datele sunt introduse corect.")

if __name__ == '__main__':

   n = int(input())
   a = [] * n
   for i in range(n):
       a.append(int(input()))
   x = int(input())
   k = int(input())
   citire_conform_restrictiilor(a, n, k)
   afis_cea_mai_stanga_poz_x_dreapta_poz_x_poz_apar_k_lui_x(a, n, k, x)

</syntaxhighlight>

Explicație rezolvare

   Programul de mai sus conține două funcții, funcția afis_cea_mai_stanga_poz_x_dreapta_poz_x_poz_apar_k_lui_x(a, n, k, x) și funcția citire_conform_restrictiilor(a, n, k), care se vor rula în interiorul main-ului (if __name__ == '__main__' , linia 35) după citirea numărului n (linia 36), celor n numere pe care le vom pune în șirul „a” (liniile 35-37) și numerele x și k (liniile 40, 41).
   După ce am terminat de citit, se va apela funcția citire_conform_restrictiilor(vector, n) care primește doi parametri: vectorul „a” și lungimea sa, reprezentată de variabila „n”. Funcția verifică dacă numerele n și k sunt mai mici decât 0 (linia 25, cele două numere trebuie să fie naturale) și dacă elementele vectorului sunt cuprinse între -1000 și 1000 (liniile 28, 29). Dacă oricare dintre condiții este încălcată, se va afișa mesajul „Datele nu corespund restricțiilor impuse.” și se va ieși din program cu comanda exit(). Dacă toate condițiile sunt respectate, se va afișa mesajul „Datele sunt introduse corect.” (linia 32) și se va continua programul.
   Dacă s-au introdus corect datele, se va apela funcția afis_cea_mai_stanga_poz_x_dreapta_poz_x_poz_apar_k_lui_x(a, n, k, x) care primește ca parametrii vectorul „a” și numerele n, k și x. În această funcție se inițializează numerele p, q, contor și r cu 0 (numerele p, q, r sunt din problemă și le inițializăm cu 0, iar contor este o variabilă pe care calcularea numărului r). Primul ciclu for parcurge vectorul a până la poziția n (de la stânga la dreapta) și verifică dacă elementul curent este x. Dacă da, variabila p va fi actualizată cu valoarea i+1 (poziția elementului x în vectorul a). Când se găsește prima apariție a lui x, bucla se oprește cu break (linia 8) și se afișează valoarea lui p. Al doilea ciclu for parcurge vectorul a în ordine inversă (de la n-1 până la 1, de la dreapta spre stânga) și verifică dacă elementul curent este x. Dacă da, variabila q va fi actualizată cu valoarea i+1 (poziția elementului x în vectorul a). Când se găsește ultima apariție a lui x, bucla se oprește cu break (linia 13) și se afișează valoarea lui q. Al treilea ciclu for parcurge vectorul a și numără cu ajutorul variabilei contor câte apariții ale lui x există până la poziția curentă (contor crește cu 1 de fiecare dată când îl găsește pe x în șirul a). Dacă contorul ajunge la valoarea k și x a fost găsit cel puțin o dată în vector (linia 18, punem și condiția că variabila contor trebuie să fie diferită de 0 pentru a nu se incrementa), variabila r va fi actualizată cu valoarea i+1 (poziția elementului x în vectorul a la a k-a apariție). Când se găsește a k-a apariție a lui x, bucla se oprește și se afișează valoarea lui r. În final, vom avea toate valorile afișate conform problemei.