Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb878390

Browse files
committed
Add Pascal's triangle.
1 parentf3189cc commitb878390

File tree

5 files changed

+61
-2
lines changed

5 files changed

+61
-2
lines changed

‎src/algorithms/math/pascal-triangle/README.md

Lines changed: 26 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
#Pascal's Triangle
22

33
In mathematics,**Pascal's triangle** is a triangular array of
4-
the binomial coefficients.
4+
the[binomial coefficients](https://en.wikipedia.org/wiki/Binomial_coefficient).
55

66
The rows of Pascal's triangle are conventionally enumerated
77
starting with row`n = 0` at the top (the`0th` row). The
@@ -34,6 +34,31 @@ paragraph may be written as follows:
3434
for any non-negative integer`n` and any
3535
integer`k` between`0` and`n`, inclusive.
3636

37+
![Binomial Coefficient](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2457a7ef3c77831e34e06a1fe17a80b84a03181)
38+
39+
##Calculating triangle entries in O(n) time
40+
41+
We know that`i`-th entry in a line number`lineNumber` is
42+
Binomial Coefficient`C(lineNumber, i)` and all lines start
43+
with value`1`. The idea is to
44+
calculate`C(lineNumber, i)` using`C(lineNumber, i-1)`. It
45+
can be calculated in`O(1)` time using the following:
46+
47+
```
48+
C(lineNumber, i) = lineNumber! / ((lineNumber - i)! * i!)
49+
C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!)
50+
```
51+
52+
We can derive following expression from above two expressions:
53+
54+
```
55+
C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i
56+
```
57+
58+
So`C(lineNumber, i)` can be calculated
59+
from`C(lineNumber, i - 1)` in`O(1)` time.
60+
3761
##References
3862

3963
-[Wikipedia](https://en.wikipedia.org/wiki/Pascal%27s_triangle)
64+
-[GeeksForGeeks](https://www.geeksforgeeks.org/pascal-triangle/)
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
importpascalTrianglefrom'../pascalTriangle';
2+
3+
describe('pascalTriangle',()=>{
4+
it('should calculate Pascal Triangle coefficients for specific line number',()=>{
5+
expect(pascalTriangle(0)).toEqual([1]);
6+
expect(pascalTriangle(1)).toEqual([1,1]);
7+
expect(pascalTriangle(2)).toEqual([1,2,1]);
8+
expect(pascalTriangle(3)).toEqual([1,3,3,1]);
9+
expect(pascalTriangle(4)).toEqual([1,4,6,4,1]);
10+
expect(pascalTriangle(5)).toEqual([1,5,10,10,5,1]);
11+
expect(pascalTriangle(6)).toEqual([1,6,15,20,15,6,1]);
12+
expect(pascalTriangle(7)).toEqual([1,7,21,35,35,21,7,1]);
13+
});
14+
});
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
/**
2+
*@param {number} lineNumber - zero based.
3+
*@return {number[]}
4+
*/
5+
exportdefaultfunctionpascalTriangle(lineNumber){
6+
constcurrentLine=[1];
7+
8+
constcurrentLineSize=lineNumber+1;
9+
10+
for(letnumIndex=1;numIndex<currentLineSize;numIndex+=1){
11+
// See explanation of this formula in README.
12+
currentLine[numIndex]=currentLine[numIndex-1]*(lineNumber-numIndex+1)/numIndex;
13+
}
14+
15+
returncurrentLine;
16+
}

‎src/algorithms/math/pascal-triangle/pascalTriangleRecursive.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
/**
2-
*@param {number} lineNumber
2+
*@param {number} lineNumber - zero based.
33
*@return {number[]}
44
*/
55
exportdefaultfunctionpascalTriangleRecursive(lineNumber){

‎src/algorithms/sets/combinations/__test__/combineWithoutRepetitions.test.js

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
importcombineWithoutRepetitionsfrom'../combineWithoutRepetitions';
22
importfactorialfrom'../../../math/factorial/factorial';
3+
importpascalTrianglefrom'../../../math/pascal-triangle/pascalTriangle';
34

45
describe('combineWithoutRepetitions',()=>{
56
it('should combine string without repetitions',()=>{
@@ -56,5 +57,8 @@ describe('combineWithoutRepetitions', () => {
5657
constexpectedNumberOfCombinations=factorial(n)/(factorial(r)*factorial(n-r));
5758

5859
expect(combinations.length).toBe(expectedNumberOfCombinations);
60+
61+
// This one is just to see one of the way of Pascal's triangle application.
62+
expect(combinations.length).toBe(pascalTriangle(n)[r]);
5963
});
6064
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp