lawl~

Project Euler problem 26~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The longest recurring cycle in its decimal fraction part.");
  8:             sw.Start();
  9:             var sum1 = test1();
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("loop + HashSet + long division algorithm(tick:{0}): {1}", sw.ElapsedTicks, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             sw.Start();
 16:             var sum2 = test2();
 17:             sw.Stop();
 18:             Console.WriteLine(string.Format("optimized version of test1(tick:{0}): {1}", sw.ElapsedTicks, sum2));
 19: 
 20:             Console.WriteLine("Press any key to exit");
 21:             Console.ReadKey();
 22:         }
 23: 
 24:         /// <summary>
 25:         /// using the remainder as indicator(long division algorithm)
 26:         /// add the remainder to HashSet(only allow unique values),
 27:         /// if there are duplicate(the Add will return false), then we know the chain has ended
 28:         /// iterate through all the number and find out the longest chain and return the number
 29:         /// </summary>
 30:         /// <returns></returns>
 31:         static int test1()
 32:         {
 33:             var num = 0;
 34:             var master = 10;
 35:             var set = new HashSet<int>();
 36:             var longest_count = 0;
 37:             var longest_num = 0;
 38: 
 39:             for (int i = 2; i < 1000; i++)
 40:             {
 41:                 num = i > 100 ? 1000 : i > 10 ? 100 : 10;
 42:                 set.Clear();
 43:                 do
 44:                 {
 45:                     num = num % i;
 46:                     num *= master;
 47:                 } while (set.Add(num));
 48: 
 49:                 if (set.Count >= longest_count)
 50:                 {
 51:                     longest_num = i;
 52:                     longest_count = set.Count;
 53:                 }
 54:             }
 55:             return longest_num;
 56:         }
 57: 
 58:         /// <summary>
 59:         /// the optimized version of test1(), with the given properties
 60:         /// 1. Since the remainder has to be a unique number in a chain, so there are only
 61:         ///    n-1 possible numbers for number n. E.g. for 1/7 the longest chain possible is 6
 62:         /// 2. A fraction in lowest terms with a prime denominator other than 2 or 5 (i.e. coprime to 10) 
 63:         ///    always produces a repeating decimal.
 64:         ///    see. http://en.wikipedia.org/wiki/Recurring_decimal#Fractions_with_prime_denominators
 65:         ///    with this, there are definitely numbers under 1000 that can have chains with length of n-1
 66:         /// 3. Iterate the number in descending order, the first number with cycle length of n-1 would
 67:         ///    most likely to be the number with longest cycle
 68:         /// </summary>
 69:         /// <returns></returns>
 70:         static int test2()
 71:         {
 72:             var num = 0;
 73:             var master = 10;
 74:             var set = new HashSet<int>();
 75: 
 76:             for (int i = 999; i >= 2; i--)
 77:             {
 78:                 num = i > 100 ? 1000 : i > 10 ? 100 : 10;
 79:                 set.Clear();
 80:                 do
 81:                 {
 82:                     num = num % i;
 83:                     num *= master;
 84:                 } while (set.Add(num));
 85: 
 86:                 if (set.Count == i - 1)
 87:                 {
 88:                     return i;
 89:                 }
 90:             }
 91:             return 0;
 92:         }
 93:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s