Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Полный перебор. Кто-нибудь в курсе??
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Сэт Сэт вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 10.11.2011
По умолчанию Полный перебор. Кто-нибудь в курсе?? - 10.11.2011, 04:24

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

Используй силу, Люк!
т.е. используй деревья, Илья!

В идеале хотелось бы с помощью деревьев ее решить, но время говорит, что придется полным перебором, и то, если получится.

Сам две недели просидел и до сих пор ничего не родил Блин, если бы получилось сгенерить все бинарные деревья разбора выражения.

Пока могу лишь подсчитать, сколько всего их должно получиться.

Количество всевозможных бинарных деревьев для определенного количества узлов, в нашем случае узлов 9 можно получить, не считая, воспользовавшись числами Каталана
Числа Каталана — Википедия

Например, всевозможные деревья для двух узлов, это ((1 o 2) o 3) и (1 o (2 o 3)) - всего два. Для трех узлов - пять. Для девяти их 4862.

Теперь посчитаем размещения с повторениями трех знаков "+", "-", "*" по девяти местам. A'_9_3 = 3^9 = 19683.

Итого 19683*4862 = 95698746.

Все, больше у меня ничего нет :(

ps: Эвристика - слово то какое!
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
подскажите кто в курсе Jt91 Планшетные ПК 4 13.03.2012 05:06
Может кто в курсе? Dmitriy777777 Любые вопросы от новичков 3 24.05.2011 01:29
Перебор механизмов как реализовать gisol Delphi 29 23.02.2011 20:51
можно ли как нибудь поставить пароль на какую нибудь папку? imported_FAN Любые вопросы от новичков 5 28.11.2010 11:13
Процесс загрузки ОС ХР (чтобы быть в курсе) Артём Библиотека 3 16.01.2010 02:09
Логическая задача (перебор чисел) videomag Prolog 38 13.04.2009 16:06
Перебор комбинаций массива ReinWolf Вопросы начинающих программистов 2 13.11.2006 22:19
Кто-нибудь что-нибудь знает про защиту от копирования на DVD tokito Офтопик 1 07.11.2006 14:05
Перебор перестановок цифр jaga_man Java 12 17.06.2006 16:52
Перебор списка. Как он работает? AntonioLazarenni Prolog 5 03.06.2006 23:42
Перебор БД artgonch Prolog 4 02.04.2005 11:58
Кто в курсе ограничений бесплатного GemStone Life_Freedom_Love Smalltalk 7 02.03.2005 13:58



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов