Best way to generate pascal's triangle (of two mentioned ways)
I have an programming assignment in Java.
I have implemented it by making an nCr ( http://en.wikipedia.org/wiki/Combination ) function then using a double for loop to make the triangle by printing it out.
However, the assignment calls for a uneven 2d array to be created and then populated by adding the 开发者_运维技巧two numbers from the previous lines and then printing the array out.
I know I am going to have to do the assignment the way it asks, however I have a small feeling that (at least for small triangles anyway) that the approach I have implemented is better.
Which is the better approach?
I'd think the method called for by the assignment would be better. You're method requires a number of multiplications to calculate each of the elements of the triangle. This number will increase for each row of the triangle you need to calculate.
The assignment's method, however, requires a single addition for each element of the triangle.
If I understand your question, you are trying to compare two approaches to generating Pascal's triangle:
- By running an
nCr
function to populate each cell of the triangle. - By generating the triangle in one pass by filling in each cell by a simple addition.
The second approach seems hands-down better. Am I missing something? Even if you use memoization in your nCr
function there is overhead in those calls.
By using recursion
/*By using recursion*/ class RecursivePascal { public static void main(String args[]) { int n = 100; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { //System.out.print(i+","+j+" "); System.out.print(pascal(i, j) + " "); } System.out.println(); } } static int pascal(int i, int j) { if (j == 0) return 1; else if (j == i) return 1; else { return pascal(i - 1, j - 1) + pascal(i - 1, j); } } }
By using simple logic
/*By using logic*/ class p { public static void main(String args[]) { int one[] = {1}; int n = 13; System.out.println("1"); for (int j = 0; j < n; j++) { int two[] = new int[one.length + 1]; int twoCounter = 0; for (int i = 0; i < one.length; i++) { if (i == 0) { two[twoCounter++] = one[i]; System.out.print(one[i] + " "); } if (i != 0) { two[twoCounter++] = one[i] + one[i - 1]; System.out.print((one[i] + one[i - 1]) + " "); } if (i == one.length - 1) { two[twoCounter++] = one[i]; System.out.print(one[i] + " "); } } System.out.println(); one = two; } } }
精彩评论