티스토리 뷰
피보나치수구하기
F0=F1=1,Fn+1=Fn+Fn−1,n≥1
1,1,2,3,5,8....
위와같은수열이피보나치수열이다.
f0=0,f1=1,fn+1=fn+fn−1,n≥1
0,1,1,2,3,5,8....
편의를위해0부터시작하기도한다.
fk+1=Fk,k>0
n번째피보나치수fn은어떻게구할까?
f2=f1+f0
f3=f2+f1
...
fn−1=fn−2+fn−3
fn=fn−1+fn−2
n−1번계산하면구할수있다.
행렬연산을이용하면좀더효율적으로구할수있다.
An=(fn−1fnfnfn+1),n≥1
피보나치행렬은위와같다.
A=(f0f1f1f2)=(0111)
행렬곱의성질에의하면
A2n=An×An
A2=A×A=(f0f1f1f2)(f0f1f1f2)=(f1f2f2f3)
A4=A2×A2=(f1f2f2f3)(f1f2f2f3)=(f3f4f4f5)
A8=A4×A4=(f3f4f4f5)(f3f4f4f5)=(f7f8f8f9)
...
A2n=An×An=(fn−1fnfnfn+1)(fn−1fnfnfn+1)=(f2n−1f2nf2nf2n+1)
n이2x의형태로표현되는수라면
fn을구하기위해log2n번계산하면된다.
n이2x의형태로표현되는못하는수라면
Am+n=Am×An
(fm−1fmfmfm+1)(fn−1fnfnfn+1)=(fm+n−1fm+nfm+nfm+n+1)
식을전개하면새로운성질을발견할수있다.
(fm+n−1fm+nfm+nfm+n+1)=(fmfn+fm−1fn−1fmfn+1+fm−1fnfm+1fn+fmfn−1fm+1fn+1+fmfn)
fm+n=fmfn+1+fm−1fn
fm+n=fm+1fn+fmfn−1
첫번째식을기준으로잡으면
m+n=(m+1)+(n−1)
f(m+1)+(n−1)=f(m+1)f(n−1)+1+f(m+1)−1f(n−1)=fm+1fn+fmfn−1
이런성질들을응용하면차례대로구하지않고특정피보나치수를구할수있다.
'수학' 카테고리의 다른 글
나머지 곱셈의 역원 (0) | 2019.02.22 |
---|---|
페르마의 소정리 (0) | 2019.02.21 |
유클리드 호제법의 확장 (0) | 2019.02.16 |
유클리드 호제법 (0) | 2019.02.14 |
- Total
- Today
- Yesterday
- 올림픽
- 우분투
- Multimedia
- 마크다운
- 클래스
- Object Oriented Programming
- Class
- 평창
- player
- 크롤링
- 파이선
- 객체지향
- media
- readme.md
- 리눅스
- ubuntu
- OOP
- Android
- ContentResolver
- Video
- Linux
- 캡슐화
- 추상화
- abstraction
- 다형성
- Polymorphism
- 동계
- Encapsulation
- markdown
- 입장권
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |