2 Replies - 15384 Views - Last Post: 27 November 2009 - 09:31 AM Rate Topic: -----

#1 prelic  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 26
  • Joined: 13-February 07

Pascal's Triangle (*So close, need help finishing*)

Posted 13 February 2007 - 08:54 PM

I have to print pascal's triangle given a user-inputted row number.

here are the constraints:
-cannot use 2d array
-cannot use more than 1 array
-cannot use temp values

here is what i have come up with so far:
-initialize all to 1
-need 2 nested for loops

i know its SO close to this, just need a push

public static void calculate(int[] triangle)
{
	
	for(int x = triangle.length - 1; x>= 1; x--)
	{
		
		for(int y= 1; y < triangle.length; y++)
		{
			triangle[y] = triangle[y] + triangle[y-1];
			printRow(triangle);
		}
		
	}
}



Is This A Good Question/Topic? 0
  • +

#5 msg555  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 9
  • View blog
  • Posts: 136
  • Joined: 04-May 06

Re: Pascal's Triangle (*So close, need help finishing*)

Posted 14 February 2007 - 08:46 AM

You're close, you want to use dynamic programming to solve this problem. I think recursive calls to printRow is cheating.

dp[j] += dp[j - 1] comes from the relationship that pascal[r][c] = pascal[r - 1][c] + pascal[r - 1][c - 1]

Before computing the new value we can assert that dp[j] == pascal[i - 1][j] and that dp[j - 1] == pascal[i - 1][j] because we are iterating backwards, therefore to calculate the value of pascal[i][j] and put it in the variable dp[j] we simply need to add dp[j - 1]

public void printPascal(int rows)
{
	int [] dp = new int[rows];

	//Set intial array to {1, 0, 0, ... 0}
	dp[0] = 1;

	//Print first row
	System.out.println(1);

	//Calculate and print each row
	for(int i = 1; i < rows; i++)
	{
		//Calculate new row values
		for(int j = i; j > 0; j--)
		{
			dp[j] += dp[j - 1];
		}
		//Print new row
		for(int j = 0; j <= i; j++)
		{
			System.out.print("" + dp[j] + " ");
		}
		System.out.println();
	}
}

This post has been edited by msg555: 14 February 2007 - 09:00 AM

Was This Post Helpful? 1

#9 ynnorj  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 3
  • Joined: 27-November 09

Re: Pascal's Triangle (*So close, need help finishing*)

Posted 27 November 2009 - 09:31 AM

Here's a little tricky formula without even using an array at all...
This might be a little too late, but hope this would help someone.

for(int i = 0; i < n; i++) {
	for(int j = 0, x = 1; j <= i; j++) {
		System.out.print(x + " ");
		x = x * (i - j) / (j + 1);
	}
	System.out.println();
}

Was This Post Helpful? 1

Page 1 of 1