Cassandra/WinPhone7/C#/and achievement unlocked~

Project Euler problem 25~(lawl a 3d triangle)

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The first term in the Fibonacci sequence to contain 1000 digits");
  8:             sw.Start();
  9:             var sum1 = test1(1000);
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("plain loop arithmetic way(ms:{0}): {1}", sw.ElapsedMilliseconds, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("Press any key to exit");
 16:             Console.ReadKey();
 17:         }
 18: 
 19:         /// <summary>
 20:         /// the while loop way of calculation Fibonacci sequence:
 21:         /// (since the number can get way too big, so int[] is used to
 22:         /// hold numbers for this problem)
 23:         /// 
 24:         /// var previous = 1;
 25:         /// var cur = 1;
 26:         /// var next = 0;
 27:         /// while (true)
 28:         /// {
 29:         ///     next = previous + cur;
 30:         ///     previous = cur;
 31:         ///     cur = next;
 32:         ///     Console.WriteLine(next);
 33:         /// }
 34:         /// </summary>
 35:         /// <param name="ceiling"></param>
 36:         /// <returns></returns>
 37:         static int test1(int ceiling)
 38:         {
 39:             var previous = new int[1000];
 40:             var next = new int[1000];
 41:             var cur = new int[1000];
 42:             previous[0] = 1; //f(1)
 43:             cur[0] = 1; //f(2)
 44:             var term = 2;
 45:             var len = 1;
 46:             var sum = 0;
 47:             var rem = 0;
 48:             var carry = 0;
 49:             var i = 0;
 50: 
 51:             while (len < ceiling)
 52:             {
 53:                 // next = previous + cur;
 54:                 for (i = 0; i < len; i++)
 55:                 {
 56:                     sum = previous[i] + cur[i] + carry;
 57:                     rem = sum > 9 ? sum - 10 : sum;
 58:                     carry = sum > 9 ? 1 : 0;
 59: 
 60:                     next[i] = rem;
 61:                     if (i == len - 1 && carry > 0)
 62:                     {
 63:                         next[i + 1] += carry;
 64:                         carry = 0;
 65:                         len++;
 66:                         break;
 67:                     }
 68:                 }
 69:                 
 70:                 //previous = cur;
 71:                 //cur = next;
 72:                 for (i = 0; i < len; i++)
 73:                 {
 74:                     previous[i] = cur[i];
 75:                     cur[i] = next[i];
 76:                 }
 77:                 term++;
 78:             }
 79:             return term;
 80:         }
 81:     }

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