#285 · Subiectul II · Programare

Număr real scris ca raport de două numere naturale cu diferența minimă

✓ Rezolvare explicatăTeleorman 2026 · nr. 45

Enunț

Fișierul text fisa18.txt conține pe prima linie un număr real pozitiv x, care are cel mult trei cifre la partea întreagă și cel mult cinci cifre la partea zecimală. Scrieți un program care afișează pe ecran, separate printr-un spațiu, două numere naturale al căror raport este egal cu x și a căror diferență absolută este minimă.

Exemple

`fisa18.txt`	Pe ecran	Explicații
`0.75`	`3 4`	0.75 = 75/100 = 3/4
`2.5`	`5 2`	2.5 = 25/10 = 5/2
`1.20`	`6 5`	1.20 = 120/100 = 6/5
`0.29`	`29 100`	fracția nu se mai simplifică
`3`	`3 1`	număr întreg

Subiectul nu dă exemplu; cele de mai sus sunt construite și verificate de mână. Primul număr afișat e numărătorul, al doilea numitorul — raportul lor, în ordinea afișării, e x. Numărul din fișier se scrie cu punct zecimal, ca orice valoare citită de un program C++.

Rezolvare

C++

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

int main() {
    ifstream f("fisa18.txt");
    string s;
    f >> s;                               // citim numarul ca TEXT, nu ca double

    long long p = 0, q = 1;               // x = p / q
    bool dupaVirgula = false;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '.')
            dupaVirgula = true;
        else {
            p = p * 10 + (s[i] - '0');    // lipim cifra la numarator
            if (dupaVirgula)
                q = q * 10;               // fiecare zecimala inmulteste numitorul cu 10
        }
    }

    long long a = p, b = q;               // cmmdc(p, q) - algoritmul lui Euclid
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    cout << p / a << ' ' << q / a;
    f.close();
    return 0;
}

Cum funcționează

Problema are două idei.

1. Diferența minimă înseamnă fracția ireductibilă. Toate perechile cu raportul x = 3/4 sunt 3 4, 6 8, 9 12… — adică t·3 și t·4. Diferența lor e t · |3 - 4|, minimă pentru t = 1. Deci răspunsul e fracția simplificată complet: împarți numărătorul și numitorul la c.m.m.d.c. lor, calculat cu algoritmul lui Euclid (explicat pe larg în lecția despre numere și divizibilitate).

2. Fracția se obține din cifre, nu din calcule cu double. Un număr cu k zecimale este numărul format din toate cifrele lui, împărțit la 10^k:

12.375  →  12375 / 1000
0.75    →     75 / 100

De aceea numărul se citește ca șir de caractere. Parcurgi caracterele: fiecare cifră se lipește la numărător (p = p * 10 + cifra), iar fiecare cifră de după punct înmulțește și numitorul cu 10.

Trasare pentru 1.20:

caracter	`p`	`q`
`1`	1	1
`.`	1	1
`2`	12	10
`0`	120	100

cmmdc(120, 100) = 20 → 6 5.

De ce nu double: numerele reale sunt memorate în baza 2, iar majoritatea zecimalelor nu se pot reprezenta exact. Citit ca double, 0.29 e de fapt 0.28999999999999998…, iar (long long)(x * 100000) dă 28999, nu 29000 — fracția finală ar fi 28999/100000 în loc de 29/100. Citirea ca text ocolește complet problema.

Mărimile sunt mici: cel mult 8 cifre la numărător și 10^5 la numitor, deci long long e mai mult decât suficient (și int ar ajunge).

Greșeli frecvente

Citirea ca double și înmulțirea cu 100000 — 0.29 dă 28999 100000, iar evaluatorul vede un răspuns evident greșit.
Simplificarea doar cu 2 și cu 5 („numitorul e o putere a lui 10”) — merge, dar e mai lungă și ușor de greșit; c.m.m.d.c. rezolvă direct orice caz.
Afișarea perechii nesimplificate (75 100) — raportul e corect, dar diferența (25) nu e minimă: 3 4 are diferența 1.
Ordinea inversată (4 3) — raportul 4/3 nu mai e x.
Partea întreagă și cea zecimală citite ca două numere (f >> a >> punct >> b) — zerourile din fața zecimalelor se pierd: 1.05 dă b = 5 și e tratat ca 1.5, adică 3 2 în loc de 21 20.

Exersează mai departe

Probleme cu aceeași tehnică

#163ProgramareCele mai mari două numere perfecte dintr-un fișier #169ProgramareNumerele pare dintre primul și ultimul număr prim #176ProgramareNumerele echilibrate dintr-un fișier, în ordinea inversă citirii #177ProgramareNumerele de două cifre dintr-un fișier, distincte și în ordine crescătoare #182ProgramareNumere divizibile cu 10 după eliminarea cifrelor impare #185ProgramareNumerele palindrom situate după primul număr par