Clasa a XII-a · Numere mariRead in English

Compararea a două numere mari în C++

În engleză: Comparing two big numbers

O(n)C++1765 de linii3 exemple

Ideea

Fără zerouri nesemnificative, numărul cu mai multe cifre este mai mare. Dacă au același număr de cifre, le comparăm de la cifra cea mai semnificativă (ultimul indice din vector) spre unități; prima poziție pe care diferă decide rezultatul. Programul afișează unul dintre semnele <, = sau > între primul și al doilea număr.

Descrierea în engleză

Without leading zeros, the number with more digits is larger. If they have the same number of digits, we compare them from the most significant digit (the last index in the array) towards the units; the first position where they differ decides the result. The program prints one of the signs <, = or > between the first and the second number.

Complexitate
O(k), unde k este numărul de cifre al numerelor
Clasa
Clasa a XII-a (Grade 12)

Exemple

Exemplul 1

Intrare

123456789012345678901 99999999999999999999

Ieșire așteptată

>
Exemplul 2

Intrare

1234 1243

Ieșire așteptată

<
Exemplul 3

Intrare

0050 50

Ieșire așteptată

=

Codul C++

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

compararea-a-doua-numere-mari.cpp
/*
 * Titlu: Compararea a două numere mari
 * Clasa: 12
 * Capitol: Numere mari
 * Descriere: Fără zerouri nesemnificative, numărul cu mai multe cifre este mai
 *            mare. Dacă au același număr de cifre, le comparăm de la cifra cea
 *            mai semnificativă (ultimul indice din vector) spre unități; prima
 *            poziție pe care diferă decide rezultatul. Programul afișează unul
 *            dintre semnele <, = sau > între primul și al doilea număr.
 * Complexitate: O(k), unde k este numărul de cifre al numerelor
 *
 * Exemplu
 * Intrare: 123456789012345678901 99999999999999999999
 * Ieșire: >
 *
 * Exemplu
 * Intrare: 1234 1243
 * Ieșire: <
 *
 * Exemplu
 * Intrare: 0050 50
 * Ieșire: =
 */
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> citesteNumar(const string &s)
{
    vector<int> a;
    for (int i = (int)s.size() - 1; i >= 0; i--)
        a.push_back(s[i] - '0');
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
    return a;
}

// Întoarce -1 dacă a < b, 0 dacă a = b și 1 dacă a > b.
int compara(const vector<int> &a, const vector<int> &b)
{
    if (a.size() != b.size())
        return a.size() < b.size() ? -1 : 1;
    for (int i = (int)a.size() - 1; i >= 0; i--)
    {
        if (a[i] != b[i])
            return a[i] < b[i] ? -1 : 1;
    }
    return 0;
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int r = compara(citesteNumar(s1), citesteNumar(s2));
    if (r < 0)
        cout << "<\n";
    else if (r == 0)
        cout << "=\n";
    else
        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.