Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Интересные и занимательные задачи по программированию > Проблема с олимпиадой

Автор: Fixin 10.2.2005, 19:09

Задано алгебраическое выражение, составленное из неотрицательных вещественных чисел и знаков операций +, - и *. Необходимо расставить в этом выражении скобки так, чтобы его значение стало максимально возможным. Технические требования Входной файл: INPUT1.TXT Выходной файл: OUTPUT1.TXT Формат входных данных В первой строке входного файла INPUT1.TXT записано исходное выражение длиной не более 250 символов. Внутри чисел пробелы не допускаются. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 10 в 6 степени. Формат выходных данных Выходной файл OUTPUT1.TXT должен содержать две строки. В первой должно находиться максимально возможное после расстановки скобок значение полученного выражения, во второй строке - само это выражение. Если вариантов решения задачи несколько, нужно выдать любой из них. Пример файла входных данных 1+2-3.0*4 Пример файла выходных данных ((1+2)-3)*4 Вобщем парсингом мудрить думаю муторно для олимпиады, а что еще можете предложить?

Автор: Sardar 10.2.2005, 19:25

Цитата(Fixin @ 10.2.2005, 18:09) Необходимо расставить в этом выражении скобки так, чтобы его значение стало максимально возможным. Цитата(Fixin @ 10.2.2005, 18:09) Пример файла входных данных 1+2-3.0*4 Пример файла выходных данных ((1+2)-3)*4 Что то я не понял примера

Автор: maxim1000 10.2.2005, 19:29

Цитата Что то я не понял примера если расставить скобки по-другому, получится меньший результат (по крайней мере, мне так показалось...)

Автор: Fixin 10.2.2005, 19:36

Пример не проверял. Дело не в том. Как решать-то? Это первая задача и пяти. Остальные сделал. Олимпиада областная. Мне тоже кажется, что можно и отрицательное получить... но не проверял. Добавлено @ 19:38 Тьфу, ошибся! Там максимум нужен!!!

Автор: Sardar 11.2.2005, 00:43

Цитата(maxim1000 @ 10.2.2005, 18:29) если расставить скобки по-другому, получится меньший результат (по крайней мере, мне так показалось...) Так тоже ноль будет: (1+(2-3))*4 Извиняюсь за глупость, но что если перебрать все возможные варианты... Медленно, но верно Строим все возможные деревья, начиная с обьеденения листьев, затем узлов. С каждой новой вариацией копируем дерево и пускаем его по альтернативному варианту.

Автор: Akina 11.2.2005, 10:26

Только перебор.

Автор: maxim1000 11.2.2005, 11:04

можно покрутить в таком направлении: как бы мы не расставили скобки, какое-то действие будет выполнено последним выделим его выбор в отдельную часть перебора т.е. сначала сделаем простой цикл по действиям, а внутри сделаем перебор по расстановке остальных скобок теперь рассмотрим, какое действие может быть последним: 1. + здесь все просто: нужно максимизировать то, что слева, и то, что справа, решаются эти задачи независимо 2. - здесь тоже все просто: нужно максимизировать то, что слева, и минимизировать то, что справа 3. * здесь менее приятный случай (из-за того, что в зависимости от знака одного множителя нужно либо минимизировать, либо максимизировать другой), тут можно просто решить 4 задачи: min и max первого, min и max второго, и выбрать один из 4х вариантов Цитата Так тоже ноль будет да в остальных случаях будут отрицательные результаты (меньше нуля )

Автор: Akina 11.2.2005, 12:35

Цитата(maxim1000 @ 11.2.2005, 12:04) 1. + здесь все просто: нужно максимизировать то, что слева, и то, что справа, решаются эти задачи независимо Не факт 2*3+3*2 2*(3+3)*2

Автор: maxim1000 11.2.2005, 13:20

