Tính Giai Thừa Số Lớn (Big Factorial) | Angels Fall First

Có thể bạn quan tâm

Angels fall first

About

Pages
- Home
- About
Categories
- An toàn và bảo mật thông tin
- Các vấn đề khác
- Cấu trúc dữ liệu và giải thuật
- Computer Vision
- CUDA
- Dev tools
- Hệ điều hành Windows
- Hỏi đáp – thắc mắc
- Kỹ thuật lập trình C
- LaTeX
- Lập trình C trên Windows
- Lập trình Hướng đối tượng và C++
- Music
- Olympic Tin học ACM – Programming Contest
- Phần mềm
- Sách hay-Tiếng Việt
- Simple about some things
- Truyện cười
- Đề cương ôn tập

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

July 16, 2009 — 4fire

Tính giai thừa số lớn (Big Factorial) (Ngày cập nhật cuối: 18/05/2009) Chủ đề bài báo: Tính giai thừa số lớn, C/C++, thuật toán. 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: // 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: // 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 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: Một phần tử mả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 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: + 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 so lê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: // 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 quả tính toán (trên bộ công cụ Visual Studio 2008 SP1): Giá trị n Thời gian tính toán (giây) Thời gian hiển thị (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

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. 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: [email protected].

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

Nguyễn Hữu Tuân

8 Responses to “Tính giai thừa số lớn (Big Factorial)”

bekhoebedep Says:

Lâu rồi em mới thấy thầy viết bài, vẫn là CTDL & GT. Có người từng nói “Tư duy mới về những vấn đề cũ”, chắc thầy cũng thích câu đó 😀 Bài số nguyên lớn dùng danh sách liên kết có biểu diễn được vô hạn các số được không thầy? Hôm nay, em qua trường thấy lại đỗ môn LTHĐT, mừng phát khóc. Lần này chắc là qua thật phải không thầy ^^!

4fire Says:

Chúc mừng em, nói chung là tôi thấy cái gì thú vị và có thể viết được thì viết thôi. Các vĩ nhân thường bị đời hắt hủi. Lần trước tôi nhớ là đã nói với em là em đỗ mà. Phải có lòng tin chứ.

nhlionheart Says:

Thầy cho em hỏi muốn vẽ đồ họa bằng c++ thì nên dùng phần mềm nào và tạo 1 project mới như thế nào . Em cảm ơn thầy

4fire Says:

Em nên dùng Visual Studio với ngôn ngữ C++ hoặc C#. Về thư viện thì còn tùy mục đích của em. Nếu chỉ để minh họa các thuật toán đồ họa thì GDI (C/C++) hoặc GDI+(C#) là đủ, còn nếu muốn cao cấp hơn thì dùng Open GL hoặc DirectX. Còn nếu là để xử lý ảnh thì còn tùy mục đích: nhận dạng số, chữ hay …

ánh dương Says:

Thầy chỉ cho em cách cài đặt và sử dụng thư viện thư viện Boost trong C++ với. Em muốn học về Multi Thread. Em cảm ơn thầy

4fire Says:

Để dùng boost (trên Windows và với VS 2010, khuyến khích dùng VS 2012 update 4 hoặc VS 2013 update 2) thì em phải tự build boost, khá mất thời gian. Nhưng điều hay là các chương trình có dùng boost sẽ không cần phải copy đi kèm với thư viện này mà vẫn chạy tốt vì nó được biên dịch với output là các static libraries. Đầu tiên em cần add hai đường dẫn sau vào biến môi trường PATH của Windows (đây là đối với VS 2012, có thể em dùng các bản VS khác thì sẽ khác): C:\Program Files\Microsoft Visual Studio 11.0\VC\bin C:\Program Files\Microsoft Visual Studio 11.0\Common7\IDE Sau đó download boost và và unzip thành thư mục D:\boost, sau đó vào command line, chạy lệnh bootstrap để cấu hình, chạy lệnh .\b2 để dịch boost bằng VS, chờ một thời gian là sẽ xong. Để cấu hình VS sử dụng boost cần thêm đường dẫn D:\boost\stage\lib vào library directory của VS, D:\boost vào include directory của VS. Và thế là xong, nói chung cũng khá đơn giản. Về lập trình đa luồng, có một vài lựa chọn sau: + boost::thread, theo đánh giá của tôi là hơi chậm nhưng đa nền tảng. + pthread, tốc độ tốt nhưng khá phức tạp, đa nền tảng nhưng tài liệu hỗ trợ trên Windows hơi kém. + windows thread, tốc độ nhanh nhất và chỉ trên các hệ thống chạy Windows, đơn giản hơn pthread. + C++11 thread, đơn giản nhất, tốc độ tốt. Với ba lựa chọn ở trên, mỗi khi muốn thực hiện một tác vụ đa luồng, em cần viết chương trình (các hàm, các lớp) theo đúng kiểu framework tương ứng còn với C++11 thread thì điều này là native nên là dễ nhất cho ai mới bắt đầu như em, tất nhiên là em phải hiểu hết C++ đã. Lựa chọn lập trình đa luồng là tất yếu vì dữ liệu cần xử lý ngày càng lớn và thật là bực mình nếu máy tính của em có 4 CPU cores mà em chỉ viết được chương trình chạy với 1 core.

kida7 Says:

Theo em thì đoạn

if(sn) a[so++]=sn;

cần sửa lại thành

while(sn){ a[so++] = sn%10000; sn=sn/10000; }

Nếu ko tính toán với các số lớn (cỡ 10002 trở lên) sẽ bị sai 😀

huydz Says:

mình từ 2022 iam genz

Tính Giai Thừa Số Lớn (Big Factorial) | Angels Fall First

Pages

Categories

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

Share this:

Related

8 Responses to “Tính giai thừa số lớn (Big Factorial)”

Leave a comment Cancel reply

Links

Archives

Misc

Giai Thừa Của Số Lớn -C/C++ - PROGRAMMING

Tính Giai Thừa Số Lớn - YouTube

Tính Giai Thừa Số Lớn | Tính 100! Trong Lập Trình C

Tính Giai Thừa Dùng Số Nguyên Lớn - Programming - Dạy Nhau Học

C++ - Tính Giai Thừa Của Một Số được Nhập Từ Bàn Phím - Freetuts

Tính N Giai Thừa Trong C/C++ Bằng đệ Quy Và Khử đệ Quy

Tính Giai Thừa Trong C++ - Bài Tập C++ Có Lời Giải - VietTuts

Làm Sao để Tính Giai Thừa Với Số Lớn! - Diễn Đàn Tin Học

Hướng Dẫn Sử Dụng 3 Cách Tính Giai Thừa Trong C - DevPro

Tính N! (n>0) | How Kteam

[ C/C++ ] - Tính Giai Thừa Và Làm Tràn Bộ Nhớ. - VozForums

Bài Tập C++ VÒNG LẶP – Wikibooks Tiếng Việt

Cộng Trừ Nhân Chia 2 Số Nguyên Lớn Trong C/C++

Liên Hệ