# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  dãy N cặp ngoặc !!!

## nguyenhuongit

Cho 1 số nguyên dương N là số cặp ngoặc "(" và ")" trong dãy X.
Đếm xem có bao nhiêu dãy ngoặc đúng được hình thành từ N cặp ngoặc này.
vd :
với n=2, xây dựng được 2 dãy ngoặc đúng là :
1: ( ( ) )
2: ( ) ( )

chú ý :
ko tồn tại dãy: ) ) ( ( do đây ko là dãy ngoặc đúng

INPUT :
số nguyên dương N 

OUTPUT :
1 số duy nhất là số lượng dãy ngoặc đúng có thể hình thành được


vd:
INPPUT:
1
OUTPUT:
1

INPUT:
4
OUTPUT:
14

INPUT:
5
OUTPUT:
42

bạn nào giỏi toán thành lập công thức cho mình nhe
thanks trước !!!

----------


## dungthinh225

Bài này chỉ số nhỏ à, số lớn thì ngồi chờ. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## vlvietlamvl

liệu có công thức cho bài này ko vậy anh ???
nếu tổ hợp thì em cũng ko bít loại bỏ đi phần đã bị đếm rồi ntn nữa, vì đơn giản là em chưa học tổ hợp, chỉ suy nghĩ vu vơ thôi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## 36hoangcau

*Cách này không tối ưu. Nhưng để anh tìm xem sao.

*


```

Const Fi='capngoac.inp';
      Fo='capngoac.out';

Var   F:text;
      X:string;
      D,N:Qword;

Procedure Inp;
Var   i:Byte;
Begin
      Assign(F,Fi);
      Reset(F);
      Readln(F,N);
      X:='';
      For i := 1 To N Do
            X := X + '';
      Close(F);
End;

Function KT : Boolean;
Var   i,k : Integer;
Begin
      k:=0;
      KT := True;
      For i:=1 To 2*n Do
      Begin
            If x[i] = '(' Then Inc(k)
            Else Dec(k);
            If k < 0 Then
            Begin
                  KT := False;
                  Exit;
            End;
      End;
      If k <> 0 Then KT := False;
End;

Procedure Try(i : Byte);
Var   j : Byte;
Begin
      For j := 40 To 41 Do
      Begin
            x[i] := Char(j);
            If (i = 2*n) Then
            Begin
                  If KT Then Inc(d);
            End
            Else Try(i+1);
      End;
End;

Procedure Pri;
Begin
      Assign(F,Fo);
      Rewrite(F);
      D := 0;
      Try(1);
      Write(F,D);
      Close(F);
End;

Begin
      Inp;
      Pri;
End.
```

----------


## sangdv291

Nguyên nghĩ ra cách này, đơn giản bài toán đi, vì đề chỉ yêu cầu in ra số lượng đúng, nên ta không cần phải in các cặp đó ra. 
Chuyển bài toán về: tính tổng các hoán vị của số nhị phân độ dài 2n sao cho:
+ n là số cặp ngoặc bài nhập vào.
+ 0 là ")", 1 là "(".
+ Trong hoán vị phải thỏa mãn điều kiện số lượng số 0 bằng số lượng số 1.
+ Số đứng đầu của hoán vị phải là 1, cuối cùng là số 0.
Có lẽ giải theo quay lui, kết hợp nhánh cận, mình sẽ cố gắng.!

----------


## cuongcung

> nếu tổ hợp thì em cũng ko bít loại bỏ đi phần đã bị đếm rồi ntn nữa, vì đơn giản là em chưa học tổ hợp, chỉ suy nghĩ vu vơ thôi


Em đừng lo. Vừa học xong chương I rồi đó, chuẩn bị học tới Chương II và Bài 2 có tựa đề là *Hoán vị - Chỉnh hợp, tổ hợp - Nhị thức Newtơn* rồi. Chúc em sớm tìm ra công thức. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

----------


## yentatoo

> Em đừng lo. Vừa học xong chương I rồi đó, chuẩn bị học tới Chương II và Bài 2 có tựa đề là *Hoán vị - Chỉnh hợp, tổ hợp - Nhị thức Newtơn* rồi. Chúc em sớm tìm ra công thức. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])


 Mình cung cấp luôn nè:
