Correct Solution

Problem Statement:
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);
}
1
2
3
4
5
6
7
8
9
10
11
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.
@Moschops your solution is the same as mine.
They are not the same, his does not compile:

if ((total%2) == 0))
Last edited on
Ok fine. so after the correction of a truly minor error. Out programs are semantically the same. But is this the most efficient solution?
Last edited on
No, wait. Two additions. Not one.

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.
Last edited on
Topic archived. No new replies allowed.