lmarkov

Catalan Number

Dec 10th, 2012
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.53 KB | None | 0 0
  1. /*
  2.  * Write a program to calculate the Nth Catalan number by given N.
  3.  *
  4.  *  3 methods included
  5. */
  6.  
  7. using System;
  8. using System.Diagnostics;
  9. using System.Numerics;
  10.  
  11. class CatalanNumber
  12. {
  13.     static void Main()
  14.     {
  15.         while (true)
  16.         {
  17.             Stopwatch stopWatch = new Stopwatch();
  18.             BigInteger numberN = InputData();
  19.            
  20.             stopWatch.Start();
  21.  
  22.             // FASTEST
  23.             // for N = 100000 , runtime: 00:00:12.90
  24.             BigInteger catalanNumberN = 1;
  25.             BigInteger result = 0;
  26.             for (int i = 1; i <= numberN; i++)
  27.             {
  28.                 catalanNumberN = (2 * ((2 * i) - 1)) * catalanNumberN / (i + 1);
  29.             }
  30.  
  31.  
  32.             //MEDIUM SPEED
  33.             // for N = 100000 , runtime: 00:01:52.81
  34.             //BigInteger divident = CalculateFactorial(2 * numberN);
  35.             //BigInteger nFactorial = CalculateFactorial(numberN);
  36.             //BigInteger nFactorialPlus1 = nFactorial * (numberN + 1);
  37.             //BigInteger divider = nFactorial * nFactorialPlus1;
  38.             //BigInteger catalanNumberN = divident / divider;
  39.  
  40.             // SLOWEST METHOD
  41.             //for N = 100000 , runtime: 00:02:09.23  
  42.             //BigInteger catalanNumberN = CalculateFactorial(2 * numberN) / (CalculateFactorial(numberN + 1) * CalculateFactorial(numberN));            
  43.  
  44.             stopWatch.Stop();
  45.             Console.WriteLine("The {0} Catalan number is {1}" + Environment.NewLine, numberN, catalanNumberN);
  46.            
  47.             TimeSpan ts = stopWatch.Elapsed;
  48.             string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
  49.             Console.WriteLine("runtime: " + elapsedTime + Environment.NewLine);
  50.         }
  51.     }
  52.  
  53.     static BigInteger InputData()
  54.     {
  55.         BigInteger numberN;
  56.         string invalidInput = "Please enter a valid number greater than or equal to 0!" + Environment.NewLine;
  57.         Console.WriteLine("Enter a value for N: ");
  58.         while (!(BigInteger.TryParse(Console.ReadLine(), out numberN) && numberN >= 0))
  59.         {
  60.             Console.WriteLine(invalidInput);
  61.             Console.WriteLine("Enter a value for N: ");
  62.         }
  63.         return numberN;
  64.     }
  65.  
  66.     static BigInteger CalculateFactorial(BigInteger numberN)
  67.     {
  68.         BigInteger factorial = 1;
  69.         for (BigInteger i = 1; i <= numberN; i++)
  70.         {            
  71.             factorial = factorial * i;
  72.         }
  73.         return factorial;
  74.     }
  75. }
Advertisement
Add Comment
Please, Sign In to add comment