Computer Science Canada "Pascal's Triangle" generator using "Binomial Theorem" |
| Author: | randint [ Sun Nov 18, 2012 11:45 am ] |
| Post subject: | "Pascal's Triangle" generator using "Binomial Theorem" |
One extension of my factorial program, using the formula (n choose k) = n! / ((n - k)! k!) [combinations] Generated by iteration as opposed to recursion due to reasons of "bad" computational complexity. |
|
| Author: | DemonWasp [ Sun Nov 18, 2012 1:03 pm ] |
| Post subject: | RE:"Pascal\'s Triangle" generator using "Binomial Theorem" |
This solution isn't any better than the recursive method. You're still recalculating 5! when you calculate 6!, even when you've previously calculated 5!. To truly do better, you need to add some storage: an array of BigIntegers. Then, when you compute factorial(n), if array(n) isn't null, then you can just return array(n). If it is null, then you can recursively compute factorial(n-1), multiply it by n, and store it in array(n). Then when you ask for 6!, it also calculates 5!, 4!, 3!, 2! and stores them in the array (note: you should put 1! in the array before you do any computation; that's your base case). When you ask for 5!, you already know the value. |
|