|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
12.11.2012, 15:27 | #11 |
Пользователь
Регистрация: 12.11.2012
Сообщений: 20
|
Advanced Вариант
Ребята, привет. Короче говоря, боюсь мне никто не ответит так как последний пост датируется годом ранее, но все таки. Короче задачку мне поставили недавно такую же, но условия несколько другие:
На вход подается 2 числа. Первое не более чем 100-значное, второе влезает в int. 1. Необходимо получить второе число вставив знаки операций между цифрами первого числа. 2. Скобки ставить не надо - то есть только + - * / или ничего. Очевидно, простой перебор в худшем случае переживет нашу вселенную. Не говоря уже о том что становятся к тому же дорогими вычисления - нужна длинная арифметика. Есть ли идеи как оптимизировать перебор до ~ 10^8 операций? |
12.11.2012, 15:52 | #12 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
1) не знаю. я вообще не представляю другого варианта решения, кроме как полный перебор... сорри..
2) стало любопытным. а что, при подборе ещё нужно учитывать приоритет операций? вот, допустим, дано число 222 знаки расставили так: 2+2*2 = ? сколько получается у Вас в этом случае? |
12.11.2012, 17:54 | #13 |
Пользователь
Регистрация: 12.11.2012
Сообщений: 20
|
Serge, да, приоритет учитывается и поэтому 2 + 2 * 2 == 6. Ладно, еще подумаю, спасибо за ответ!
|
12.11.2012, 20:20 | #14 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Серж, а Вы не могли бы прокоментировать форму вывода?
Вот Код:
Код:
Это эквивалентно 1/2 + 3 + 4 * 56? |
12.11.2012, 20:26 | #15 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Aspirisha, а Вы зря в двух темах одновременно одну и ту же проблему обсуждаете!
Но называете "КРОССПОСТИНГ" и является нарушением правил форума! думаю, что правильным будет здесь обсуждение прекратить, а в созданной Вами теме продолжить. Удачи и не нарушайте, плиз, больше! Poma][a, нет. смысл постфиксной записи, что она выполняется над двумя операндами в стеке и результат помещается тоже в стек. 1 2 3 /+ 4 56 +* 1 в стек 2 в стек 3 в стек / достаём два числа с вершины стека и делим одно на другое (т.е. 2 делим на 3). результат (число равное 2/3) в стек + добавляем к результату 1 - полученный результат (1+2/3) в стек 4 в стек 56 в стек + берём два числа из стека, суммируем. результат (60) в стек * берём два числа из стека и перемножаем (60 * (1+2/3) = 60 + 40 = 100 ) результат (100) в стек = результат достаём из стека (это число 100). Вычисления закончены. Последний раз редактировалось Stilet; 30.04.2015 в 06:28. |
12.11.2012, 20:36 | #16 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Серж, огромное спасибо
|
18.06.2013, 09:51 | #17 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
ну, если очень вкратце, то алгоритм такой: вызываем рекурсивную процедуру NextVariant ей изначально передаём пустую строку (в качестве левой части), само число в виде строки, пустую строку (в качестве правой части). первым делом в NextVariant вызывается функция вычисления по переданным параметрам. Данная процедура заменяет знаки вопроса '?' в строке на все возможные арифметические операции (т.е. опять таки перебор - только уже ар.знаков) и вычисляет полученное выражение. Т.к. при первом вызове никаких вопросительных знаков в переданной строке нет, то тут же происходит выход из процедуры. далее в NextVariant происходит разбиение полученного исходной строки s (содержащей число) на отдельные элементы: Код:
для строки 12345 в результате данного цикла (с учётом рекурсии!!) будем получать следующие варианты рекурсивного вызова: Цитата:
полученные строки передаются в процедуру OutEq. Все знаки вопросов последовательно заменяются на знаки операции. Чтобы упростить алгоритм перебора знаков, используется т.н. польская форма записи выражения. Это когда идут сначала операнды, а потом уже сама операция. Преимущество этой записи в том, что она: 1) не использует скобки - они не имеют смысла в данной форме записи 2) все операции выполняются последовательно, все операции одного приоритета. Например, обычное выражение (1+2)*3 будет в польской записи выглядеть как 1 2 + 3 * а выражение 1+2*3 будет в польской записи выглядеть так 1 2 3 *+ процедура CheckAndShow вычисляет переданную ей строку с помощью функции Calculate (о вычислении выражения в польской записи см. мой пост #16 выше) полученное (вычисленное) значение строки сверяется с заданным числом и если оно совпадает (или если задали target = 0) - то строка выдаётся как подходящее решение. Кстати, можно доработать программу и полученную строку выражения переводить из польской записи в обычную, инфиксную, что нам более понятно и привычно. я не стал этим заниматься, чтобы не усложнять и так достаточно замороченный код... p.s. для разбора программ весьма рекомендую пошаговую отладку с контролем переменных. Очень помогает разобраться, что и где происходит.. p.p.s. если в результате моего рассказа какие-то детали остались невыясненными/непонятыми - спрашивайте конкретно, постараюсь ответить. |
||
23.06.2013, 10:12 | #18 |
Регистрация: 17.06.2013
Сообщений: 4
|
Спасибо Serge_Bliznykov, разобрался, а не могли бы вы написать процедуру перевода в инфиксную форму?
|
24.06.2013, 15:36 | #19 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
Код:
например, для 1 2 * 3 * 4 * = 24 выражение в infix: ((1 * 2) * 3) * 4 очевидно, что скобки здесь избыточны.. Впрочем, ошибочным это выражение от избыточности не становится p.s. полностью код PEREB_V3.PAS в архиве. |
|
17.04.2014, 17:54 | #20 |
Новичок
Джуниор
Регистрация: 11.04.2014
Сообщений: 1
|
Предлагаю вариант решения исходной задачи на С++ (аналог Perebor_2)
Последний раз редактировалось SeaSnake; 17.04.2014 в 17:56. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Проблема с цифрами | CrazyTosser | Помощь студентам | 8 | 07.02.2011 09:00 |
Арифметические действия над числами | DeathWisher | Помощь студентам | 5 | 24.01.2011 19:24 |
Ассемблер.Арифметические действия с условием | Лилея | Помощь студентам | 0 | 21.01.2011 20:23 |
Арифметические действия со строкой. | Небесный | Java Мобильная разработка (Android) | 3 | 01.01.2011 01:41 |
Арифметические действия над матрицами и транспонирование | Axel1981 | Помощь студентам | 14 | 12.06.2010 20:20 |