View Full Version : 1000!=??? ai biết giúp mình với !!
Mình lập trình để tính 1000! nhưng nó báo lỗi overflow !
Mình thử dùng mảng để tính nhưng thấy rắc rối quá đi mất,ai biết chỉ cho mình thuật toán với .
Xin cảm ơn mọi người nhiều !!!
Tui nghĩ 1000! qúa lớn => nếu CCTS xài int hay long int chắc là 0 được rồi
==> có thể thử biểu diễn số nguyên như mảng của các chữ số (hình như CCTS đã thử qua nhưng cho là rắc rối quá ?)
bạn đã có idea con số này lớn đến mức nào ko?
Nó có khoảng sum(log10(i),i=1->1000) = 2570 con số ah
Toi thu du`ng cac kieu so nhung de'n 64 so' la` kich, con so 1000! uoc phai de'n 3000 so'. Vi` vay toi dinh du`ng mang ti'nh nhu kieu tre con lo'p 3 tap nhan i' nhung ra'c ro'i qua'/
.....
a:=1000;
fillchar(d,sizeof(d),0);
d[0]:=1;
k:=0;
for i:=2 to a do
begin
. nho:=0;
. for j:=0 to k do
. begin
. . nho:=d[j]*i+nho;
. . d[j]:=nho mod 10;
. . nho:=nho div 10;
. end;
. while nho>0 do
. begin
. . inc(k);
. . d[k]:=nho mod 10;
. . nho:=nho div 10;
. end;
end;
for i:=k downto 0 do write(d[i]);
.....
Bạn tự hoàn chỉnh chương trình nhé
bạn hãy vào forum diendantinhoc.org, trong CLB thuật toán tui cũng có một bài hướng dẩn cụ thể về thuật toán tính giai thừa với số lớn và rất nhiều bài khác nữa của các mem khác rất hay. Với thuật toán của tui bạn có thể tính lên đến 14000! và có thể cao hơn nữa, và bạn yên tâm là kết quả tính hoàn toàn chính xác trong phạm vi từ 0! đến 14000!
moibelgal
25-03-2004, 21:35
bài này đơn giản ma`....
Bài này tui đã làm và post lên đây rồi, bạn lục lại các bài của tui thì sẽ gặp, tui tính được 1450! với môi trường Pascal
Gửi svxd: có phải bạn xài số nguyên lớn dùng mảng của kí tự => mỗi phần tử chứa 1 kí tự ('0' -> '9') ? (tui có vô CLB thuật toán của diendantinhoc.org => nhưng 0 thấy có chức năng tìm kiếm => chịu 0 tìm ra bài viết của bạn !)
Gửi eureka: có phải bạn xài số nguyên lớn dùng mảng của kí tự => mỗi phần tử chứa 1 kí tự ('0' -> '9') ?
learncpp
28-03-2004, 15:18
Tính 30000!
http://www.vninformatics.com/forum/?action=msg&msg=1023437043#1023437043
Xin chào!
Trước đây, tôi đã viết 1 chương trình nhỏ tính 2 mũ n với n nguyên dương lớn t̀uy ý, nay xin post lên để các bạn tham khảo ý tưởng tính 10000! (tôi đã thử trên máy với giá trị 2^100.000 )
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.
Xin có 1 ý kiến nhỏ: tui có coi 1 số bạn cài đặt số nguyên (lớn hơn hay bằng 0) => thấy có 2 hướng:
Huớng 1: xài mảng; mỗi phần tử (thường là 1 byte) có giá trị từ 0 đến 9. Nếu mình xài N phần tử (N bytes) thì sẽ biểu diễn được từ 0 đến 10^N-1 . Khi tính toán sẽ div/mod cho 10
Huớng 2: cũng xài mảng; mỗi phần tử có giá trị từ 0 đến 10^m-1 . Nếu mình xài N phần tử thì sẽ biểu diễn được từ 0 đến 10^m^N-1 . Khi tính toán sẽ div/mod cho 10^m
Ví dụ:
Nếu mỗi phần tử là 1 byte => mỗi phần tử sẽ có giá trị từ 0 đến 99 (m=2). Nếu mình xài N phần tử (N bytes) thì sẽ biểu diễn được từ 0 đến 100^N-1 . Khi tính toán sẽ div/mod cho 100
Nếu mỗi phần tử là 2 bytes => mỗi phần tử sẽ có giá trị từ 0 đến 9999 (m=4). Nếu mình xài N phần tử (2N bytes) thì sẽ biểu diễn được từ 0 đến 10000^N-1 . Khi tính toán sẽ div/mod cho 10000
Về mặt sử dụng bộ nhớ thì hướng 2 hiệu quả hơn là hướng 1.
Nếu cùng chọn hướng 2: giữa mỗi phần tử là 1 byte so với mỗi phần tử là 2 bytes thì sử dụng bộ nhớ hiệu quả như nhau. Tuy nhiên giả sử mình phảI tính tóan đến 10^100 thì nếu chọn mảng 50 phần tử (mỗi phần tử là 2 bytes) sẽ chỉ phải lặp 50 lần khi tính toán cho 1 số nguyên lớn; còn nếu chọn mảng 100 phần tử (mỗi phần tử là 1 byte) sẽ phải lặp 100 lần khi tính toán cho 1 số nguyên lớn
Nhận xét:
1) hướng 1 & 2: chưa xử dụng hết bộ nhớ hết "công suất". Ở huớng 1, 1 byte có thể biểu diễn đuợc từ 0 đến 255 mà mình chỉ xài để biểu diễn từ 0 đến 9. Ở huớng 2, 1 byte có thể biểu diễn đuợc từ 0 đến 255 mà mình chỉ xài để biểu diễn từ 0 đến 99; 2 bytes có thể biểu diễn đuợc từ 0 đến 65535 mà mình chỉ xài để biểu diễn từ 0 đến 9999 thôi
2) về tốc độ tính tóan: hướng 1 phải div/mod cho 10; hướng 2 phải div/mod cho 10^m (100, 10000, ...)
Tuy nhiên tui thấy vẫn còn có hướng thứ 3 (và chắc cũng có bạn đã thử qua rồi); xin nói thử các bạn xem sao nhé .
Huớng 3: cũng xài mảng; mỗi phần tử có giá trị từ 0 đến 2^m-1 . Nếu mình xài N phần tử thì sẽ biểu diễn được từ 0 đến 2^m^N-1 . Khi tính toán sẽ div/mod cho 2^m
Ví dụ:
Nếu mỗi phần tử là 1 byte => mỗi phần tử sẽ có giá trị từ 0 đến 255 (m=8). Nếu mình xài N phần tử (N bytes) thì sẽ biểu diễn được từ 0 đến 255^N-1 . Khi tính toán sẽ div/mod cho 256
Nếu mỗi phần tử là 2 bytes => mỗi phần tử sẽ có giá trị từ 0 đến 65535 (m=16). Nếu mình xài N phần tử (2N bytes) thì sẽ biểu diễn được từ 0 đến 65535^N-1 . Khi tính toán sẽ div/mod cho 65536
Như vậy: xử dụng bộ nhớ tạm gọi là hết "công suất". Về tốc độ tính toán: div/mod cho 2^m (255, 65535) có thể làm nhanh hơn bằng phép dịch (shift) các bit hoặc lấy thẳng từ byte đó (xài union)
Tuy nhiên, để in ngược lại kết quả chứa trong mảng ra lại dạng thập phân thì rắc rối hơn là hướng 1 & 2 . Nhưng giả sử mình muốn tính 30000! (hoặc 300000!) thì thứ nhứt là có khả năng hướng 1 & 2 mình 0 có đủ bộ nhớ (còn hướng 3 thì đủ); thứ nhì là nếu lặp 30000N (hoặc 300000N) lần (lặp 30000 (hoặc 300000) lần , mỗi lần N phần tử cho 1 số nguyên lớn) thì chuyển từ div/mod 10 (hay 100, 10000) qua dịch chuyển bit (hay lấy byte trực tiếp) có vẻ tốt thơn 1 tí . Cho dù mình tốn công trong việc in kết quả nhưng mình chỉ in kết quả có 1 lần mà thôi ?
Sau cùng, có thể với 1 bài toán nào đó, xài hướng 3 không có lợi gì lắm (về mặt xử dụng bộ nhớ hoặc tốc độ tính tóan) hơn so với hướng 1 & 2 (lập trình đơn giản hơn) . Nhưng mà tui nghĩ tạo thói quen "tìm 1 giải thuật khác" cũng là 1 điều có lợi, phải 0 các bạn ?
Theo kinh nghiệm của bản thân tui; những bài toán nào tui biết giải rồi (nhứt là những bài đơn giản) thường là những bài còn có cách giải khác. Nhưng vì nghĩ là đã có cách giải rồi nên ít khi nghĩ đến chuyện "tìm 1 giải thuật khác hơn giải thuật đang có" (đôi khi nghĩ "chạy cho ra là được qúa rồi; nghĩ thêm làm gì cho mệt" :))
Nếu có gì sai thì các bạn chỉ cho nhé .
hặc hặc hặc ! Cháu tính được 26534234234654263952850 .........23 ! Nói chung là chuỗi số dài lắm, wên không nhớ chính xác là mấy nữa, không vượt qua con 255 ký tự số :D. Thuật toán thì nói ra khá dài dòng lắm, và cũng đã wên mất lun rùi :D ( Cả mấy năm rùi :D ) . Anh tìm trong BOX Pascal có cái link share source làm bằng Pascal của cháu về thuật toán mã hóa chứng thực RSA, anh cứ xem nếu mà làm với số lớn nhiều và dài nhé ( Cái này cool đấy :D)
Bạn bebe nhận xét quá sắc, ko có thêm ý kiến.
Bài này tui chỉ mạo muội trình bày cách tính 14000! bàng cách dùng mảng lưu các chữ số tư..9
Thật ra bài toán tính 10000! là bài toán của bọn lớp ..... 3(?!?!??)
Các bạn ko tin à?
Bài toán lớp 3 như sau:
tính
12345
* 678
---------------
----------------
???????
Thì việc tính 10000! củng chỉ có thế
Đây là đoạn mã tính:
+>Đầu tiên là
Const m=50000;
+>Khai báo kiểu thập phân::
Type thapphan=0..9;
+> Sau đó khai báo mảng A để chứa cái số lớp 3 đó:
var a:array[1..m] of thapphan;
và nh,j:longint;(trong đó: nh là biến "NHỚ", như vd trên chẵng hạn 8 nhân 4 bằng 32 viết 2 NHỚ 3; còn j là biến duyệt).
xong phần khai báo
Đến đoạn tính( cực ngắn): theo thứ tự từng bước:
a[j]:=0 voi mọi j:0..m;
i:=1;
a[1]:=1;
nh:=0;
repeat
j:=1;
repeat
nh:=nh+i*a[j];
a[j]:=tg mod 10;(tương ứng với ví dụ trên là"......viết 2..."
nh:=nh div 10;(".....nhớ 3");
inc(j);
until j>d+1;(chú ý ở đây d là gì các bạn bit ko? d là số chữ số của (i-1)! + số chữ sồ của i đó, các bạn tự tìm nha. Nếu có bạn nào ko tìm được thì........ẹ cứ cho d=m là ổn).
inc(i);
until i>n;
Thế là xong.
Sau đó inra thì đơn giản rùi:
write(n,'!=');
for j:=d downto 1 do
write(a[j]);
Thế nào, các bạn đã tin đây là bài toán lớp 3 chưa.
Chú ý nhé:
Thuật toán trên chỉ tính được lên đến 10000!. (Và kết quả hoàn toàn chính xác, nếu bạn ko tin thử ... đặt bút tính xem...hehhe)hoặc cao hơn tí xíu( Lớp 3 thì thế là đủ rùi), còn bạn nào muốn tính cao hơn nữa thì có thay đổi tí chút:
Thứ nhất là thay cái mảng kia bằng cái danh sách( để tăng độ dài).
Thứ hai là thay cái biến nh đó đi, ko phải longint nữa mà bằng byte thui( thật ra là bằng 0..99 là đủ rùi).Tất nhiên sẽ kéo theo thay đổi nữa nếu bạn thay biến nh này.
và thứ 3 là như cách của bạn bebe đã nói.
Các bạn thử tìm đi, nếu các bạn thành công, chắc chắn kết quả sẽ thú vị hơn rất nhiều. Và việc thay đổi này củng chỉ là.....lớp 3 một lần nữa mà thôi.
Thôi, nhường đất lại cho các huynh. Mệt rùi, out đây.BYE!
(Trích nguyên xi trongĐTH.org)
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.