Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 "Pascal's Triangle" generator using "Binomial Theorem"
Index -> Programming, Java -> Java Submissions
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
randint




PostPosted: 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.



Pascals_Triangle.java
 Description:
Pascal's Triangle generated by the Binomial Theorem

Download
 Filename:  Pascals_Triangle.java
 Filesize:  1.47 KB
 Downloaded:  542 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
DemonWasp




PostPosted: 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.
Display posts from previous:   
   Index -> Programming, Java -> Java Submissions
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 2 Posts ]
Jump to:   


Style:  
Search: