void Solve(Expression[] values)
{
if (values.Length == 1)
{
if (values[0].Succeed())
{
bool dup = false; string exp = values[0].Exp(); // Remove duplication
foreach (string s in solutions)
{
if (s == exp)
{
dup = true;
break;
}
} if (!dup)
{
solutions.Add(exp);
Console.WriteLine("{0}: {1} \t {2}", solutions.Count, exp, values[0].ToString());
}
} return;
} for (int i = 0; i < values.Length; i++)
for (int j = i + 1; j < values.Length; j++)
{
Solve1(values, i, j, values[i].Add(values[j])); Solve1(values, i, j, values[i].Sub(values[j]));
Solve1(values, j, i, values[j].Sub(values[i])); Solve1(values, i, j, values[i].Mul(values[j])); Solve1(values, i, j, values[i].Div(values[j]));
Solve1(values, j, i, values[j].Div(values[i]));
}
} static void Solve(int v1, int v2, int v3, int v4)
{
Expression[] values = new Expression[4]; values[0] = new Expression(v1);
values[1] = new Expression(v2);
values[2] = new Expression(v3);
values[3] = new Expression(v4); Console.WriteLine("{0} {1} {2} {3} ->", v1, v2, v3, v4); SixtyFour solver = new SixtyFour(); solver.Solve(values); Console.WriteLine();
} [STAThread]
static void Main(string[] args)
{
Solve(3, 8, 8, 8);
Solve(3, 3, 8, 8);
Solve(5, 6, 6, 7);
Solve(4, 5, 8, 7);
}
}
}
3 8 8 8 ->3 3 8 8 ->
1: 8*8+3-3 (3-3)+(8*8)
2: 8*(8+3-3) 8*(8+(3-3))
3: 8*3*3-8 (8*(3*3))-8
4: 8*8*3/3 (3/3)*(8*8)5 6 6 7 ->4 5 8 7 ->
1: 8*(7+5-4) 8*(7+(5-4))
2: 8*4*(7-5) (4*8)*(7-5)
private bool fSearchExpression(double[] ANumbers, string[] AExpressions,
int ALevel, int ADest, List<string> AResults)
{
bool Result = false;
if ((ALevel <= 1) && (Math.Abs(ANumbers[0] - ADest) <= Precision))
{
AResults.Add(AExpressions[0]);
return true;
}
for (int i = 0; i < ALevel; i++)
for (int j = i + 1; j < ALevel; j++)
{
double A = ANumbers[i];
double B = ANumbers[j];
ANumbers[j] = ANumbers[ALevel - 1];
string vExpA = AExpressions[i];
string vExpB = AExpressions[j];
AExpressions[j] = AExpressions[ALevel - 1];
AExpressions[i] = '(' + vExpA + '+' + vExpB + ')';
ANumbers[i] = A + B;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
AExpressions[i] = '(' + vExpA + '-' + vExpB + ')';
ANumbers[i] = A - B;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
AExpressions[i] = '(' + vExpB + '-' + vExpA + ')';
ANumbers[i] = B - A;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
AExpressions[i] = '(' + vExpA + '*' + vExpB + ')';
ANumbers[i] = A * B;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
if (B != 0)
{
AExpressions[i] = '(' + vExpA + '/' + vExpB + ')';
ANumbers[i] = A / B;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
}
if (A != 0)
{
AExpressions[i] = '(' + vExpB + '/' + vExpA + ')';
ANumbers[i] = B / A;
if (fSearchExpression(ANumbers, AExpressions,
ALevel - 1, ADest, AResults)) Result = true;
}
ANumbers[i] = A;
ANumbers[j] = B;
AExpressions[i] = vExpA;
AExpressions[j] = vExpB;
}
return Result;
}private bool SearchExpression(List<string> AResults, int ADest, params int[] ANumbers)
{
double[] vNumbers = new double[ANumbers.Length];
string[] vExpressions = new string[ANumbers.Length];
for (int i = 0; i < ANumbers.Length; i++)
{
vNumbers[i] = ANumbers[i];
vExpressions[i] = ANumbers[i].ToString();
}
return fSearchExpression(vNumbers, vExpressions, ANumbers.Length, ADest, AResults);
}private void button1_Click(object sender, EventArgs e)
{
List<string> vExpressions = new List<string>();
SearchExpression(vExpressions, 64, 4, 5, 8, 7);
foreach (string vExpression in vExpressions)
Console.WriteLine(vExpression + "\r\n");
}表达式不够美观