Вот и я теперь студент

Приветствую всех посетителей форума. Вот теперь и я стал студентом, учусь в МИСиС. А чтобы толк от этого поста хоть какой-нибудь был, дам вам задачку порешать на асме (хотя, может кто и формулу найдет):

есть 2n скобок, нужно определить сколькими вариантами их можно правильно расположить. 2 скобки - один вариант: (), 4 скобки - два варианта: ()() и (()), 6 - 5: ()()(), (())(), ()(()),((())) и (()()). Для 2n скобок - ? вариантов. Задача со "*" из книжки.



И еще. Для чего служат функции ...GenericTable... и ...MemoryStream... в ntdll.dll? (Точки заменяют часть названия функции)

 

dr_dred

Ну прямым перебором в пол пинка решается ) Но я так понимаю тебе формула нужна?

 

Программу, которая использует перебор, я написал. Для 1-17 пар скобок считает за время меньшее 1 секунды, а вот для 20 уже больше минуты. Формулу действительно подобрать не могу, да мне она и не нужна особо, я задачу решал ради интереса. Просто попробуйте, интересная задача.

Я делал так:

рассмотрим для 3 пар:

101010

101100

110010

110100

111000

(1 - откр. скобка, 0 - закр.)

Закономерность видна: перемещать последнюю 1 влево, пока она не встретится с предпоследней, а как это произойдет, эту последовательность перераспределить так: крайнюю левую 1 сдвинуть на 1 влево, а остальные разместить с канца строки так: ...10101010.

Есть варианты лучше у кого?

 

dr_dred

Поздравляю.

Ты на каком факультете?

Было время и я там учился!

 

vito

Я на физхиме. Bogdanov rules!!!

А давно это было?

 

Вот еща такой вопрос. Я ведь в общаге живу теперь в МИСиСовской, на 15 этаже. Телефона там конечно нету. Как и какой инет лучше пустить, & во сколько встанет подключение и ежемесячная плата. Прочитаю все предложения.

 

dr_dred



Самый легкий путь - GPRS

 

Млин какие имена!



Ну дела и общага еще стоит)!

 

Да насчет инета. Раньше в МИСиС был свободный доступ, но понятно не ночью. Что сейчас по другому?



Ну а вообще немного пообтрись, попробуй подключиться к общаковской линии. Только без вандализма

 

Рассматривать нужно не отдельные скобки, а их пары!



Будем называть "парой" сочетание открывающей и закрывающей скобок, внутри которых либо ничего нет, либо присутствует некоторое количество парных скобок. Сочетание "(()" "парой" не является. "()" - простейшая "пара", "(())" - "пара", в которую вложена другая "пара", "(())()" - две "пары", в одну из которых вложена еще одна, и т. п. Заметим, что из n открывающих и n закрывающих скобок, как их ни располагай (я имею в виду только допустимые варианты), получится ровно n "пар".



Введем функцию F(n), возвращающую количество возможных вариантов расположения n пар скобок. Условимся, что F(0) = 1. Нам уже известны значения F(n) для n = 1, 2 и 3 (1, 2 и 5 соостветственно).



Пусть n = 4. Возможные варианты расположения "пар":

1) 4 вложенных "пары" - "(...)". Очевидно, это дает нам F(3) = 5 вариантов;

2) 3 вложенных "пары" и одна простая - "(...)()". Это еще F(2) * F(0) = 2 * 1 = 2 варианта;

3) 1 простая и 3 вложенных - "()(...)". Опять же, 2 варианта;

4) 2 вложенных, 1+1 простая - "(...)()()". F(1) * F(0) * F(0) = 1 * 1 * 1 = 1 вариант.



Итого:

4: F(3) = 5

3, 1: F(2) * F(0) = 2 * 1 = 2

1, 3: = 2

2, 1, 1: F(1) * F(0) * F(0) = 1 * 1 * 1 = 1

1, 2, 1: = 1

1, 1, 2: = 1

2, 2: F(1) * F(1) = 1 * 1 = 1

1, 1, 1, 1: = 1



В сумме: F(4) = 5 + 2 * 2 + 1 * 3 + 1 + 1 = 14



Аналогично находим F(5) = 42, F(6) = 132. Дальше на бумаге считать неудобно, а программу писать лениво.

 

dr_dred

Это стандартная проблема, расположение скобок соответствует деревьям, то есть количество вариантов для 2n скобок соответствует количеству деревьев с n+1 узлами. И решается задача последовательным построением деревьев ("динамическим программированием"). Есть ли общая формула для количества сейчас не помню, похожая теория(так называемых rooted trees) используется при построении системы уравнений для коэффициентов методов Runge-Kutta, так что можно там посмотреть. Если интересно, могу рекомендовать могучий труд Hairerа и Wannerа, там уже будут ссылки дальше.



P.S. смотри например здесь:

Sequence A000108

 

Вот пример функции F(n) на турбо паскале:





var

tab: array[0..19] of longint;





function F(n: word): longint;

var

res: longint;

i, j: word;



begin

if tab[n] <> 0 then begin

F := tab[n];

exit;

end;



if n < 2 then begin

F := 1;

tab[n] := 1;

exit;

end;



res := 0;



j := 0;

for i := (n - 1) downto 0 do begin

res := res + F(i) * F(j);

j := j + 1;

end;



tab[n] := res;

F := res;

end;





tab служит кэшем значений F(n), изначально заполнен нулями.



F(19) считается моментально. При бОльших значениях n longint переполняется.



Осталось только перевести на ассемблер

 

Я могу ошибаться, но насколько я понимаю, при увеличении числа пар скобок на 1, из каждого правильного скобочного выражения x более чем с 1 парой скобок, можно получить 3 разных выражения: ()x, (x), x(), кроме случаев если x = ()()...(), тогда только 2. Отсюда получается рекуррентная формула X(n+1)=3*X(n)-1, которая, если верить Maple, преобразуется в X(n)=3^(n-1)/2+1/2

 

Sharp



К сожалению рассуждение неверно, общая формула есть по ссылке, которую я привел выше.

 

из каждого правильного скобочного выражения x более чем с 1 парой скобок, можно получить 3 разных выражения: ()x, (x), x() ...



В некоторых случаях можно получить еще x()y, (x)y, x(y) и x(y)z. И чем больше скобок, тем больше вариантов.

 

Stiver

Sequence A000108

У меня нет прав доступа к странице?

 

dr_dred

Хм, не знаю, у меня все в порядке. Если надо могу страницу приаттачить в виде текстового файла.

 

Stiver

Давай.

 

Смотри аттач

1264785418__sequence.txt

 

...действительно интересная задачка...

...вот мой вариант ее решения (к сожалению проверял только в уме)...

Код (Text):

1.  
2. n - количество скобок (должно быть кратно 2-м)
3.  
4. r = 0
5. \--|  /     ( n/2 ) !     \ 2
6.  >    | -----------------  |
7. /--|  \ ( n/2 - r ) ! r ! /
8. n/2
9.