Factorial

Q: Độ phức tạp thời gian của việc tính giai thừa là bao nhiêu?

Cả vòng lặp lẫn đệ quy đều thực hiện một phép nhân cho mỗi số đến n : thời gian O(n) . Vòng lặp cần thêm không gian O(1) . Đệ quy giữ lại một khung ngăn xếp cho mỗi lần gọi cho đến khi trường hợp cơ sở trả về, nên dùng không gian O(n) .

Q: Tại sao 0! bằng 1?

0! là tích của không số nào, và tích không có thừa số nào bằng 1 , cũng giống như tổng không có số hạng nào bằng 0 . Nhờ vậy, đẳng thức n! = n × (n-1)! vẫn đúng khi n = 1 . Và chỉ có đúng một cách sắp xếp không món đồ nào.

Q: Giai thừa lớn nhất nào có thể chứa trong một số nguyên?

12! = 479001600 là giai thừa lớn nhất có thể chứa trong số nguyên có dấu 32 bit. 20! = 2432902008176640000 là giai thừa lớn nhất có thể chứa trong số nguyên có dấu 64 bit. Lớn hơn nữa, bạn cần các số có kích thước không giới hạn, chẳng hạn như int của Python, BigInteger của Java hoặc BigInt của JavaScript.

Người mớiToán và mô phỏng Đệ quy

+10

Giai thừa của một số nguyên không âm n, được viết là n!, là tích của mọi số nguyên từ 1 đến n. Ví dụ, 4! = 1 × 2 × 3 × 4 = 24. Theo định nghĩa, 0! = 1. Hàm của bạn nhận n và trả về n!.

Hàm

factorial(n: integer) → integer

ninteger: số nguyên mà bạn tính giai thừa
Trả vềinteger: tích của mọi số nguyên từ 1 đến n, bằng 1 khi n bằng 0

Ràng buộc

0 ≤ n ≤ 12
Đáp án nằm trong phạm vi số nguyên có dấu 32 bit: số lớn nhất là 12! = 479001600.

Ví dụ

Đầu vào: n = 5
Đầu ra: 120
Giải thích: Nhân 1 × 2 × 3 × 4 × 5. Tích lũy tiến lần lượt là 1, 2, 6, 24 và kết thúc ở 120.

Đầu vào: n = 0
Đầu ra: 1
Giải thích: Không có gì để nhân, và tích không có thừa số nào bằng 1. Đó là lý do vì sao 0! = 1.

Câu hỏi mở rộng

100! có 158 chữ số. Bạn có thể đếm xem nó có bao nhiêu số 0 ở cuối mà không cần tính giá trị không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một giai thừa có hai cách mô tả tương đương, và mỗi cách đều có thể viết thành code. Dưới dạng tích, n! = 1 × 2 × ... × n là một vòng lặp. Theo định nghĩa đệ quy, 0! = 1 và n! = n × (n-1)! là một hàm tự gọi chính nó. Cả hai đều thực hiện khoảng n phép nhân; vòng lặp không cần ngăn xếp lời gọi.

Đệ quy từ định nghĩa

Ý tưởng

Nếu bạn biết 4! = 24, thì 5! = 5 × 24 = 120. Vì vậy, factorial(n) gọi factorial(n-1) rồi nhân kết quả với n. Trường hợp cơ sở factorial(0) trả về 1 mà không gọi hàm nào. Bắt đầu từ 5, các lời gọi giảm dần theo thứ tự 5, 4, 3, 2, 1, 0, rồi kết quả lần lượt quay ngược lên: 1, 1, 2, 6, 24, 120.

Có n + 1 lời gọi và n phép nhân: độ phức tạp thời gian O(n). Mỗi lời gọi chờ trên ngăn xếp cho đến khi lời gọi bên dưới hoàn tất, nên ngăn xếp chứa n + 1 khung, độ phức tạp không gian O(n).

Thuật toán

Nếu n bằng 0, trả về 1. Đây là trường hợp cơ sở.
Nếu không, hãy gọi hàm với n-1.
Nhân kết quả đó với n rồi trả về kết quả.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

Nhân trong vòng lặp

Ý tưởng

Chuyển đệ quy thành phép nhân tích lũy: bắt đầu với result = 1, rồi nhân với 2, sau đó là 3, cứ tiếp tục như vậy cho đến n. Bắt đầu từ 1 cũng xử lý được cả n = 0 và n = 1: vòng lặp từ 2 đến n chạy 0 lần và trả về 1, đáp án đúng cho cả hai trường hợp.

Cách này cần n-1 phép nhân, có thời gian O(n) và dùng một số, tức bộ nhớ O(1), không có ngăn xếp lời gọi nào có thể bị tràn.

Thuật toán

Đặt result = 1.
Lặp k từ 2 đến n, bao gồm cả hai giá trị.
Nhân result với k ở mỗi bước.
Trả về result.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Lỗi thường gặp và trường hợp biên

Khởi tạo tích bằng 0. Mọi phép nhân đều giữ tích ở mức 0, vì vậy hãy bắt đầu bằng 1.
Dừng đệ quy chỉ khi n == 1. Khi được gọi với 0, hàm tiếp tục chạy với -1, -2, rồi cứ thế cho đến khi ngăn xếp bị tràn. Hãy dùng n == 0 làm trường hợp cơ sở.
Lặp với k < n thay vì k ≤ n. Cách này bỏ sót thừa số cuối cùng, nên 5 cho kết quả 24 thay vì 120.
Trong Swift, viết for k in 2...n. Phạm vi đóng có giá trị cuối nhỏ hơn giá trị đầu sẽ gây lỗi khi chạy nếu n là 0 hoặc 1.

Câu hỏi thường gặp3

Độ phức tạp thời gian của việc tính giai thừa là bao nhiêu?

Cả vòng lặp lẫn đệ quy đều thực hiện một phép nhân cho mỗi số đến n: thời gian O(n). Vòng lặp cần thêm không gian O(1). Đệ quy giữ lại một khung ngăn xếp cho mỗi lần gọi cho đến khi trường hợp cơ sở trả về, nên dùng không gian O(n).

Tại sao 0! bằng 1?

0! là tích của không số nào, và tích không có thừa số nào bằng 1, cũng giống như tổng không có số hạng nào bằng 0. Nhờ vậy, đẳng thức n! = n × (n-1)! vẫn đúng khi n = 1. Và chỉ có đúng một cách sắp xếp không món đồ nào.

Giai thừa lớn nhất nào có thể chứa trong một số nguyên?

12! = 479001600 là giai thừa lớn nhất có thể chứa trong số nguyên có dấu 32 bit. 20! = 2432902008176640000 là giai thừa lớn nhất có thể chứa trong số nguyên có dấu 64 bit. Lớn hơn nữa, bạn cần các số có kích thước không giới hạn, chẳng hạn như int của Python, BigInteger của Java hoặc BigInt của JavaScript.

def factorial(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

n = 5

Đầu ra mong đợi