← Subiecte de Titularizare
Titularizare 2015 · Subiectul II, problema 2

Interclasare cu doi indici — simulator

II.1 subprogram Liste Șiruri caractere Matrice Backtracking
II.2 eficient Greedy intervale Reuniune Interclasare LIS LIS tije LCS Kadane Frecvențe Căutare binară
pas 0 / 0
📋 Enunțul problemei (Titularizare 2015)

Fișierul titu.in conține pe prima linie două numere naturale na și nb, pe a doua linie un șir descrescător de na numere, iar pe a treia linie un șir crescător de nb numere.

Se cere să se afișeze, în ordine strict crescătoare, toate numerele impare distincte aflate fie doar în primul, fie doar în al doilea șir. Dacă nu există niciunul, se afișează nu exista. Algoritm eficient ca timp.

Exemplu: pentru 9 7 5 4 3 3 2 și 1 2 2 5 8 se afișează 1 3 7 9.

Ideea: ambele șiruri sunt deja ordonate, deci nu e nevoie de nicio sortare. Primul se parcurge de la coadă spre cap — astfel ambele se citesc crescător și avansăm cu doi indici, într-o singură trecere.

startApasă „Pas înainte”. Comparăm mereu valoarea de sub indicele i cu cea de sub j și avansăm doar acolo unde e valoarea mai mică.

Cele două șiruri indicii i și j avansează independent

Șirul A descrescător → parcurs de la dreapta spre stânga
Șirul B crescător → parcurs de la stânga spre dreapta
rezultat(încă nimic)
indicele i (în A) indicele j (în B) valoare în ambele → se exclude

Starea algoritmului comparația curentă

Codul C++ linia activă e evidențiată

Cod C++

    

Algoritmul în limbaj natural pasul curent e evidențiat