Làm Sao để Tính Giai Thừa Với Số Lớn! [Archive]

Diễn Đàn Tin Học > Lập trình > Các vấn đề khác trong lập trình > Data Structures + Algorithms > Làm sao để tính giai thừa với số lớn! PDA

View Full Version : Làm sao để tính giai thừa với số lớn!

Dau_Dat30-12-2005, 08:50Có ai biết cách tính giai thừa của số lớn không?, khoảng 1 tỷ chẳng hạn, tui có thấy một công thức dùng để tính khai triển như sau: log(N!) = SUM log(k) FOR k = 1 to N log(N!) = floor(log(N!)) + (log(N!) - floor(log(N!))) cuối cùng là: n+½ -n n! ~ n e SQRT(2pi)*( 1 + 1/(12n) + 1/(288n²) - ... ) ở đây hiển thị không đúng nên chú thích chút(n mũ n+1/2, e mũ -n) n -n n! ~ n e SQRT(2pi*n + 1/3) (n mũ n, e mũ -n) không biết dùng thế này có ổn không? Rikku30-12-2005, 13:501 tỉ giai thứa ặc ặc pinochu30-12-2005, 14:041 tỉ giai thứa ặc ặc chuyện nhỏ, bác chuyển 1 tỉ giai thừa ra kí tự, lưu vô file, xong rồi chia nhỏ dãy số ra, xử lí trên file, không xử lí số mà chuyển số sang kí tự số rồi xử lí là ok. Dau_Dat30-12-2005, 16:19Bạn có thể nói rõ hơn không?, tui vẫn chưa hình dung được cách làm của bạn, tui có tìm thấy thuật toán này chạy 1000000! khá nhanh, nhưng không có code, nếu dùng số thông thường thì overflow là cái chắc rùi. StarGhost04-01-2006, 03:07He he, có ai lại đi tính 1 tỉ giai thừa bao giờ, kể cả ghi kết quả ra file thì cũng phải mất cả GB, chả có trình nào mở nổi, tính làm gì cho mệt. Còn nếu muốn viết chương trình, thì chỉ cần viết 1 hàm nhân thôi Mach204-01-2006, 05:21Cái này gọi là ¨rubbish kỹ thuật cao¨ vì mất bài toán như thế này ít khi có ý nghĩa thực tế mà thường chỉ dùng để nghiên cứu. Giai thừa số lớn ko lạ lắm trong toán học, nhưng 1 tỉ giai thừa thì là... overkill. 1 tỉ giai thừa là khoảng vài tỉ chữ số nên lưu nó cũng là vấn đề. Ở đây bàn đến 2 cách: tính chính xác và tính xấp xỉ. Tính chính xác có nhiều thuật toán, cách ¨ngu¨ là dùng đệ quy hay tính kiểu bình thường nhân là cách ai cũng biết. Đương nhiên là nó cần phải có cách biểu diễn số lớn tương ứng. Không kể đến chuyện này, độ phức tạp là khoảng O(n*log(n)^2*(loglog(n))^2). Tôi nghĩ tính xong chắc cũng mất vài ngày cho là dùng thuật toán nhanh nhất hiện nay (dựa vào phân tích thừa số nguyên tố - prime factorization và fast multiplication). Đương nhiên tốc độ còn phụ thuộc cách thức lưu và truy cập dữ liệu nữa. Bạn liệt kê vài công thức xấp xỉ nên chắc hỏi tính xấp xỉ. Tính xấp xỉ thì cũng phải dùng biểu diễn số lớn thôi (ở đậy là số thực lớn) vì bạn cũng biết số chữ số của n! là khoảng O(n*log(n)). Công thức tính xấp xỉ tốt nhất là dùng xấp xỉ Stirling cho hàm Gamma (công thức cuối bạn ghi ở trên). Công thức này hội tụ khi x->inf nên x càng lớn càng đúng :) Tiện đây nói luôn là hàm Gamma cho phép tính giai thừa của cả số thực. pinochu18-01-2006, 17:35uh, mà tính 1 tỉ giai thừa làm chi vậy ta?? Dau_Dat20-01-2006, 08:09Cái tui định đề cập ở đây không phải là tính 1 tỷ giai thừa để làm gì, mà chỉ muốn thử xem trên một máy tính bình thường, với một giải thuật tối ưu thì có thể thực hiện được điều này hay không thôi. Hiện nay có rất nhiều các giải thuật tối ưu mà thời gian chạy thì không thể tưởng tượng nổi, nếu có thời gian thì các bạn có thể xem trên trang này www.usaco.org, có những bài toán khá phức tạp nhưng thời gian chạy của họ là 0s, quá ngang bằng không chạy. G-Style20-01-2006, 08:49nhớ hồi xưa nhặt được cái Source tính giai thừa lớn (1 tỷ thì không chắc chứ 1 triệu thì được đó) trên trang web của ông ĐH nào đó. Rất tiếc mất rùi. SOurce bằng pascal có 1 chương trình con xài ASM cũng ngắn thôi. Hermex10-03-2006, 08:03Có ai biết cách tính giai thừa của số lớn không?, khoảng 1 tỷ chẳng hạn, tui có thấy một công thức dùng để tính khai triển như sau: log(N!) = SUM log(k) FOR k = 1 to N log(N!) = floor(log(N!)) + (log(N!) - floor(log(N!))) cuối cùng là: n+½ -n n! ~ n e SQRT(2pi)*( 1 + 1/(12n) + 1/(288n²) - ... ) ở đây hiển thị không đúng nên chú thích chút(n mũ n+1/2, e mũ -n) n -n n! ~ n e SQRT(2pi*n + 1/3) (n mũ n, e mũ -n) không biết dùng thế này có ổn không? Cái công thức bạn đưa ở trên chỉ gần đúng thôi , chúng chỉ ứng dụng trong việc đánh giá giá trị thôi , còn nếu để tính chính xác n! thì không chuẩn , vì n! là số nguyên. Tôi có viết một program tính 2006! băng C++ chạy mất độ 10 phút, không biết nếu bạn tính 1 tỉ giai thừa không biết mất bao nhiêu thời gian , nếu bạn nào đã tính một tỉ giai thừa , xin cho biết thời gian thực hiện là bao lâu vậy? Rikku10-03-2006, 12:54chắc khoảng vài năm thôi lol Dau_Dat10-03-2006, 12:58Nếu ai đó mà ngồi viết chương trình tính một tỷ giai thừa thì...(^_^), ở đây tui chỉ muốn hỏi cách giải quyết vấn đề mà thui. mrlinh_280128-12-2009, 14:40the cho em cong thuc sterling la the nao duongk52cb06-01-2010, 23:41Nếu muốn tính giai thừa với thời gian nhanh bạn dùng phương pháp Quy hoạch động. Chỉ biết phương pháp như thế thui, search google thử coi. Good luck! vannhau18-01-2010, 15:57Bạn sử dụng cấu trúc String để giải quyết các bài toán tính toán với các số lớn nhé. Minh Beo18-01-2010, 23:58Bạn có thể sử dụng danh sách liên kết để xử lý bài này, hồi tôi đi học có làm bài tính 2 mũ n với n nguyên, theo lý thuyết thì nó chỉ phụ thuộc kích thước bộ nhớ và độ lớn số mũ n, trong bài chọn n là real cho nó lớn nhưng vẫn xử lý là số nguyên. Nay gởi các Bạn tham khảo, chúc thành công. Program Tinh2mu; uses crt; type kc=-1..9; pn=^no; no=record va:kc; next:pn end; Var fn,ln,he:pn; i,mul,add,di:word; n:real; procedure init(var head:pn); begin new(head);head^.va:=-1; head^.next:=head; end; procedure insertnode(var p:pn; val:kc); var z:pn; begin new(z);z^.va:=val; z^.next:=p^.next; p^.next:=z;p:=z; end; procedure writeval(he:pn); var p,q:pn; begin p:=he;q:=he; while p^.next<>he do p:=p^.next; write(p^.va);he:=p; while he^.va<>-1 do begin while p^.next<>he do p:=p^.next; he:=p; if he^.va=-1 then exit; write(he^.va); end end; BEGIN init(he);ln:=he;fn:=he; insertnode(ln,2); write(' So mu (lon hon hoac = 0) = ');readln(n); if n=0 then begin write('2^0 = 1');halt; end; if n<0 then begin write('so mu <0 khong tinh');halt; end; for i:=1 to trunc(n-1) do begin di:=0;add:=0; while ln<>he do begin mul:=ln^.va*2+di; di:=mul div 10; ln^.va:=mul mod 10; fn:=ln;ln:=ln^.next; end; if di<>0 then insertnode(fn,di); ln:=he^.next;fn:=he; end; writeval(he); readln END. cuongbn19-01-2010, 01:03Mình chỉ có kinh nghiệm vấn đề này là khi xử lý số lớn các bạn đừng tính từng chữ số một mà tạo kiểu cấu trúc dữ liệu mà 1 chữ số kiểu mới gồm 9 chữ số bình thường. Vì vậy khi tính toán ta sẽ nhanh gấp tầm 9 lần Các bạn cũng nên lưu ý nên chặt nhị phân để tính, ví dụ tính a^21 ta chỉ cần tính a^1 a^2 a^4 a^8 a^16 a^21 = a^16 * a^4 * a^1 Số lượng phép tính sẽ giảm rất nhiều Powered by vBulletin® Version 4.2.0 Copyright © 2025 vBulletin Solutions, Inc. All rights reserved.