Factorial și ridicare la putere

În multe probleme avem nevoie să calculăm expresii matematice precum:

• 5! = 1 × 2 × 3 × 4 × 5 = 120
• 2^10 = 1024

Ambele se bazează pe înmulțiri repetate și se rezolvă ușor cu o buclă for.

Ce este factorialul?

Factorialul unui număr natural n, notat n!, este produsul tuturor numerelor naturale de la 1 la n.

n! = 1 × 2 × 3 × ... × n

Cazuri speciale:

• 0! = 1 (prin convenție)
• 1! = 1

Exemple

Calculul factorialului

Ideea:

• pornim cu un produs egal cu 1;
• înmulțim pe rând cu 1, 2, 3, ..., n.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int factorial = 1;

    for (int i = 1; i <= n; i++) {
        factorial = factorial * i;
    }

    cout << factorial;

    return 0;
}

Input:
5

Output:
120

Pas cu pas pentru n = 5

Factorialul cu long long

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    long long factorial = 1;

    for (int i = 1; i <= n; i++) {
        factorial = factorial * i;
    }

    cout << factorial;

    return 0;
}

Input:
15

Output:
1307674368000

Ridicarea la putere

Ridicarea la putere înseamnă să înmulțim o bază b cu ea însăși de n ori:

b^n = b × b × b × ... × b (de n ori)

Cazuri speciale:

• b^0 = 1 (orice număr la puterea 0 este 1)
• b^1 = b

Exemple

Calculul puterii

#include <iostream>
using namespace std;

int main()
{
    int b, n;
    cin >> b >> n;

    long long putere = 1;

    for (int i = 1; i <= n; i++) {
        putere = putere * b;
    }

    cout << putere;

    return 0;
}

Input:
2 10

Output:
1024

Pas cu pas pentru b = 2, n = 5

Ultima cifră a unei puteri

O problemă frecventă: care este ultima cifră a lui b^n?

Nu trebuie să calculăm toată puterea (ar fi uriașă). La fiecare pas, păstrăm doar ultima cifră:

#include <iostream>
using namespace std;

int main()
{
    int b, n;
    cin >> b >> n;

    int ultima = 1;

    for (int i = 1; i <= n; i++) {
        ultima = (ultima * b) % 10;
    }

    cout << ultima;

    return 0;
}

Input:
7 100

Output:
1

Combinarea: n! are ultima cifră…

Pentru n >= 5, factorialul conține factorul 2 × 5 = 10, deci n! se termină cu 0.

Dar pentru n < 5, putem calcula:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int ultima = 1;

    for (int i = 1; i <= n; i++) {
        ultima = (ultima * i) % 10;
    }

    cout << ultima;

    return 0;
}

Input:
4

Output:
4

Explicație: 4! = 24, ultima cifră este 4.

Greșeli frecvente

1. Inițializarea produsului cu 0

int factorial = 0; // GREȘIT

Dacă pornim de la 0, orice înmulțire va da 0. Produsul trebuie inițializat cu 1.

2. Depășirea la factorial

13! depășește int. Folosește long long dacă n poate fi mai mare de 12.

3. Confuzia între factorial și putere

• Factorial: 5! = 1 × 2 × 3 × 4 × 5 - înmulțim numerele de la 1 la n
• Putere: 2^5 = 2 × 2 × 2 × 2 × 2 - înmulțim baza cu ea însăși de n ori

4. Uitarea cazului n = 0

Atât 0! = 1 cât și b^0 = 1. Bucla for de la 1 la 0 nu se execută, deci rezultatul rămâne 1 - ceea ce este corect.

Ce să reții

• Factorialul: n! = 1 × 2 × ... × n. Se calculează cu un for și un produs care pornește de la 1.
• Puterea: b^n = b × b × ... × b. Aceeași idee, dar înmulțim mereu cu b.
• Produsul se inițializează cu 1, niciodată cu 0.
• Folosește long long pentru valori mari.
• Pentru ultima cifră, aplică % 10 la fiecare pas.

Probleme

pbinfoFactorial→

pbinfoFactzero→

pbinfoPower→