Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Задача про хорды(динам.прогр)

Автор: hter 11.12.2013, 16:07

Окружность на ней точки обозначены буквами A,B,C,D. Дается строка(порядка 200 букв) с произвольным наборов букв (количество А и B совпадает, С и D тоже совпадает). Надо найти количество способов соединить все точки непересекающимися хордами. Если А можно соединить только с B(и обратно можно B c A), С только с D(D можно с C).  Я ее решил рекурсией, но не подходит из-за времени выполнения.  Не понимаю как с помощью динамического программирования решить. Помогите. p.s. я python использую

Автор: Lipetsk 13.12.2013, 13:24

не пойму, при чём тут динамическое программирование но если вы найдёте такое решение, отпишитесь, пожалуйста возможно, вы делаете полный перебор, а можно сократить соединять можно только те точки A и B, между которыми, двигаясь по окружности, количество точек A совпадает с количеством точек B, и количество C совпадает с количеством D

Автор: Фантом 13.12.2013, 13:40

Цитата(hter @  11.12.2013,  17:07 ) Я ее решил рекурсией, но не подходит из-за времени выполнения.  Цитата(hter @  11.12.2013,  17:07 ) p.s. я python использую Может быть, проще переписать уже имеющееся решение на чем-то другом? У Python'а, при всех его достоинствах, скорость выполнения крайне низкая, даже замена на другой интерпретируемый язык может оказаться достаточной.

Автор: hter 13.12.2013, 17:54

Цитата(Lipetsk @  13.12.2013,  13:24 ) не пойму, при чём тут динамическое программирование но если вы найдёте такое решение, отпишитесь, пожалуйста возможно, вы делаете полный перебор, а можно сократить соединять можно только те точки A и B, между которыми, двигаясь по окружности, количество точек A совпадает с количеством точек B, и количество C совпадает с количеством D  Отпишусь, но как то я далек от этого. Я не все перебираю, а только которые остались. Цитата(Фантом @  13.12.2013,  13:40 ) Может быть, проще переписать уже имеющееся решение на чем-то другом? У Python'а, при всех его достоинствах, скорость выполнения крайне низкая, даже замена на другой интерпретируемый язык может оказаться достаточной.  Может быть, но O(n^3). Если б в строке было 10-20 символов то не проблема, а в строке их 200 и более.  на чем попробовать советуете?

Автор: Фантом 13.12.2013, 20:13

Цитата(hter @  13.12.2013,  18:54 ) Может быть, но O(n^3). Если б в строке было 10-20 символов то не проблема, а в строке их 200 и более.  на чем попробовать советуете? В идале - на чистом C. В реальности лучше сначала прикинуть, насколько надо увеличить быстродействие.

Автор: OpenGL 16.12.2013, 11:54

А как решали? Надо так - проводим хорду, далее считаем ответ для левой и правой половин, перемножаем. И, разумеется, ответы сохраняем, чтобы по нескольку раз их не считать. Такой алгоритм и с такими ограничениями, как мне кажется, и на питоне будет быстро работать.

Автор: Lipetsk 16.12.2013, 15:39

hter, а есть последовательности, на которых можно потестироваться, чтоб заведомо было решение

Автор: hter 16.12.2013, 23:00

Цитата(OpenGL @  16.12.2013,  11:54 ) А как решали? Надо так - проводим хорду, далее считаем ответ для левой и правой половин, перемножаем. И, разумеется, ответы сохраняем, чтобы по нескольку раз их не считать. Такой алгоритм и с такими ограничениями, как мне кажется, и на питоне будет быстро работать.  Одних первых хорд может быть э так вариантов 100. Я решал по кругу..от первого и перебрал какие подходят Добавлено через 4 минуты и 13 секунд Цитата(Lipetsk @  16.12.2013,  15:39 ) hter, а есть последовательности, на которых можно потестироваться, чтоб заведомо было решение  Так можно и придумать: CACBADBDCDAB - 2 варианта АBABAB - 5 вариантов АBABСDAB - 1 вариант

Автор: OpenGL 17.12.2013, 11:17

Цитата(hter @  16.12.2013,  23:00 ) Одних первых хорд может быть э так вариантов 100. Ну и что? Всего состояний в динамике 100 * 199, а каждое большее состояние просчитывается за O(n) через меньшие (уже подсчитанные и сохраненные), а значит общая сложность - куб. Тормозить в данной реализации может только сам питон

Автор: hter 17.12.2013, 14:43

Цитата(OpenGL @  17.12.2013,  11:17 ) уже подсчитанные и сохраненные Вот что значит сохраненные? Добавлено через 59 секунд Может мой нубский код скинуть? Добавлено через 4 минуты и 22 секунды ну должно же быть решение не за O(n^3) а там за O(nlogn)

