Pascal's triangle: Difference between revisions
(Ada) |
(Added Haskell example) |
||
Line 47: | Line 47: | ||
end Pascals_Triangle; |
end Pascals_Triangle; |
||
</ada> |
</ada> |
||
=={{header|Haskell}}== |
|||
An approach using the "think in whole lists" principle: Each row in |
|||
the triangle can be calculated from the previous row by adding a |
|||
shifted version of itself to it, keeping the ones at the ends. The |
|||
Prelude function ''zipWith'' can be used to add two lists, but it |
|||
won't keep the old values when one list is shorter. So we need a |
|||
similar function |
|||
<pre> |
|||
zapWith :: (a -> a -> a) -> [a] -> [a] -> [a] |
|||
zapWith f xs [] = xs |
|||
zapWith f [] ys = ys |
|||
zapWith f (x:xs) (y:ys) = f x y : zapWith f xs ys |
|||
</pre> |
|||
Now we can shift a list and add it to itself, extending it by keeping |
|||
the ends: |
|||
<pre> |
|||
extendWith f [] = [] |
|||
extendWith f xs@(x:ys) = x : zapWith f xs ys |
|||
</pre> |
|||
And for the whole (infinite) triangle, we just iterate this operation, |
|||
starting with the first row: |
|||
<pre> |
|||
pascal = iterate (extendWith (+)) [1] |
|||
</pre> |
|||
For the first ''n'' rows, we just take the first ''n'' elements from this |
|||
list, as in |
|||
<pre> |
|||
*Main> take 6 pascal |
|||
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]] |
|||
</pre> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 10:17, 24 June 2008
You are encouraged to solve this task according to the task description, using any language you may know.
Pascal's triangle is an interesting math concept. Its first few rows look like this:
1 1 1 1 2 1 1 3 3 1
where each element of each row is either 1 or the sum of the two elements right above it. For example, the next row would be 1 (since the first element of each row doesn't have two elements above it), 4 (1 + 3), 6 (3 + 3), 4 (3 + 1), and 1 (since the last element of each row doesn't have two elements above it). Each row n (starting with row 0 at the top) shows the coefficients of the binomial expansion of (x + y)n.
Write a function that prints out the first n rows of the triangle (with f(1) yielding the row consisting of only the element 1). This can be done either by summing elements from the previous rows or using a binary coefficient or combination function. Behavior for n <= 0 does not need to be uniform, but should be noted.
Ada
<ada> -- Pascals triangle
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io; with Ada.Text_Io; use Ada.Text_Io;
procedure Pascals_Triangle is
type Row is array(Positive range <>) of Integer; type Row_Access is access Row; type Triangle is array(Positive range <>) of Row_Access; function General_Triangle(Depth : Positive) return Triangle is Result : Triangle(1..Depth); begin for I in Result'range loop Result(I) := new Row(1..I); for J in 1..I loop if J = Result(I)'First or else J = Result(I)'Last then Result(I)(J) := 1; else Result(I)(J) := Result(I - 1)(J - 1) + Result(I - 1)(J); end if; end loop; end loop; return Result; end General_Triangle; procedure Print(Item : Triangle) is begin for I in Item'range loop for J in 1..I loop Put(Item => Item(I)(J), Width => 3); end loop; New_Line; end loop; end Print;
begin
Print(General_Triangle(7));
end Pascals_Triangle; </ada>
Haskell
An approach using the "think in whole lists" principle: Each row in the triangle can be calculated from the previous row by adding a shifted version of itself to it, keeping the ones at the ends. The Prelude function zipWith can be used to add two lists, but it won't keep the old values when one list is shorter. So we need a similar function
zapWith :: (a -> a -> a) -> [a] -> [a] -> [a] zapWith f xs [] = xs zapWith f [] ys = ys zapWith f (x:xs) (y:ys) = f x y : zapWith f xs ys
Now we can shift a list and add it to itself, extending it by keeping the ends:
extendWith f [] = [] extendWith f xs@(x:ys) = x : zapWith f xs ys
And for the whole (infinite) triangle, we just iterate this operation, starting with the first row:
pascal = iterate (extendWith (+)) [1]
For the first n rows, we just take the first n elements from this list, as in
*Main> take 6 pascal [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
Java
Summing from Previous Rows
This implementation prints nothing for n <= 0. <java>import java.util.LinkedList; ...//class definition, etc. public static void genPyrN(int rows){ if(rows <= 0) return; //save the last row here LinkedList<Integer> last= new LinkedList<Integer>(); last.add(1);//it's row 0...it starts with 1 for(int i= 0;i <= rows;++i){ //work on the next row LinkedList<Integer> thisRow= new LinkedList<Integer>(); for(int j= 0;j < i;++j){//loop the number of elements in this row if(j == last.size() || j == 0){//if we're on the ends thisRow.add(1); }else{//otherwise, sum from the last row thisRow.add(last.get(j - 1) + last.get(j)); } } thisRow.add(1); last= thisRow;//save this row System.out.println(thisRow); } }</java>