Giai thừa của một số nguyên dương là tích của một số nguyên và tất cả các số nguyên bên dưới nó, tức là giai thừa của số n (được biểu thị bằng n!) Sẽ được cho bởi
n! = 1 * 2 * 3 * 4 *. . . . . * n
Giai thừa của 0 được xác định là 1 và không được xác định cho số nguyên âm. Có nhiều cách để tìm nó được liệt kê bên dưới-
- Chương trình giai thừa trong Csử dụng vòng lặp For
- Chương trình giai thừa sử dụngChức năng
- Chương trình giai thừasử dụng đệ quy
Bắt đầu nào.
Giai thừa sử dụng cho vòng lặp
Đây là cách dễ nhất và đơn giản nhất để tìm giai thừa của một số. Đầu tiên hãy để chúng tôi truy cập mã -
#include int main () {int I, num, fact = 1 // xác định giai thừa là 1 vì giá trị nhỏ nhất là 1 printf (“Nhập một số để tính giai thừa của nó”) scanf (“% d”, & num) if (num<0) //if the input is a negative integer { printf (“Factorial is not defined for negative numbers.”) } else { for(i=1i0, therefore fact value remains 1 { fact = fact * i // keeps on multiplying and storing in the value of factorial till the input integer is reached } printf(“Factorial of %d = %dn”, num, fact) } return 0 //since we have defined the main() method with a return value of integer type }Đầu ra-
Giai thừa của 5 = 120
Giải trình -
Số có giai thừa cần tìm được lấy làm đầu vào và được lưu trữ trong một biến và được kiểm tra xem nó có âm hay không. Nếu số nguyên được nhập là số âm thì thông báo thích hợp sẽ được hiển thị. Giá trị của giai thừa được xác định trước là 1 vì giá trị nhỏ nhất của nó là 1. Vòng lặp for được thực hiện cho các số nguyên dương (ngoại trừ 0 với điều kiện kiểm tra là sai và do đó thực tế vẫn bằng không). Trong vòng lặp for, giá trị của giai thừa được nhân với mỗi số nguyên và được lưu trữ liên tiếp cho đến khi đạt đến số đầu vào. Ví dụ: đối với đầu vào = 5, luồng chuyển đến vòng lặp for và các bước sau sẽ diễn ra-
fact = 1, i = 1 -> fact = 1 * 1 = 1 -> i = 2
fact = 1, i = 2 -> fact = 1 * 2 = 2 -> i = 3
fact = 2, i = 3 -> fact = 2 * 3 = 6 -> i = 4
fact = 6, i = 4 -> fact = 6 * 4 = 24 -> i = 5
fact = 24, i = 5 -> fact = 24 * 5 = 120 -> i = 6
Bây giờ 6> 5, do đó điều kiện kiểm tra trở thành sai và vòng lặp bị kết thúc. Giá trị của giai thừa được hiển thị.
Giai thừa sử dụng các hàm
Cách tiếp cận này được gọi là cách tiếp cận mô-đun và nên được tuân theo để lập trình vì nó khá hiệu quả. Một trong những lợi thế của nó là khi chúng ta cần thay đổi mã thì thay vì thay đổi mã hoàn chỉnh, chúng ta chỉ có thể sửa đổi chức năng liên quan. Mã để tìm giai thừa của một số bằng cách sử dụng phương pháp này được hiển thị bên dưới
#include long factorial (int num) // hàm tính giai thừa nhận một giá trị nguyên làm tham số và trả về giá trị kiểu int {int i long fact = 1 for (i = 1 i<= num i++) fact = fact * i return fact //returns to function call } int main() //execution begins from main() method { int num printf('Enter a number to calculate its factorialn') scanf('%d', &num) if(num<0) //if the input is a negative integer { printf('Factorial is not defined for negative numbers.') } printf('Factorial of %d = %dn', num, factorial(num)) //call to factorial function passing the input as parameter return 0 }
Đầu ra - Giai thừa của 5 = 120
Giải trình-
Logic của chương trình là như nhau ngoại trừ hàm khác được sử dụng để tính giai thừa và trả về giá trị cho phương thức chính từ nơi bắt đầu thực thi.
Giai thừa sử dụng đệ quy
Đệ quy là quá trình trong đó một hàm gọi chính nó và hàm tương ứng được gọi là hàm đệ quy. Nó bao gồm hai phần - một điều kiện cơ sở và một lời gọi đệ quy. Giải pháp cho điều kiện cơ bản được cung cấp trong khi giải pháp cho giá trị lớn hơn có thể được giải quyết bằng cách chuyển đổi sang các giá trị nhỏ hơn cho đến khi đạt được và sử dụng giải pháp cơ sở.
Dưới đây là mã để tìm giai thừa bằng cách sử dụng đệ quy: -
#include int fact (int) // nguyên mẫu hàm int main () {int num printf ('Nhập số có giai thừa cần tìm:') scanf ('% d', & num) if (num<0) { printf('ERROR. Factorial is not defined for negative integers') } printf('Factorial of %d is %d', num, fact(num)) //first call is made return 0 } int fact(int num) { if(num==0) //base condition { return 1 } else{ return(num*fact(num-1)) //recursive call } } Đầu ra - Giai thừa của 5 = 120
thuật toán fibonacci c ++
Giải trình -Giả sử người dùng nhập 5 làm đầu vào, thì trong phương thức main () giá trị của num là 5. Khi luồng đi trong câu lệnh printf (dòng 12), một lệnh gọi hàm fact (5) được thực hiện. Bây giờ đối với fact (5) num là 5 không bằng 0, do đó luồng chuyển đến câu lệnh else, trong đó câu lệnh return sẽ thực hiện một cuộc gọi đệ quy và thực tế (4) được thực hiện. Quá trình này được lặp lại cho đến khi đạt được điều kiện cơ bản, tức là num = 0 và 1 được trả về. Bây giờ luồng chuyển đến thực tế (1) từ nơi 1 (đối với thực tế (1) num = 1) * 1 (giá trị trả về từ thực tế (0)) được trả về. Quá trình này được lặp lại cho đến khi đạt được giá trị yêu cầu.
Độ phức tạp về thời gian và không gian - Phép lặp đệ quy V / S
Đối với Đệ quy-
Về thời gian phức tạp , chúng ta biết rằng giai thừa 0 là phép so sánh duy nhất. Do đó T (0) = 1. Đối với giai thừa của bất kỳ số nào khác, quá trình bao gồm một phép so sánh, một phép nhân, một phép trừ và một lệnh gọi hàm. vì thế
T (n) =T (n-1) +3
= T(n-2)+6
= T(n-3)+9
= & hellip.
= T (n-k) + 3k
Vì chúng ta biết T (0) = 1 và k = n, (n-k) = 0
Do đó T (n) = T (0) + 3n
= 1 + 3n
Do đó độ phức tạp về thời gian của mã là O (n).
Về không gian phức tạp, một ngăn xếp được tạo cho mỗi lệnh gọi sẽ được duy trì cho đến khi giá trị của nó làđược tính toán và trả về. Ví dụ đối với n = 5, các ngăn xếp sau sẽ phải được duy trì
f (5) -> f (4) -> f (3) -> f (2) -> f (1) -> f (0)
Như chúng ta có thể thấy rằng 5 ngăn xếp sẽ phải được duy trì cho đến khi đạt được lệnh gọi đến f (0) có giá trị làđược biết đến và được trả lại. Do đó đối với n giai thừa, n ngăn xếp sẽ phải được duy trì. Do đó không gian phức tạplà O (n). Cũng có thể thấy rõ từ các hình trên rằng đối với n = 5, 5 ngăn xếp sẽ phải làđược duy trì. Do đó đối với n giai thừa, n ngăn xếp sẽ phải được duy trì. Do đó độ phức tạp của không gian là O (n).
Để lặp lại-
Về thời gian phức tạp, có n lần lặp bên trong vòng lặp, do đó độ phức tạp về thời gian là O (n).
Về không gian phức tạp, đối với giải pháp lặp lại, chỉ có một ngăn xếp cần được duy trì và một biến số nguyên được sử dụng. Vì vậy, độ phức tạp không gian là O (1).
Đó là tất cả cho bài viết này. Tôi hy vọng bạn đã hiểu khái niệm về chương trình giai thừa trong C cùng với sự phức tạp về thời gian.
Nếu bạn gặp bất kỳ câu hỏi nào, vui lòng đặt tất cả câu hỏi của bạn trong phần nhận xét của “chương trình giai thừa trong C” và nhóm của chúng tôi sẽ sẵn lòng giải đáp.