Simplificarea fracțiilor

De ce contează?

Tai o pizza în 24 de felii și iei 18. Sau o tai în 4 sferturi și iei 3. E aceeași cantitate: 18/24 și 3/4 reprezintă exact aceeași bucată. Simplificarea înseamnă să găsești cea mai „curată" scriere a aceleiași fracții.

Ideea: scoatem factorul comun maxim

O fracție a/b se simplifică împărțind numărătorul și numitorul la același număr. Cea mai eficientă alegere e chiar cmmdc-ul lor — îl scoate dintr-un singur pas:

a/b ireductibilă: a / cmmdc(a, b) peste b / cmmdc(a, b)

După împărțire, noul numărător și numitor sunt prime între ele — nu mai au ce simplifica.

Algoritm pas cu pas: 18/24

cmmdc(18, 24) = 6.
Numărător: 18 / 6 = 3.
Numitor: 24 / 6 = 4.
Rezultat: 3/4.

Observația-cheie

Dacă ai împărți pas cu pas (întâi la 2, apoi la 3...) ai ajunge la același rezultat, dar cu mai mulți pași. Împărțirea la cmmdc face totul dintr-o singură mișcare.

Implementare C++

#include <iostream>
using namespace std;

int cmmdc(int a, int b) {
    while (b != 0) {
        int rest = a % b;
        a = b;
        b = rest;
    }
    return a;
}

int main() {
    int a, b;
    cin >> a >> b;          // numarator, numitor
    int d = cmmdc(a, b);
    cout << a / d << "/" << b / d << "\n";   // 18 24 -> 3/4
    return 0;
}

Verificare: fracția e ireductibilă?

O fracție e deja în forma cea mai simplă dacă cmmdc(a, b) == 1 — adică numărătorul și numitorul sunt prime între ele.

if (cmmdc(a, b) == 1) cout << "deja ireductibila\n";

Complexitate

Caz	Timp	Spațiu
oricare	O(log(min(a, b)))	O(1)

Un apel cmmdc plus două împărțiri — costul e dat de Euclid.

Greșeli frecvente

Capcane reale la simplificarea fracțiilor:

Simplificare incompletă: împarți doar la 2 sau la o cifră comună evidentă și lași fracția neredusă complet (ex. 6/8 în loc de 3/4). Împarte la cmmdc.
Numitor zero: o fracție cu numitor 0 nu există — tratează b = 0 separat.
Împărțirea numai a numărătorului: trebuie împărțiți ambii termeni la același cmmdc, altfel schimbi valoarea fracției.
Semnul: la fracții negative, decide unde pui semnul (de obicei la numărător) și lucrează cu valori absolute la cmmdc.

De reținut

a/b ireductibilă = împarți ambii termeni la cmmdc(a, b).
După simplificare, numărător și numitor sunt prime între ele (cmmdc = 1).
Cost O(log) — un singur Euclid, nu împărțiri repetate la factori mici.