hmm…..

Project Euler problem 6~

  1: class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The difference between the sum of the squares of the first one hundred natural numbers and the square of the sum");
  8:             sw.Start();
  9:             var num1 = BruteForceWay(100);
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("Plain loop addition brute force way(Linq aggregate)(tick:{0}): {1}", sw.ElapsedTicks, num1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("The difference between the sum of the squares of the first one hundred natural numbers and the square of the sum");
 16:             sw.Start();
 17:             var num3 = BruteForceWay2(100);
 18:             sw.Stop();
 19:             Console.WriteLine(string.Format("Plain loop addition brute force way(for loop)(tick:{0}): {1}", sw.ElapsedTicks, num3));
 20:             
 21:             sw.Reset();
 22: 
 23:             Console.WriteLine("The difference between the sum of the squares of the first one hundred natural numbers and the square of the sum");
 24:             sw.Start();
 25:             var num2 = ArithmeticWay(100);
 26:             sw.Stop();
 27:             Console.WriteLine(string.Format("Smart Arithmetic Way(tick:{0}): {1}", sw.ElapsedTicks, num2));
 28: 
 29:             Console.WriteLine("Press any key to exit");
 30:             Console.ReadKey();
 31:         }
 32:         /// <summary>
 33:         /// the summation formula is
 34:         /// (n/2)(2a+(n-1)d)
 35:         /// n = number of terms in the sequence
 36:         /// d = common difference
 37:         /// a = first term
 38:         /// eg 1+2+3+4+...+100=5050
 39:         /// (100/2)(2*1+(100-1)*1)
 40:         /// </summary>
 41:         /// <returns></returns>
 42:         static int BruteForceWay(int x)
 43:         {
 44:             var sumSq = Enumerable.Range(1, x)
 45:                 .Aggregate((s, n) => s += n * n);
 46: 
 47:             var sqSum = x * (2 * 1 + (x - 1) * 1) / 2;
 48:             sqSum = sqSum * sqSum;
 49: 
 50:             return sqSum - sumSq;
 51:         }
 52: 
 53:         static int BruteForceWay2(int r)
 54:         {
 55:             int x = 0;
 56:             int y = 0;
 57:             int z = 0;
 58: 
 59:             for (x = 1; x <= r; x++)
 60:             {
 61:                 y += x * x;
 62:                 z += x;
 63:             }
 64: 
 65:             return z * z - y;
 66:         }
 67: 
 68:         /// <summary>
 69:         /// got the forumla from wikipedia, see: 
 70:         /// http://en.wikipedia.org/wiki/List_of_mathematical_series
 71:         /// 
 72:         /// (1+2+3+...+n) = n(n+1)/2
 73:         /// (1+2+3+...+n)^2 = n*n(n+1)(n+1)/4
 74:         /// (1^2+2^2+3^2+...+n^2) = n(n+1)(2n+1)/6
 75:         /// </summary>
 76:         /// <param name="x"></param>
 77:         /// <returns></returns>
 78:         static int ArithmeticWay(int x)
 79:         {
 80:             var sumSq = x * (x + 1) * (2 * x + 1) / 6;
 81: 
 82:             var sqSum = x * x * (x + 1) * (x + 1) / 4;
 83: 
 84:             return sqSum - sumSq;
 85:         }
 86:     }

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