Numărul de cifre ale factorialului unui număr
Dându-se un număr natural n
, vrem să aflăm numărul de cifre ale operației
n! = 1 * 2 * … * n
(n
factorial).
Exemple
Pentru n = 1
, răspunsul este 1
(1! = 1
are o cifră).
Pentru n = 5
, răspunsul este 3
(5! = 120
are trei cifre).
Pentru n = 0
, răspunsul este 1
(0! = 1
are o cifră).
Algoritm naiv de aflare a numărului de cifre ale factorialului
Un algoritm naiv calculează valoarea n!
, după care calculează numărul de
cifre ale acestuia. Acest algoritm nu este recomandat deloc, deoarece n!
crește foarte repede (13!
depășește tipul de date int
), iar folosirea
anumitor tehnici precum numerele mari este impractică, fiind ineficientă, în special pentru valori uriașe (n = 1.000.000
, spre exemplu).
Algoritm eficient de aflare a numărului de cifre ale factorialului
Vom folosi logaritmii pentru a simplifica calculul nostru. Operațiile
prezentate sunt notate cu lg
, reprezentând logaritmul în baza 10
a unui
număr.
Proprietăți știute
În primul rând, lg(a * b) = lg(a) + lg(b)
.
De asemenea, [lg(x)] + 1 = numărul de cifre ale numărului x
(în baza 10
),
unde [x]
reprezintă partea întreagă a numărului x
.
Algoritmul explicat
Din a doua proprietate, deducem că noi trebuie să aflăm valoarea [lg(n!)] + 1
.
Așadar, ne propunem să aflăm valaorea lg(n!)
. Din proprietățile de mai sus
găsim că lg(n!) = lg(1 * 2 * 3 * … * n) = lg(1) + lg(2) + lg(3) + … + lg(n)
.
Practic am redus problema la ceva rezolvabil: logaritmii numerelor se află repede, iar însumându-i și aplicând formula de mai sus, putem găsi ușor răspunsul dorit.
Rezolvare în C++
Vom asuma că numărul citit este natural (n ≥ 0
).
#include <iostream>
#include <cmath>
using namespace std;
int nFactorialCifre(int x) {
double suma = 0;
for(int i = 1; i <= x; i++) {
suma += log10(i);
}
//suma conține valoarea lg(1) + lg(2) + … + lg(n) = lg(n!)
return floor(suma) + 1; // [lg(n!)] + 1, adică numărul de cifre ale lui n!
}
int main()
{
int n;
cin >> n;
cout << nFactorialCifre(n);
return 0;
}
Bibliografie sau alte resurse
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0