Самая СЛОЖНАЯ ЗАДАЧА ВО ВСЕЛЕННОЙ - Паскаль, Turbo Pascal, PascalABC.NET

Акашаев Нурлан · 26.04.2008, 17:28

здр всем кто читает. У меня есть задачка:
Так вот, дана строка, состоящая из символов '?' и '(' и ')'.
Требуется вывести все варианты преобразованной строки, где вместо вопросов стоят '(' или ')' и полученное скобочное выражение правильное.
например: (??)
ответ: (())
()()
А, кстати, длина строки составляет 254 символа

evg_m · 26.04.2008, 18:23

как такая идея алгоритма

бежим по строке считаем количество ( и количество )

для правильной формулы число ( всегда >= числа ) и в конце они должны быть равными

т.е. (как только число ( < число ) дольше проверять строчку нет смысла

встретили ?
выполняем подстановку ( и пытаемся работать дальше
выполняем подстановку ) и пытаемся работать дальше

Акашаев Нурлан · 26.04.2008, 18:34

Ну я сам тоже так додумался, то есть рекусривным перебором. Но этот метод у меня работает медленно. Да и проверка сложноватая

evg_m · 26.04.2008, 21:12

какие характеристики по времени для 20-30 "?" в строке сочтешь приемлимыми

дополнительное правило чмсло откр =число закр стало быть число откр <=длина строки /2

eoln · 26.04.2008, 22:32

Если проблема только со временем, то строку забей в массив как char или byte (код символа). Т.к. с длиной массива в паскале проблема (ограничен), то возможно на динамические переменные перейти.

26.04.2008, 17:28	#1
Акашаев Нурлан Пользователь Регистрация: 02.05.2007 Сообщений: 53	Самая СЛОЖНАЯ ЗАДАЧА ВО ВСЕЛЕННОЙ здр всем кто читает. У меня есть задачка: Так вот, дана строка, состоящая из символов '?' и '(' и ')'. Требуется вывести все варианты преобразованной строки, где вместо вопросов стоят '(' или ')' и полученное скобочное выражение правильное. например: (??) ответ: (()) ()() А, кстати, длина строки составляет 254 символа

26.04.2008, 18:23	#2
evg_m Старожил Регистрация: 20.04.2008 Сообщений: 5,526	как такая идея алгоритма бежим по строке считаем количество ( и количество ) для правильной формулы число ( всегда >= числа ) и в конце они должны быть равными т.е. (как только число ( < число ) дольше проверять строчку нет смысла встретили ? выполняем подстановку ( и пытаемся работать дальше выполняем подстановку ) и пытаемся работать дальше программа — запись алгоритма на языке понятном транслятору

26.04.2008, 21:12	#4
evg_m Старожил Регистрация: 20.04.2008 Сообщений: 5,526	какие характеристики по времени для 20-30 "?" в строке сочтешь приемлимыми дополнительное правило чмсло откр =число закр стало быть число откр <=длина строки /2 программа — запись алгоритма на языке понятном транслятору Последний раз редактировалось evg_m; 26.04.2008 в 21:15.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Сложная задача	asale	Microsoft Office Excel	6	07.04.2009 20:36
Сложная задача....можно ли решить?	Pleksy	Microsoft Office Excel	1	23.02.2008 05:27
Вот ещё одна,самая сложная:	felice	Паскаль, Turbo Pascal, PascalABC.NET	4	03.02.2008 17:21
Простая и в то же время сложная задача	fiveelement	Microsoft Office Excel	1	28.10.2007 21:03

26.04.2008, 18:34	#3
Акашаев Нурлан Пользователь Регистрация: 02.05.2007 Сообщений: 53	Ну я сам тоже так додумался, то есть рекусривным перебором. Но этот метод у меня работает медленно. Да и проверка сложноватая

26.04.2008, 22:32	#5
eoln Старожил Регистрация: 26.04.2008 Сообщений: 2,645	Если проблема только со временем, то строку забей в массив как char или byte (код символа). Т.к. с длиной массива в паскале проблема (ограничен), то возможно на динамические переменные перейти.