Using a sequence of operations from N to get the value of M

Question

This is homework! Please do not give me a solution, just a hint!

The task is to apply a sequence of operations from N to find M. Input - 6 numbers: A, B, C, D, N, M, where A corresponds to additions, B to subtraction, C to multiplication, and D to division . Here is an example:

10 4 2 3 21 32 

We will try to find the number 32, starting at 21 using those operations

 ADD 10 // "A" number SUB 4 // "B" number MUL By 2 // "C" number DIV By 3 // "D" number 

Possible answer:

 32 = ((((21 * 2) + 10) - 4) / 3) * 2 

the program displays 1 , if otherwise there is a sequence of actions 0 . Can someone give me a hint how to solve this?

Answer 1

You can make some kind of graph, but with four numbers and four possible operations to perform with these numbers there will be 16 branches on each node, and it will probably work quickly.

Answer 2

It seems that the biggest problem will be to determine if there is an answer. If GCD (A, B) is 1, then the answer is 1, because it means that there is a sequence of operations ADD A and SUB B that increases or decreases the value of the source by 1, so if you repeat this sequence enough times, you get ANY number from ANY other number. If it is not 1, and your DIV operation rounds the value, do a search if you can reach the target mod GCD(A,B) value using all 4 operations. This value should be quite small, so you can perform the aforementioned graph search by cutting off the result of the next step through mod LCM(A,B) AND equal branches that produce the same value modulo GCD (A, B). So, if you reach a single value equal to target mod GCD(A,B) , you can print 1, if none have been reached, print 0. The graphical move will eventually stop, since in the interval (0, LCM(A,B)-1) there is a fixed number of different values, and if correctly programmed, it will satisfy the requirements of both memory and time.

Yes, you need to take care of special situations, such as A = 0, B = 0, C = 1 or D = 1. For example, the sequence 0 3 1 3 81 5 will lead to 1, and 0 3 1 3 81 29 to 0. Edit: changed the module in the crop and placed the correct abbreviations A and B.

Answer 3

you can solve it with brute force if you use polymorphic functors for operations and just keep trying. you will need a good break criterion (for example, limit the number of operations used to 10 or something similar).

answer on functors: C ++ Functors - and their use

Polymorphism

must be found on the internet.

Example:

 class operation { public: enum TYPE { ADD = 0, SUB }; virtual int operator()(int left, int right) = 0; } class add : public operation { public: int operator()(int left, int right) { return left + right; } } class sub : public operation { public: int operator()(int left, int right) { return left - right; } } int main() { std::vector<operation*> foo; foo[0] = new add(); foo[1] = new sub(); foo[2] = new add(); int bar = 21; for (auto& op : foo) { bar = (*op)(bar, 2); std::cout << bar << std::endl; } } 

these classes are functors. Using such constructs, you can process algorithms or basic operational variables, such as a variable that you can assign or shuffle or randomize or whatever. since they all have the same interface inherited from the operation, they all know what () means, but they act differently.

the presence of such things allows you to store and return used operations and a simple cycle through permutations. while you are doing this, you should know that you must limit the number of possible combinations of maxumum operations for each set, or you will encounter infinite loops / recursions.

Answer 4

This answer is based on the accepted answer to this question on math.stackexchange:

https://math.stackexchange.com/questions/354625/how-to-compose-given-add-sub-mult-div-functions-to-map-an-integer-m-to-n

Given the six inputs (a, b, c, d, M, N)

• a: the number we can add
• b: the number we can subtract
• c: the number we can multiply
• d: the number we can divide
• M: start number
• N: end number

I assume that they are all integers, and a> 0, b> 0, c can be positive or negative, d is not equal to 0.

Then there is a way to convert M to N by applying add, sub, mult, div,

if and only if

there are integers m and n such that

So, the first thing to do is find the greatest common factor a and b (I recommend the Euclidean algorithm as described here . Call gcd "g".

The mod is applied to both sides to verify equality.

So, start making a list of possible values ​​that the left side can take for different m:

(M * (Pow (c, m)))% g

Then start making a list of possible values ​​that the right side may have for different n:

(N * (Pow (d, n)))% g

You want to start m and n to zero and start your way up.

In the end, both sides will begin to repeat themselves, since you are using mod.

If at any time you find a match, that is, the left side is equal to some right side, return 1.

Otherwise, if you have exhausted all the values ​​of the left hand and the right values, without coincidence, return 0.

Note that the mod (%) operator in C ++ behaves differently for negative numbers than the math described above. You will need to adjust the results of the mod always in the range 0 <= result <g

Finally, this only works in cases where division acts in accordance with ordinary mathematics, i.e. 3/2 = 1.5 etc.

In your case, you need to slightly modify the formula to accept integer division. In particular, the right side of the equation deals with division. Be that as it may, how the following equation works, we can make a difference, move it to the other side and multiply.

x / 3 = 1

x = 1 * 3

You will need to allow rhs to take multiple values ​​each time you power on d. For example, in the above example, we need to allow 1 * 3 equal to 3.4 or 5.

So, if d = 3, then

• Pow (d, 0) = 1.
• Pow (d, 1) = 3 or 4 or 5.
• Pow (d, 2) = 9 or 10 or 11 or 12 or 13 or 14 or 15 or 16 or 17

You will see that 9 = 3 * 3, 12 = 4 * 3 and 15 = 5 * 3. Thus, the template should be easily replicated even for different values ​​of d.

I have not tried this last part, so I'm not quite sure that this covers all cases of integer division exactly, but I think it is, although it is rather tedious.