две задачки (математическое)

[avva]

1. Используя только цифры 1,5,6,7, четыре арифметических действия и, если нужно, скобки, напишите выражение, результат которого равен 21. Вместе соединять цифры, т.е. например, использовать число 15, нельзя. Использовать цифры можно в любом порядке, но каждую не более одного раза.

2. Используя только цифры 2,2,2 (три двойки), а также математическую нотацию из стандартной школьной программы, выразите любое целое число. Нельзя использовать стандартные константы (например, числа пи или е). Из цифр - в любом месте выражения - можно использовать только эти три двойки.

Комментарии я скрывать не буду, так что не заглядывайте, если хотите сами решить.

Еще, на мой взгляд, написать программу для решения первой задачи может быть неплохим заданием для программиста на интервью. Если вы программист, подумайте, как бы вы это написали, и сколько времени у вас это займет?

Comments

[avva.livejournal.com]

По-моему, нормально (время в смысле). И решение хорошее. У меня примерно столько же времени заняло (и тоже на всякую ерунду значительная часть его ушла - так ведь всегда бывает). Но написал я немного по-другому (тоже на Питоне): я тоже пользуюсь RPN и стеком, но я рекурсивно пытаюсь вставлять операции. Т.е. если я начал со стека 1,5,6,7 то я попробую в каждое из 5 возможных мест вставить каждую из 4 возможных операций, немедленно проверю, законно ли это с точки зрения кол-ва аргументов, и заодно не нашел ли я решение, а потом рекурсивно вызову себя. Эта функция вызывается со всеми возможными перестановками 1,5,6,7 плюс распределений знаков по ним.

Это заметно менее эффективно, чем ваш вариант, потому что много раз проходит через одни и те же варианты, зато код получается несколько проще. Ну и работает тоже очень быстро, конечно.

У меня примерно 25 минут на Perl'е ушло ^_^

[bakabaka.livejournal.com]

Но я "тупо" рекурсию и циклы использовал.
Параметры: текущее выражение и список оставшихся цифр.
(Если (вначале) текущее выражение пустое, перебрать цифры.)
В цикле перебрать все оставшиеся цифры, добавляя их к текущему выражению (со скобками), как слева, так и справа (можно было бы оптимизировать: не делать этого для "+" и "*").
Если нашли - "ура" и конец.
(Сейчас добавил счётчик вызовов функции: 6686 раз (2900, если с оптимизацией для "+" и "*").)