What's Here?
- Members: 300,419
- Replies: 826,024
- Topics: 137,455
- Snippets: 4,419
- Tutorials: 1,148
- Total Online: 1,505
- Members: 89
- Guests: 1,416
|
just a small snippet to compute the binomial Coefficient nCk..
mathematically to compute the binomial coefficient
ncK = n!/k!(n-k)! but if n is too large, computing it will be very inefficient, instead there's a recursive formula
nCk = (n-1)C(k-1)+(n-1)Ck, so this can be used in a dynamic programming approach...also to speed things up, binomial Coefficients have this identity that nCk = nC(n-k), so we can use this to minimize the number of terms computed
|
Submitted By: mostyfriedman
|
|
|
Rating:
|
|
Views: 258 |
Language: Java
|
|
Last Modified: July 18, 2009 |
Snippet
public static long binomialCoefficient(int n, int k) { if(n - k == 1 || k == 1) return n; long [][] b = new long[n+1][n-k+1]; b[0][0] = 1; for(int i = 1; i < b.length; i++) { for(int j = 0; j < b[i].length; j++) { if(i == j || j == 0) b[i][j] = 1; else if(j == 1 || i - j == 1) b[i][j] = i; else b[i][j] = b[i-1][j-1] + b[i-1][j]; } } return b[n][n-k]; }
Copy & Paste
|
|
|
|
Forum Index:
Programming Help |
C and C++ |
VB6 |
Java |
VB.NET |
C# |
ASP.NET |
PHP |
ColdFusion |
Perl and Python |
Ruby |
Databases |
Other Languages |
Game Programming |
Mobile Development |
Software Development |
Computer Science |
Industry News |
Programming Tutorials |
C++ Tutorials |
Visual Basic Tutorials |
Java Tutorials |
VB.NET Tutorials |
C# Tutorials |
Linux Tutorials |
PHP Tutorials |
ColdFusion Tutorials |
Windows Tutorials |
HTML/JavaScript Tutorials |
CSS Tutorials |
Flash Tutorials |
Web Promotion Tutorials |
Graphic Design & Photoshop Tutorials |
Software Development Tutorials |
Database Tutorials |
Other Language Tutorials |
ASP.NET Tutorials |
Game Programming Tutorials |
WPF & Silverlight Tutorials |
| 
