Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 2
CHỦ ĐỀ - Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !!
#66783
itviapro (Thành viên)
Đang tập code
Bài viết: 2
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 3 tháng trước   (+0)
Các pro chỉ giùm mình cách tính n! , n^n với số n rất lớn với @@
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#66786
blackstart (Thành viên)
blackstart+40
Không code nữa rồi
Bài viết: 362
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 3 tháng trước   (+0)
bạn có thể vào thư viện xem cách xử lí số lớn và làm thử bài BIGNUM
 
Đã lưu IP Đã lưu IP  
 
"Nothing is impossible; impossible itself says "I m possible"..."


Là Nam Nhi gõ phím bình thiên hạ...
Thân Anh Hùng click chuột định giang sơn...
  Đã khóa chức năng gửi bài.
#66806
compoko (Thành viên)
compoko
Đã biết code đệ quy
Bài viết: 6
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 3 tháng trước   (+0)
mới học viết n!,
Code:
 
Uses Math,windows;
Const
fi              ='';
fo              ='';
MAXN            =100000;
CS              =1000000000;
MAXX            =15000000000;
 
Type
num  = Qword;
snum = longint;
 
Var
a               : array [0..MAXN] of num;
c2,c5           : longint;
sz              : snum;
dau,cuoi    : int64;
 
function gt     : int64;
begin
    exit(gettickcount);
end;
 
Procedure Mul(x: num);
var i           : snum;
begin
    for i:=1 to sz do
        a[i]:=a[i]*x;
    for i:=1 to sz-1 do
        begin
           inc(a[i+1],a[i] div CS);
           a[i]:=a[i] mod CS;
        end;
while a[sz]>CS do
        begin
            inc(sz);
            inc(a[sz],a[sz-1] div CS);
            a[sz-1]:=a[sz-1] mod CS;
        end;
end;
 
Procedure G2(var y: num);
begin
while y mod 2 = 0 do
        begin
            y:=y div 2;
            inc(c2);
        end;
end;
 
Procedure G5(var y: num);
begin
    while y mod 5 = 0 do
        begin
            y:= y div 5;
            inc(c5);
        end;
end;
 
Procedure nhap;
var n,x,y      : num;
 
begin
    assign(input,fi);reset(input);
    a[1]:=1;
    sz:=1;
                 readln(n);
                 while n>1 do
                        begin
                        x:=n*(n-1); dec(n,2);
                        while (x*n<MAXX) and (n>1) do
                                begin
                                    y:=x;
                                    G2(y);G5(y);
                                    x:=y*n;
                                    dec(n);
                                end;
                        mul(x);
                        end;
    close(input);
end;
 
Procedure xuly;
var k             : longint;
        x,y       : num;
begin
k:=min(c5,c2);
if k = 0 then exit;
if c2>c5 then x:=2 else x:=5;
        while k<max(c5,c2) do
                begin
                    y:=1;
                    while (y*x<MAXX) and (k<max(c5,c2)) do
                        begin
                            inc(k);
                            y:=y*x;
                        end;
                Mul(y);
                end;
end;
 
Procedure ghi(x: num);
var t           : num = CS div 10;
begin
while t>x do
        begin
            write(0);
            t:=t div 10;
        end;
if x>0 then
write(x);
end;
 
Procedure xuat;
var i           : snum;
begin
    assign(output,fo);rewrite(output);
    write(a[sz]);
    for i:=sz-1 downto 1 do
        ghi(a[i]);
    for i:=1 to min(c2,c5) do write(0);
    close(output);
end;
 
BEGIN
dau:=gt;cuoi:=gt;
 
{--------------------------------------}
                  NHAP;
{--------------------------------------}
 
writeln('NHAP: ',gt-cuoi);
cuoi:=gt;
 
{--------------------------------------}
                  XULY;
{--------------------------------------}
 
writeln('XULY: ',gt-cuoi);
cuoi:=gt;
 
{--------------------------------------}
                  XUAT;
{--------------------------------------}
 
assign(output,'');rewrite(output);
writeln('XUAT: ',gt-cuoi);
writeln('Tong thoi gian chay chuong trinh : ',gt-dau);
close(output);
END.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67310
quandum (Thành viên)
quandum+14
Nhắm mắt code không bug
Bài viết: 261
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 2 tháng trước   (+0)
N! thì chắc phải trâu O(n) thôi. n!=(n-1)!*n

