Вывести все правильные скобочные выражения размера 2N.

[woodey]

В школе задали, люблю информатику, но вот тут что-то не выходит, хотя примерный и понятно.. Помогите, напиши кусок программы в паскале или дайте наводку на правильный алгоритм. Задача на тему рекурсия, 9 класс

Построить все правильные скобочные выражения длины 2N, то есть те, которые содержат по N правых и N левых скобок.

Заранее спасибо)

[Serge_Bliznykov]

в некоторых случаях рекурсия - это просто находка для решения задачи.

ловите вот такое решение:

procedure ShowVariant(s : string; a, b : integer);
begin
  if (a=0) and (b=0) then begin Writeln(s); Exit; end;
  if (a>0) and (b>=a) then ShowVariant(s+'(',a-1,b);
  if b>0 then ShowVariant(s+')',a,b-1);
end;

var N : integer;
begin
  N := 4;
  ShowVariant('',N,N);
  readln;
end.

[woodey]

Спасибо, сейчас попробуем)

[Alter]

Редактировано под delphi, вроде верно:

procedure ShowVariant(s : string; a, b : integer; var R :string);
begin
  if (a=0) and (b=0) then
  begin
    R := R + s + #13;
    Exit;
  end;
  if (a>0) and (b>=a) then
   ShowVariant(s+'(', a-1, b, R);
  if b>0 then
   ShowVariant(s+')', a, b-1, R);

end;

procedure TForm1.Button1Click(Sender: TObject);
var
  s :string;
  N : integer;
begin
 N := 4;
 S := '';
 ShowVariant('', N, N, S);
 ShowMessage(S);
end;

[woodey]

Первый вариант подошел идеально, чуть-чуть под себя подстроил задал N.
Спасибо

Все не получается, хотя вроде все перепробовал..
Как сосчитать кол-во строк?

Думал ввести некое l

procedure Skobki(s: string; a, b :integer; var l :longint);
begin
if (a=0) and (b=0) then
begin
writeln(s);
l:=l+1;
exit;
end;
if (a>0) and (b>=a) then Skobki(s+'(',a-1,b, l);
if b>0 then Skobki(s+')',a,b-1, l);
end;

Но он все равно выводит 0, что не так?


Так, все, сам допер, всем спасибо)

[Serge_Bliznykov]

begin
l:=0; {убрать!!}
if (a=0) and (b=0) then

выкиньте инициализацию I:=0 из начала рекурсивной процедуры, ведь, каждый раз, когда она (процедура) вызывается счётчик обнуляется...

[canadamoscow]

Сгенерировать правильные скобочные выражения размера 2N
на PascalABC.net для одно, двух или более видов пар скобок:

var n := 3;
var res: string;

procedure P(s: string; a, b: Integer);
begin
  if (a=0) and (b=0) then begin Write(res,' '); Exit end;
  if b>0 then begin
     s += '('; res += '('; P(s, a+1, b-1);            {один вид скобок}
      s[^1] := '['; res[^1] := '['; P(s, a+1, b-1);   {два} //строку можно закомментировать
      s[^1] := '{'; res[^1] := '{'; P(s, a+1, b-1);   {три} //строку можно закомментировать
      s[^1] := '<'; res[^1] := '<'; P(s, a+1, b-1);   {четыре} //строку можно закомментировать
     s := s[:^1]; res := res[:^1];    //избавляемся от последнего символа s := Copy(s, 1, Length(s)-1)
  end;
  if a>0 then begin
      case s[^1] of       // case s[Length(s)] of
         '(' : res += ')';
         '[' : res += ']';
         '{' : res += '}';     
         '<' : res += '>';     
      end;
      P(s[:^1], a-1, b);
      res := res[:^1];    //избавляемся от последнего символа
  end;
end;

begin
  P('', 0, n);
end.

[ViktorR]

Рыться в архивах 10-ти летней давности может быть и полезно, но вот предлагать такое решение ...

Возьмите книжку А.Шень, Программирование: теоремы и задачи.
У меня 2004-го года.
Открываете стр. 97 и читаете алгоритм решения этой задачи для любого числа скобок.
Реализуете этот алгоритм на любом языке.

Там ещё много всяких алгоритмов изложено.
Читайте и пишите в свой удовольствие и радуйте нас хорошими и понятными решениями ...

PS: PascalABC - это наше всё

[digitalis]

Сообщение от ViktorR

Рыться в архивах 10-ти летней давности может быть и полезно...

За 10 лет наука шагнула семимильными шагами - не угнаться