Tính số Catalan

[tanviet]

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ố đó ạ???

[noname00 (HK boy)]

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 (2*n) 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

[tanviet]

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??

[noname00 (HK boy)]

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é.

[noz1995 (Trần Hoàn)]

1*2*3*...*(n + 1) = (n+1)!
1*2*3*...*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

[tanviet]

Đú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 ạ

[noz1995 (Trần Hoàn)]

Hàm tính thì số nhỏ số lớn ảnh hưởng gì?

[tanviet]

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!!!

[rogp10]

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.

[noname00 (HK boy)]

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

tử có 2*n -> khử 2 và n ở mẫu
tử có 2*(n-1) -> khử 2 và (n-1) ở mẫu
...
-> TS = (2k)*(2k+1)*(2k+2)*...*(2(n-1))*(2n-1)*(2n)
      = [2n*2(n-1)*2(n-2)*...*2k] * [(2n-1)(2n-3)...(2k-1)]
      = 2^(n-k+1) * [n(n-1)(n-2)...k] * [(2n-1)(2n-3)...(2k-1)]

-> TS/(n!) = 2^(n-k+1) * [n(n-1)(n-2)...k] * [(2n-1)(2n-3)...(2k-1)] / n!
           = 2^(n-k+1) * [(2n-1)(2n-3)...(2k-1)] / [(k-1)(k-2)...*2*1]
...

Việc này giống như kiểu phân tích số thành các thừa số thôi mà.

[Thu_Trang3 (Thu Trang)]

Hy vọng giúp được bạn ^^

#include<stdio.h>
#include<math.h>
int tinhGiaiThua(int n)
{
	if( n == 1) return 1;
	else return n * tinhGiaiThua(n - 1);
}
int main(){
	int n;
	scanf("%d", &n);
	printf("KQ = %g", (float)tinhGiaiThua(2*n) / ( (float)tinhGiaiThua(n + 1) * (float)tinhGiaiThua(n) ));
return 0;
}

[noname00 (HK boy)]

Thớt dùng Pascal mà bạn.

[Sherly1001]

Convert cho bạn nè. Free nhá.

program Sherly1001;
var n, kq : real;

function tinhGiaiThua(n : real) : real;
begin
    if (n = 1) then begin
        tinhGiaiThua := 1;
        exit;
    end
    else
        tinhGiaiThua := n * tinhGiaiThua(n - 1);
end;

begin
    readln(n);
    kq := tinhGiaiThua(2 * n) / (tinhGiaiThua(n + 1) * tinhGiaiThua(n));
    writeln('KQ = ', kq);
end.

P/s: Highlight có vẻ k hỗ trợ pascal mấy nhỉ.