Tính giai thừa số lớn (Big Factorial)

by **pkt_zz** 13/6/2010, 4:11 am

Nguồn: [You must be registered and logged in to see this link.]
Bài toán tính giai thừa là một trong các bài toán cơ bản khi học về lập trình (vòng lặp và đệ qui). Về cơ bản tính giai thừa (Factorial) là một bài toán tính tích n! = 1*2*...*n. Đối với các giá trị n nhỏ (n ≤ 20) thì giá trị của n! vẫn nằm trong vùng biểu diễn của số nguyên, tuy nhiên đối với số n lớn (khoảng vài trăm, vài nghìn) thì việc tính n! trở nên khó khăn vì giá trị của n! vượt quá khoảng biểu diễn của kiểu số nguyên lớn nhất. Trong bài báo này tôi sẽ giới thiệu với các bạn một thuật toán cơ bản dùng để tính giai thừa của một số nguyên lớn (n ≤ 100000) trên ngôn ngữ C/C++.

1.Giới hạn của kiểu số nguyên trong C/C++
Trước khi đi vào các thuật toán, tôi muốn giới thiệu với các bạn độc giả giới hạn biểu diễn của các kiểu số nguyên trong C/C++. Các bạn hãy xem ví dụ C++ sau:

Code:: // file intlimit.cpp #include #include #include using namespace std; int main() { cout << "CHAR_MIN = " << CHAR_MIN << endl; cout << "CHAR_MAX = " << CHAR_MAX << endl; cout << "UCHAR_MAX = " << UCHAR_MAX << endl; cout << "SHRT_MIN = " << SHRT_MIN << endl; cout << "SHRT_MAX = " << SHRT_MAX << endl; cout << "USHRT_MAX = " << USHRT_MAX << endl; cout << "INT_MIN = " << INT_MIN << endl; cout << "INT_MAX = " << INT_MAX << endl; cout << "UINT_MAX = " << UINT_MAX << endl; cout << "LONG_MIN = " << LONG_MIN << endl; cout << "LONG_MAX = " << LONG_MAX << endl; cout << "ULONG_MAX = " << ULONG_MAX << endl; cout << "LLONG_MIN = " << LLONG_MIN << endl; cout << "LLONG_MAX = " << LLONG_MAX << endl; cout << "ULLONG_MAX = " << ULLONG_MAX << endl; system("pause"); return 0; }

Kết quả chạy chương trình trên là:

CHAR_MIN = -128

CHAR_MAX = 127

UCHAR_MAX = 255

SHRT_MIN = -32768

SHRT_MAX = 32767

USHRT_MAX = 65535

INT_MIN = -2147483648

INT_MAX = 2147483647

UINT_MAX = 4294967295

LONG_MIN = -2147483648

LONG_MAX = 2147483647

ULONG_MAX = 4294967295

LLONG_MIN = -9223372036854775808

LLONG_MAX = 9223372036854775807

ULLONG_MAX = 18446744073709551615

Như vậy chúng ta thấy rằng kiểu số nguyên lớn nhất là long long (có dấu), còn unsigned long long là kiểu số nguyên không có dấu lớn nhất (có giá trị dương lớn nhất gấp đôi giá trị dương lớn nhất của kiểu long long).
2.Tính giai thừa với kiểu dữ liệu số nguyên lớn nhất.
Bây giờ chúng ta đã biết kiểu số nguyên lớn nhất là long long, chúng ta sẽ sử dụng kiểu số nguyên này để tính giai thừa của một số nguyên bằng chương trình sau:

Code:: // file bigfac0.cpp #include using namespace std; int main() { long long kq = 1ll; unsigned long n; unsigned long i = 1ul; cout << "Nhap n = "; cin>> n; for(i=1ul;i<=n;++i) kq = kq * i; cout << kq; system("pause"); return 0; }

Theo kết quả thử nghiệm chạy chương trình trên chúng ta có thể tính tới giá trị 20! (bằng 2432902008176640000), một con số khá khiêm tốn.
3.Thuật toán tính giai thừa số lớn
Để có thể tính được giai thừa của các số lớn, chúng ta bắt buộc phải thay đổi cách biểu diễn kết quả của việc tính giai thừa, đó là một số nguyên lớn. Chúng ta sẽ sử dụng một mảng các số nguyên để biểu diễn các chữ số của số nguyên lớn n!. Tuy nhiên một số nguyên có thể biểu diễn không chỉ 1 chữ số của n!, nó có thể biểu diễn 2, 3, 4, .. chữ số của n!. Vậy chúng ta nên chọn một phần tử của mảng kết quả sẽ biểu diễn bao nhiêu chữ số. Nói một cách dễ hiểu hơn giả sử với n = 20, ta có n! = 2432902008176640000, nếu ta sử dụng một mảng số nguyên biểu diễn các chữ số của n!, sẽ có các khả năng sau:

