Pascal's Triangle - Topic

Member

Posts: 19,234

Joined: Aug 13 2009

Gold: 33,940.00

Aug 9 2015 07:55pm

Code

import java.util.Scanner;

public class Seven {

public static void main(String[] args) {
Scanner console = new Scanner(System.in);
System.out.print("How many rows for your Pascal's triangle? ");
int rows = console.nextInt();

pascalsTriangle(rows);
}

public static void pascalsTriangle(int rows) {
for (int i = 0; i < rows; i++) {
int number = 1;
// left spaces
for (int j = 1; j <= (rows - i) * 2 - 2; j++) {
System.out.print(" ");
}
// print #'s
for (int j = 0; j <= i; j++) {
System.out.printf("%4d", number);
number *= (i - j) / (j + 1);
}
// next line
System.out.println();
}
}
}

I think this should work but its not printing correctly. Its printing 0's at the end of each row and some of the numbers (near the middle of each row) aren't correct. I went through the code in my head and it seems like it should be printing out the correct numbers.

Here's an output from my code of an 11 row Pascal's Triangle:

Code

How many rows for your Pascal's triangle? 11
1
1 1
1 2 0
1 3 3 0
1 4 4 0 0
1 5 10 10 0 0
1 6 12 12 0 0 0
1 7 21 21 21 0 0 0
1 8 24 48 48 0 0 0 0
1 9 36 72 72 72 0 0 0 0
1 10 40 80 80 80 0 0 0 0 0

Here is how it should look:

Code

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1

carteblanche

Member

Posts: 32,925

Joined: Jul 23 2006

Gold: 3,804.50

Aug 9 2015 08:37pm

i suggest starting with a smaller test case (eg: row = 5) and debugging your code. either use a debugger or add print statements for everything inside your loops. include every variable so you can see what it's doing vs what the variables are in your head

bentherdonethat

Member

Posts: 13,578

Joined: Jul 27 2010

Gold: 2,285.00

Aug 10 2015 06:13am

Quote (carteblanche @ Aug 9 2015 10:37pm)

IMO since he's actually got a bug by the time i == 3, so he should start there, then step up to 4 then 5.

GomDoori

Member

Posts: 4,748

Joined: Apr 19 2010

Gold: 19.00

Aug 10 2015 10:46pm

do this:
number *= (double)(i - j) / (j + 1);

PuppyMonkeyBaby

Member

Posts: 5,167

Joined: Nov 23 2006

Gold: 11.01

Sep 1 2015 08:16am

Write it out on paper.

Go through the math on paper as well.

zeroRooter

Member

Posts: 21,211

Joined: May 22 2009

Gold: 9,036.90

Sep 12 2015 12:55pm

This algorithm is very slow but it will calculate well up to row 10-15 lol, and it's a little harder to make mistakes with recursion. A recursive solution is a stupid solution to this problem, I was just curious if I could do it elegantly with recursion, not so sure it's possible

It will compute the nth row in pascals triangle.
To get the 6th row run it like this: java Pascal 6
NB: I called the first row: row 1 and not row 0

If you need to print the whole triangle that shouldn't be too hard of a modification

Code

import java.util.*;

public class Pascal {
static Integer[] triangle;
public static void main(String[] args) {

String rowsString = args[0];
int rows = Integer.parseInt(rowsString);

triangle = pascalsTriangle(rows);
for(Integer i: triangle){
System.out.print(i + " ");
}
}

public static Integer[] pascalsTriangle(int rows) {
if(rows == 1)
return new Integer[]{1};
else if(rows == 2)
return new Integer[]{1,1};
else if(rows == 3)
return new Integer[]{1,2,1};
else{
//row represents a row in the triangle
Integer[] row = new Integer[rows];
//we know the begining and end of the row will be 1
row[0] = 1;
row[rows-1] = 1;

for(int i=1; i<rows-1; i++){
row[i] = pascalsTriangle(rows-1)[i-1] + pascalsTriangle(rows-1)[i];
}
return row;
}
}
}

This post was edited by zeroRooter on Sep 12 2015 12:59pm

carteblanche

Member

Posts: 32,925

Joined: Jul 23 2006

Gold: 3,804.50

Sep 12 2015 01:25pm

what's the point of all the arrays? try writing one with (row, col) as param without the arrays.

Minkomonster

Member

Posts: 1,995

Joined: Jun 28 2006

Gold: 7.41

Sep 12 2015 10:32pm

You can absolutely do it with recursion. There is a recursive definition of the pascal triangle formula, so it is pretty easy to translate that into code. The issue becomes a performance problem. Recursive algorithms fail without optimizations on their own due to increasing number of stack frames generated as you increase in levels. This can be fixed with dynamic programming techniques like memoization. However, if you are just looking for a bare bones recursive algorithm, you can do it like so :

Code

import java.util.Scanner;

public class PascalTriangle {
private Integer[][] triangle;
private String formattedTriangle;

public PascalTriangle(int rows)
{
triangle = new Integer[rows][];
calculate();
}

private void calculate()
{
for(int r = 0; r < triangle.length; r++)
{
triangle[r] = new Integer[r+1];
for(int c = 0; c <= r; c++)
{
triangle[r][c] = pascal(r, c);
}
}
}

private int pascal(int r, int c)
{
return c == 0 || r == c ? 1 : pascal(r-1, c-1) + pascal(r-1, c);
}

private String format(Integer[][] triangle)
{
String s = "";
for(Integer[] row : triangle)
{
s += format(row, triangle.length) + "\n";
}

return s;
}
private String format(Integer[] row, int n)
{
String rowFormat = "";
for(int i = 0; i < row.length; i++)
{
rowFormat += "%d ";
}

return String.format(rowFormat, (Object[])row);
}

public String toString()
{
if(formattedTriangle == null)
formattedTriangle = format(triangle);

return formattedTriangle;
}

public static void main(String[] args)
{
Scanner in = new Scanner(System.in);

int rows = Integer.parseInt(in.nextLine());

System.out.println(new PascalTriangle(rows));

}
}

Go Back To Programming & Development Topic List