Цитата Не факт 2*3+3*2 2*(3+3)*2 гы-гы, факт я описывал только "внешнюю" операцию (ту, которая выполняется последней в первом случае все, действительно, просто во втором "внешней" операцией является умножение, так что используется 3-е правило а после того, как внешняя операция разделила выражение (ну, еще не совсем выражение, скорее, выражение без скобок) на два независимых (если не считать зависимости, описанной в пункте 3), в каждом из них можно перебирать свою внешнюю операцию

Автор: En_t_end 11.2.2005, 16:39

На этот вопрос с программерской точки зрения знает ответ ~FOX~, он в одной из тем флейма хвастался спроси у него, может код подкинет ЗЫ 3.0 - не совсем удачное число

Автор: Sardar 12.2.2005, 01:19

maxim1000 а что если выражение может быть сколь угодно большим, операции: +, -, *, /, %(модуль), -(унарный минус). Какова логика теперь?

Автор: Fedor 12.2.2005, 07:17

перебор. Чистый. Это классическая задача.

Автор: Fixin 12.2.2005, 10:49

Но для перебора нужны кие-то ограничения.

Автор: Fixin 12.2.2005, 11:33

Основная проблема, как организовать разбор выражения по-проще, вставить-то скобки потом можно. Добавлено @ 11:35 И еще. Может пробовать расставить скобки по каждому знаку действия?

Автор: Sardar 12.2.2005, 13:55

Цитата(Fixin @ 12.2.2005, 10:33) как организовать разбор выражения по-проще Дык это регулярные выражения(можно LL(1) разбор). Делаешь лексический анализ на табличноуправляемом ДКА, получил числа и операторы(лексемы). Затем по лексемам собираешь деревья выражений, это по разному сделать можно. Если нужно как можно проще и изменятся в будущем особо не будет, то закодируй в ручную лексер. Приемр на JS за 5 минут: Код //разбор возвращает массив лексем function simpleLexer(str) {  var ret=[], c, l;  for(var i=0; i<str.length; i++) {     c=str.charAt(i);  if((c>="0"&&c<="9")||c==".") {    l=getNumber(str, i);    if(l.type=="error") throw "Parse error at "+i+", wrong syntax of number";    else ret.push(l);  } else if("+-*/".indexOf(c)>=0) {     l={type:"operator", val:c}; //при условии что у нас все операторы односимвольные  ret.push(l);  } //всё остальное просто игнорируем  }  return ret; } //достать число, я исользую встроенный parseFloat, ты же здесь можешь его распарсить function getNumber(str, j) {  var ret="", fnum=false, gotval=false;  for(var i=j; i<str.length; i++) {   if(str.charAt(i)==".") {     if(!fnum) { ret+="."; fnum=true;}     else return {type:"error",val:""}; //564.546. error   } else if(str.charAt(i)>="0"&&str.charAt(i)<="9") {ret+=str.charAt(i); gotval=true;}      else if(!gotval) return {type:"error",val:""}; //. error   else return {type:"number", val:parseFloat(ret)};  }  if(!gotval) return {type:"error",val:""}; //. error  else return {type:"number", val:parseFloat(ret)}; } //пример var p=simpleLexer("2*3+3*2"); for(var i=0; i<p.length; i++) {  alert(p[i].type+": "+p[i].val); } С табличноуправляемым разбором покажу попозже.

Автор: Sardar 12.2.2005, 17:35

Не знаю нужно ли это, примера выше вполне хватает. Но если нужен лексический анализ посложнее, то используем теорию(обращатся на http://www.softcraft.ru) Сначала придумывал реги: Код operator:=[+-*/%] number:=(([0-9]*\.)?[0-9]+)|([0-9]+(\.[0-9]*)?) Затем нарисовал по ним граф(по диаграме Вирта). ДКА строил ручками по нарисованному графу, в уме создавал множества first/follow. Для такой маленькой таблички это еще возможно, при более сложной грамматике юзаем соответствующие инструменты(GOLDParser, flex и т.п.) Код //вводим классы для удобства litera.WSPACE=0; litera.NUMBER=1; litera.POINT=2; litera.OPERATOR=3 litera.EOF=4; litera.UNKNOWN_LIT=5; function litera(sym) { //транслитератор, преобразовываем символы к классам выше  if(sym<=" ") return litera.WSPACE;  if(sym>="0"&&sym<="9") return litera.NUMBER;  if(sym==".") return litera.POINT;  if("+-*/%".indexOf(sym)>=0) return litera.OPERATOR;  return litera.UNKNOWN_LIT; } var dka=[ //собственно сама таблица ДКА  [ 0,-1, 6, 6, 6, 6], //wspace  [ 3, 2, 2, 3, 5, 5], //number  [ 1,-1,-1, 4,-1,-1], //point  [ 7,-1, 6, 6, 6, 6],  //operator  [-2,-1, 6, 6, 6, 6] //end of string ]; function dkaParser(str) { //ну и простой разбор  var ret=[];  var state=0, lt, c, i=0, numbuf="";  while(true) { //прерывание цикла по автомату        lt = (i<str.length)? litera(c=str.charAt(i)): litera.EOF; //достаём класс символа if(lt>dka.length) throw "Parse error: illigal character: "+c+", at position: "+i; state=dka[lt][state]; //делаем переход        //расбор состояний автомата if(state==0) i++; else if(state>=1 && state<=5) {numbuf+=c; i++; } else if(state==6) {ret.push({type:"number", val:parseFloat(numbuf)}); numbuf=""; state=0;} else if(state==7) {ret.push({type:"operator", val:c}); i++; state=0;} else if(state=-2) break; else throw "Parse error unknown token at position: "+i;  }  return ret; } var p=dkaParser("2*3+3*2"); //получаем массив лексем for(var i=0; i<p.length; i++) {  alert(p[i].type+": "+p[i].val); } Состояния 6 и 7 не внесенны в таблицу, мы просто устанавливаем начальное состояние вручную state=0 Цикл разбора бесконечный, прерывается автоматом, потому за ним нужно хорошо следить, а то можешь уйти в бесконечный цикл Для парсинга числа я использовал parseFloat, ты можешь при получении числа вторично пройтись по нему и распарсить встроенными функциями, либо парсить на состояниях 1-5 Это была лексика, теперь нужно это всё собрать до четвёрок либо любого другого представления со всеми возможными вариантами раставления скобок. Затем всё выполнить, найти требуемый результат и выбрать наиболее подходящее выражение.

Автор: Fixin 12.2.2005, 20:51

Прикольно. С такой теорией любая олимпиада = "нефиг нафиг пофиг" . Пока поизучаю. Придумаете еще - буду рад. пока что - сенькс.

Автор: maxim1000 14.2.2005, 11:54

Цитата(Sardar @ 11.2.2005, 23:19) maxim1000 а что если выражение может быть сколь угодно большим, операции: +, -, *, /, %(модуль), -(унарный минус). Какова логика теперь? количество комбинаций расстановки скобок конечно, поэтому количество всевозможных значений выражения конечно, а значит, из них можно выбрать максимум с операциями типа % действительно проблема - зависимость не монотонна по аргументам, там так не получится...

Автор: Fixin 14.2.2005, 18:47

В условии такех вообще не имеется. Я решил попробовать грузить цифры в один массив, а знаки в другой. Изменяем массив со знаками, сливаем, проверяем на макс, сохр. копию, идем дальше... Но, хр-вато как-то

Автор: Fixin 14.2.2005, 22:39

А действительно. Так как "+" и "-" равнозначны, то смысл есть только относительно "*" скобки ставить, больше они нигде роли не играют. Надеюсь. Если неправ, то скажите.

Автор: maxim1000 15.2.2005, 11:14

Цитата Так как "+" и "-" равнозначны, то смысл есть только относительно "*" скобки ставить, больше они нигде роли не играют. Надеюсь. Если неправ, то скажите. (1-2)+3 1-(2+3)

Автор: Fixin 15.2.2005, 21:27

Уже догадался. Обломчик. Добавлено @ 21:32 Задолбался. Не могу заставить ету штуку все варианты строить. Тут нужна рекурсия или псевдорек., что-то вообще ничего не получается. Хоть словами опишите алгор. Извиняюсь за ламерство.

Автор: Sardar 16.2.2005, 02:28

Блин сижу и гадаю как порешать, никогда таким не занимался, алгоритм придумал сам, так что извиняюсь за глупости Отсюда вывод, надо читать теорию! Хранить все деревя выражения крайне не эффективно, ибо всю память сожрёт. Вот что я надумал, может завтра выложу код: Код 1+2+3+4+5+6 level 1: (1+2)+3+4+5+6 1+(2+3)+4+5+6 (1+2)+(3+4)+5+6 1+2+(3+4)+5+6 (1+2)+3+(4+5)+6 1+(2+3)+(4+5)+6 (1+2)+(3+4)+(5+6) level 2: (R1+3)+4+5+6 R1+(3+4)+5+6 (R1+3)+(4+5)+6 R1+3+(4+5)+6 (R1+3)+4+(5+6) R1+(3+4)+(5+6) R1+3+4+5+6 Сначала убираем все приоритеты операций, мы расставляем все скобки. Заводим для каждого уровня дерева целый счётчик, присваиваем ему 1. Считаем сколько в выражении чисел, делим на два, вот это максимальная разрядность счётчика. В примере это 3 бита. Взяли значение счётчика текущего уровня, раскладываем на биты и идём вдоль битового ряда и ряда чисел нашего выражения. Если бит равен 0, то пропускаем число, иначе обьеденяем текущее число и следующее в ноду Ri. Переходим на уровень выше, повторяем действия выше. Так продолжается до корня. Вычисляем выражение, это очень просто если ты строил дерево на обéктах операторах, тогда вызываем у корня выполнить, а тот в свою очередь рекурсивно опросит потомков и так до самых листьев. Если пишем не на обьектно ориентированном языке, то строим линейное дерево на тройках, такое представление очень легко вычислить. Посчитали, сохранили где нибудь результат + все счётчики с уровней. Таким образом мы можем сравнить результаты и если надо, востановить дерево. Построенное и уже не нужное дерево удаляем, освобождая память под следующее дерево. Инкрементируем счётчик первого уровня и повторяем все действия снова. Как только счётчик первого уровня переполнится, инкрементируем счётчик второго уровня, по такому правилу и выше по дереву. Посчитали, ОК, теперь всё по новой, но связывать узлы по счётчику будем не слева на право, а с права на лево. Последнее дерево можно не генерить, оно такое же как и при первой половине вычислений. Всё посчитали, теперь достаём нашь своп файл и т.п. куда мы сохраняли результаты вычисления дерева и счётчики. Находим тот результат, который нужен(наибольший, наименьший, по указанию васи пупкина...). Отсюда находим все вариации деревьев которые дают этот результат. По счётчикам ставим скобки точно также как строили деревья.

Автор: maxim1000 16.2.2005, 10:58

хм... честно говоря, не понял алгоритма есть два пути (как, впрочем, и в большинстве случаев): снизу (по первой выполняемой операции) и сверху (по последней) 1. сверху (я уже описал): типичная рекурсия, перебираем последнюю операцию (которая делит выражение на две части), вызываем минимизацию/максимизацию для частей, выбираем максимум 2. снизу (тоже, вобщем-то, рекурсия): выбираем первую операцию, которая будет выполнена, заменяем пару чисел и знак между ними на результат операции, получаем N новых выражений (потому, как первую операцию можно выполнить N способами, N - количество операций), к каждому применяем тот же алгоритм (эти выражения стали короче на 1 операцию) теперь будем думать: нам нужен быстрый алгоритм или алгоритм с неболшим использованием памяти? 1. небольшое использование памяти: тогда рекурсия, максимальное использованием памяти - приблизительно N*Length(s)/2 2. скорость: дело в том, что алгоритм можно ускорить, пожертвовав некоторым объемом памяти, получается так, что граф разбора деревом не является (точнее не совсем является), т.к. выражения: (1+1)-(2+2) (первая операция - над 1-цами) и (1+1)-(2+2) (первая операция - над 2-ками) логично было бы считать одинаковыми (а тогда уже и обрабатывать один раз) но к ним можно прийти двумя путями, а значит, это не дерево вот на отказе от повторной обработки и получится ускорение но для этого надо хранить все результаты обработки каждого такого выражения (вот и наша жертва - память)

Автор: Sardar 16.2.2005, 11:01

Права пословица, утром голову глючит меньше чем вечером Дерево можно не строить! На каждом уровне мы имеем ряд чисел, все связанные узлы вычисляем и получаем новый ряд, в котором как миннимум на одно число стане меньше. Над новым рядом повторяем те же операции и опять вычисляем узлы. Так до тех пор пока в ряду не останется всего одно число, которое и будет результатом. Количество счётчиков равно высоте самого высокого дерева, т.е. N-1, где N это количество чисел в выражении. Самое низкое дерево получаем если обьеденяем как можно больше пар из соседних элементов. Добавлено @ 11:04 Дерево точно можно не строить, извиняюсь если не ясно описал, попробую обьяснить кодом вечером, сейчас я на работе, перерыв

Автор: Sardar 16.2.2005, 11:13

Если усложним задачу: в выражении могут встречатся негативные числа и уже проставленные скобки: 1+-3-(45/7+12*6+9)*(-1)+34 Негативные числа распознаются парсером, он же и номрализует их до вида (- число). Мы получаем ряд готовых чисел. По грамматике разбора генерим в конце выражение назад. Уже существующие скобки убирать нельзя. Тогда мы вычилсяем содержимое скобок отдельно(подвыражение) и получаем множество результатов {число:счётчики}. Заменяем все вхождения выражений в скобках на Si, где для каждой Si вычислили своё множество результатов. Ну а затем работаем с текущим деревом подставляя на места Si числа из связанного множества. Таким образом можно иметь скольугодно уже ресставленных скобок как угодно вложенных друг в друга.

Автор: Fixin 16.2.2005, 17:54

Спасибо, за что есть Буду разбираться. Можете порекомендовать теорию по динам(или простому) программингу в электронном виде или имена авторов?

Автор: Fixin 16.2.2005, 18:10

Цитата Сначала убираем все приоритеты операций Это как?

Автор: Sardar 17.2.2005, 22:57

Цитата(Fixin @ 16.2.2005, 17:10) Это как? Приоритеты операций это то что ты сам реализуешь. Если этого не делать, то приоритетов не будет Звныяюсь за код, сейчас порпобую разрулить у себя и выложить что нибудь.

Автор: Fixin 17.2.2005, 23:12

Цитата Цитата  Сначала убираем все приоритеты операций Это как? Я не понял куда убираем-то?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)