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

Commit1b64ba6

Browse files
authored
Fibonacci.js overhaul (TheAlgorithms#1049)
1 parent95a8ec0 commit1b64ba6

File tree

2 files changed

+150
-53
lines changed

2 files changed

+150
-53
lines changed

‎Maths/Fibonacci.js

Lines changed: 85 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -1,51 +1,67 @@
1-
constlist=[]
2-
3-
constFibonacciIterative=(nth)=>{
4-
constsequence=[]
5-
6-
if(nth>=1)sequence.push(1)
7-
if(nth>=2)sequence.push(1)
8-
9-
for(leti=2;i<nth;i++){
10-
sequence.push(sequence[i-1]+sequence[i-2])
1+
// https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Extension_to_negative_integers
2+
constFibonacciIterative=(num)=>{
3+
constisNeg=num<0
4+
if(isNeg)num*=-1
5+
constsequence=[0]
6+
7+
if(num>=1)sequence.push(1)
8+
if(num>=2)sequence.push(isNeg ?-1 :1)
9+
10+
for(leti=2;i<num;i++){
11+
sequence.push(
12+
isNeg ?sequence[i-1]-sequence[i] :sequence[i]+sequence[i-1]
13+
)
1114
}
1215

1316
returnsequence
1417
}
1518

16-
constFibonacciRecursive=(number)=>{
19+
constFibonacciGenerator=function*(neg){
20+
leta=0
21+
letb=1
22+
yielda
23+
while(true){
24+
yieldb;
25+
[a,b]=neg ?[b,a-b] :[b,a+b]
26+
}
27+
}
28+
29+
constlist=[]
30+
constFibonacciRecursive=(num)=>{
31+
constisNeg=num<0
32+
if(isNeg)num*=-1
1733
return(()=>{
1834
switch(list.length){
1935
case0:
20-
list.push(1)
21-
returnFibonacciRecursive(number)
36+
list.push(0)
37+
returnFibonacciRecursive(num)
2238
case1:
2339
list.push(1)
24-
returnFibonacciRecursive(number)
25-
casenumber:
40+
returnFibonacciRecursive(num)
41+
casenum+1:
2642
returnlist
2743
default:
28-
list.push(list[list.length-1]+list[list.length-2])
29-
returnFibonacciRecursive(number)
44+
list.push(list.at(-1)+list.at(-2))
45+
returnFibonacciRecursive(num)
3046
}
31-
})()
47+
})().map((fib,i)=>fib*(isNeg ?(-1)**(i+1) :1))
3248
}
3349

3450
constdict=newMap()
35-
3651
constFibonacciRecursiveDP=(stairs)=>{
37-
if(stairs<=0)return0
38-
if(stairs===1)return1
52+
constisNeg=stairs<0
53+
if(isNeg)stairs*=-1
54+
55+
if(stairs<=1)returnstairs
3956

4057
// Memoize stair count
41-
if(dict.has(stairs))returndict.get(stairs)
58+
if(dict.has(stairs))return(isNeg ?(-1)**(stairs+1) :1)*dict.get(stairs)
4259

43-
constres=
44-
FibonacciRecursiveDP(stairs-1)+FibonacciRecursiveDP(stairs-2)
60+
constres=FibonacciRecursiveDP(stairs-1)+FibonacciRecursiveDP(stairs-2)
4561

4662
dict.set(stairs,res)
4763

48-
returnres
64+
return(isNeg ?(-1)**(stairs+1) :1)*res
4965
}
5066

5167
// Algorithms
@@ -59,12 +75,16 @@ const FibonacciRecursiveDP = (stairs) => {
5975
// a function of the number of input bits
6076
//@Satzyakiz
6177

62-
constFibonacciDpWithoutRecursion=(number)=>{
63-
consttable=[]
78+
constFibonacciDpWithoutRecursion=(num)=>{
79+
constisNeg=num<0
80+
if(isNeg)num*=-1
81+
consttable=[0]
6482
table.push(1)
65-
table.push(1)
66-
for(leti=2;i<number;++i){
67-
table.push(table[i-1]+table[i-2])
83+
table.push(isNeg ?-1 :1)
84+
for(leti=2;i<num;++i){
85+
table.push(
86+
isNeg ?table[i-1]-table[i] :table[i]+table[i-1]
87+
)
6888
}
6989
returntable
7090
}
@@ -76,24 +96,31 @@ const copyMatrix = (A) => {
7696
}
7797

7898
constIdentity=(size)=>{
99+
constisBigInt=typeofsize==='bigint'
100+
constZERO=isBigInt ?0n :0
101+
constONE=isBigInt ?1n :1
102+
size=Number(size)
79103
constI=Array(size).fill(null).map(()=>Array(size).fill())
80104
returnI.map((row,rowIdx)=>row.map((_col,colIdx)=>{
81-
returnrowIdx===colIdx ?1 :0
105+
returnrowIdx===colIdx ?ONE :ZERO
82106
}))
83107
}
84108

85109
// A of size (l x m) and B of size (m x n)
86-
// product C will be of size (l x n)
110+
// product C will be of size (l x n).
111+
// both matrices must have same-type numeric values
112+
// either both BigInt or both Number
87113
constmatrixMultiply=(A,B)=>{
88114
A=copyMatrix(A)
89115
B=copyMatrix(B)
116+
constisBigInt=typeofA[0][0]==='bigint'
90117
constl=A.length
91118
constm=B.length
92119
constn=B[0].length// Assuming non-empty matrices
93120
constC=Array(l).fill(null).map(()=>Array(n).fill())
94121
for(leti=0;i<l;i++){
95122
for(letj=0;j<n;j++){
96-
C[i][j]=0
123+
C[i][j]=isBigInt ?0n :0
97124
for(letk=0;k<m;k++){
98125
C[i][j]+=A[i][k]*B[k][j]
99126
}
@@ -110,18 +137,25 @@ const matrixMultiply = (A, B) => {
110137
// A is a square matrix
111138
constmatrixExpo=(A,n)=>{
112139
A=copyMatrix(A)
140+
constisBigInt=typeofn==='bigint'
141+
constZERO=isBigInt ?0n :0
142+
constTWO=isBigInt ?2n :2
113143

114144
// Just like Binary exponentiation mentioned in ./BinaryExponentiationIterative.js
115-
letresult=Identity(A.length)// Identity matrix
116-
while(n>0){
117-
if(n%2!==0)result=matrixMultiply(result,A)
118-
n=Math.floor(n/2)
119-
if(n>0)A=matrixMultiply(A,A)
145+
letresult=Identity((isBigInt ?BigInt :Number)(A.length))// Identity matrix
146+
while(n>ZERO){
147+
if(n%TWO!==ZERO)result=matrixMultiply(result,A)
148+
n/=TWO
149+
if(!isBigInt)n=Math.floor(n)
150+
if(n>ZERO)A=matrixMultiply(A,A)
120151
}
121152
returnresult
122153
}
123154

124-
constFibonacciMatrixExpo=(n)=>{
155+
constFibonacciMatrixExpo=(num)=>{
156+
constisBigInt=typeofnum==='bigint'
157+
constZERO=isBigInt ?0n :0
158+
constONE=isBigInt ?1n :1
125159
// F(0) = 0, F(1) = 1
126160
// F(n) = F(n-1) + F(n-2)
127161
// Consider below matrix multiplication:
@@ -134,23 +168,28 @@ const FibonacciMatrixExpo = (n) => {
134168
// or F(n, n-1) = A * A * F(n-2, n-3)
135169
// or F(n, n-1) = pow(A, n-1) * F(1, 0)
136170

137-
if(n===0)return0
171+
if(num===ZERO)returnnum
172+
173+
constisNeg=num<0
174+
if(isNeg)num*=-ONE
138175

139176
constA=[
140-
[1,1],
141-
[1,0]
177+
[ONE,ONE],
178+
[ONE,ZERO]
142179
]
143-
constpoweredA=matrixExpo(A,n-1)// A raised to the power n-1
180+
181+
constpoweredA=matrixExpo(A,num-ONE)// A raised to the power n-1
144182
letF=[
145-
[1],
146-
[0]
183+
[ONE],
184+
[ZERO]
147185
]
148186
F=matrixMultiply(poweredA,F)
149-
returnF[0][0]
187+
returnF[0][0]*(isNeg ?(-ONE)**(num+ONE) :ONE)
150188
}
151189

152190
export{FibonacciDpWithoutRecursion}
153191
export{FibonacciIterative}
192+
export{FibonacciGenerator}
154193
export{FibonacciRecursive}
155194
export{FibonacciRecursiveDP}
156195
export{FibonacciMatrixExpo}

‎Maths/test/Fibonacci.test.js

Lines changed: 65 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2,30 +2,61 @@ import {
22
FibonacciDpWithoutRecursion,
33
FibonacciRecursiveDP,
44
FibonacciIterative,
5+
FibonacciGenerator,
56
FibonacciRecursive,
67
FibonacciMatrixExpo
78
}from'../Fibonacci'
89

910
describe('Fibonacci',()=>{
1011
it('should return an array of numbers for FibonacciIterative',()=>{
11-
expect(FibonacciIterative(5)).toEqual(
12-
expect.arrayContaining([1,1,2,3,5])
12+
expect(FibonacciIterative(6)).toEqual(
13+
expect.arrayContaining([0,1,1,2,3,5,8])
14+
)
15+
expect(FibonacciIterative(-6)).toEqual(
16+
expect.arrayContaining([0,1,-1,2,-3,5,-8])
1317
)
1418
})
1519

20+
it('should return number for FibonacciGenerator',()=>{
21+
constpositive=FibonacciGenerator()
22+
expect(positive.next().value).toBe(0)
23+
expect(positive.next().value).toBe(1)
24+
expect(positive.next().value).toBe(1)
25+
expect(positive.next().value).toBe(2)
26+
expect(positive.next().value).toBe(3)
27+
expect(positive.next().value).toBe(5)
28+
expect(positive.next().value).toBe(8)
29+
30+
constnegative=FibonacciGenerator(true)
31+
expect(negative.next().value).toBe(0)
32+
expect(negative.next().value).toBe(1)
33+
expect(negative.next().value).toBe(-1)
34+
expect(negative.next().value).toBe(2)
35+
expect(negative.next().value).toBe(-3)
36+
expect(negative.next().value).toBe(5)
37+
expect(negative.next().value).toBe(-8)
38+
})
39+
1640
it('should return an array of numbers for FibonacciRecursive',()=>{
17-
expect(FibonacciRecursive(5)).toEqual(
18-
expect.arrayContaining([1,1,2,3,5])
41+
expect(FibonacciRecursive(6)).toEqual(
42+
expect.arrayContaining([0,1,1,2,3,5,8])
43+
)
44+
expect(FibonacciRecursive(-6)).toEqual(
45+
expect.arrayContaining([-0,1,-1,2,-3,5,-8])
1946
)
2047
})
2148

2249
it('should return number for FibonacciRecursiveDP',()=>{
23-
expect(FibonacciRecursiveDP(5)).toBe(5)
50+
expect(FibonacciRecursiveDP(6)).toBe(8)
51+
expect(FibonacciRecursiveDP(-6)).toBe(-8)
2452
})
2553

2654
it('should return an array of numbers for FibonacciDpWithoutRecursion',()=>{
27-
expect(FibonacciDpWithoutRecursion(5)).toEqual(
28-
expect.arrayContaining([1,1,2,3,5])
55+
expect(FibonacciDpWithoutRecursion(6)).toEqual(
56+
expect.arrayContaining([0,1,1,2,3,5,8])
57+
)
58+
expect(FibonacciDpWithoutRecursion(-6)).toEqual(
59+
expect.arrayContaining([0,1,-1,2,-3,5,-8])
2960
)
3061
})
3162

@@ -36,5 +67,32 @@ describe('Fibonacci', () => {
3667
expect(FibonacciMatrixExpo(3)).toBe(2)
3768
expect(FibonacciMatrixExpo(4)).toBe(3)
3869
expect(FibonacciMatrixExpo(5)).toBe(5)
70+
expect(FibonacciMatrixExpo(6)).toBe(8)
71+
72+
expect(FibonacciMatrixExpo(-0)).toBe(-0)
73+
expect(FibonacciMatrixExpo(-1)).toBe(1)
74+
expect(FibonacciMatrixExpo(-2)).toBe(-1)
75+
expect(FibonacciMatrixExpo(-3)).toBe(2)
76+
expect(FibonacciMatrixExpo(-4)).toBe(-3)
77+
expect(FibonacciMatrixExpo(-5)).toBe(5)
78+
expect(FibonacciMatrixExpo(-6)).toBe(-8)
79+
})
80+
81+
it('should return bigint for FibonacciMatrixExpo',()=>{
82+
expect(FibonacciMatrixExpo(0n)).toBe(0n)
83+
expect(FibonacciMatrixExpo(1n)).toBe(1n)
84+
expect(FibonacciMatrixExpo(2n)).toBe(1n)
85+
expect(FibonacciMatrixExpo(3n)).toBe(2n)
86+
expect(FibonacciMatrixExpo(4n)).toBe(3n)
87+
expect(FibonacciMatrixExpo(5n)).toBe(5n)
88+
expect(FibonacciMatrixExpo(6n)).toBe(8n)
89+
90+
expect(FibonacciMatrixExpo(-0n)).toBe(0n)
91+
expect(FibonacciMatrixExpo(-1n)).toBe(1n)
92+
expect(FibonacciMatrixExpo(-2n)).toBe(-1n)
93+
expect(FibonacciMatrixExpo(-3n)).toBe(2n)
94+
expect(FibonacciMatrixExpo(-4n)).toBe(-3n)
95+
expect(FibonacciMatrixExpo(-5n)).toBe(5n)
96+
expect(FibonacciMatrixExpo(-6n)).toBe(-8n)
3997
})
4098
})

0 commit comments

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