Комментарии 23
Мое медленное решение на TCL решение. Работает около 30 секунд на P4 3ГГц. На КПК запускать боюсь. Думаю, что в данном случае тормозит именно язык, и если переписать почти дословно на C можно много выиграть.
Две запятые после плюса это опечатка или задумка? :)
Моё решение немного побольше, зато и работает побыстрее =)
~418мс на Dell Preceision 490.
www.pastie.org/264061
~418мс на Dell Preceision 490.
www.pastie.org/264061
Спасибо, вы оживили этот пост. Код интересный, минут 10 разбирал, получил удовольствие до конца поняв его, Ваш код можно использовать для иллюстрации паттерна посетитель, И он действительно как минимум в четыре раза быстрее — вы учли коммуникативность сложения и умножения. Я сходу не могу оценить, сколько примерно деревьев вы храните в expressions — грубая оценка около 8000, близко в реальности?
Ровно 5184. А у Вас, на сколько я понял, подсчёт выражений происходит средствами самого языка? Я, к сожалению, не знаю TCL, но компактность решения впечатляет =)
Там все просто: в списке expressions всевозможные варианты расстановки скобок (5 штук), далее машина просто заменяет a b c d на числа, а x y z на арифметические операции, и используя eval производит вычисления.
Остальной код — функции для генерации перестановок, сочетаний и декартового произведения.
Остальной код — функции для генерации перестановок, сочетаний и декартового произведения.
коммутативность сложения и умножения
Блин, как страшно жить. Вокруг столько умных людей…
В Науке и Жизни когда-то было аналогичное задание. Только там оно давалось на целый год и цифры были цифрами года, то есть к примеру, 1, 9, 7, 5. В отличие от интерпретации автора там нельзя было менять порядок следования цифр, но можно было группировать цифры в числа и использовать любые действия, в том числе, степени и корни.
Когда-то было на отборах на 4 этап эта задача. Правда я ее не решил) Но были люди, которые решили и без програмирования ее. Мне кажеться более интерестным заданием будет, если добавить в условие «без компьютерных вычислений».
Для перебора возможных выражений использовал обратную польскую нотацию.
Получается всего 5 возможных шаблонов расположений операций и операндов. Если символом '0' обозначить операнды, а символом '1' — операции, эти 5 шаблонов будут выглядеть так:
0 0 1 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 0 1
0 0 0 1 0 1 1
0 0 0 0 1 1 1
Каждый из них можно закодировать одним числом. Для удобства младшим битом будем считать крайний левый. Тогда получится пятерка { 84, 100, 88, 104, 112 }. Еще нужно заметить, что в любом выражении ровно четыре операнда и ровно три операции.
Остается перебрать все четверки цифр a < b < c < d, для каждой из них рассмотреть все их перестановки (24 штуки), все 5 шаблонов и все возможные варианты подстановки операций (3 позиции для операций * 4 возможных операции = 12 вариантов), и для каждой такой комбинации вычислить значение выражения.
Решение не учитывает коммутативности операций, но и так работает примерно за секунду.
clipie.org/view.php? key=9S2WJDHN0VL5M6Z4KXYQ
Получается всего 5 возможных шаблонов расположений операций и операндов. Если символом '0' обозначить операнды, а символом '1' — операции, эти 5 шаблонов будут выглядеть так:
0 0 1 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 0 1
0 0 0 1 0 1 1
0 0 0 0 1 1 1
Каждый из них можно закодировать одним числом. Для удобства младшим битом будем считать крайний левый. Тогда получится пятерка { 84, 100, 88, 104, 112 }. Еще нужно заметить, что в любом выражении ровно четыре операнда и ровно три операции.
Остается перебрать все четверки цифр a < b < c < d, для каждой из них рассмотреть все их перестановки (24 штуки), все 5 шаблонов и все возможные варианты подстановки операций (3 позиции для операций * 4 возможных операции = 12 вариантов), и для каждой такой комбинации вычислить значение выражения.
Решение не учитывает коммутативности операций, но и так работает примерно за секунду.
clipie.org/view.php? key=9S2WJDHN0VL5M6Z4KXYQ
К сожалению, что-то умнее перебора не придумалось
Работает где-то полминуты
Работает где-то полминуты
А вот, кстати, интересно было бы посмотреть на решение с использованием C# Expression Trees.
после прочтения задачи, вспомнилась классика под названием «four fours» — нужно представить натуральные числа, используя ровно четыре четверки.
если кто о ней не слышал, то на википедии есть про нее статья, и там в частности упоминается интересная pdf-статья 2002 года с ответами, за некоторым исключением, на первые 40 тысяч чисел (пробелы идут начиная со второй тысячи).
если кто о ней не слышал, то на википедии есть про нее статья, и там в частности упоминается интересная pdf-статья 2002 года с ответами, за некоторым исключением, на первые 40 тысяч чисел (пробелы идут начиная со второй тысячи).
Около 500 милисекунд работает на руби и выдает ответ 1256 и 1258 — 1..43.
Здесь никто не приводил полученные ответы, поэтому оценивая то, как мы с одним человеком долго пытались сойтись в ответах, полагаю, что только единицы из вас получили ответ верный.
Просьба пересмотреть свои решения, если ответ не совпал с моим.
Решение (не моё) на перле: rafb.net/p/MIxkD182.html
Мой быдлокод на руби: rafb.net/p/b5yJh242.html
Здесь никто не приводил полученные ответы, поэтому оценивая то, как мы с одним человеком долго пытались сойтись в ответах, полагаю, что только единицы из вас получили ответ верный.
Просьба пересмотреть свои решения, если ответ не совпал с моим.
Решение (не моё) на перле: rafb.net/p/MIxkD182.html
Мой быдлокод на руби: rafb.net/p/b5yJh242.html
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача №93