Giai Thừa (n < 23)

Nguồn: Bài tập nhập môn Độ khó: Dễ Vòng lặp Kiểu dữ liệu Tràn số Số lớn

Đề bài

Giai Thừa

Giới hạn thời gian: 1 giây. Giới hạn bộ nhớ: 524288 KB.

Viết chương trình nhập vào một số nguyên không âm $n$. Viết chương trình tính giai thừa $n!$. Biết $n! = 1 \times 2 \times 3 \times \ldots \times n$.

Input: Số nguyên không âm $n$ $(n \lt 23)$.

Output: In ra số nguyên là kết quả của việc tính giai thừa.

Ví dụ – input

3

Ví dụ – output

6

Lời mở đầu

Có bạn nhắn tin hỏi mình bài tập này, mình thấy cũng thú vị nè nên viết bài giải để anh em thử sức và tham khảo luôn 😇. Nhìn qua thì bài quá đơn giản, nhưng có một cái "bẫy" nho nhỏ nằm ngay ở giới hạn $n \lt 23$ mà nhiều bạn mới học hay bị dính.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ cho bạn nào chưa hiểu đề: với $n = 3$ thì $3! = 1 \times 2 \times 3 = 6$ ⇒ in ra 6. Lưu ý theo quy ước toán học $0! = 1$ (tích rỗng), nên với $n = 0$ ta in ra $1$.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vòng lặp + kiểu double · O(N)Cách 2Mở rộng: nhân số lớn (Big Int) · tính được cả 1000!

Cách 1Vòng lặp nhân dồn, lưu bằng double – O(N)

Bài này không có cách nào khác ngoài việc làm đúng theo công thức tính giai thừa: đi tính tích từ $1$ đến $N$. Có thể dùng vòng lặp hay đệ quy đều được, nhưng dùng vòng lặp thì sẽ tối ưu hơn (nhanh hơn được xíu ^^, không tốn bộ nhớ cho các lời gọi hàm).

Cái bẫy: 22! lớn cỡ nào?

Vấn đề không đơn giản của bài nằm ở chỗ $N \lt 23$, tức là tối đa $N$ có thể là $22$. Tính nhanh bằng máy tính thì:

22! = 1,124,000,727,777,607,680,000 (22 chữ số)

Trong khi đó kiểu số nguyên lớn nhất mà C/C++ hỗ trợ sẵn là số nguyên không dấu 64 bit unsigned long long, cũng chỉ lưu được tối đa $2^{64} - 1$ = 18,446,744,073,709,551,615 (20 chữ số) ⇒ không lưu nổi giá trị của $22!$ (thật ra từ $21!$ đã tràn rồi). Còn int thì từ $13!$ là tràn, long long có dấu thì từ $21!$ là tràn.

Bẫy tràn số

Bạn nào khai báo int hay long long rồi nhân dồn thì vẫn ra đúng ví dụ $3! = 6$, nhưng nộp lên sẽ sai ở các test $n$ lớn. Code đệ quy kiểu int gthua(int a) cũng vậy, và còn sai luôn với $n = 0$ nếu điều kiện dừng là a == 1 (đệ quy không dừng).

Lúc này ta có thể nghĩ tới việc xử lý số lớn: dùng chuỗi/mảng để cài đặt phép nhân giống quy tắc hồi tiểu học (bài toán Big Int). Nhưng như vậy thì lại phải cài đặt phức tạp thêm (mình để ở Cách 2 cho bạn nào muốn tìm hiểu). Với bài này có hướng khác đơn giản hơn nhiều:

Phá cách tư duy: dùng kiểu số thực double

Nhân các số nguyên với nhau thì chắc chắn ra số nguyên, nên ai cũng chỉ nghĩ tới kiểu số nguyên – mà kiểu số nguyên lớn nhất cũng không chứa nổi. Hãy chọn kiểu số thực double: double lưu được giá trị rất lớn (tới cỡ $10^{308}$), và $22!$ vẫn được lưu chính xác.
Khi in thì nhớ chỉ in phần trước dấu chấm: dùng printf("%.0lf", s). Nếu quên chỗ này thì với $3!$ sẽ in ra 6.000000, không đúng với kết quả, mình chỉ cần in 6 thôi.

Vì sao double lại lưu đúng được 22!?

double có 53 bit để lưu phần "chữ số có nghĩa" (khoảng 15–16 chữ số thập phân), phần còn lại là số mũ của 2. $22! = 2^{19} \times 2\,143\,861\,251\,406\,875$, mà phần lẻ $2\,143\,861\,251\,406\,875 \lt 2^{53} \approx 9 \cdot 10^{15}$ ⇒ biểu diễn được chính xác. Sang $23!$ thì phần lẻ vượt $2^{53}$ nên bị làm tròn ⇒ sai. May mắn bài này giới hạn tối đa $N$ cũng chỉ là $22$ 😁.

Minh hoạ

Em nhập $n$ rồi bấm Tiếp để xem từng bước nhân: cột "giá trị đúng" là $i!$ thật sự, cột double là giá trị mà biến double đang giữ (in bằng %.0lf), cột unsigned long long là giá trị nếu dùng kiểu số nguyên 64 bit. Ô đỏ là bị sai. Thử $n = 25$ để thấy double bắt đầu sai từ $23!$ nhé:

n

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int n;
    cin >> n;
    double s = 1;
    for(int i = 2; i <= n; ++i){
        s *= i;
    }
    printf("%.0lf", s);
    return 0;
}

