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.
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