Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Numărul de cifre ale factorialului unui număr

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

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

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Numărul de apariții al unui număr într-un vector în C++Funcții în C++. Ce sunt subprogrameleCodul ASCII (tabel complet)Află secolul unui an citit de la tastatură în C++Matrice pătratice în C++. Diagonala principală și secundarăPrima cifră a unui număr în C++Divide et Impera (metodă de programare C++)Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorInstrucțiunea do while (structuri repetitive)Rădăcina cubică a unui număr în C++ (cube root)Interschimbarea a două variabile în C++ (3 metode)Câte numere naturale sunt într-un interval dat? (C++)Cel mai mic număr cu suma cifrelor N în C++Indicatorul lui Euler în C++Numărul de divizori primi ai unui număr în C++Maximul și minimul a trei valori în C++Verificare număr prim în C++ (Clasa a IX-a)Citește un șir de caractere cu spații în C++Valoarea absolută (modulul) unui număr în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Cifra maximă și minimă a unui număr în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Verifică dacă un caracter este cifră în C++Vectori de frecvență (de apariții) în C++Citirea și afișarea matricelor în C++Cum să calculezi instant 2 la puterea N în C++Șiruri de caractere în C++. Tot ce trebuie să știiCum să afișezi partea întreagă a unui număr real în C++Al N-lea termen dintr-o progresie geometricăInversarea unui șir de caractere în C++Ce este o variabilă unsigned în C++?Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Operații cu numere mari în C++ - Toate funcțiile explicateNumărul de cifre ale factorialului unui numărMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleTransformarea unei litere mari în literă mică în C++Verifică dacă trei puncte sunt coliniare C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Afișarea divizorilor primi ai unui număr în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Cea mai lungă secvență de elemente crescătoare în C++Aria și circumferința unui cerc în C++Numărul de divizori al unui număr în C++Factorialul unui număr în C++Recursivitate în C++Tipuri de date în C++: numere întregi, reale, caractere și alteleNumărul permutărilor în C++ (formula permutărilor)Verificarea unui an bisect în C++Verifică dacă o literă este mică sau mare în C++Structuri repetitive (while, do while, for, etc)Oglinditul unui număr în C++Cifra maximă a unui număr recursiv în C++Distanța dintre două puncte în C++Cum să citești și să afișezi în fișiere în C++Verifică dacă un număr este par sau impar fără modulo în C++Cel mai frecvent element dintr-un șir în C++Aria unui triunghi folosind coordonatele acestora în C++Verifică dacă un caracter este literă în C++Transformarea unui număr din baza 2 în baza 10 în C++Maximul și minimul unui vector în C++Al N-lea termen dintr-o progresie aritmeticăInversarea unui vector în C++Mediana unui șir de valori în C++Suma divizorilor unui număr în C++Generarea șirului Fibonacci generalizat în C++Verificare dacă un număr este palindrom în C++Calculul combinărilor de n luate câte k (nCk) în C++Maximul și minimul a n valori în C++Ciurul lui Eratostene în C++Comentarii în C++Afișarea elementelor unui vector recursiv în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Ce este o funcție void în C++?Verifică dacă un număr aparține șirului Fibonacci în C++Căutare binară în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăNumărul combinărilor în C++ (formula combinărilor)Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicCel mai puțin semnificativ bit în C++Transformarea unei litere mici în literă mare în C++Al N-lea termen Fibonacci în C++Instrucțiunea for (structuri repetitive)Verifică dacă un număr dat este o putere de 2 în C++Complexitatea unui algoritm (timp și spațiu) în C++Instrucțiunea while (structuri repetitive)Oglinditul recursiv al unui număr în C++Cifra de control a unui numărCombinatorică în C++: permutări, aranjamente, combinări și alteleCopiuțe: Cifrele unui numărAlgoritm recursiv pentru căutare binară (clasa a X-a)Instrucțiunea de decizie în C++: if, else, switch, caseCMMDC recursiv a două numere naturale în C++Vectorii în C++: declarare și parcurgereMaximul și minimul a două valori în C++Instrucțiunea break (structuri repetitive)Pointer în C++. Variabile de tipul char * (char steluță)Suma 1 + 2 + 3 + ... + N în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cel mai semnificativ bit în C++Ce înseamnă endl în C++?Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Tipul struct în C++. Ce sunt structurile de date neomogeneMateria pentru olimpiada de informatică - tot ce trebuie să știiVectorii în C++: citire și afișareTransformarea unui număr din baza 10 în baza 2 în C++Verifică dacă o literă este vocală în C++Radicalul unui număr în C++ (rădăcina pătrată)Cel mai mare divizor comun (CMMDC) a două numere în C++Ce înseamnă variabilă globală și locală în C++?Suma numerelor naturale dintr-un interval dat în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Șirul lui Fibonacci în C++Do while vs while în C++ - Care e diferența?Bordarea unei matrice în C++Numărul minim de peroane pentru o gară în C++Verificare dacă șir de caractere este palindrom în C++Instrucțiunea continue (structuri repetitive)Suma elementelor unui vector recursiv în C++Interclasarea a doi vectori în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Aflarea sumei primelor N sume GaussNumere triunghiulare. Verificarea unui număr triunghiularSortare crescătoare recursivă în C++ - Merge sort și Bubble sort

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont