Thất tình

Thất tình là một cảm giác rất khó diễn tả – không có bàn phím nào có thể tả nổi, chỉ biết rằng nếu ai đã từng yêu, đã từng thất tình thì mãi mãi không bao giờ quên cảm giác đó. Cũng không khó để bạn có thể biết rằng một ai đó đang thất tình hay không. Bạn có thể thấy một người thất thểu trên đường, mặt không cảm xúc, không quan tâm tới bất cứ điều gì xung quanh, miệng lảm nhảm những điều vô nghĩa, khi đó dù bạn có gọi thì họ cũng không nghe thấy, bạn có nói thì họ cũng không để ý bạn nói gì … Khi bạn thất tình, thì dù bạn có là ai, bạn đang ở đâu, bên cạnh bạn là bất cứ ai thì bạn vẫn cảm thấy … thất tình. Bạn sẽ có cảm giác không cần bất cứ gì cả, dù chúa trời có cho bạn cả thế giới, cho bạn bất cứ điều gì bạn muốn thì cũng không còn ý nghĩa gì nữa, đơn giản bởi vì bạn đang … thất tình. Khi đó mọi điều diễn ra xung quanh đối với bạn như không có, bạn sẽ chẳng quan tâm mọi người nghĩ gì về mình, tất cả những gì tồn tại trong đầu bạn chỉ là một cảm giác trống rỗng, bạn sẽ không hiểu tại sao mình tồn tại, để làm gì, và chỉ có một điều bạn quan tâm duy nhất là tại sao? Tại sao bạn lại bị thất tình? Tại sao người ấy lại bỏ bạn ra đi sau những gì tốt đẹp mà hai người đã có với nhau. Lịch sử của thế giới loài người đã trải qua hàng ngàn năm nhưng vẫn chưa thể tìm thấy một loại thuốc có thể chữa ngay cho bạn khỏi căn bệnh thất tình, chỉ có một giải pháp duy nhất: đó là thời gian. Thời gian sẽ làm cho bạn quên đi cảm giác chán nản, vô vọng và đưa bạn trở lại với cuộc sống bình thường. Vì vậy khi thất tình, bạn hãy nằm xuống bên cạnh bàn phím của mình và bắt đầu mơ về một giấc mơ mới.

Con đường thứ hai

Đối với những người trẻ tuổi vừa mới qua trường phổ thông, không có thảm họa nào lớn hơn việc thi trượt đại học. Nhưng có một thực tế mà họ không biết: trong gần 1 triệu thí sinh thi vào đại học, số người trượt – cùng cảnh với họ nhiều hơn nhiều so với số người đỗ. Vả lại thất bại lần đầu cũng không phải là một điều gì ghê gớm, rất nhiều sinh viên đại học chỉ đỗ ở lần thi thứ 2, thứ 3 thậm chí là thứ 5. Bạn có thể thi lại ở năm sau với 1 quyết tâm cao hơn và sự chuẩn bị tốt hơn. Và điều quan trọng nhất là: vào đại học qua kỳ thi đại học chính qui không phải là con đường duy nhất để thành công trong cuộc đời này. Có rất nhiều con đường để họ có thể thành công: đi học một nghề mà mình có năng khiếu hoặc yêu thích, hoặc vẫn có thể tiếp tục đi học bằng các con đường khác nhau: học nước ngoài nếu điều kiện kinh tế cho phép, học từ các trường Cao đẳng, sau đó liên thông lên đại học, học các lớp tại chức, học các trường dân lập, tự học … Tóm lại là có rất nhiều con đường để theo đuổi sự nghiệp học tập nếu bạn quyết tâm. Cuộc sống thật tươi đẹp và có nhiều ý nghĩa khi chúng ta trẻ, chân trời mới đang chờ chúng ta phía trước, hãy chuẩn bị hành trang sẵn sàng cho bình minh tuổi trẻ mỗi ngày mai thức dậy.

Tính giai thừa số lớn (Big Factorial)

Tính giai thừa số lớn (Big Factorial)
(Ngày cập nhật cuối: 18/05/2009)
Chủ đề bài báo: Tính giai thừa số lớn, C/C++, thuật toán.
Bài toán tính giai thừa là một trong các bài toán cơ bản khi học về lập trình (vòng lặp và đệ qui). Về cơ bản tính giai thừa (Factorial) là một bài toán tính tích n! = 1*2*…*n. Đối với các giá trị n nhỏ (n ≤ 20) thì giá trị của n! vẫn nằm trong vùng biểu diễn của số nguyên, tuy nhiên đối với số n lớn (khoảng vài trăm, vài nghìn) thì việc tính n! trở nên khó khăn vì giá trị của n! vượt quá khoảng biểu diễn của kiểu số nguyên lớn nhất. Trong bài báo này tôi sẽ giới thiệu với các bạn một thuật toán cơ bản dùng để tính giai thừa của một số nguyên lớn (n ≤ 100000) trên ngôn ngữ C/C++.
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 <> 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:
Một phần tử mảng biểu diễn
1 chữ số a[0] = 0, a[1] = 0, a[2] = 0, a[3] = 0, a[4] = 4, …, a[18] = 2
2 chữ số a[0] = 0, a[1] = 0, a[2] = 64, a[3] = 76, …, a[9] = 2
3 chữ số a[0] = 0, a[1] = 640, a[2] = 176, …, a[6] = 2
4 chữ số a[0] = 0, a[1] = 7664, a[2] = 81, …, a[4] = 243
…. ….
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 so lê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
#define MAX 100000
using namespace std;
int main()
{
int i,j,n,so;
unsigned long sl;
unsigned sn;
int a[MAX];
clock_t t1, t2;
cout << "Chuong trinh tinh giai thua so lon\n";
cout <> 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 <=0;–j)
cout << setw(4) << setfill('0') << a[j];
t2 = clock() – t2;
cout << "\nThoi gian tinh toan:" << (float)t1/CLK_TCK;
cout << "\nThoi 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):
Giá trị n Thời gian tính toán (giây) Thời gian hiển thị (giây)
1000 0 0.04
3000 0.03 0.15
5000 0.06 0.28
10000 0.29 0.59
30000 2.62 1.92
50000 7.5 3.26
80000 21 5.64
100000 33 7

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à 106 * 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.

Hải Phòng, ngày 18, tháng 05, năm 2009

Nguyễn Hữu Tuân