Clasa a XII-a · Recapitulare pentru bacalaureatRead in English

Fișier — valorile care apar o singură dată în C++

În engleză: File: the values that appear exactly once

O(n)C++1747 de linii2 exemplefolosește date.in / date.out

Ideea

Cerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6 numere naturale de cel mult trei cifre, separate prin spații. Afișați pe ecran, în ordine crescătoare, valorile care apar exact o dată în fișier, sau „nu exista”. Eficiența: nu memorăm șirul și nu îl sortăm. Cum valorile sunt între 0 și 999, un vector de frecvență f[1000] numără aparițiile la citire (O(1) pe număr), apoi parcurgerea vectorului de la 0 la 999 dă direct ordinea crescătoare. Memoria folosită nu depinde de câte numere sunt în fișier.

Descrierea în engleză

The task (exam part III.3 style): the file date.in holds at most 10^6 natural numbers with at most three digits, separated by spaces. Print on the screen, in increasing order, the values that appear exactly once in the file, or 'nu exista' (none). Efficiency: we neither store nor sort the sequence. Since the values are between 0 and 999, a frequency array f[1000] counts the occurrences while reading (O(1) per number), then walking the array from 0 to 999 gives the increasing order directly. The memory used does not depend on how many numbers the file holds.

Complexitate
O(n + 1000) timp, O(1000) memorie
Clasa
Clasa a XII-a (Grade 12)

Exemple

Exemplul 1

Intrare (date.in)

5 12 7 5 300 12 999 0 0

Ieșire așteptată

7 300 999
Exemplul 2

Intrare (date.in)

4 4 4

Ieșire așteptată

nu exista

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

fisier-valori-unice.cpp
/*
 * Titlu: Fișier — valorile care apar o singură dată
 * Clasa: 12
 * Capitol: Recapitulare pentru bacalaureat
 * Descriere: Cerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6
 *            numere naturale de cel mult trei cifre, separate prin spații. Afișați
 *            pe ecran, în ordine crescătoare, valorile care apar exact o dată în
 *            fișier, sau „nu exista”. Eficiența: nu memorăm șirul și nu îl sortăm.
 *            Cum valorile sunt între 0 și 999, un vector de frecvență f[1000]
 *            numără aparițiile la citire (O(1) pe număr), apoi parcurgerea
 *            vectorului de la 0 la 999 dă direct ordinea crescătoare. Memoria
 *            folosită nu depinde de câte numere sunt în fișier.
 * Complexitate: O(n + 1000) timp, O(1000) memorie
 *
 * Exemplu
 * Intrare: 5 12 7 5 300 12 999 0 0
 * Ieșire: 7 300 999
 *
 * Exemplu
 * Intrare: 4 4 4
 * Ieșire: nu exista
 */
#include <fstream>
#include <iostream>
using namespace std;

int f[1000];

int main()
{
    ifstream fin("date.in");
    int x;
    while (fin >> x)
        f[x]++;
    bool gasit = false;
    for (int v = 0; v < 1000; v++)
        if (f[v] == 1)
        {
            cout << v << ' ';
            gasit = true;
        }
    if (!gasit)
        cout << "nu exista";
    cout << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.