O proprietate interesanta a fracțiilor ireductibile este ca orice fracție se poate obține după următoarele reguli:
- pe primul nivel se afla fracția 1/1;
- pe al doilea nivel, în stânga fracției 1/1 de pe primul nivel, plasam fracția 1/2 iar în dreapta ei fracția 2/1;

nivelul 1: 1/1
nivelul 2: 1/2 2/1

- pe fiecare nivel k se plasează sub fiecare fracție i / j de pe nivelul de deasupra, fracția i / (i + j) în stânga, iar fracția (i + j) / j în dreapta.

nivelul 1: 1/1
nivelul 2: 1/2 2/1
nivelul 3: 1/3 3/2 2/3 3/1

Cerința

Dându-se o fracție oarecare prin numărătorul și numitorul său, determinați numărul nivelului pe care se află fracția sau o fracție echivalentă (având aceeași valoare) cu aceasta.

Date de intrare

Fișierul de intrare fractzii.in conține pe prima linie două numere naturale nenule N M, separate printr-un spațiu, reprezentând numărătorul și respectiv numitorul unei fracții.

Date de ieșire

Fișierul de ieșire fractzii.out va conţine o ingură linie, pe care va fi scris număr natural nenul, reprezentând numărul nivelului care corespunde fracţiei.

Restricții și precizări

1 ≤ N, M ≤ 2 000 000 000

Exemplul 1:

fractzii.in

13 8

fractzii.out

Exemplul 2:

fractzii.in

12 8

fractzii.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Fractzii:

#include <bits/stdc++.h>
using namespace std;

int Cmmdc(int a, int b)
{
    int r;
    while (b > 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    int n, m, c, niv = 0;
    ifstream fin("fractzii.in");
    ofstream fout("fractzii.out");
    fin >> n >> m;
    c = Cmmdc(n, m);
    n /= c;
    m /= c;
    while (n != 1 && m != 1)
    {
        if (n > m)
        {
            niv += (n / m);
            n = n % m;
        }
        else
        {
            niv += (m  / n);
            m = m % n;
        }
    }
    niv += max(n, m);
    fout << niv << "\n";
    fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2308 Fractzii

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2308 Fractzii de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2308 Fractzii