If you start with $1 and, with each move, you can either double your money or add another $1, what is the smallest number of moves you have to make to get to exactly $200?
(write a program to calculate this)
My solution:
1 2 3 4 5 6 7 8 9 10 11 12 13
#include <iostream>
int main() {
int N,i; //The $200
std::cin>>N;
for(i=0; N!=1; ++i) { //i is the number of moves
if(!(N%2)) N>>=1; //when read forward it will be *2
else --N; //when read forward it will be +1
}
std::cout<<i;
return(0);
}
int main()
{
int total = 200;
int moves = 0;
while (total !=1)
{
if ((total%2) == 0)) total = total/2;
else total = total - 1;
moves++;
}
}
This comes up with 9 moves but I've no idea if it's the fastest way. It does seem to take most advantage of doubling, in that it uses the doubling 8 times and the addition only once.
I think it is the most efficient, as the most efficient will be that which uses as many doublings as possible to cover the distance fastest, but I can't put it into decent words just at the moment.
The way the question is worded makes me suspect that the idea is just to see if the coder spots that working back from 200 along the best path is far more efficient than starting at 1 and having to test all possible paths.