using System; using System.Collections.Generic; namespace RandomNumber5To7 { class Program { static void Main(string[] args) { int[] results = new int[7]; for (int i = 0; i < 100; i++) { // Change to call RandomNumber1To7Old for a different algorithm int result = RandomNumber1To7(); results[result - 1]++; Console.WriteLine(result); } Console.WriteLine("=============================================="); foreach (int count in results) { Console.WriteLine(count); } Console.ReadLine(); } // This method is based on the theory that if we 'roll the five-sided dice' // five times, we can treat roll 1 as having values in range 1-5, roll 2 as having values // in the range 6-10 and so on. We can then decide which of the five 'rolls' we're going // to use with another roll of the dice, so we're actually picking a number between 1-125 // at random. We can increase this in powers of 5 by then 'rolling' our new 125-sided // dice 5 times, treating the first roll as 1-125, the second as 126-250 etc. This will // give us a random number in the range 1-625. We can then do the same thing with 5 625-sided // dice, giving us 3125 and so on. // Clearly, these are all powers of 5 (5^3 = 125, 5^4=625, 5^5=3125) // To give an exact value in the range 1-7 we need to be able to divide the final range // (1-625 or 1-3125) by 7 to give us 7 equal ranges with a equal possiblities of our random // value falling in each. Unfortunately this isn't possible because we need integral x and y // such that 5^x = 7 * y, which has no solution. // But we can use this method to randomize to an arbitrary level of accuracy. // Say we choose '3' as our 'level', so we generate random numbers between 1 and 5^3=125. // Actually the maths is easier if we treat this as 0 to 124 by subtracting 1. // We can then divide into buckets 0 to less than int(125/7), int(125/7) to less than int(2 * 125/7), // int(2 * 125/7) to less than int(3 * 125/7) // and so on up to int(6 * 125/7) to less than int(7 * 125/7)=125 // We can treat the first bucket as '1', the second as 2, up to 7, and get a 'random' // number 1-7. We can make this as accurate as we like by increasing the original level. static int RandomNumber1To7() { // Set our level. E.g. level 3 corresponds to randomizing 1-125 as above int level = 5; // Calculate 5 ^ level, the upper bound of the randomization (e.g. 5 ^ 3 = 125 = maxValue) int maxValue = (int)Math.Pow(5.0, (double)(level)); // Genearate a random number Range 0 to maxValue - 1 int randomValueLessThenMaxValue = CalculateRandomSpread(level) - 1; double seventh = maxValue / 7.0; // Easiest is to think of this in terms of the example above: if our random // value is greater than or equal to int(6 * 125/7) then it's a 7, if greater than or equal to int(5 * 125/7) // but less than int(6 * 125/7) it's a 6 and so on. This is the same as saying the value // divided by 125/7 is a 7 if it's greater than or equal to 6, is a 6 if greater than or equal to 5 but less than 6 // and so on. // So if we divide it by 125/7 and apply the 'floor' function and add 1. int result = (int)Math.Floor(randomValueLessThenMaxValue / seventh) + 1; if (result > 7) System.Diagnostics.Debug.Assert(false); return result; } static int CalculateRandomSpread(int level) { // Roll a dice at the lowest level int total = RandomNumber1To5(); for (int i = 1; i < level; i++) { // Assign that roll to one of 5 buckets based on another random roll int random = RandomNumber1To5(); // Calculate what that means in terms of the value: if level is 2 // we call this with i=1 only, so multiply our new random number by 5 // giving us one of 0, 5, 10, 15, 20. We then add original number to // this (it's in range 1-5), giving us 1-25 as our range overall. total += (int)Math.Pow(5.0, (double)i) * (random - 1); } return total; } // Accurate, but can take infinite time // Put seven results in a list (values 1-7). Roll one five-sided dice for each // value in the list (so seven times). Work out the highest value // rolled and put all the values in the original list for which this number was // rolled into a new, hopefully shorter, list. Repeat the process for the shorter list // until you get down to just one value. static int RandomNumber1To7Old() { List<int> maxResults = new List<int>(); int[] values = {1,2,3,4,5,6,7}; maxResults.AddRange(values); do { maxResults = PickValuesFromList(maxResults); } while (maxResults.Count > 1); return maxResults[0]; } static List<int> PickValuesFromList(List<int> results) { List<int> maxResults = new List<int>(); int highestValue = 0; for (int counter = 0; counter < results.Count; counter++) { int thisResult = RandomNumber1To5(); if (thisResult == highestValue) maxResults.Add(results[counter]); else if (thisResult > highestValue) { maxResults = new List<int>(); maxResults.Add(results[counter]); highestValue = thisResult; } } return maxResults; } static int RandomNumber1To5() { System.Threading.Thread.Sleep(100); return new Random().Next(1, 6); } } }
Attempted Solutions to Random Numbers Problem
Leave a Comment »
No comments yet.
RSS feed for comments on this post. TrackBack URI