Còn n^n thì mình có thể tách thành
n^n = ( ( n^( n div 2 ) ) ^ 2 ) * ( n^( n mod 2 ) )
còn phần xử lý số lớn thì tuỳ mõi người có cách khác nhau.
 
Đã lưu IP Đã lưu IP  
 
Nhất trường, nhất tỉnh làm chi?
Cũng là con ếch ngồi lì giếng hôi...
  Đã khóa chức năng gửi bài.
#68117
sang23121996 (Thành viên)
sang23121996
Đã biết code đệ quy
Bài viết: 8
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 1 tháng trước   (+0)
compoko viết:
QUOTE:
mới học viết n!, :)
Code:
 
Uses Math,windows;
Const
fi              ='';
fo              ='';
MAXN            =100000;
CS              =1000000000;
MAXX            =15000000000;
 
Type
num  = Qword;
snum = longint;
 
Var
a               : array [0..MAXN] of num;
c2,c5           : longint;
sz              : snum;
dau,cuoi    : int64;
 
function gt     : int64;
begin
    exit(gettickcount);
end;
 
Procedure Mul(x: num);
var i           : snum;
begin
    for i:=1 to sz do
        a[i]:=a[i]*x;
    for i:=1 to sz-1 do
        begin
           inc(a[i+1],a[i] div CS);
           a[i]:=a[i] mod CS;
        end;
while a[sz]>CS do
        begin
            inc(sz);
            inc(a[sz],a[sz-1] div CS);
            a[sz-1]:=a[sz-1] mod CS;
        end;
end;
 
Procedure G2(var y: num);
begin
while y mod 2 = 0 do
        begin
            y:=y div 2;
            inc(c2);
        end;
end;
 
Procedure G5(var y: num);
begin
    while y mod 5 = 0 do
        begin
            y:= y div 5;
            inc(c5);
        end;
end;
 
Procedure nhap;
var n,x,y      : num;
 
begin
    assign(input,fi);reset(input);
    a[1]:=1;
    sz:=1;
                 readln(n);
                 while n>1 do
                        begin
                        x:=n*(n-1); dec(n,2);
                        while (x*n<MAXX) and (n>1) do
                                begin
                                    y:=x;
                                    G2(y);G5(y);
                                    x:=y*n;
                                    dec(n);
                                end;
                        mul(x);
                        end;
    close(input);
end;
 
Procedure xuly;
var k             : longint;
        x,y       : num;
begin
k:=min(c5,c2);
if k = 0 then exit;
if c2>c5 then x:=2 else x:=5;
        while k<max(c5,c2) do
                begin
                    y:=1;
                    while (y*x<MAXX) and (k<max(c5,c2)) do
                        begin
                            inc(k);
                            y:=y*x;
                        end;
                Mul(y);
                end;
end;
 
Procedure ghi(x: num);
var t           : num = CS div 10;
begin
while t>x do
        begin
            write(0);
            t:=t div 10;
        end;
if x>0 then
write(x);
end;
 
Procedure xuat;
var i           : snum;
begin
    assign(output,fo);rewrite(output);
    write(a[sz]);
    for i:=sz-1 downto 1 do
        ghi(a[i]);
    for i:=1 to min(c2,c5) do write(0);
    close(output);
end;
 
BEGIN
dau:=gt;cuoi:=gt;
 
{--------------------------------------}
                  NHAP;
{--------------------------------------}
 
writeln('NHAP: ',gt-cuoi);
cuoi:=gt;
 
{--------------------------------------}
                  XULY;
{--------------------------------------}
 
writeln('XULY: ',gt-cuoi);
cuoi:=gt;
 
{--------------------------------------}
                  XUAT;
{--------------------------------------}
 
assign(output,'');rewrite(output);
writeln('XUAT: ',gt-cuoi);
writeln('Tong thoi gian chay chuong trinh : ',gt-dau);
close(output);
END.
vậy code này dùng cho n khoảng bao nhiêu vậy ạ?
 
Đã lưu IP Đã lưu IP  
 
Anh đã code thì mốt mới AC ))))
  Đã khóa chức năng gửi bài.
