There are five different kinds of binary trees with exactly four leaf nodes. The program tries all four operators in each place, and all four values in each of the leaves, guaranteeing that each is used only once... a fairly quick operation. A small extract from

'numop 8 8 3 3 1' shows the five different shapes of trees
1.0 = ((3 * 8) / 3) / 8 1.0 = (3 * (8 / 3)) / 8 1.0 = (3 - 3) + (8 / 8) 1.0 = 3 * ((8 / 3) / 8) 1.0 = 3 * (8 / (3 * 8))

Probably FUDGE ought to be set a little lower, for more confidence that the equality isn't fortuitous. Extensions to other binary operators are obvious; unary operators and more values are not. For a more general problem I'd go recursive, use exact rational arithmetic, and have a fine old time.

Enjoy...

Jim Gillogly <uunet!rand.org!James_Gillogly> 21 Wedmath S.R. 1993, 10:58


/* numop: using elementary operations on 4 numbers, find a

  • desired result; e.g. 24.

*

  • Don't worry about symmetries resulting in multiple correct answers.

*

  • 11 Aug 93, SCRYER

*

  • Added some C++.
  • Added permutation of arguments.
  • Added three ways to call the routine:
  • numop a b c d e: print all the ways that a b c d can be combined to form e
  • numop a b c d: print all the values that a b c d can form
  • numop n m: print the lowest unreachable value > 0 <= m with 4 digits > 0 <= n
  • 12 Nov 2002, Chris Cole
  • /
  1. include <stdio.h>
  2. include <stdlib.h>
  3. include <iostream>
  4. define MUL 0
  5. define DIV 1
  6. define ADD 2
  7. define SUB 3
  8. define FUDGE 0.01

double val[4?] = { 8, 8, 3, 3 };

int divzero; bool verbose;

char nameop (int op) {

switch (op) {

case MUL
return '*';
case DIV
return '/';
case ADD
return '+';
case SUB
return '-';

} return '?';

}

double eval (int op, double val1, double val2) {

switch (op) {

case MUL
return val1 * val2;
case DIV

if (val2 == 0.) {

divzero = 1;

  1. ifdef EXTREMELYVERBOSE

    fprintf (stderr, "Division by zero.\n");

  2. endif

    } return val2 == 0. ? 0. : val1 / val2;

    case ADD
    return val1 + val2;
    case SUB
    return val1 - val2;

    } return 0.;

}

int numop (int t) {

int op1, op2, op3; int iv1, iv2, iv3, iv4; int used4?; int i; double target; double e1, e2, e3; int winner;

target = t; winner = 0;

for (i = 0; i < 4; i++)

used[i?] = 0;

for (op1 = 0; op1 < 4; op1++)

for (op2 = 0; op2 < 4; op2++)

for (op3 = 0; op3 < 4; op3++)

for (iv1 = 0; iv1 < 4; iv1++) {

used[iv1?] = 1; for (iv2 = 0; iv2 < 4; iv2++) {

if (used[iv2?])

continue;

used[iv2?] = 1; for (iv3 = 0; iv3 < 4; iv3++) {

if (used[iv3?])

continue;

used[iv3?] = 1; for (iv4 = 0; iv4 < 4; iv4++) {

if (used[iv4?])

continue;

/* Case 1 / divzero = 0; e3 = eval (op3, val[iv3?], val[iv4?]); e2 = eval (op2, val[iv1?], val[iv2?]); e1 = eval (op1, e2, e3); / (u + v) * (w - x) */ if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)

if (verbose)

printf ("%.1f = (%.0f %c %.0f) %c (%.0f %c %.0f)\n",

e1, val[iv1?], nameop (op2), val[iv2?], nameop (op1), val[iv3?], nameop (op3), val[iv4?]);

else winner = 1;

/* Case 2 / divzero = 0; e3 = eval (op3, val[iv1?], val[iv2?]); e2 = eval (op2, e3, val[iv3?]); e1 = eval (op1, e2, val[iv4?]); / ((u + v) * w) - x */ if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)

