1.Giới hạn của kiểu số nguyên trong C/C++

Trước khi đi vào các thuật toán, tôi muốn giới thiệu với các bạn độc giả giới hạn biểu diễn của các kiểu số nguyên trong C/C++. Các bạn hãy xem ví dụ C++ sau:

// 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 quả chạy chương trình trên là:

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 chúng ta thấy rằng kiểu số nguyên lớn nhất là long long (có dấu), còn unsigned long long là kiểu số nguyên không có dấu lớn nhất (có giá trị dương lớn nhất gấp đôi giá trị dương lớn nhất của kiểu long long).

2.Tính giai thừa với kiểu dữ liệu số nguyên lớn nhất.

Bây giờ chúng ta đã biết kiểu số nguyên lớn nhất là long long, chúng ta sẽ sử dụng kiểu số nguyên này để tính giai thừa của một số nguyên bằng chương trình sau:

// 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 quả thử nghiệm chạy chương trình trên chúng ta có thể tính tới giá trị 20! (bằng 2432902008176640000), một con số khá khiêm tốn.

3.Thuật toán tính giai thừa số lớn

Để có thể tính được giai thừa của các số lớn, chúng ta bắt buộc phải thay đổi cách biểu diễn kết quả của việc tính giai thừa, đó là một số nguyên lớn. Chúng ta sẽ sử dụng một mảng các số nguyên để biểu diễn các chữ số của số nguyên lớn n!. Tuy nhiên một số nguyên có thể biểu diễn không chỉ 1 chữ số của n!, nó có thể biểu diễn 2, 3, 4, .. chữ số của n!. Vậy chúng ta nên chọn một phần tử của mảng kết quả sẽ biểu diễn bao nhiêu chữ số. Nói một cách dễ hiểu hơn giả sử với n = 20, ta có n! = 2432902008176640000, nếu ta sử dụng một mảng số nguyên biểu diễn các chữ số của n!, sẽ có các khả năng sau:

Vậy chúng ta sẽ chọn các biểu diễn nào, trước hết để an toàn chúng ta sử dụng một phần tử mảng để biểu diễn 4 chữ số của n!.

Với các biểu diễn này, chúng ta sẽ sử dụng phương pháp nhân đa thức để tính n!, kết quả n! là một đa thức với các hệ số nguyên, mỗi hệ số biểu diễn 4 chữ số. Thuật toán có một vòng lặp chính, mỗi lần lặp ta sẽ lấy giá trị của biến chạy i nhân với đa thức kết quả. Ở đây cần chú ý các điểm sau:

+ Do mỗi phần tử mảng biểu diễn 4 chữ số của n! nên khi in ra ta cần thêm các số 0 vào phần đầu của số nếu như phần tử mảng tương ứng không có đủ 4 chữ số (xét theo giá trị thực của nó), trừ phần tử mảng cuối cùng. Ví dụ nếu a[j] = 0 (với 1 vị trí j nào đó) thì sẽ in ra 0000, nếu a[j] = 23 thì sẽ in ra 0023.

+ Ta sẽ thực hiện nhân giá trị i với giá trị hiện tại của đa thức kết quả bằng thuật toán nhân tay:

-Lấy i nhân với giá trị a[j] (j là vị trí đang xét của đa thức) và cộng với kết quả dư từ phép nhân trước (i nhân với a[j-1]), lưu vào biến sl.

-Chia sl cho 10000 (vì mỗi hệ số của đa thức biểu diễn 4 chữ số), phần dư và gán cho a[j], kết quả của phép chia gá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 quả) biến sn được gán bằng 0.

+ Ban đầu số chữ số của n! được xem là 1 (biến so), sau mỗi lần lặp, nếu giá trị của sn còn lớn hơn 0 thì phải tăng biến solên 1 đơn vị (để biểu diễn giá trị dư sn).

Sau đây là phần chương trình cài đặt thuật toán:

// 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 quả tính toán (trên bộ công cụ Visual Studio 2008 SP1):

Các bạn có thể thay đổi thuật toán trên để mỗi phần tử của mảng a biểu diễn 5, 6 chữ số của n!, tuy nhiên theo thực nghiệm tôi thấy rằng nó không làm thuật toán nhanh hơn, và cũng cần chú ý là khi đó giá trị của biến sn cực đại sẽ là 10⁶ * n và với n = 100000 thì sẽ vượt qúa miền biểu diễn của kiểu số nguyên int, nên kết quả có thể sai. Đối với mảng a[] bạn có thể dùng kiểu unsigned, hiệu năng của thuật toán hầu như không thay đổi. Tuy nhiên đối với các giá trị n nhỏ (n < 20000) bạn có thể dùng kiểu long thay cho unsigned long đối với biến sl và thuật toán sẽ chậm hơn so với kiểu unsigned long.

Thêm một chú ý nhỏ nữa là nếu bạn dịch chương trình trên với DevCpp thì thời gian thực hiện thuật toán có thể sẽ chậm hơn một chút. Bảng kết quả trên chạy trên hệ thống của tôi có cấu hình: CPU Centrino 1.5 Ghz, Cache 2 Mb, Ram 1 GB, HDD 120 Gb Samsung ATA 5400 rpm.

Cuối cùng, thuật toán tôi trình bày trong bài báo này không phải là thuật toán nhanh nhất, hiệu quả nhất để tính giai thừa của một số nguyên lớn, nó là một thuật toán cơ bản. Các thuật toán cao cấp hơn, có thể tính được với giá trị của n rất lớn trong thời gian ngắn xin hẹn các bạn trong một bài viết khác.

Mặc dù đã hết sức thận trọng và xem xét kỹ lưỡng các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: tuannhtn@yahoo.com.

School@net