#68124
compoko (Thành viên)
compoko
Đã biết code đệ quy
Bài viết: 6
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 1 tháng trước   (+0)
150000 đổ xuống
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68980
nguyennhatanh (Thành viên)
nguyennhatanh-
Đã biết code đệ quy
Bài viết: 5
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 1 tháng trước   (+0)
ờm! mình chỉ hướng dẫn bạn cách xử lí số nguyên lớn thôi nhé! còn phần còn lại bạn tính n! như bình thường thôi:
{$MODE OBJFPC}
program BIGNUM;
type
sn=record
num:longint;
digit:array[0..500] of longint;
end;

const
tfi='BIGNUM.INP';
tfo='BIGNUM.OUT';
coso=100000000;
cs=8;

var
fi,fo:text;


procedure doc(var x:sn);
var i,j,p:longint;
a:array[1..1001] of char;
ch:char;
begin
repeat
read(fi,ch);
until (ch>='0' and (ch<='9';
p:=1; a[1]:=ch;
while not eof(fi) do
begin
read(fi,ch);
if (ch<'0' or (ch>'9' then break;
inc(p);a[p]:=ch;
end;
with x do
begin
num:=-1;
while p>0 do
begin
i:=p-cs+1;
if i<1 then i:=1;
inc(num);
digit[num]:=0;
for j:=i to p do digit[num]:=digit[num]*10+ord(a[j])-48;
p:=i-1;
end;
while (num>0) and (digit[num]=0) do dec(num)
end;
end;

procedure tong(a,b:sn;var c:sn);
var i,nho,tong:longint;
begin
c.num:=a.num;
if c.num<b.num then c.num:=b.num;
for i:=a.num+1 to c.num do a.digit[i]:=0;
for i:=b.num+1 to c.num do b.digit[i]:=0;
nho:=0;
for i:=0 to c.num do
begin
tong:=a.digit[i]+b.digit[i]+nho;
c.digit[i]:=tong mod coso;
nho:=tong div coso;
end;
if nho>0 then
begin
inc(c.num);
c.digit[c.num]:=1;
end;
end;

procedure viet(var x:sn);
var i:longint;
s:AnsiString;
begin
with x do
begin
write(fo,digit[num]);
for i:=num-1 downto 0 do
begin
str(digit[i],s);
while length(s)<cs do s:='0'+s;
write(fo,s);
end;
end;
writeln(fo);
end;

function lonhon(var a,b:sn):boolean;
var i:longint;
begin
if a.num>b.num then exit(true);
if a.num<b.num then exit(false);
i:=a.num;
while (i>=0) and (a.digit[i]=b.digit[i]) do dec(i);
lonhon:=(i>=0) and (a.digit[i]>b.digit[i]);
end;

procedure tru(a,b:sn; var c:sn);
var nho,hieu,i:longint;
begin
c.num:=a.num;
for i:=b.num+1 to c.num do b.digit[i]:=0; nho:=0;
for i:=0 to c.num do
begin
hieu:=a.digit[i]-b.digit[i]-nho;
if hieu<0 then
begin
hieu:=hieu+coso;
nho:=1;
end
else nho:=0;
c.digit[i]:=hieu;
end;
while (c.num>0) and (c.digit[c.num]=0) do dec(c.num);
end;


procedure nhan(a,b:sn; var c:sn);
var tich,nho,s:int64;
i,j:longint;
begin
c.num:=a.num+b.num;
for i:=a.num+1 to c.num do a.digit[i]:=0;
for i:=b.num+1 to c.num do b.digit[i]:=0;
nho:=0;
for i:=0 to c.num do
begin
tich:=nho;
for j:=0 to i do
begin
s:=a.digit[j];
tich:=tich+s*b.digit[i-j];
end;
c.digit[i]:=tich mod coso; nho:=tich div coso;
end;
while nho>0 do
begin
inc(c.num);
c.digit[c.num]:=nho mod coso;
nho:=nho div coso;
end;
while (c.num>0) and (c.digit[c.num]=0) do dec(c.num);
end;


procedure main;
var a,b,c,d,e:sn;
begin
assign(fi,tfi);reset(fi);
assign(fo,tfo);rewrite(fo);
doc(a);doc(b);
tong(a,b,c); viet(c);
if lonhon(b,a) then
begin
tru(b,a,d);
write(fo,'-';viet(d);
end
else
begin
tru(a,b,d);
viet(d);
end;
nhan(a,b,e);viet(e);
close(fi);close(fo);
end;

BEGIN
main;
END.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68981
nguyennhatanh (Thành viên)
nguyennhatanh-
Đã biết code đệ quy
Bài viết: 5
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 1 tháng trước   (+0)
đây là file .pas
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68982
nguyennhatanh (Thành viên)
nguyennhatanh-
Đã biết code đệ quy
Bài viết: 5
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán tính n! , n^n , khi n rất lớn !! 8 năm, 1 tháng trước   (+0)
{$MODE OBJFPC}
program BIGNUM;
type
sn=record
num:longint;
digit:array[0..500] of longint;
end;

const
tfi='BIGNUM.INP';
tfo='BIGNUM.OUT';
coso=100000000;
cs=8;

var
fi,fo:text;


procedure doc(var x:sn);
var i,j,p:longint;
a:array[1..1001] of char;
ch:char;
begin
repeat
read(fi,ch);
until (ch>='0' and (ch<='9';
p:=1; a[1]:=ch;
while not eof(fi) do
begin
read(fi,ch);
if (ch<'0' or (ch>'9' then break;
inc(p);a[p]:=ch;
end;
with x do
begin
num:=-1;
while p>0 do
begin
i:=p-cs+1;
if i<1 then i:=1;
inc(num);
digit[num]:=0;
for j:=i to p do digit[num]:=digit[num]*10+ord(a[j])-48;
p:=i-1;
end;
while (num>0) and (digit[num]=0) do dec(num)
end;
end;

procedure tong(a,b:sn;var c:sn);
var i,nho,tong:longint;
begin
c.num:=a.num;
if c.num<b.num then c.num:=b.num;
for i:=a.num+1 to c.num do a.digit[i]:=0;
for i:=b.num+1 to c.num do b.digit[i]:=0;
nho:=0;
for i:=0 to c.num do
begin
tong:=a.digit[i]+b.digit[i]+nho;
c.digit[i]:=tong mod coso;
nho:=tong div coso;
end;
if nho>0 then
begin
inc(c.num);
c.digit[c.num]:=1;
end;
end;

procedure viet(var x:sn);
var i:longint;
s:AnsiString;
begin
with x do
begin
write(fo,digit[num]);
for i:=num-1 downto 0 do
begin
str(digit[i],s);
while length(s)<cs do s:='0'+s;
write(fo,s);
end;
end;
writeln(fo);
end;

function lonhon(var a,b:sn):boolean;
var i:longint;
begin
if a.num>b.num then exit(true);
if a.num<b.num then exit(false);
i:=a.num;
while (i>=0) and (a.digit[i]=b.digit[i]) do dec(i);
lonhon:=(i>=0) and (a.digit[i]>b.digit[i]);
end;

procedure tru(a,b:sn; var c:sn);
var nho,hieu,i:longint;
begin
c.num:=a.num;
for i:=b.num+1 to c.num do b.digit[i]:=0; nho:=0;
for i:=0 to c.num do
begin
hieu:=a.digit[i]-b.digit[i]-nho;
if hieu<0 then
begin
hieu:=hieu+coso;
nho:=1;
end
else nho:=0;
c.digit[i]:=hieu;
end;
while (c.num>0) and (c.digit[c.num]=0) do dec(c.num);
end;


procedure nhan(a,b:sn; var c:sn);
var tich,nho,s:int64;
i,j:longint;
begin
c.num:=a.num+b.num;
for i:=a.num+1 to c.num do a.digit[i]:=0;
for i:=b.num+1 to c.num do b.digit[i]:=0;
nho:=0;
for i:=0 to c.num do
begin
tich:=nho;
for j:=0 to i do
begin
s:=a.digit[j];
tich:=tich+s*b.digit[i-j];
end;
c.digit[i]:=tich mod coso; nho:=tich div coso;
end;
while nho>0 do
begin
inc(c.num);
c.digit[c.num]:=nho mod coso;
nho:=nho div coso;
end;
while (c.num>0) and (c.digit[c.num]=0) do dec(c.num);
end;


procedure main;
var a,b,c,d,e:sn;
begin
assign(fi,tfi);reset(fi);
assign(fo,tfo);rewrite(fo);
doc(a);doc(b);
tong(a,b,c); viet(c);
if lonhon(b,a) then
begin
tru(b,a,d);
write(fo,'-';viet(d);
end
else
begin
tru(a,b,d);
viet(d);
end;
nhan(a,b,e);viet(e);
close(fi);close(fo);
end;

BEGIN
main;
END.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS