Вот все возможные (нетривиально различающиеся) варианты получения пятёрки из пяти двоек с использованием четырёх арифметических операций, конкатенации и скобок:
Я написал прогу, вмиг решающую такие задачи без полного перебора выражений. И даже придумал для неё полезное применение: «анализ» имени: http://iproc.ru/interesting/the-name/ (естественно, всерьёз воспринимать такой «анализ» нельзя!)
Ответ: Какое бы ты имя и фамилию не ввел, то все равно "Вы самый страшный человек на свете!" Круто! Молодец!
Ответ на ответ (from Lazer): Ничего подобного. Я перебирал знакомых, из 10 человек всего 1 попался с "красивыми" именем и фамилией, при этом у него число было не 666, а 777.
А интересно, как ты написал ее без полного перебора выражений? Можешь поделиться, очень интересно? Я такую делать не буду, просто интересно как ты ее сделал.
Формально алгоритм отличается от полного перебора тем, что не перебираются выражения, дающие одно и то же число из одних и тех же аргументов. Однако, теоретически, как и полный перебор, в худшем случае алгоритм всё равно имеет ужасную оценку сложности O(exp(N)), где N — количество исходных чисел. В среднем на практике он существенно быстрее из-за большого количества «схлопывающихся» вариантов типа 2*2=4 и 2+2=4.
В форуме не описан «обратный ход» алгоритма, приводящий от заветного числа из полученного множества к конкретным выражениям. Но, думаю, понятно, как его реализовать. Один из самых простых способов (подходящий для нахождения одного выражения) — к каждому получаемому числу из множества возможных чисел приписывать самое простое выражение, которое его породило. Более изощрённые приёмы (которые оставлю в секрете) позволяют двигаться обратно (от результата к аргументам), «вычисляя» требуемые арифметические операции на основе множеств чисел.
Впоследствии до меня дошло, что для получения выражений можно вовсе не получать множество возможных чисел, а начинать сразу с обратного хода, предполагая, что нужное число содержится в результирующем множестве. Если же предположение о существовании оказывается неверным, то просто не будет получено ни одного выражения. Такой способ проверки возможности получения числа существенно быстрее, чем получение множества всех возможных чисел; работает за время O(sqrt(exp(N))).
Естественно, реальная программная реализация содержит большое число оптимизаций, позволяющих существенно сократить время вычислений и требуемую память. Но основная идея остаётся той же.
