Probleme informatica clasa 10 cu vectori

Tipuri de probleme avansate cu vectori

• Probleme de interclasare Interclasarea a doi vectori sortați într-unul singur, păstrând ordinea. Exemplu: pentru vectorii a (cu n elemente) și b (cu m elemente), se creează un vector c cu n+m elemente prin compararea elementelor pe rând.
• Probleme cu secvențe maxime Găsirea secvenței de sumă maximă într-un vector (algoritmul lui Kadane). Exemplu: int max_global = v[0], max_curent = v[0]; for (i=1; i<n; i++) { max_curent = max(v[i], max_curent + v[i]); max_global = max(max_global, max_curent); }
• Probleme de frecvență și statistică Determinarea elementului majoritar sau a frecvențelor elementelor într-un vector. Exemplu: pentru elementul majoritar (apare de peste n/2 ori), se poate folosi algoritmul Boyer-Moore.

Exemple numerice de rezolvare

1. 1
   Problema: Interclasare vectori Se dau vectorii a = [1, 3, 5] și b = [2, 4, 6]. Să se interclaseze în c = [1, 2, 3, 4, 5, 6]. Rezolvare: Se folosesc indici i=0 pentru a și j=0 pentru b, se compară a[i] și b[j], se adaugă elementul mai mic în c.
2. 2
   Problema: Secvență de sumă maximă Pentru vectorul v = [-2, 1, -3, 4, -1, 2, 1, -5, 4], secvența de sumă maximă este [4, -1, 2, 1] cu suma 6. Rezolvare: Aplică algoritmul lui Kadane pentru a obține suma maximă.