Очередная несложная задачка для разминки;)

← →
MBo (2002-11-21 10:03) [0]

Найти количество S пpавильных скобочных последовательностей длины 2N (1<=N<=30)
Пpимеp: 2N=6:
((())), (()()), ()()(), (())(), ()(())
S= 5

Задача, естественно, не в нахождении формулы, а в составлении алгоритма программы

(взято с fido.ru.algoritms)

← →
McSimm (2002-11-21 10:43) [1]

Очевидное решение - рекурсивно.
Может есть неочевидное и более простое?

← →
MBo (2002-11-21 10:45) [2]

я тоже рекурсивно делал, без рекурсии пока не пробовал

← →
Igorek (2002-11-21 10:49) [3]

> MBo © (21.11.02 10:03)

На выходные надо задавать, когда время есть. А то работа еще...
:-)

← →
Igorek (2002-11-21 10:52) [4]

> McSimm © (21.11.02 10:43)
> Очевидное решение - рекурсивно.
> Может есть неочевидное и более простое?

В любом случае алгоритм аналогичный рекурсивному. Можно через стек. Также можно дать рекурентную формулу.

← →
Alx2 (2002-11-21 11:53) [5]

Хм... :))

function sCount(stop, sum: integer): Integer; begin if stop = 0 then Result := cardinal(sum=0) else begin Result := sCount(stop - 1, sum + 1); if sum > 0 then inc(Result, sCount(stop - 1, sum - 1)); end; end; begin ShowMessage(IntToStr(sCount(6 {длина последовательности}, 0))); end;

← →
Оливейра (2002-11-21 12:56) [6]

На CBOSS.ru такую х... на тестовом задании предлагают, только на голых сях. В общем-то нерекурсивно даже проще - ищется первая открывающая скобка, копируется указатель на нее, во вложенном втором цикле ищется, начиная с этого указателя, закрывающая и подсчитывается количество открывающих и закрывающих скобок, найденных попутно. Если найдена закрывающая и число найденных открывающих равно числу закрывающих (0-0, 1-1 и т.п.) значит, найдена парная.

← →
Alx2 (2002-11-21 13:44) [7]

>Оливейра © (21.11.02 12:56)
"Найти количество S пpавильных скобочных последовательностей длины 2N (1<=N<=30)
Пpимеp: 2N=6:
((())), (()()), ()()(), (())(), ()(())
S= 5"

← →
MBo (2002-11-21 13:45) [8]

>Alx2
отлично

>Оливейра
Это другая задача - в твоей нужно проверить сбалансированность скобок в выражении, решается прямым однопроходным прогоном, а здесь нужно кратчайшим способом перечислить все правильные комбинации

← →
down (2002-11-21 13:50) [9]

2Alx2
Можно пояснить, как работает?

← →
MBo (2002-11-21 13:57) [10]

мой вариант
procedure TForm1.Button1Click(Sender: TObject); var nmax, nhalf, NVar: integer; s: string; procedure AddSkobka(n, nl, right: integer); begin s[n * 2] := Chr(Ord("(") + right); if right = 0 then inc(nl); if n = nmax then begin Memo1.Lines.Add(s); inc(NVar); Exit; end; if 2 * nl > n then //если левых больше, чем правых, можно добавить правую AddSkobka(n + 1, nl, 1); if nl < nhalf then //если левых половина общего количества, перестаем их добавлять AddSkobka(n + 1, nl, 0); end; begin nhalf := 4; nmax := nhalf *2; nvar := 0; s := StringOfChar(" ", 2 * nmax); AddSkobka(1, 0, 0); Memo1.Lines.Add(IntToStr(NVar)); end;

← →
MBo (2002-11-21 14:03) [11]

решение задачи Оливейры
функция считает макс. глубину вложения, выдавая 255 для случая дисбаланса

function skobki(st:string):byte;
var i,j,max:byte;
begin
max:=0;
j:=0;
for i:=1 to length(st) do begin
if st[i]="(" then inc(j);
if st[i]=")" then dec(j);
if max<j then max:=j;
end;
if j<>0 then
max:=255;
Result:=max;
end;

← →
MBo (2002-11-21 15:08) [12]

пардон, последний постинг неправильный. Так вернее:
procedure TForm1.Button5Click(Sender: TObject); function VernyeSkobki(st:string):Boolean; var i,j:byte; begin Result:=False; j:=0; for i:=1 to length(st) do begin if st[i]="(" then inc(j); if st[i]=")" then if j>0 then dec(j) else Exit; end; Result:=j=0; end; begin If VernyeSkobki("(()())") then ShowMessage("OK") else ShowMessage("Fignya"); end;

← →
Alx2 (2002-11-21 15:42) [13]

>MBo © (21.11.02 13:57)

Вот с выдачей результатов:

function RunProcess(Dimension: Integer): integer; var S: string; function sCountWithResult(stop, sum: integer): Integer; begin if stop = 0 then if sum = 0 then begin Result := 1; Memo1.Lines.Add(S) end else Result := 0 else begin S[Stop] := ")"; Result := sCountWithResult(stop - 1, sum + 1); if sum > 0 then begin S[Stop] := "("; inc(Result, sCountWithResult(stop - 1, sum - 1)); end; end; end; begin SetLength(S, Dimension); Result := sCountWithResult(Dimension, 0); end; begin RunProcess(6); end;

← →
MBo (2002-11-21 15:46) [14]

>Alx2
Угу. Но главное- алгоритм, маленький и симпатичный ;)

← →
Alx2 (2002-11-21 15:51) [15]

>down (21.11.02 13:50)
>Можно пояснить, как работает?

Можно, конечно.
Если представить заполняемую скобками последовательность как последовательность элементов "-1" и "1", где "-1" означает закрывающую скобку, а "1" - открывающую скобку, то для того, чтобы соблюсти правильность парности скобок, достаточно потребовать, чтобы сумма элементов по мере заполнения массива никогда не была меньше нуля. Отсюда следует условие
if sum > 0 then
.....

Остальное - простая рекурсия :)

← →
down (2002-11-21 16:23) [16]

Понятно, спасибо! Красиво, черт побери!

← →
Alx2 (2002-11-21 16:27) [17]

>down (21.11.02 16:23)

:)

← →
Igorek (2002-11-22 10:30) [18]

> Alx2 © (21.11.02 16:27)

А еще полный перебор можно представить в виде бинарного дерева, где каждый узел имеет суму предыдущих и свое число (1 или -1). В данном случае реализован метод ветвей и границ - поиск обрывается при отрицательной сумме.
Но вот нерекурентную простую формулу не могу найти. :-(
Еще подумаю.

Очередная несложная задачка для разминки;) Найти похожие ветки