01/10/2018, 09:55
Tính số Catalan
Số Catalan được xác định bởi công thức :
Sau khi rút gọn ta được:
Để tính nó thì em dùng ct sau
program gin;
uses crt;
type bignum = String;
function munlti1(a : bignum; b : Longint) : bignum; //hàm nhân số nguyên lớn cho số nhỏ
var
du, s : Longint;
i : Integer;
c, tmp : bignum;
begin
c := ';
du := 0;
for i := Length(a) downto 1 do
begin
s := b*(ord(a[i])- 48) + du;
du := s div 10;
c := chr(s mod 10 + 48) + c;
end;
if du > 0 then str(du, tmp) else tmp := ';
exit(tmp + c);
end;
function bigdiv1(a : bignum; b : longint) : bignum; //hàm chia số nguyên lón cho số nhỏ
var
hold, s : longint;
i : Integer;
c : bignum;
begin
hold := 0;
c := ';
for i := 1 to Length(a) do
begin
hold := hold * 10 + ord(a[i]) -48;
s := hold div b;
hold := hold mod b;
c := c + chr(s + 48);
end;
while (Length(c) > 0) and (c[1] = '0') do delete(c, 1, 1);
exit(c);
end;
var
n, i : longint;
s : bignum;
begin
write('Nhap N : ');
readln(n);
s := '1';
for i := n+2 to 2*n do
s := munlti1(s, i);
for i := 1 to n do
s := bigdiv1(s, i);
writeln(s);
end.
Nhưng mà trong tài liệu nói là có thể rút gọn hoàn toàn mẫu số của phân số đó để chỉ sử dụng hàm nhân số nguyên lớn với số nhỏ, vậy làm sao để rút gọn phân số đó ạ???
Bài liên quan
Tử số có thể phân tích thành
n! * a * b *...được mà. Bạn thử viết ra giấy xem.Ít nhất thì thấy (2n) có thể rút được n và 2 rồi.
-> 2(n-1) rút được n-1, 2*(n-2) rút được n-2
Em thì em chưa học phần giai thừa nên em mù tịt anh ạ, anh rút giúp em được hông??
Giai thừa: n! = 1 * 2 * 3 *… * n
Bạn nghĩ thêm một chút nữa nhé, mình nhớ nguồn bài này là ở UVa, bạn search google “calalan number uva solution” hoặc “combinatorics uva solution” nhé.
123*…(n + 1) = (n+1)!
123…2n = (2n)!
=> (n+2)(n+3)…(2n) = (2n)!/(n+1)!
=> Số catalan chuyển lại thành (2n)! / [ (n+1)! * n!]
=> (2n)! / [ (n+1) * n!^2]
Nói chung viết hàm tính giai thừa là cách giải dễ nhất
Đúng là nếu số nhỏ thì viết hàm giai thừa là dễ nhất nhưng với số cực lớn thì cách đó thành ra phức tạp nhất ạ
http://www.luschny.de/math/swing/SwingingFactorial.html
Hàm tính thì số nhỏ số lớn ảnh hưởng gì?
Nếu dùng giai thừa thì phải viết một cái hàm nhân 2 số lớn với nhau, mà để có hàm nhân hai số lớn thì phải có hàm cộng hai số lớn và hàm nhân số lớn với số nhỏ => tổng cộng là có 3 hàm, trong khi cái cách em thì chỉ dùng 2 hàm, còn nếu rút gọn được thì chỉ cần 1 hàm nhân số lớn với số nhỏ là OK!!!
Có đấy bạn. Các thuật toán nhân số lớn đều khống chế số chữ số của số nguyên lớn, vì vậy hai thừa số phải xêm xêm nhau thì mới tận dụng được.
Nếu chỉ nhân số lớn với số nhỏ thì số bước luôn là theta(n^2), quá tệ với n vào hàng 10k trở lên.
Mình nghĩ là có cần số lớn, nhưng có thể khử mẫu được bằng cách dùng toán chứ không phải nhân 2 cái giai thừa to tướng :v
Việc này giống như kiểu phân tích số thành các thừa số thôi mà.