patterncsharpMinor
Pascal Triangle implementation in C#
Viewed 0 times
pascalimplementationtriangle
Problem
This is my attempt to implement the Pascal Triangle in C#. It is meant to calculate and return a pascal triangle of size
I feel this code is a little messy. Thus I seek some opinion on it and ways to improve it.
n (which it takes is through the parameter rows).static List> GetPascalTriangle(int rows)
{
List> result = new List>();
for (int x = 0; x prevRow = result[x - 1];
List semiResult = new List();
semiResult.Add(1);
for (int x1 = 0; x1 <= prevRow.Count - 2; x1++)
{
semiResult.Add(prevRow[x1] + prevRow[x1 + 1]);
}
semiResult.Add(1);
result.Add(semiResult);
}
}
return result;
}I feel this code is a little messy. Thus I seek some opinion on it and ways to improve it.
Solution
First: The Pascal Triangle will grow very rapidly. And
The only suggestion is
Second: Why are you using
Third: if you know the first and last element is always a 1, then the if-statement for the first 2 rows is redundant
So with all the improvements, you code would be shorter and could handle much more rows. As a bonus I removed the dependency on system.linq. It could look like this:
rows=100, your maximum value is 1.27388061294904e+28. Yes, that's right it will overflow int, uint, long, and ulong within 100 rows. Check it out on interactive pascal triangle siteThe only suggestion is
Numerics.BigInteger where there is no upperbound.Second: Why are you using
List? You can use a jagged array, which is much shorter: int[][], and effectively does the same. You just need to initialize them ahead with their sizevar triangle = new int[rows][];
for(int i = 0; i<rows;i++){triangle[i] = new int[i+1];}Third: if you know the first and last element is always a 1, then the if-statement for the first 2 rows is redundant
// This part is redundant, you already check if the first/last element is 1
if (x == 0 || x == 1)
{
result.Add(Enumerable.Repeat(1, x + 1).ToList());
}So with all the improvements, you code would be shorter and could handle much more rows. As a bonus I removed the dependency on system.linq. It could look like this:
public static BigInteger[][] GetPascalTriangleImproved(int rows)
{
BigInteger[][] result = new BigInteger[rows+1][];
for (int x = 0; x < rows; x++)
{
result[x] = new BigInteger[x + 1];
result[x][0] = 1; // first element is ALWAYS 1
for (int x1 = 1; x1 <= x; x1++)
{
// last element is always 1 (just like the first)
if (x1 == x) { result[x][x] = 1; continue; }
// in all other cases, just add the 2 digits in the upper row
result[x][x1] = result[x - 1][x1 - 1] + result[x - 1][x1];
}
}
return result;
}Code Snippets
var triangle = new int[rows][];
for(int i = 0; i<rows;i++){triangle[i] = new int[i+1];}// This part is redundant, you already check if the first/last element is 1
if (x == 0 || x == 1)
{
result.Add(Enumerable.Repeat(1, x + 1).ToList());
}public static BigInteger[][] GetPascalTriangleImproved(int rows)
{
BigInteger[][] result = new BigInteger[rows+1][];
for (int x = 0; x < rows; x++)
{
result[x] = new BigInteger[x + 1];
result[x][0] = 1; // first element is ALWAYS 1
for (int x1 = 1; x1 <= x; x1++)
{
// last element is always 1 (just like the first)
if (x1 == x) { result[x][x] = 1; continue; }
// in all other cases, just add the 2 digits in the upper row
result[x][x1] = result[x - 1][x1 - 1] + result[x - 1][x1];
}
}
return result;
}Context
StackExchange Code Review Q#118656, answer score: 6
Revisions (0)
No revisions yet.