Tính N Giai Thừa Trong C/C++ Bằng đệ Quy Và Khử đệ Quy

Bài viết chia sẻ thuật toán và cách tính n giai thừa trong C/C+ sử dụng hai phương pháp đệ quy và khử đệ quy. Một bài toán hay dành cho các bạn học lập trình.

Mục lục bài viết

• 1. Giới thiệu bài toán
• 2. Tính giai thừa sử dụng vòng lặp
• 3. Tính giai thừa sử dụng đệ quy

1. Giới thiệu bài toán

Giai thừa là một bài toán kinh điển trong lập trình, nó là một bài toán mà mình tin là bất kì bạn nào mới học đều phải trải qua. Bài toán này sẽ giúp bạn hiểu được thuật toán đệ quy hoặc sử dụng thành thạo vòng lặp.

Đề bài đại loại có thể tóm tắt lại như sau: Tính n giai thừa và in kết quả ra màn hình, n nhập vào từ bàn phím.

Trước khi giải quyết bài toán, chúng ta cần hiểu định nghĩa về n! (n là một số nguyên dương): n giai thừa là tích của n số nguyên dương đầu tiên.Công thức tổng quát: n! = n*(n-1)!Trường hợp đặc biệt: 0! = 1

2. Tính giai thừa sử dụng vòng lặp

Cách tính đầu tiên này sẽ đơn giản hơn cách sử dụng đệ quy. Và nó được gọi là cách khử đệ quy bởi vì nó tránh được việc phải dùng đến đệ quy. Tùy từng trường hợp mà đệ quy và khử đệ quy có ưu điểm khác nhau.

Tư tưởng giải quyết:

• Khai báo một biến để lưu giá trị và gán nó bằng 1: giai_thua = 1 Sử dụng vòng lặp chạy i từ 1 đến n sau đó gán: giai_thua = giai_thua*i

Code C/C++:

// giai thua su dung vong lap int giaithualap(int n){ int giai_thua = 1; for (int i = 1; i <= n; i++) giai_thua = giai_thua * i; return giai_thua; }

3. Tính giai thừa sử dụng đệ quy

Để hiểu rõ hơn thuật toán này trước tiên bạn nên tìm hiểu thuật toán đệ quy.

Ở bài này, ta có công thức tổng quát n giai thừa là : n!=n*(n-1)!Chính vì thế, ta cũng sử dụng lệnh truy hồi dựa trên công thức này. Điều kiện dừng ở đây là khi n =1 (vì ta tính tích các số bắt đầu từ 1)

Code C/C++:

// tinh giai thua su dung de quy int factorial(int n){ if(n==1) return 1; return(n*factorial(n-1)); }

Đánh giá cả 2 cách: Cách sử dụng đệ quy để tính giai thừa có vẻ chuyên nghiệp hơn. Tuy nhiên cách sử dụng vòng lặp có tốc độ nhanh không kém đệ quy, thậm trí là nhanh hơn.Trong cách bài toán thực tế, nếu để lựa chọn thì các lập trình viên sẽ sử dụng cách 1 để hạn chế ít nhất việc sử dụng đệ quy.

Chú ý: Ở đây kiểu dữ liệu của hàm mình để là kiểu int, chính vì thế chỉ có thể chạy khi n <= 19 (nếu quá thì sẽ vượt kích thước của kiểu int dẫn đến sai kết quả). Nếu bạn muốn chạy được số lớn hơn thì nên để kiểu double (max n 170).

Code full bài toán nhập N và tính đệ quy:

/* Bai toan tinh N giai thua trong C++ By: https://duongdinh24.com/ github: https://github.com/duongdinh24/ */ #include<bits/stdc++.h> using namespace std; // n! su dung de quy int factorial(int n){ if(n==1) return 1; return(n*factorial(n-1)); } // nn! Khu de quy su dung vong lap int giaithualap(int n){ int giai_thua = 1; for (int i = 1; i <= n; i++) giai_thua = giai_thua * i; return giai_thua; } int main(){ int n; cout<<"Nhap n: "; cin>>n; cout<<"Ket qua "<<n<<"!: "<<factorial(n); // De quy // cout<<"Ket qua "<<n<<"!: "<<giaithualap(n); // Khu de quy }

Kết quả chạy chương trình:

Bài viết của mình đến đây là hết, cảm ơn bạn đã quan tâm bài viết. Xem thêm các bài viết về C/C++ của mình tại đây!

Chúc bạn may mắn và thành công ^^!