И снова рекуррентные соотношения...

← →
ProgRAMmer Dimonych © (2007-01-08 23:47) [0]

Ну, не переношу я просто эти задачи по инфе. Нормальные программы - пожалуйста, а ворон и кочки считать - не моё и всё тут :(

Короче говоря, есть задача...

Дана символьная строка, состоящая из k открывающих и k закрывающих скобок. Найти минимальное число способов правильной расстановки скобок. Считаем, что скобки расставлены правильно, если каждой открывающей скобке соответствует закрывающая.

Самым правильным было бы вычислить k! (факториал), т.е. любая из скобок может стоять на любом месте. При этом, т.к. кол-во откр. скобок=кол-во закр. скобок, то каждой открывающей скобке соответствует закрывающая.

Но логика подсказывает, что расстановку ))(()()( правильной считать ну никак нельзя. Поэтому на основе алгоритма проверки правильности расстановки скобок (не помню, как правильно называется) вытрудил я вот такой код (Turbo Pascal)...

Program VsyakoeNikomuNenuzhnoe;
Uses Crt;
Var
K,L,R:Byte;
Res:LongInt;

Procedure Work;
begin
if L=K then begin Inc(Res); Exit; end;
if L=R then begin Inc(L); Work; Dec(L); Exit; end;
Inc(L); Work; Dec(L);
Inc(R); Work; Dec(R);
end;

Begin
clrscr;
write("Введите K: "); readln(K);
L:=0; R:=0; Res:=0;
Work;
writeln(Res);
ReadKey;
End.

Т.е. пробуем все варианты расстановки, количество открыващих и закрывающих скобок храним в L и R соответственно (Left и Right). Результат - в Res.

Проблема в том, что для k=15 программа работает ужасно медленно (секунд 5-10), а для k=20 ответа я так и не дождался :(

Как здесь можно сократить перебор или ускорить работу (ассемблер предпочтительнее не использовать).

Заранее спс.

← →
Gero © (2007-01-09 00:04) [1]

Рекурсия не нужна. Расставлены неправильно, если колчиество открывающих не равно количеству закрывающих или если при проходе слева направо появляется лишняя закрывающая.

← →
ProgRAMmer Dimonych © (2007-01-09 00:07) [2]

> Gero © (09.01.07 00:04) [1]
> Рекурсия не нужна. Расставлены неправильно, если колчиество
> открывающих не равно количеству закрывающих или если при
> проходе слева направо появляется лишняя закрывающая.
Я думал вариант, когда некоторая последовательность для k-1 уже готова... Мы обозначаем её за некоторый X и пробуем добавить ещё одну откр. и закр. скобки, т.е.

(X)
()X
X(),

но оказалось, что это ещё не всё... И в ответах закономерности не прослеживается:

k Res
=======================================
1 1
2 2
3 5
...............................................

:(

← →
Gero © (2007-01-09 00:09) [3]

> [2] ProgRAMmer Dimonych © (09.01.07 00:07)

Я тебе написал верный и наиболее удобный алгоритм.

← →
ProgRAMmer Dimonych © (2007-01-09 00:11) [4]

> Gero © (09.01.07 00:09) [3]
Да, знаю... Берём счётчик... Если открывающая - +1, закрывающая - -1. Если в конце не 0, то неправильно, если по ходу ушли в минус - неправильно, иначе правильно. Но по условию требуется найти кол-во правилных расстановок...

← →
Gero © (2007-01-09 00:12) [5]

А вобще задача элементарна, стыдно не уметь решать такое, если знаком с программированием хотя бы месяц.

← →
Palladin © (2007-01-09 00:12) [6]

тут нужно просто проанализировать способ получения правильных пар...
взял и посмотреть наглядно на первые 3

()

()()
(())

()()()
(())()
()(())
((()))

отсюда сразу видно что...

procedure calc(n:Integer;vars:TStringList); var lvars:TStringList; i:integer; Procedure _add(const s:String); Begin If vars.IndexOf(s)=-1 Then vars.Add(s); End; procedure _do(const s:String); var i:integer; Begin _add("()"+s); _add(s+"()"); for i:=1 to length(s)-1 Do If (s[i]="(") and (s[i+1]=")") then _add(copy(s,1,i)+"()"+copy(s,i+1,length(s))); End; begin if n=1 then vars.Add("()") Else Begin lvars:=TStringList.Create; Try calc(n-1,lvars); lvars.Sorted:=true; for i:=0 to lvars.count-1 do _do(lvars[i]); Finally lvars.free; End; End; end; procedure TForm1.Button1Click(Sender: TObject); var t:TStringList; begin t:=TStringList.Create; t.Sorted:=true; calc(4,t); Memo1.Lines.AddStrings(t); t.Free; end;

это визуальное решение задачи, другое решение - использовать деревья, это уж сам... попробуй декомпилировать :)

← →
Palladin © (2007-01-09 00:12) [7]

> [4] ProgRAMmer Dimonych ©

ничего подобного

← →
доцент (2007-01-09 00:15) [8]

Правильная скобочная структура начинается с открывающей скобки. Найдем соответствующую закрывающую кнопку. Тогда исходная структура окажется разбитой на 2 куска.
(структура-1)структура-2

структура-1 и структура-2 - тоже правильные с меньшим количеством скобок. Получается, что количество скобочных структур с k парами скобок можно выразить через количества скобочных структур с меньшим числом скобок. То есть написать рекурентное соотношение.

Обозначь количество структур через c(k) и напиши рекурентное соотношение.

← →
ProgRAMmer Dimonych © (2007-01-09 00:15) [9]

> Palladin © (09.01.07 00:12) [6]
> тут нужно просто проанализировать способ получения правильных
> пар...
> взял и посмотреть наглядно на первые 3
>
> ()
>
> ()()
> (())
>
> ()()()
> (())()
> ()(())
> ((()))
Не хватает варианта (()()).

← →
Palladin © (2007-01-09 00:16) [10]

> [1] Gero ©

задача не проверка правильности, а количество правильных вариантов...

← →
Palladin © (2007-01-09 00:17) [11]

> [9] ProgRAMmer Dimonych ©

мда действительно... нужно поподробней подумать...

← →
ProgRAMmer Dimonych © (2007-01-09 00:17) [12]

> доцент (09.01.07 00:15) [8]
Т.е. что-то в духе [2]? А как быть с (()())? Первая скобка соответствует последней, или наоборот. Одна подпоследовтельность получается... :(

← →
Gero © (2007-01-09 00:18) [13]

> [10] Palladin © (09.01.07 00:16)

Дейтсивтельно. Прошу прощения, невнимательно прочтиал условие. Спать пора )

← →
Palladin © (2007-01-09 00:18) [14]

а, все понятно, маленькое дополнение

procedure _do(const s:String); var i:integer; Begin _add("()"+s); _add(s+"()"); _add("("+s+")"); for i:=1 to length(s)-1 Do If (s[i]="(") and (s[i+1]=")") then _add(copy(s,1,i)+"()"+copy(s,i+1,length(s))); End;

← →
Palladin © (2007-01-09 00:19) [15]

но для академического решения задачи нужно строить дерево, как - уже понятно... надеюсь...

← →
ProgRAMmer Dimonych © (2007-01-09 00:20) [16]

> Palladin © (09.01.07 00:18) [14]
Прошу прощения за нескромный вопрос, но...

вложенные вызовы функций с параметрами действительно будут работать быстрее одной рекурсивной процедуры на глобальных переменных?

← →
ProgRAMmer Dimonych © (2007-01-09 00:22) [17]

> Palladin © (09.01.07 00:19) [15]
Программист должен за свою жизнь дерево построить, ...

сына посадить...

и, выходит, дом вырастить :)

Дерево - это которое бинарное? Левая ветка - одна скобка, правая - другая?

← →
Gero © (2007-01-09 00:24) [18]

> [16] ProgRAMmer Dimonych © (09.01.07 00:20)
> вложенные вызовы функций с параметрами действительно будут
> работать быстрее одной рекурсивной процедуры на глобальных
> переменных?

Нет, медленнее.

← →
доцент (2007-01-09 00:24) [19]

> А как быть с (()())? Первая скобка соответствует последней,
> или наоборот. Одна подпоследовтельность получается... :
> (

в этом случае
структура-1 = ()()
структура-2 = пустая (из 0 скобок) - она одна такая

← →
доцент (2007-01-09 00:24) [20]

← →
Gero © (2007-01-09 00:25) [21]

> [18] Gero © (09.01.07 00:24)

Хотя может потери скорости и не будет, а вот стек засоряется однозначно. Но для такой задачи все это не существенно.

← →
Palladin © (2007-01-09 00:26) [22]

> [16] ProgRAMmer Dimonych ©

не факт, но надежней и понятней... это раз, развертывание рекурсии в линейную операцию никогда ни к чему хорошему не приводило, это два... рекурсивное построение и обработка деревьев гораздо быстрей чем визуальное решение, это три и четыре - не бинарное, обыкновенное, простое, как в TTreeView...

← →
Zeqfreed © (2007-01-09 02:04) [23]

А можно для тех у кого 4 часа ночи переформулировать условия задачи? :)
А то я никак не могу понять что значит "Найти минимальное число способов правильной расстановки скобок".

← →
Palladin © (2007-01-09 02:08) [24]

необращай внимания, это закрут роликов за шарики у авторов задачи, если учитывать это условие то ответ всегда 1... хотя чем черт не шутит...

← →
Sha © (2007-01-09 10:19) [25]

C(2n,n) - C(2n,n-1), где C(n,k) = n! / (k! (n-k)!)

← →
BiN © (2007-01-09 10:29) [26]

задача будет интересней, если скобки будут разных типов ([{

← →
Sha © (2007-01-09 12:00) [27]

Для тех, кто не переносит рекурсию :)

procedure TForm1.Button8Click(Sender: TObject); var i, j, k: integer; begin k:=10; j:=1; for i:=1 to k do j:=j*(i+k) div i; j:=j div (k+1); ShowMessage(IntToStr(j)); end;

← →
доцент (2007-01-09 13:23) [28]

> Sha

поломал весь педагогический процесс на фиг :)

а именно, для k=6 забывает посчитать такую строку (()())(()())

Вот еще решение перебором:

procedure TForm1.Button11Click(Sender: TObject); const ct: array[0..15] of integer= (0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4); var i, j, k, m, n: integer; label next; begin; k:=6; if (k>0) and (k<=16) then begin; m:=0; i:=0; for j:=1 to k do i:=(i shl 2) + 1; repeat; j:=i; n:=0; repeat; n:=n+ct[j and 15]; j:=j shr 4; until j=0; if n<>k then goto next; j:=i; n:=0; repeat; if j and 1=0 then begin; dec(n); if n<0 then goto next; end else inc(n); j:=j shr 1; until j=0; inc(m); next: i:=i-2; until i<=0; end; ShowMessage(IntToStr(m)); end;

Более быстрый вариант решения перебором:
procedure TForm1.Button11Click(Sender: TObject); const p: array[0..3] of integer= (2, 0, 1, 0); d: array[0..3] of integer=(-2, 0, 0, 2); var ct: array[0..255] of integer; i, j, k, m, n: integer; label next; begin; m:=0; k:=16; if (k>0) and (k<=16) then begin; for i:=0 to 255 do begin; j:=i; n:=0; while j>0 do begin; inc(n,j and 1); j:=j shr 1; end; ct[i]:=n; end; i:=0; for j:=1 to k do i:=(i shl 2) + 1; repeat; j:=i; n:=0; repeat; n:=n+ct[j and 255]; j:=j shr 8; until j=0; if n<>k then goto next; j:=i; n:=0; repeat; if n<p[j and 3] then goto next; n:=n+d[j and 3]; j:=j shr 2; until j=0; inc(m); next: i:=i-2; until i<=0; end; ShowMessage(IntToStr(m)); end;

и вариант решения вычислением для большего диапазона значений k:
procedure TForm1.Button8Click(Sender: TObject); var i, k: integer; m: int64; begin; k:=16; m:=1; for i:=2 to k do m:=m*(i+k) div (i-1); m:=m div k; ShowMessage(IntToStr(m)); end;

> Sha © (09.01.07 12:00) [27]
> Для тех, кто не переносит рекурсию :)
> procedure TForm1.Button8Click(Sender: TObject);
> var
> i, j, k: integer;
> begin
> k:=10;
> j:=1;
> for i:=1 to k do j:=j*(i+k) div i;
> j:=j div (k+1);
> ShowMessage(IntToStr(j));
> end;
Наверное, пора мне спать идти: сидел, пытался вникнуть, почему этот короткий код работает. Это как-то связано с [25]?
> Sha © (09.01.07 10:19) [25]
> C(2n,n) - C(2n,n-1), где C(n,k) = n! / (k! (n-k)!)
Или через куда?

> Sha © (10.01.07 09:35) [34]
Мда, честно говоря, когда вчера одной ногой в мире снов задавал этот вопрос, надеялся утром просто увидеть да или нет и, возможно, какое-нибудь краткое пояснение. А тут так вот...

Короче, возненавидел я эти факториалы с сегодняшнего дня. Забавные превращения пронаблюдал: ! -> : -> ¡... Но в итоге допёр, что предложенный вариант - это не что иное как ((2n)!)/(n!n!(n+1)), которое сокращено до ((n+1)(n+2)...2n)/(n+1)!. А в цикле объединено вычисление всех факториалов сразу.

Только вот насколько правильно такое деление, если там не всегда будут кратные числитель и знаменатель? Я эту программу пробовал для всех от 1 до 14 - прошла. А для k=15 выдаёт отрицательное число, хотя тип для j поставлен LongInt. Для 15 мой алгоритм тупого перебора выдаёт положительное число в пределах LongInt.

> ProgRAMmer Dimonych © (10.01.07 11:06) [35]
> Но в итоге допёр, что предложенный вариант - это не что иное как ((2n)!)/(n!n!(n+1)),
> которое сокращено до ((n+1)(n+2)...2n)/(n+1)!. А в цикле объединено вычисление всех факториалов сразу.

Цикл предназначен для вычисления C(2n,n) - C(2n,n-1), где C(n,k) = n! / (k! (n-k)!)

> Только вот насколько правильно такое деление, если там не всегда будут кратные числитель и знаменатель?

Конечно, т.к. всегда среди любых m последовательных натуральных чисел
найдется число, делящееся на m

> Я эту программу пробовал для всех от 1 до 14 - прошла.
> А для k=15 выдаёт отрицательное число, хотя тип для j поставлен LongInt.

Это так, потому что по ходу вычислений на больших числах возникает целочисленное переполнение.
Используй вариант решения вычислением из [32]. Он гораздо шире.

> Для 15 мой алгоритм тупого перебора выдаёт положительное число в пределах LongInt.

А мой вариант острого перебора из [32] выдает решение даже для k=16
на 500MHz компе менее чем за минуту :)

Пропустил слово "правильно":

Конечно правильно, т.к. всегда среди любых m последовательных натуральных чисел
найдется число, делящееся на m

> Sha
Спасибо за помощь, пойду вспоминать, как правильно "!" пишется ([35]) ;)

> Sha © (10.01.07 11:35) [37]
> всегда среди любых m последовательных натуральных чисел найдется число, делящееся на m

Но этого мало для доказательства коррекности деления в [27] и [32].

Попробуй доказать сам, что произведение m последовательных натуральных чисел делится на m!

корректности )

И снова рекуррентные соотношения... Найти похожие ветки