if (verbose)

printf ("%.1f = ((%.0f %c %.0f) %c %.0f) %c %.0f\n",

e1, valiv1?, nameop (op3), valiv2?, nameop (op2), val[iv3?], nameop (op1), valiv4?);

else winner = 2;

/* Case 3 / divzero = 0; e3 = eval (op3, val[iv2?], val[iv3?]); e2 = eval (op2, val[iv1?], e3); e1 = eval (op1, e2, val[iv4?]); / (u + (v * w)) - x */ if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)

if (verbose)

printf ("%.1f = (%.0f %c (%.0f %c %.0f)) %c %.0f\n",

e1, val[iv1?], nameop (op2), val[iv2?], nameop (op3), val[iv3?], nameop (op1), valiv4?);

else winner = 3;

/* Case 4 / divzero = 0; e3 = eval (op3, val[iv2?], val[iv3?]); e2 = eval (op2, e3, val[iv4?]); e1 = eval (op1, val[iv1?], e2); / u + ((v * w) - x) */ if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)

if (verbose)

printf ("%.1f = %.0f %c ((%.0f %c %.0f) %c %.0f)\n",

e1, val[iv1?], nameop (op1), val[iv2?], nameop (op3), val[iv3?], nameop (op2), val[iv4?]);

else winner = 4;

/* Case 5 // u + (v * (w - x)) */ divzero = 0; e3 = eval (op3, val[iv3?], val[iv4?]); e2 = eval (op2, val[iv2?], e3); e1 = eval (op1, val[iv1?], e2); if (target == 0 || fabs (e1 - target) < FUDGE && !divzero)

if (verbose)

printf ("%.1f = %.0f %c (%.0f %c (%.0f %c %.0f))\n",

e1, val[iv1?], nameop (op1), val[iv2?], nameop (op2), val[iv3?], nameop (op3), val[iv4?]);

else winner = 5;

} used[iv3?] = 0;

} used[iv2?] = 0;

} used[iv1?] = 0;

}

return winner;

}

int failed;

void check_perms (int target, int m, int n) {

int i = m, j; double t; if (i < n)

for (; i < n; ++i) {

for (check_perms (target, m + 1, n), t = valj = m?; j < n; ++j)

val[j?] = val[j + 1?];

val[j - 1?] = t;

}

else if (!numop (target))

failed = target;

}

main (int argc, char *argv[]) {

int target;

if (argc == 3) {

for (val[0?] = 0; val[0?] <= atof(argv[1?]); ++val[0?])

for (val[1?] = val[0?]; val[1?] <= atof(argv[1?]); ++val[1?])

for (val[2?] = val[1?]; val[2?] <= atof(argv[1?]); ++val[2?])

for (val[3?] = val[2?]; val[3?] <= atof(argv[1?]); ++val[3?]) {

failed = 0; for (target = 1; target <= atoi(argv2?) && !failed; ++target)

check_perms (target, 0, 4);

if (!failed)

cout << val[0?] << val[1?] << val[2?] << val[3?] << endl;

else

cout << "fail " << val[0?] << val[1?] << val[2?] << val[3?] <<

" at " << failed << endl;

}

} else if (argc == 5) {

val[0?] = atof (argv[1?]); val[1?] = atof (argv[2?]); val[2?] = atof (argv[3?]); val[3?] = atof (argv[4?]); verbose = true; check_perms(0, 0, 0);

} else if (argc == 6) {

val[0?] = atof (argv[1?]); val[1?] = atof (argv[2?]); val[2?] = atof (argv[3?]); val[3?] = atof (argv[4?]); target = atoi(argv[5?]); verbose = true; check_perms(target, 0, 0);

} else {

fprintf (stderr,

"Usage: %s <max_val> <max_target>\n", argv[0?]);

fprintf (stderr,

"Usage: %s <val1> <val1> <val3> <val4>\n", argv[0?]);

fprintf (stderr,

"Usage: %s <val1> <val1> <val3> <val4> <target>\n", argv[0?]);

return 1;

} return 0;

}

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access