#578 · Subiectul II · Programare

Căutare binară printre numerele de trei cifre, ordonate descrescător (construire și cautare)

✓ Rezolvare explicatăBucurești 2020 · nr. 6

Enunț

Fișierul atestat.in conține cel mult 100 de numere naturale cu cel mult patru cifre, scrise pe o singură linie, separate prin câte un spațiu. Valorile din fișier sunt ordonate descrescător.

Se consideră subprogramele:

construire, cu doi parametri: v, un tablou unidimensional cu numere naturale, și n, numărul de elemente ale lui v. Subprogramul citește numerele din atestat.in și furnizează prin v un tablou care conține doar numerele din fișier care au exact trei cifre, iar prin n numărul acestora. Fișierul conține cel puțin un număr cu 3 cifre;
cautare, cu trei parametri: v, un tablou unidimensional cu numere naturale, n, numărul de elemente ale lui v, și x, un număr natural. Subprogramul returnează, utilizând algoritmul de căutare binară, poziția pe care se găsește x în v, sau -1 în caz contrar.

a. Scrieți definiția completă a subprogramului construire.

b. Scrieți definiția completă a subprogramului cautare.

c. Scrieți un program care, utilizând apeluri utile ale celor două subprograme, scrie în atestat.out poziția din v pe care se găsește un număr natural x cu exact trei cifre, citit de la tastatură, sau mesajul nu exista dacă x nu se află printre elementele lui v.

Exemple

`atestat.in`	Tastatură	`atestat.out`	Explicații
`1204 991 234 102 79`	`105`	`nu exista`	`v = 991 234 102`; `105` lipsește
`1204 991 234 102 79`	`991`	`1`	Subiectul nu dă acest exemplu; pozițiile se numără de la 1 (alegere declarată, enunțul nu decide)

Rezolvare

C++

#include <fstream>
#include <iostream>
using namespace std;

void construire(int v[], int &n) {
    ifstream f("atestat.in");
    int x;
    n = 0;
    while (f >> x)
        if (x >= 100 && x <= 999) v[++n] = x;   // ordinea descrescatoare se pastreaza
}

int cautare(int v[], int n, int x) {
    int st = 1, dr = n;
    while (st <= dr) {
        int m = (st + dr) / 2;
        if (v[m] == x) return m;
        if (v[m] > x) st = m + 1;    // descrescator: valorile mai mici sunt la dreapta
        else dr = m - 1;
    }
    return -1;
}

int main() {
    ofstream g("atestat.out");
    int v[101], n, x;
    construire(v, n);
    cin >> x;
    int p = cautare(v, n, x);
    if (p == -1) g << "nu exista";
    else g << p;
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#283ProgramarePoziția unui element în vectorul ordonat, fără a-l ordona #569ProgramareElementele comune ale unui tablou crescător și ale unuia descrescător (subprogramul tablou)#573ProgramareNumere cu prima cifră pătrat perfect, ordonate descrescător (p_cifra recursiv și sortare)#577ProgramareSortarea descrescătoare a unor numere reale cu poziția maximului (citeste și pozmax)#061ProgramareModulele numerelor complexe dintr-un fișier, afișate în ordine descrescătoare #067ProgramareSă se afişeze, în ordine crescătoare, numerele distincte din cele două fişiere