Vậy chúng ta sẽ chọn các biểu diễn nào, trước hết để an toàn chúng ta sử dụng một phần tử mảng để biểu diễn 4 chữ số của n!.
Với các biểu diễn này, chúng ta sẽ sử dụng phương pháp nhân đa thức để tính n!, kết quả n! là một đa thức với các hệ số nguyên, mỗi hệ số biểu diễn 4 chữ số. Thuật toán có một vòng lặp chính, mỗi lần lặp ta sẽ lấy giá trị của biến chạy i nhân với đa thức kết quả. Ở đây cần chú ý các điểm sau:
Tính giai thừa số lớn (Big Factorial) Tinhgiathuasolon1

Tính giai thừa số lớn (Big Factorial) Tinhgiathuasolon1

+ Do mỗi phần tử mảng biểu diễn 4 chữ số của n! nên khi in ra ta cần thêm các số 0 vào phần đầu của số nếu như phần tử mảng tương ứng không có đủ 4 chữ số (xét theo giá trị thực của nó), trừ phần tử mảng cuối cùng. Ví dụ nếu a[j] = 0 (với 1 vị trí j nào đó) thì sẽ in ra 0000, nếu a[j] = 23 thì sẽ in ra 0023.

+ Ta sẽ thực hiện nhân giá trị i với giá trị hiện tại của đa thức kết quả bằng thuật toán nhân tay:

-Lấy i nhân với giá trị a[j] (j là vị trí đang xét của đa thức) và cộng với kết quả dư từ phép nhân trước (i nhân với a[j-1]), lưu vào biến sl.

-Chia sl cho 10000 (vì mỗi hệ số của đa thức biểu diễn 4 chữ số), phần dư và gán cho a[j], kết quả của phép chia gán cho biến dư sn.

-Khởi đầu mỗi lần lặp (nhân i với đa thức kết quả) biến sn được gán bằng 0.

+ Ban đầu số chữ số của n! được xem là 1 (biến so), sau mỗi lần lặp, nếu giá trị của sn còn lớn hơn 0 thì phải tăng biến solên 1 đơn vị (để biểu diễn giá trị dư sn).

Sau đây là phần chương trình cài đặt thuật toán:

Code:: // file bigfacvs.cpp #include #include #include #defineMAX 100000 using namespacestd; int main() { int i,j,n,so; unsigned longsl; unsigned sn; int a[MAX]; clock_t t1, t2; cout << "Chuong trinh tinh giai thua so lon "; cout << "Ban muon tinh giai thua cua n="; cin >> n; a[0]=1; t1=clock(); sn=0; so = 1; for(i=1;i<=n;i++) { sn = 0l; for(j=0;j<so;j++) { sl=i*a[j]+sn; a[j]=sl%10000; sn=sl/10000; } if(sn) a[so++] = sn; } t1=clock()-t1; i=so-1; t2 = clock(); cout << a[i]; for(j=i-1;j>=0;--j) cout << setw(4) << setfill('0') << a[j]; t2 = clock() - t2; cout << " Thoi gian tinh toan:" << (float)t1/CLK_TCK; cout << " Thoi gian hien thi:" << (float)t2/CLK_TCK; system("pause"); return 0; }

Một số kết quả tính toán (trên bộ công cụ Visual Studio 2008 SP1):

Các bạn có thể thay đổi thuật toán trên để mỗi phần tử của mảng a biểu diễn 5, 6 chữ số của n!, tuy nhiên theo thực nghiệm tôi thấy rằng nó không làm thuật toán nhanh hơn, và cũng cần chú ý là khi đó giá trị của biến sn cực đại sẽ là 106 * n và với n = 100000 thì sẽ vượt qúa miền biểu diễn của kiểu số nguyên int, nên kết quả có thể sai. Đối với mảng a[] bạn có thể dùng kiểu unsigned, hiệu năng của thuật toán hầu như không thay đổi. Tuy nhiên đối với các giá trị n nhỏ (n < 20000) bạn có thể dùng kiểu long thay cho unsigned long đối với biến sl và thuật toán sẽ chậm hơn so với kiểu unsigned long.

Thêm một chú ý nhỏ nữa là nếu bạn dịch chương trình trên với DevCpp thì thời gian thực hiện thuật toán có thể sẽ chậm hơn một chút. Bảng kết quả trên chạy trên hệ thống của tôi có cấu hình: CPU Centrino 1.5 Ghz, Cache 2 Mb, Ram 1 GB, HDD 120 Gb Samsung ATA 5400 rpm.

Cuối cùng, thuật toán tôi trình bày trong bài báo này không phải là thuật toán nhanh nhất, hiệu quả nhất để tính giai thừa của một số nguyên lớn, nó là một thuật toán cơ bản. Các thuật toán cao cấp hơn, có thể tính được với giá trị của n rất lớn trong thời gian ngắn xin hẹn các bạn trong một bài viết khác.