Tổng số các hoán vị n số nguyên dương đầu tiên: n!.
Chỉnh hợp n chập r: A(n,r)=n!/(n-r)!.
Tổ hợp n chập r: C(n,r)=A(n,r)/r!=n!/((n-r)!*r!)=C(n-1,k)+c(n-1,k-1). Với C(n,n)=C(n,0)=1.
Nhị thức newton biểu diễn dưới dạng:
(a+b)^n=C(n,0)*a^n+C(n,1)*a^(n-1)*b+C(n,2)*a^(n-2)*b^2+...+C(n,n-1)*a*b^(n-1)+C(n,n)*b^n.
_Chúc bạn học tốt._
*Thân.:book:*

----------


## quyend832

> Nguyên nghĩ ra cách này, đơn giản bài toán đi, vì đề chỉ yêu cầu in ra số lượng đúng, nên ta không cần phải in các cặp đó ra. 
> Chuyển bài toán về: tính tổng các hoán vị của số nhị phân độ dài 2n sao cho:
> + n là số cặp ngoặc bài nhập vào.
> + 0 là ")", 1 là "(".
> + Trong hoán vị phải thỏa mãn điều kiện số lượng số 0 bằng số lượng số 1.
> + Số đứng đầu của hoán vị phải là 1, cuối cùng là số 0.
> Có lẽ giải theo quay lui, kết hợp nhánh cận, mình sẽ cố gắng.!


