Задача на решение полным перебором!

 
0
 
Functional languages
ava
Сэт | 10.11.2011, 03:33
Вобщем, есть такая задача:
Определить, можно ли расставить знаки «+», «-», «*» и круглые скобки между числами 1, 2,..., 10 (именно в этом порядке, без перестановок) так, чтобы в результате выполнения всех действий получилось заданное число. Функция должна получать на вход число и выдавать строку, изображающую правильную расстановку знаков и скобок, или строку «impossible», если заданное число получить невозможно. Например, для числа 2011 возможный вариант мог бы выглядеть так:
(1+((2*3)+(4+(5*((6*((7*8)+9))+10)))))
Пытался хоть какую-нибудь эвристику для этой программы придумать или найти - не удалось... Приходится думать над полным перебором, а время уже поджимает... Если у кого есть соображения - поделитесь, пожалуйста!!
Comments (3)
ava
Фантом | 10.11.2011, 03:22 #
Не знаю, поможет или нет, но...

Всякое выражение со скобками может быть преобразовано в обратную польскую запись с тем же порядком операндов (но, соответственно, без скобок). При этом первые два элемента записи - это "1" и "2", а дальше каждый элемент может быть одной из трех операций или очередным числом, и количество операций в любой момент должно быть как минимум на единицу меньше количества чисел. Это позволяет написать достаточно простой перебор, правда, после обнаружения ответа его надо будет переводить из ОПЗ в обычное представление, но это не так уж сложно.
ava
Сэт | 10.11.2011, 23:53 #
пробую решить через обратную польскую запись, спасибо за совет! Только столкнулся с вопросом, что при составлении списка, который будет участвовать в полном переборе мне не хватает выделенной памяти! Конечно, можно было бы поискать более оптимальное решение, но сейчас, если честно, просто нет на это времени, уже ухватился за этот вариант... не подскажите, как выделить побольше памяти для интерпретатора?? Я в Hugs конечно же работаю...
ava
Сэт | 11.11.2011, 00:09 #
С этим разобрался...
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
advanced
Submit