Автор: OpenGL 17.12.2013, 15:22

Цитата(hter @  17.12.2013,  14:43 ) ну должно же быть решение не за O(n^3) а там за O(nlogn)  Почему должно?   Тем более на таких ограничениях n^3 вполне приемлем. Цитата(hter @  17.12.2013,  14:43 ) Может мой нубский код скинуть? Что-то типа псевдокода c синтаксисом C++  Код // Посчитать ответ для строки, начинающийся в позиции s и заканчивающийся в e (не включая e). int f(int s, int e)  {     if(уже_считали_ответ_для_данных_s_и_e)      {         return посчитанное_значение;     }     // Для пустой строки примем ответ за 1     if(s == e) return 1;     if(количество_A_в_строке != количество_B_в_строке ||         количество_С_в_строке != количество_D_в_строке)     {         return 0;     }     int res = 0;     for(int i = s + 1; i != e; ++i)     {         // Если символы парные - проводим хорду и считаем отдельно для левой и отдельно для правой половины\         // Поскольку любой из левой может соответствовать любому из правой, перемножаем и прибавляем к ответу         if(символ_s_и_символ_i_парные) res += f(s + 1, i) * f(i + 1, e);     }     return res; } ... string str = ...; f(0, str.length()); Это - вполне себе динамика, только записанная в рекурсивной форме. Цитата(hter @  17.12.2013,  14:43 ) Вот что значит сохраненные? Для каждой пары входных параметров функции, если уже считали ответ, возвращаем его сразу.

Автор: hter 17.12.2013, 21:07

Цитата(OpenGL @  17.12.2013,  15:22 ) Это - вполне себе динамика, только записанная в рекурсивной форме. Цитата(hter @  17.12.2013,  14:43 ) Вот что значит сохраненные? Для каждой пары входных параметров функции, если уже считали ответ, возвращаем его сраз Спасибо, попробую реализовать. Цитата(OpenGL @  17.12.2013,  15:22 ) Почему должно?   Тем более на таких ограничениях n^3 вполне приемлем. ну как то хочется, что б было)) Добавлено через 28 секунд Цитата(OpenGL @  17.12.2013,  15:22 ) код C++ жаль си не знаю

Автор: OpenGL 18.12.2013, 05:39

Цитата(hter @  17.12.2013,  21:07 ) жаль си не знаю  Что непонятного в этом псевдокоде? Убрать int и скобки {} - почти питон будет

Автор: Lipetsk 18.12.2013, 08:42

Цитата(hter @  16.12.2013,  23:00 ) Так можно и придумать: CACBADBDCDAB - 2 варианта АBABAB - 5 вариантов АBABСDAB - 1 вариант  так вроде должно быть 200 букв  просто случайно сгенерированная последовательность из 200 у меня имеет не более 5 возможных (с учётом правила из моего первого комментария) хорд из одного узла, а для некоторых узлов ни одного

Автор: OpenGL 18.12.2013, 08:54

Цитата(Lipetsk @  18.12.2013,  08:42 ) просто случайно сгенерированная последовательность из 200 у меня имеет не более 5 возможных (с учётом правила из моего первого комментария) хорд из одного узла, а для некоторых узлов ни одного  На случайных ответ чаще всего 0 будет  А на правильно подобранных - очень большое число. Цитата(hter @  16.12.2013,  23:00 ) АBABСDAB - 1 вариант  Тут, кстати, 5 вариантов.

Автор: hter 19.12.2013, 14:09

Цитата(Lipetsk @  18.12.2013,  08:42 ) так вроде должно быть 200 букв  ABACDBACDBBAABDBACCDABADDCBADCCCDDCBABAABADABCBBAABCABABDBAABAABBBABDCABABDCABADCBABBAAABABADCBBBDAB ABABABBACCDCDCDABDABDCCDCABAABADABBAABAAAABADCBBBABAABBBDCCCCDCDDCCDCABDBADCBCDCDAABBAABDBABCDCBCA BABABDCDCDABACCDDCDBBACDADCDABCDBCCDCDDABCDABBABACDDBCDABACAADCBBABACD Добавлено @ 14:18 ответ = число способов mod 1000000

Автор: hter 19.12.2013, 14:30

Цитата(OpenGL @  18.12.2013,  05:39 ) Что непонятного в этом псевдокоде? Убрать int и скобки {} - почти питон будет  только ноль и получается же

Автор: OpenGL 20.12.2013, 07:00

Цитата(hter @  19.12.2013,  14:30 ) только ноль и получается же Ищите ошибку в вашей реализации. Алгоритм верный.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)