You are not logged in.
Generate random number 1..N , using D-sided dice
1) Logic problem: How to generate single uniform random number 1..N using fair D-sided dice in optimal way ( so that lowest number of rolls are needed on average) ?
2) math problem: How to calculate average needed rolls for any N and D ? What would be specific value for (N=4,D=6) or (N=20,D=6) ?
3) programming problem: Write function that will calculate averageRolls(N,D)=? It should return exact value as calculated in #2, not simulated or approximate value.
Obviously correct solution to Math problem depends on first finding correct optimal solution to Logic problem, and correct solution to Program problem depends on previously solving both Logic and Math problem. I can post further hints if needed . Actual reason why I posted this problem is because I find Program solution interesting ( since it may need slightly non-standard approach to transforming Math solution into program ). And reason I posted in this forum, instead of "Coder's corner' for example, is because it starts with solving logic problem.
Offline
To make it easier for those who would like to try Math or Programming problem, below is solution for Logic problem:
Below is pseudo code that returns random number based on desired N and dice sides D. It represent shorter version of more detailed steps explained in solution above. But is not solution to Programming problem, since this return actual random number, while solution to programming problem need to return average/expected rolls needed to get random number.
Last edited by gmn (2020-01-27 23:41:48)
Offline