I have a problem with an assignment. In this assignment I have to create a program which needs to calculate how many different possibilities are there to get from number a to b. To get from a to b you can only D(double) the value or I(increment) the value.
So you can have a=3 and b=14. This will get you 8 different possibilities:
DDII = 3*2*2+2 = 14
DID = ((3*2)+1)*2 =14
DIIIIIIII = 3*2+8 =14
IDIIIIII=(3+1)*2+6=14
IIDIIII =(3+2)*2+4=14
IIIDII =(3+3)*2+2=14
IIIID =(3+4)*2+0=14
IIIIIIIIIII=3+11=14
In my current solution I’m using a breadth-first search (BFS) to calculate all the possibilities only this is very slow, because sometimes there are many possibilities and with BFS you will go through all of them. So for example if want to calculate a=10 and b=1000, this will give me 74,116,423 possibilities.
This is almost impossible to calculate with my computer and the solution I’m currently using.
What is the proper approach to take to solve this problem? Being an assignment I am not looking for the answer, I need an algorithm or other push in the right direction.
2
For example for the number of ways to go from 10 to 1000:
Let A (N) = number of ways to get from N to 1000. Calculate and store A (N) for N = 1000, 999, …, 10.
For N = 1000, 999, …, 501, A (N) = 1 because you cannot double the number.
For N ≤ 500, A (N) = A (2N) + A (N + 1), because you can either double and get from 2N to 1000, or increment and go from N+1 to 1000.
1