Algorithm to find a number, by asking questions to choose between 2 numbers
Budget: $30 – $250 USD
I need an algorithm to find a number A between 1 and 100 someone is thinking by asking the minimum number of questions.
In each round, the algorithm asks the user to choose between 2 numbers (X or Y?), and the user will choose the one that is closest to their target number. In the following round, the algorithm gives the user another pair of numbers to choose from (numbers can be completely different, or keep one of the numbers from before, whatever is most efficient).
A twist to this is that previously, the user has given another number B for a different question. A and B tend to be correlated, and we could assume that A follows a normal distribution with B as mean. This means that once we know B, we know that A is more likely to be close to B, but it is possible that it is not. Therefore, the algorithm should start either assuming A=B or assume that the number will be very close (B+10, B-10).
The algorithm should stop, when it thinks they know the number A with 2 points of accuracy.
The algorithm should be optimized to ask the minimum number of questions to find A.
Part of the work is to provide a way to prove the algorithm and do a couple of rounds to make sure that it works.
In each round, the algorithm asks the user to choose between 2 numbers (X or Y?), and the user will choose the one that is closest to their target number. In the following round, the algorithm gives the user another pair of numbers to choose from (numbers can be completely different, or keep one of the numbers from before, whatever is most efficient).
A twist to this is that previously, the user has given another number B for a different question. A and B tend to be correlated, and we could assume that A follows a normal distribution with B as mean. This means that once we know B, we know that A is more likely to be close to B, but it is possible that it is not. Therefore, the algorithm should start either assuming A=B or assume that the number will be very close (B+10, B-10).
The algorithm should stop, when it thinks they know the number A with 2 points of accuracy.
The algorithm should be optimized to ask the minimum number of questions to find A.
Part of the work is to provide a way to prove the algorithm and do a couple of rounds to make sure that it works.
Related categories:
C Programming
Business, Accounting, Human Resources & Legal
Algorithm
C++ Programming
Mathematics