Позаимствовал задачку одну: Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение. Должны заменяться все знаки вопроса. Пример: ????(? Ответ - 2 Есть идеи кроме полного перебора?
Самый тупой вариант: Код (Text): int rec(char *pattern, int opened){ if(opened < 0) return 0; switch(*pattern++){ case '(': return rec(pattern, opened + 1); case ')': return rec(pattern, opened - 1); case '?': return rec(pattern, opened + 1) + rec(pattern, opened - 1); default: return (!opened); } } int solve(char *pattern){ return rec(pattern, 0); }
Quantum Не уверен, что в твоем варианте будет выполняться условие . Например в случае ?? у тебя по-моему будет два ответа: () и )(. Nouzui Посмотри здесь: http://www.wasm.ru/forum/viewtopic.php?pid=102625#p102625 Я бы предожил перебирать деревья и откидывать не подходящие по сравнению с шаблоном.
Stiver Исправил. Первоначальный вариант работал, т.к. компилятор VC6 почему-то заменяет строку "????(?" на "??[?". Интересно, почему он так делает?
Nouzui Если шаблон состоит из одних знаков вопроса длины n, то определение количества возможных расстановок скобок K(n) - это известная в комбинаторике задача о правильной расстановке скобок (см., например http://journal.issep.rssi.ru/articles/pdf/0102_103.pdf). Число K(n)=C(2n, n)/(n+1), где C(n,m)=n!/(m!*(n-m)!) - биномиальный коэффициент. Если известно, что на каких-то местах уже заданы скобки, то это будет более сложная задача.
Вот сдесь разобрана эта задача. http://homepages.compuserve.de/chasluebeck/practic_info2.htm Собственно по этой книге ("Особенности национальных задач по информатике") все или почти все задачи прорешал в школе.
Pavia Здесь алгоритм дан, а число вариантов зависит от шаблона, это и так понятно. А вот каков вид зависимости - это сложно определить.
Quantum На самом деле Ваш интуитивный вариант отразил классическую рекуррентную формулу, лежащую в основе подсчета.
