Precise statement of restrictions (enumerating these may give you a bit of a hint): You're allowed to use these operators: + - * / √ !
I did this, and then I figured out that if you're allowed to use the floor function as well, you can fulfill this task for any n ≥ 1. If [x] denotes the floor of x, then I'll demonstrate with 56:
√56 is somewhat less than 8. √√56 is somewhat less than 3. √√√56 is somewhat less than 2. Then [√√√56] = 1. Thus, we can have: ([√√√56]+[√√√56]+[√√√56])! = 3! = 6.
The expression to find "number of times you'll have to take square root of n" is slightly interesting: we want to take k square roots and end up with something less than 2, so n^(1/2^k) < 2, or n < 2^(2^k), so k > log_2(log_2(n)).
For the lazy, solutions are at http://pastebin.com/XJZTFGHP
A few different solutions: http://pastebin.com/Mf6ZmhfA
No factorial is applied on a non integer intermediate result indeed, but if the intermediate result "becomes integer again", factorial are tried.
For example, if a candidate is (1/2) * 3 * 4 + 5, then the algorithm won't try to compute any factorial of (1/2) * 3 = 1.5, but it will consider (1/2) * 3 * 4 = 6.0 as integer and try the factorial on 6.
http://blog.boyet.com/blog/pcplus/pcplus-297-arithmetic-with...
As usual, well explained and interesting.
I had to solve this version of the problem once upon a time in a programming competition. I approached it slightly differently than this article; I implemented a RPN stack machine evaluator, and a recursive routine which permuted first over operators, then operands; the core routine looked like this:
static int FindSolutions(int[] numbers, int numberIndex, int stackDepth)
{
int result = 0;
if (stackDepth == 1)
if (Evaluate(g_program.Program) == g_target)
++result;
// Try the operators (all are binary here)
if (stackDepth > 1)
{
for (OpCode opCode = OpCode.Add; opCode <= OpCode.Div; ++opCode)
{
g_program.Push(opCode);
result += FindSolutions(numbers, numberIndex, stackDepth - 1);
g_program.Pop();
}
}
if (numberIndex < numbers.Length)
{
// Try each number
for (int i = numberIndex; i < numbers.Length; ++i)
{
Swap(numbers, numberIndex, i);
g_program.Push(numbers[numberIndex]);
result += FindSolutions(numbers, numberIndex + 1, stackDepth + 1);
g_program.Pop();
Swap(numbers, numberIndex, i);
}
// Try without the number
result += FindSolutions(numbers, numberIndex + 1, stackDepth);
}
return result;
}