Jump to content
Main menu
Main menu
move to sidebar
hide
Navigation
Main page
Recent changes
Random page
Help about MediaWiki
Bitnami MediaWiki
Search
Search
Create account
Log in
Personal tools
Create account
Log in
Pages for logged out editors
learn more
Contributions
Talk
Editing
4037 - CautariLiniare
Page
Discussion
English
Read
Edit
Edit source
View history
Tools
Tools
move to sidebar
hide
Actions
Read
Edit
Edit source
View history
General
What links here
Related changes
Special pages
Page information
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
Sursa: [https://www.pbinfo.ro/probleme/4037/cautariliniare 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:<br>a) Cea mai din stânga poziție '''p''' din șir cu '''a[p] = x'''<br>b) Cea mai din dreapta poziție '''q''' din șir cu '''a[q] = x'''<br>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. <br> == Rezolvare == <syntaxhighlight lang="python" line> # 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).<br> 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.<br> 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.
Summary:
Please note that all contributions to Bitnami MediaWiki may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
Bitnami MediaWiki:Copyrights
for details).
Do not submit copyrighted work without permission!
Cancel
Editing help
(opens in new window)
Toggle limited content width