Tính giai thừa n!

Đề bài: Viết chương trình tính n! với n là số tự nhiên không âm nhập vào từ bàn phím

Để làm được bài này, trước tiên các bạn cần nhớ lại công thức tính n! đã. Theo định nghĩa giai thừa ta có:

  • 0! = 1
  • n! = 1.2.3…n

Vậy là ta có công thức rồi. Nhìn vào công thức ta thấy với n = 0 thì dễ rồi, nếu n > 0 thì nó là tích các số từ 1 đến n. Vậy chúng ta có thể dùng vòng lặp for để tính dễ dàng 🙂

/*
* Calculate n!
*/

#include <stdio.h>

int main()
{
	int i, n;
	int fact = 1;

	printf("Enter n = ");
	scanf("%d", &n);

	for(i = 1; i <= n; i++) 
	{
		fact = fact * i;
	}

	printf("%d! = %d\n", n, fact);

	return 0;
}

Khá dễ dàng. Tuy nhiên các bạn để ý một chút kẻo nhầm.

  • Tại sao chúng ta lại gán giá trị ban đầu cho biến fact (Factorial) là 1 mà không phải là 0 hoặc số khác? Đơn giản vì nếu gán fact = 0 thì fact luôn là 0 do 0 nhân với số nào cũng là 0.
  • Tại sao trong code chúng ta không xét trường hợp n = 0 ? Vì trong vòng lặp for chúng ta cho biến i chạy từ 1 đến n. Nếu n = 0 thì dĩ nhiên là vòng lặp sẽ không chạy lần nào và khi đó fact của chúng ta vẫn là 1. Vậy chương trình vẫn đúng

Lại xem xét chút nhé. Các bạn thử nhập n là 20 hoặc lớn hơn xem có chuyện gì xảy ra? Các bạn sẽ thấy kết quả bị sai hoặc là trả về một số âm nào đó. Lý do là vì sao? Các bạn lưu ý là do tính chất của giai thừa là nhân liên tiếp nên kết quả của nó sẽ tăng rất là nhanh. 5! = 120 nhưng 6! = 720 mất rồi. Do vậy số fact của chúng ta sẽ lớn rất nhanh làm cho kiểu dữ liệu (int) của chúng ta không thể chứa được (Các bạn có thể xem phạm vi giới hạn của các kiểu dữ liệu). Do vậy chúng ta cần đổi kiểu dữ liệu. Tùy vào độ lớn của n mà chúng ta ước lượng kiểu dữ liệu chúng ta dùng là kiểu gì. Các bạn có thể dùng long hoặc long long cho bài tính giai thừa nhé.

/*
* Calculate n!
*/

#include <stdio.h>

int main()
{
	int i, n;
	long long fact = 1;

	printf("Enter n = ");
	scanf("%d", &n);

	for(i = 1; i <= n; i++) 
	{
		fact = fact * i;
	}

	printf("%d! = %lld\n", n, fact); // lld for long long

	return 0;
}

Khi này các bạn có thể tính được 20!. Và kết quả như sau:

Enter n = 20
20! = 2432902008176640000

20! là một số rất là lớn.

Viết chương trình tính n! bằng đệ quy. Với n là số nguyên không âm nhập từ bàn phím

Ngoài cách dùng vòng for ra, chúng ta có thể dùng hàm với tính chất đệ quy để tính giai thừa. Các bạn để ý lại công thức tính giai thừa của chúng ta.

  • 0! = 1
  • n! = 1.2.3…n = n.(n-1).(n-2)…2.1 = n.(n-1)!

Có nghĩa là n! = n.(n-1)!. Trong định nghĩa giai thừa lại có giai thừa, nó tương đuơng với đệ quy – gọi lại chính hàm đó trong hàm đó. Chúng ta có thể viết chương trình như sau:

/*
* Calculate n! by recursive
*/

#include <stdio.h>

long long fact(int n) 
{
	if(n == 0) return 1;
	return n * fact(n-1);
}

int main()
{
	int n;

	printf("Enter n = ");
	scanf("%d", &n);

	printf("%d! = %lld\n", n, fact(n));

	return 0;
}

Các bạn có thể tham khảo thêm tại đây về cách sử dụng hàm và hàm đệ quy.

Bài tập: Viết chương trình hiển thị 1!, 2!, 3!,…, 20! cùng lúc. Mỗi dòng hiển thị một số.