Tính giai thừa (factorial) trong C++

1. Giai thừa (factorial) là gì?

Cho n là một số nguyên dương, giai thừa (factorial) của n là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng n. Và được gọi là n giai thừa (ký hiệu là n!) với n! = 1 × 2 × 3 × … × n. Ví dụ: 8! = 1 × 2 × 3 × … × 7 × 8 = 40.320.

Lưu ý, với n = 0 thì chúng ta quy ước 0! = 1.

Ngoài ra, chúng ta có thể định nghĩa đệ quy n! như sau:

1. 0! = 1

2. (n + 1)! = n! × (n + 1) với n> 0

Bảng bên dưới cho biết kết quả tính giai thừa của một vài số nguyên dương.

Dễ thấy, giai thừa của các số nguyên dương càng ngày càng lớn. Do đó, nên sử dụng kiểu dữ liệu phù hợp trong C++ khi lưu trữ các giá trị này.

2. Tính giai thừa sử dụng vòng lặp (loop) trong C++

Đoạn code bên dưới sử dụng vòng lặp for để tính giai thừa của một số nguyên dương trong C++.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cout << "Nhap vao mot so nguyen: ";
    cin >> n;
    unsigned long int fact = 1;
    if (n != 0 || n != 1) {
        for (int i = 2; i <= n; i++) {
            fact = fact * i;
        }
    }
    cout<<"Factorial of "<<n<<" is "<<fact;
    return 0;
}

Có thể thay vòng lặp for bằng vòng lặp while như sau:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cout << "Nhap vao mot so nguyen: ";
    cin >> n;
    unsigned long int fact = 1;
    if (n != 0 && n != 1) {
        int i = 2;
        while(i<=n) {
            fact = fact * i;
            i++;
        }
    }
    cout<<"Factorial of "<<n<<" is "<<fact;
    return 0;
}

Chúng ta đang sử dụng kiểu dữ liệu unsigned long int để lưu kết quả giai thừa tính được. Nếu cần tính giai thừa của những số nguyên lớn thì có thể sử dụng vector để lưu giá trị giai thừa tính được. Vì kiểu unsigned long int không thể lưu được những giá trị lớn hơn. Xem phần 4 để rõ hơn về cách sử dụng vector trong tính giai thừa.

3. Tính giai thừa sử dụng đệ quy (recursion) trong C++

Chúng ta có thể định nghĩa đệ quy n! như sau:

1. 0! = 1

2. (n + 1)! = n! × (n + 1) với n> 0

Đoạn code bên dưới sử dụng đệ quy để tính giai thừa của một số nguyên dương trong C++.

#include <iostream>
using namespace std;

unsigned long int factorialUsingRecursion(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorialUsingRecursion(n - 1);
}

int main()
{
    int n;
    cout << "Nhap vao mot so nguyen: ";
    cin >> n;
    unsigned long int fact = factorialUsingRecursion(n);
    cout<<"Factorial of "<<n<<" is "<<fact;
    return 0;
}

4. Tính giai thừa cho số lớn trong C++

Kiểu dữ liệu long chỉ được sử dụng để lưu kết quả giai thừa của các số nguyên dương nhỏ. Để lưu giai thừa của các số nguyên dương lớn hơn, chúng ta có thể sử dụng vector để lưu trữ giá trị giai thừa lớn.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Nhan tung chu so cua num cho mot so nguyen duong
vector<int> multiply(vector<int>& num, int x) {
    vector<int> result;
    int carry = 0;
    for (int i = 0; i < num.size(); ++i) {
        int prod = num[i] * x + carry;
        result.push_back(prod % 10);
        carry = prod / 10;
    }
    while (carry) {
        result.push_back(carry % 10);
        carry /= 10;
    }
    return result;
}

// Tinh giai thua
vector<int> factorial(int n) {
    vector<int> result;
    result.push_back(1); // Giai thua cua 0 là 1
    for (int i = 2; i <= n; ++i) {
        result = multiply(result, i);
    }
    reverse(result.begin(), result.end());
    return result;
}

// In ket qua giai thua
void printFactorial(vector<int>& num) {
    for (int i = 0; i <=num.size() - 1; i++) {
        cout << num[i];
    }
    cout << endl;
}

int main() {
    int n;
    cout << "Nhap vao mot so nguyen: ";
    cin >> n;
    vector<int> result = factorial(n);
    cout << "Giai thua cua " << n << " la: ";
    printFactorial(result);
    return 0;
}

Trong chương trình trên, chúng ta sử dụng một vector<int> để lưu trữ các chữ số của giá trị giai thừa lớn. Hàm multiply thực hiện phép nhân của của một số nguyên dương với một chữ số. Hàm factorial tính giai thừa bằng cách sử dụng vòng lặp và gọi hàm multiply. Cuối cùng, chúng ta in ra kết quả giai thừa bằng cách duyệt qua vector<int> và in từng chữ số.

Bài này đã trình bày cách sử dụng vòng lặp và đệ quy để tính giai thừa trong C++. Các bạn cần lưu ý sử dụng kiểu dữ liệu long hoặc sử dụng vector để lưu kết quả giai thừa.