GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Java/DynamicProgramming/CatalanNumber.java at master · thisxulz/Java Expand file tree/ Copy pathCatalanNumber.javaMore file actions 60 lines (48 loc) · 1.72 KB / Copy pathCatalanNumber.javaFile metadata and controls60 lines (48 loc) · 1.72 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 package DynamicProgramming; /** * This file contains an implementation of finding the nth CATALAN NUMBER using dynamic programming * Wikipedia: https://en.wikipedia.org/wiki/Catalan_number * * Time Complexity: O(n^2) * Space Complexity: O(n) * * @author AMRITESH ANAND (https://github.com/amritesh19) */ import java.util.Scanner; public class CatalanNumber { /** * This method finds the nth Catalan number * * @param n input n which determines the nth Catalan number * n should be less than equal to 50 as 50th Catalan number is 6,533,841,209,031,609,592 * for n > 50, BigInteger class should be used instead long * * @return catalanArray[n] the nth Catalan number */ static long findNthCatalan(int n){ // Array to store the results of subproblems i.e Catalan numbers from [1...n-1] long catalanArray[] = new long[n + 1]; // Initialising C₀ = 1 and C₁ = 1 catalanArray[0] = 1; catalanArray[1] = 1; /** * The Catalan numbers satisfy the recurrence relation * C₀=1 and Cn = Σ (Ci * Cn-1-i), i = 0 to n-1 , n > 0 */ for(int i = 2; i <= n; i++){ catalanArray[i] = 0; for(int j = 0; j < i; j++){ catalanArray[i] += catalanArray[j] * catalanArray[i - j - 1]; } } return catalanArray[n]; } // Main method public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter the number n to find nth Catalan number (n <= 50)"); int n = sc.nextInt(); System.out.println(n + "th Catalan number is " + findNthCatalan(n)); sc.close(); } } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |