Cách tính giai thừa của một số
Giai thừa của một số là một khái niệm toán học quan trọng. Bạn có thể sử dụng nó để thực hiện hoán vị và kết hợp, viết biểu thức hàm mũ và logarit, cũng như tính toán xác suất.
Bạn sử dụng nó để tìm ra số lượng các cách khác nhau mà bạn có thể thiết kế sắp xếp chỗ ngồi hoặc chọn áo phông cho kỳ nghỉ của bạn đến Maldives. Nhưng làm thế nào bạn có thể tính giai thừa của một số?
Mục Lục
Giai thừa của một số là gì?
Giai thừa của một số dương là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng giá trị của chính số đó. Một số theo sau là dấu chấm than (!) Biểu thị giai thừa của một số. Bạn đại diện cho giai thừa của năm là 5! và tính toán nó như sau:
5! = 5 * 4 * 3 * 2 * 1 = 120
Một cách khác để hình dung nó là:
5! = 5 * 4! nơi 4! = 4 * 3 !, 3! = 3 * 2! và cứ tiếp tục như vậy cho đến khi bạn nhận được 1! = 1 * 0! là 1.
Bạn sẽ sử dụng khái niệm này để xây dựng chương trình giai thừa của chúng tôi bằng cách sử dụng một khái niệm phổ biến được gọi là đệ quy.
Đệ quy là gì?
Đệ quy là một quá trình trong đó một hàm gọi chính nó. Một trong những ưu điểm chính của quá trình này là nó chia một vấn đề lớn hơn thành các phần nhỏ hơn. Điều này làm cho vấn đề dễ giải quyết hơn.
Bạn có thể sử dụng đệ quy để giải các bài toán thích hợp theo ba bước đơn giản:
- Tìm trường hợp cơ sở: Nếu một hàm luôn gọi chính nó, quá trình sẽ là vô hạn. Để ngăn điều này xảy ra, hãy xác định một trường hợp cơ sở trở thành điểm dừng hợp lý cho hàm của bạn. Ví dụ, trong chương trình giai thừa, dừng phép tính ở số không. Điều này trở thành trường hợp cơ bản cho vấn đề.
- Tìm mối quan hệ giữa bài toán và các bài toán con: Chia vấn đề lớn hơn thành một vấn đề con. Ví dụ, vấn đề là tìm giai thừa của năm. Giả sử bạn có câu trả lời là giai thừa của bốn, tức là 24. Bạn sẽ lấy giai thừa của năm bằng cách sử dụng 24 như thế nào? Bằng cách nhân năm chính nó vào nó. Đây là mối quan hệ giữa bài toán và bài toán con.
- Tổng quát hóa mối quan hệ được tìm thấy trong Bước 2: Bây giờ bạn đã có mối quan hệ, hãy tổng quát hóa nó dưới dạng n. Vì vậy, giai thừa của một số n là tích của n và giai thừa của n-1.
Bạn có thể sử dụng khái niệm này để tìm tổng của n số tự nhiên, tính GCD, LCM, chuỗi Fibonacci và kiểm tra các số nguyên tố.
Mã giả cho hàm thừa sử dụng đệ quy
Đây là cách bạn sử dụng đệ quy và viết mã giả để xây dựng chương trình của bạn bằng bất kỳ ngôn ngữ nào. Với các ngôn ngữ khác nhau, cú pháp và cách thực thi thay đổi nhưng logic vẫn nguyên vẹn.
function Fact(n)
If n == 0 then
Return 1
Return n * Call Fact(n - 1)
Chương trình giai thừa trong C
C là ngôn ngữ lập trình cấp cao, độc lập với nền tảng đầu tiên. Nó có cú pháp chặt chẽ, phân biệt chữ hoa chữ thường và thực thi mã với tốc độ nhanh nhất. Nó là một ngôn ngữ lập trình thủ tục và do đó bạn khai báo bất kỳ hàm nào trên đầu chính hàm số. Đây là cách bạn có thể xây dựng chương trình giai thừa bằng cách sử dụng đệ quy trong ngôn ngữ C:
Bạn có thể tìm thấy toàn bộ mã nguồn của chương trình giai thừa bằng cách sử dụng đệ quy trong C, Java và Python trong kho lưu trữ GitHub này.
- Nhập tệp tiêu đề đầu ra đầu vào chuẩn để hiển thị đầu ra ra màn hình.
#include <stdio.h> - Xác định chức năng thực tế và lấy số nguyên N như một lập luận.
int fact(int n) { - Viết trường hợp cơ sở của hàm bằng cách sử dụng nếu tuyên bố và kiểm tra tính bình đẳng của nó bằng cách sử dụng ==. Nếu n bằng 0, trả về một.
if (n == 0)
return 1; - Viết phương trình tổng quát và trả về tích của N với một lời gọi hàm của bài toán con n-1.
return n * fact(n - 1);
} - Khai báo hàm main và khởi tạo một biến kiểu số nguyên để lưu trữ số có giai thừa mà bạn muốn tìm.
int main() {
int num = 5; - Hiển thị giai thừa của số bằng cách sử dụng printf () hàm số. % d là định dạng thập phân. Sử dụng từng từ định dạng để thay thế nó bằng số có giai thừa mà bạn muốn tìm và nhận kết quả bằng cách gọi hàm.
printf("Factorial of %d is %d", num, fact(num));
return 0;
}
Chương trình giai thừa trong Java
Java là một ngôn ngữ lập trình được biên dịch và độc lập với nền tảng. Bạn lưu trữ tất cả mã bên trong một lớp và việc thực hiện bắt đầu từ chính hàm số. Nó phân biệt chữ hoa chữ thường và cú pháp nghiêm ngặt. Mã dài hơn một chút nhưng nhanh hơn so với Python. Đây là cách bạn có thể xây dựng chương trình giai thừa bằng cách sử dụng đệ quy trong Java:
- Xác định lớp Chính.
class Main { - Định nghĩa một hàm tĩnh với kiểu trả về int chấp nhận một biến n kiểu số nguyên. Bạn đã khai báo một phương thức static vì phương thức chính trong Java cũng được khai báo là static. Ngoài ra, bạn không thể gọi một phương thức không tĩnh từ một trường hợp tĩnh.
static int fact(int n) { - Viết trường hợp cơ sở của hàm bằng cách sử dụng nếu tuyên bố và kiểm tra tính bình đẳng của nó bằng cách sử dụng ==. Nếu n bằng 0, trả về một.
if (n == 0)
return 1; - Viết phương trình tổng quát và trả về tích của N với một lời gọi hàm của bài toán con n-1.
return n * fact(n - 1);
} - Khai báo hàm main trong Java. Khai báo công cụ sửa đổi quyền truy cập là công cộng, vì vậy nó có thể được truy cập bởi tất cả các lớp và phương thức khác. Bạn khai báo hàm chính là tĩnh để trình biên dịch có thể gọi nó mà không cần khởi tạo lớp. Loại trả lại là vô hiệu, và nó chấp nhận các đối số kiểu Sợi dây. Lưu trữ số có giai thừa bạn muốn tìm.
public static void main(String[] args) {
int num = 5; - Sử dụng println () phương thức, một phiên bản của PrintStream lớp, được định nghĩa trong Hệ thống lớp để hiển thị giai thừa của một số.
System.out.println("Factorial of " + num + " is " + fact(num));
}
}
Chương trình giai thừa bằng Python
Viết mã bằng Python rất dễ dàng và thú vị. Vì nó là một ngôn ngữ độc lập với nền tảng được thông dịch, bạn không phải khai báo kiểu dữ liệu của các biến. Bạn cũng tránh phải khai báo các lớp và nhập các thư viện cho một chương trình đơn giản như vậy. Sân chơi đã sẵn sàng để bạn bắt đầu viết mã.
Cú pháp dễ dàng hơn, với độ dài mã nhỏ nhưng mất nhiều thời gian hơn để thực thi so với các ngôn ngữ khác. Đây là cách bạn có thể xây dựng chương trình giai thừa bằng cách sử dụng đệ quy trong Python:
- Xác định thực tế của hàm chấp nhận là đối số n.
def fact(n): - Viết trường hợp cơ sở của hàm bằng cách sử dụng nếu tuyên bố và kiểm tra tính bình đẳng của nó bằng cách sử dụng ==. Nếu n bằng 0, trả về một.
if n == 0:
return 1 - Viết phương trình tổng quát và trả về tích của N với một lời gọi hàm của bài toán con n-1.
return n * fact(n-1) - Lưu trữ số có giai thừa bạn muốn tìm và hiển thị nó bằng cách sử dụng câu lệnh in.
num = 5;
print("Factorial of", num, "is", fact(num))
Có nhiều ứng dụng của đệ quy
Đệ quy là một cách giải quyết vấn đề hiệu quả. Đây là điểm mấu chốt của Trí tuệ nhân tạo và được sử dụng trong thế giới thực trong các trò chơi giải đố như cờ vua hoặc Sudoku.
Nó cũng là một phương pháp mạnh mẽ để sắp xếp các cấu trúc dữ liệu như Cây hoặc các thuật toán sắp xếp như Sắp xếp nhanh và Sắp xếp hợp nhất. Bạn cũng có thể sử dụng đệ quy trong các thuật toán tìm kiếm như tìm kiếm nhị phân, các biểu thức toán học như chuỗi Fibonacci, v.v.