n = int(input())
s = 1  # số nguyên của Python không giới hạn độ lớn nên không lo tràn số
for i in range(2, n + 1):
    s *= i
print(s)

Riêng với Python

Số nguyên của Python tự mở rộng không giới hạn độ lớn, nên bản Python cứ nhân thẳng bằng số nguyên là ra đúng, không cần "mẹo" double (dùng float trong Python còn bị in ra dạng 1.1240007277776077e+21 nữa).

C++▶ Chạy tay từng dòng codeNhân dồn từ 2 đến n vào biến double s, in phần nguyên bằng %.0lf.

Dữ liệu vào (stdin) – sửa thoải mái3

Dữ liệu mẫu:

1#include <iostream>

2#include <cstdio>

3using namespace std;

4

5int main() {

6 int n;

7 cin >> n;

8 double s = 1;

9 for(int i = 2; i <= n; ++i){

10 s *= i;

11 }

12 printf("%.0lf", s);

13 return 0;

14}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ dùng vài biến ⇒ $O(1)$.
• Thời gian: một vòng lặp từ 2 đến $N$ ⇒ $O(N)$, với $N \le 22$ thì chạy tức thì nha các bạn.

Không gian$O(1)$

Thời gian$O(N)$

Muốn tính lớn hơn 22! một chút?

Nếu các bạn thử nghiệm sẽ thấy double chỉ tính đúng tới $22!$ là hết mức, sang $23!$ là ra kết quả sai. Nếu cần tính lớn hơn thì có thể chọn kiểu long double, nó lưu được nhiều hơn double; đặc tả in của long double là %Lf (L hoa nhé, khác với double là l thường), tức là printf("%.0Lf", s). Thay double thành long double trong code trên thì tính chính xác được tới $25!$, còn từ $26!$ trở lên sẽ ra kết quả sai (mình đã chạy thử trên g++ Linux; riêng một số trình biên dịch trên Windows coi long double giống hệt double nên cần cẩn thận). Lúc đó chỉ còn cách xử lý số lớn như Cách 2.

Cách 2Mở rộng: nhân số lớn theo quy tắc tiểu học (Big Int) – O(N · D)

Phần này dành cho bạn nào muốn tính giai thừa lớn hơn nữa, ví dụ $1000!$ (có tới 2568 chữ số). Với bài này thì không cần, nhưng biết thêm thì chẳng thiệt gì 😁.

Ý tưởng: lưu kết quả thành một mảng các chữ số, lưu ngược (phần tử a[0] là hàng đơn vị) để khi có nhớ thì chỉ việc thêm chữ số vào cuối mảng. Mỗi lần nhân với $i$ (một số nhỏ), ta làm y như nhân tay hồi tiểu học: đi từ hàng đơn vị lên, mỗi chữ số nhân với $i$ rồi cộng phần nhớ, giữ lại chữ số hàng đơn vị, phần còn lại nhớ sang hàng tiếp theo. Cuối cùng còn nhớ bao nhiêu thì viết thêm vào đầu số (cuối mảng).

Ví dụ: 720 × 7 (tính 7! từ 6! = 720)

Mảng lưu ngược: a = [0, 2, 7], nhớ = 0.

• $j = 0$: $0 \times 7 + 0 = 0$ ⇒ a[0] = 0, nhớ $0$.
• $j = 1$: $2 \times 7 + 0 = 14$ ⇒ a[1] = 4, nhớ $1$.
• $j = 2$: $7 \times 7 + 1 = 50$ ⇒ a[2] = 0, nhớ $5$.
• Còn nhớ $5$ ⇒ thêm vào cuối: a = [0, 4, 0, 5], đọc ngược lại là 5040 = $7!$ ✔.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main() {
    int n;
    cin >> n;
    vector<int> a(1, 1); // các chữ số của kết quả, lưu ngược: a[0] là hàng đơn vị
    for(int i = 2; i <= n; ++i){
        int nho = 0;
        for(int j = 0; j < (int)a.size(); ++j){
            int x = a[j] * i + nho;
            a[j] = x % 10;
            nho = x / 10;
        }
        while(nho > 0){
            a.push_back(nho % 10);
            nho /= 10;
        }
    }
    for(int j = (int)a.size() - 1; j >= 0; --j){
        cout << a[j];
    }
    return 0;
}

n = int(input())
a = [1]  # các chữ số của kết quả, lưu ngược: a[0] là hàng đơn vị
for i in range(2, n + 1):
    nho = 0
    for j in range(len(a)):
        x = a[j] * i + nho
        a[j] = x % 10
        nho = x // 10
    while nho > 0:
        a.append(nho % 10)
        nho //= 10
print(''.join(str(d) for d in reversed(a)))

Đánh giá độ phức tạp của cách làm này: gọi $D$ là số chữ số của $N!$ (với $N = 1000$ thì $D = 2568$).

• Không gian: mảng chữ số ⇒ $O(D)$.
• Thời gian: mỗi lần nhân duyệt hết mảng ⇒ $O(N \cdot D)$, với $N = 1000$ chỉ khoảng 2.5 triệu phép tính, chạy tức thì.

Không gian$O(D)$

Thời gian$O(N \cdot D)$

Ghi chú của mình: code C++ và Python của cả 2 cách đã được chạy với mọi $n$ từ 0 đến 22, so với giá trị giai thừa chính xác – khớp hết. Mình cũng chạy thử với $n = 23, 25, 26$: bản double ra sai đúng như phân tích, bản long double (g++ Linux) đúng tới $25!$ và sai từ $26!$; còn Cách 2 ra đúng cả $1000!$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