Clasa a XII-a · Numere mariRead in English
Compararea a două numere mari în C++
În engleză: Comparing two big numbers
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)
- Capitol
- Numere mari
Exemple
Intrare
123456789012345678901 99999999999999999999
Ieșire așteptată
>
Intrare
1234 1243
Ieșire așteptată
<
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.
/*
* 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.