Windows Phone 7 Series

windows phone 7 series

Project Euler problem 15~

  1: class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The number of routes in a 20×20 grid");
  8:             sw.Start();
  9:             var sum1 = Explorer(20);
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("Pascal's Triangle brute force way(tick:{0}): {1}", sw.ElapsedTicks, sum1));
 12:             
 13:             Console.WriteLine("Press any key to exit");
 14:             Console.ReadKey();
 15:         }
 16:         
 17:         /// <summary>
 18:         /// http://mathforum.org/advanced/robertd/manhattan.html
 19:         /// </summary>
 20:         /// <param name="bound"></param>
 21:         /// <returns></returns>
 22:         static long Explorer(int bound)
 23:         {
 24:             var map = new long[bound + 1, bound + 1];
 25: 
 26:             // 1. populate edge row and columns
 27:             for (int i = 0; i <= bound; i++)
 28:             {
 29:                 map[i, bound] = 1;
 30:                 map[bound, i] = 1;
 31:             }
 32: 
 33:             // 2. starting 2nd last column to populate values in each cell(pascal triangle value)
 34:             for (int col = bound - 1; col >= 0; col--)
 35:             {
 36:                 for (int row = bound - 1; row >= 0; row--)
 37:                 {
 38:                     map[row, col] = map[row + 1, col] + map[row, col + 1];
 39:                 }
 40:             }
 41: 
 42:             return map[0, 0];
 43:         }
 44:     }

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