Geek Answers Handbook

What is the best way to deal with the “all combinations” project?

I was assigned a school project in which I need to find as many integers as possible, using only the integers 2 3 4 and the operators + - * / % . Then I have to output integers with cout along with how I got this answer. For instance:

 cout << "2 + 3 - 4 = " << 2 + 3 - 4;

I can only use every integer in one cout statement, and there cannot be duplicate answers.

All the others seem to perform brute force (that is, copying and pasting the same operators and changing numbers and operators), but this hardly seems effective. I decided that I would try to go through each number and operator one by one and check if an answer was found, but I'm not sure that the easiest way to do this would be.

I suppose I could use nested loops, but there is still a problem with checking if an answer is found. I tried to save the answers in a vector, but could not pass the vector to a user-defined function that checks if a value exists in the vector.

+4
source share
3 answers

You can use map or hash_map from the standard template library (STL). These structures efficiently store key-value pairs. Read them before using them, but they can give you a good starting point. Hint. The integers you calculate are likely to make good keys.

+2
source

Assuming you can use each of the numbers in the set (2, 3, 4) only once when there are 3! ways to place these three numbers. Then there are 2 places for the sign, and you have only 5 characters (+ - * /%), so there are 5 * 5 = 25 ways to do this. So, you have only 3! * 25 expressions. How can you create a hash map where the key will be a number and the value will be an expression. If the hash map contains the key, you will already skip this expression.

0
source

You can try some metaprogramming as shown below. It has the advantage that C itself evaluates the expressions, rather than trying to make its own evaluator (and possibly wrong):

 #include <stdlib.h> #include <iostream> #include <fstream> using namespace std; int main (void) { int n1, n2, n3; const char *ops[] = {" + ", " - ", " * ", " / ", " % ", 0}; const char **op1, **op2; ofstream of; of.open ("prog2.cpp", ios::out); of << "#include <iostream>\n"; of << "using namespace std;\n"; of << "#define IXCOUNT 49\n\n"; of << "static int mkIdx (int tot) {\n"; of << " int ix = (IXCOUNT / 2) + tot;\n"; of << " if ((ix >= 0) && (ix < IXCOUNT)) return ix;\n"; of << " cout << \"Need more index space, " << "try \" << IXCOUNT + 1 + (ix - IXCOUNT) * 2 << \"\\n\";\n"; of << " return -1;\n"; of << "}\n\n"; of << "int main (void) {\n"; of << " int tot, ix, used[IXCOUNT];\n\n"; of << " for (ix = 0; ix < sizeof(used)/sizeof(*used); ix++)\n"; of << " used[ix] = 0;\n\n"; 

  for (n1 = 2; n1 <= 4; n1++) { for (n2 = 2; n2 <= 4; n2++) { if (n2 != n1) { for (n3 = 2; n3 <= 4; n3++) { if ((n3 != n1) && (n3 != n2)) { for (op1 = ops; *op1 != 0; op1++) { for (op2 = ops; *op2 != 0; op2++) { of << " tot = " << n1 << *op1 << n2 << *op2 << n3 << ";\n"; of << " if ((ix = mkIdx (tot)) < 0) return ix;\n"; of << " if (!used[ix])\n"; of << " cout << " << n1 << " << \"" << *op1 << "\" << " << n2 << " << \"" << *op2 << "\" << " << n3 << " << \" = \" << tot << \"\\n\";\n"; of << " used[ix] = 1;\n\n"; } } } } } } } of << " return 0;\n"; of << "}\n"; of.close(); system ("g++ -o prog2 prog2.cpp ; ./prog2"); return 0; }

This gives you:

 2 + 3 + 4 = 9 2 + 3 - 4 = 1 2 + 3 * 4 = 14 2 + 3 / 4 = 2 2 + 3 % 4 = 5 2 - 3 + 4 = 3 2 - 3 - 4 = -5 2 - 3 * 4 = -10 2 - 3 % 4 = -1 2 * 3 + 4 = 10 2 * 3 * 4 = 24 2 / 3 + 4 = 4 2 / 3 - 4 = -4 2 / 3 * 4 = 0 2 % 3 + 4 = 6 2 % 3 - 4 = -2 2 % 3 * 4 = 8 2 * 4 + 3 = 11 2 / 4 - 3 = -3

I am not quite sure of the wisdom to convey this as an appointment, however :-)

0
source

More articles:


All Articles