- Quay lui chỉ đc n<=10 thôi e
- số lượng 0 = số lượng 1 thế này thì sao )))(((
- số đứng đầu là 1, số cuối là 0 , thế này thì sao ())(()

mà sao e cứ phang công thức vậy , quay lui là in ra cái trường hợp chứ có bảo e đếm trường hợp đâu mà phang công thức làm j`

----------


## phamhoasp

> - Quay lui chỉ đc n<=10 thôi e
> - số lượng 0 = số lượng 1 thế này thì sao )))(((
> - số đứng đầu là 1, số cuối là 0 , thế này thì sao ())(()
> 
> mà sao e cứ phang công thức vậy , quay lui là in ra cái trường hợp chứ có bảo e đếm trường hợp đâu mà phang công thức làm j`


 Cám ơn chị hằng nhiều nhé, Nguyên quên mất đề yêu cầu in số lượng.
_Vậy điều kiện trên không mô tả đầy đủ rồi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]. Nguyên tính trả về bài toán nhị phân, chắc phải thêm tính chất :"có mở phải có đóng", "không được chưa mở đã đóng" ... => Qui hoạch động phải không chị hằng???_

----------


## huahien

Bài này dùng QHĐ mới giải quyết được với số lượng lớn. Nếu quay lui chạy rất lâu.

----------


## hajdajgja

Em cố gắng giải thử, khi nào có anh góp ý nhé [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## giangnt

quay lui cũng tới 36 àh , phải k Hiếu [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
dk của e tất nhiên là thiếu r` [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) . Thử làm bài đơn giản này nhé Nguyên : kiểm tra tính đúng đắn của 1 xâu gồm các dấu ngoặc

----------


## hungsanphuongdong

QHĐ thì được đến 36 là max rồi
cao hơn thì tràn Qword.
Nhưng mà mình lại ko nghĩ ra công thức tổng quát cho n bất kỳ, như là công thức tổ hợp hay đại loại thế í

----------


## skygame

> quay lui cũng tới 36 àh , phải k Hiếu [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
> dk của e tất nhiên là thiếu r` [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) . Thử làm bài đơn giản này nhé Nguyên : kiểm tra tính đúng đắn của 1 xâu gồm các dấu ngoặc


 Thuật toán thế này, chị hằng xem thử nhá:
- Cho một mảng để kiểm tra, ban đầu =0;
- Gặp '(' thì a_=1. inc(i);
- Gặp ')' thì kiểm tra nếu a[i-1]=0 => không hợp lệ. Dừng.
Ngược lại dec(i);a=0;
- Nếu hết xâu mà mảng a có phần tử khác 0 => không hợp lệ. 
Ngược lại (tất cả =0) => hợp lệ.
Chị Hằng xem xét, cải thiện nhé.!:emlaugh:_

----------


## phukiensamsung

```
uses crt;
var s:string;

function hople(s:string):boolean;
var i,j:integer;
begin
      j:=0;
      hople:=true;
      for i:=1 to length(s) do
      begin
            if s[i]='(' then inc(j) else dec(j);
            if j<0 then
            begin
                  hople:=false;
                  exit;
            end;
      end;
      if j<>0 then hople:=false;
end;

begin
      clrscr;
      write('Nhap day dau ngoac : ');
      readln(s);
      if hople(s) then writeln('Day ngoac hop le')
      else writeln('Day ngoac khong hop le');
      readln;
end.
```

coi ùi tự bổ sung thuật toán của e nha . Thuật toán chưa giải quyết đc tất các th đâu

----------


## nanivodoi

> ```
> uses crt;
> var s:string;
>  
> function hople(s:string):boolean;
> var i,j:integer;
> begin
>       j:=0;
>       hople:=true;
> ...


 Cách của chị tiết kiệm tài nguyên bộ nhớ, dễ hiểu.
*Thanks!*

----------


## developers

cách ktra này của Hằng đúng đấy
trở lại bài toán của tui nhe 
Hằng quay lui để sinh dãy ngoặc rồi mới ktra, chi bằng dùng 1 biến đếm để loại sớm 1 số trường hợp đi.
lấy vd nhe :
dem:=0; { giá trị ban đầu là 0 nà }
sinh ra dãy ( ( ) ) ).... thì đếm bi giờ có giá trị là -1, loại
đúng theo ý tưởng ktra của Hằng đó
và còn, nếu như dem>n thì cũng loại lun nà, rồi ...... các trường hợp khác cũng loại được sớm nữa

----------


## vietkanpy

length(s) lẻ ?
--------------------------------------------

----------


## xecutkit

Liệu phương án quay lui và kiểm tra ngoặc đúng có chịu đựng nổi với dữ liệu vào hàng chục không, dù có kết hợp nhánh cận đi chăng nữa?
Phương pháp liệt kê tỏ ra không tốt rồi!#-o
Có ai có bài giải tối ưu về đề này không??[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG][IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## dqua99

a Hiếu đang hỏi mà sao e lại lật ngược vấn đề [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])
@ Hiếu : vào 4rum sao k onl yh ? Ra yh hỏi tí

----------


## aduy1992

> length(s) lẻ ?
> --------------------------------------------


uh
mặc dù chưa đủ cấu hình, nhưng nếu xảy ra các điều như thế thì sinh thêm các phần tử tiếp theo cũng ko làm chuỗi s trở thành dãy ngoặc đúng, đúng ko nào ??? Vậy loại sớm đi

----------


## quanglong87

> Liệu phương án quay lui và kiểm tra ngoặc đúng có chịu đựng nổi với dữ liệu vào hàng chục không, dù có kết hợp nhánh cận đi chăng nữa?
> Phương pháp liệt kê tỏ ra không tốt rồi!#-o
> Có ai có bài giải tối ưu về đề này không??[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG][IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]


mình thì mình có bài giải bằng QHĐ đây, nhưng mình là mình mún tìm công thức tổng quát cơ !!!
nếu bạn cần mình post lên để test kq nhe !!!

1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440
15 9694845
16 35357670
17 129644790
18 477638700
19 1767263190
20 6564120420
21 24466267020
22 91482563640
23 343059613650
24 1289904147324
25 4861946401452
26 18367353072152
27 69533550916004
28 263747951750360
29 1002242216651368
30 3814986502092304
31 14544636039226909
32 55534064877048198
33 212336130412243110
34 812944042149730764
35 3116285494907301262
36 11959798385860453492

----------


## Vibe89

> mình thì mình có bài giải bằng QHĐ đây, nhưng mình là mình mún tìm công thức tổng quát cơ !!!
> nếu bạn cần mình post lên để test kq nhe !!!


 Bạn post lên đi, cho các bạn khác học hỏi, tối ưu hóa .[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## fbi098

mình bổ sung bài viết rồi đó bạn
kq mình in ra mỗi dòng tương ứng với n (input) đó !!!

----------

