| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Алгоритм] Перебор в ряду |
| Автор: Be_Happy 4.12.2007, 20:50 |
| Дан ряд 123456, нужно расставить в нем скобки и знаки +, -, * и / так, чтобы в результате получалось 100. Я знаю 1 вариант: -1*2+3*(4+5*6) Но нужно чтобы программа перебирала все возможные. Какой алгорит перебора можно пременить? |
| Автор: dereyly 5.12.2007, 04:26 |
| Ну можно решить эту задачу с помощью генетических алгоритмов, хотя тут и без них неплохо... Только в этой задаче нужно работать с другим представлением данных... (т.е. чуток преформулировать задание) В этой задаче основную комбинаторную сложность вносят скобки и хрен знает как их ставить: в одном месте может стоять 3 скобки открывающих в другом 2 закр и еще нужно следить чтобы они были парными... короче жесть. Так как по сути скобки меняют расположение вершин в дереве решений, то можно работать с этим деревом. Но можно еще проще -- дерево решений замечательно работает на стеке в префиксной форме алгебраического выражения... (или в двух стеках) не учитывая унарного минуса стек1: 123456 (или 654321) стек2: xzxzxzxzx где x это произвольная операция * + - / а z это модификатор позиции т.е скобки, и принимает значения 0,1,2 (операция сразу после операции в стеке, операция после одного и с двух операндов в стеке), причем надо проверять чтобы для каждой операции в стеке оставалось два операнда. Этого можно добиться последовательным подбором при случайном переборе... 12 кидаем кубик выпало * записываем 12*=2 (сразу вычисляем) в стеке один операнд значит z может принимать значения 1 и 2, т.е мы можем добавить в стек следующее число 3 затем случайную опрацию или добавить 34 и случ операцию. префиксная форма 12+34+*56- / ~ (1+2)*(3+4)/(5-6) Унарный минус добавляет бинарную опратор к каждой цифре +- стек1: 1у2у3у4у5у6у (или стек1: 123456 стек3: уууууу) стек2: xzxzxzxzx ЗЫ: Рассуждения можно не читать. Кратко: пользуйтесь префиксной формой (с этой формой проще кодировать скобки) |
| Автор: Be_Happy 9.12.2007, 22:43 |
| dereyly, что такое префиксная форма? |
| Автор: dereyly 9.12.2007, 23:36 |
| http://forum.vingrad.ru/index.php?showtopic=185803&view=findpost&p=1341742 префиксной формы http://www.intuit.ru/department/pl/plintro/3/ |
| Автор: Akina 10.12.2007, 00:00 | ||
Строим возможные деревья вычислений (их будет немного) в польской нотации и начинаем подставлять в узлы и ветви все подряд. В простейшем случае (не допускается решение типа 123-4!-5+6 ) операндов - 6, вариантов мат. действий - 5, вариантов перебрать (для каждого дерева) - 6!*5^5... развернуть же подходящее дерево обратно в выражение тоже не проблема. |
| Автор: Be_Happy 16.12.2007, 16:42 |
| дерево теоретически понял, а как это на С++ написать? |
