시작과 끝 숫자가 있는 범위가 주어지고 O(Log n) 시간과 O(1) 공간에서 주어진 범위 사이에서 사용할 수 있는 피보나치 수의 총 개수를 계산하는 작업입니다.
피보나치 수란 무엇입니까
피보나치 수열은 피보나치 수열로 알려진 수열로, 모든 새로운 수는 앞의 마지막 두 수의 합입니다.
여기서 f(0) =0 및 f(1) =1 즉, f(0) 및 f(1)은 시퀀스에서 고정 위치를 가지며 계산은 세 번째 숫자부터 시작됩니다.
시퀀스 계산에 사용된 공식은 -
Fn =Fn-1 + Fn-2
어디,
F0 =0, F1 =l
예를 들어
Input − start = 6 and last = 100 Output − Number of fibonacci Numbers in the series are 6
설명 - 6에서 100 사이의 피보나치 수는 8, 13, 21, 34, 55, 89입니다. 즉, 총 개수는 6입니다.
Input − start = 0 and last = 8 Output − Number of fibonacci Numbers in the series are 7
설명 - 0과 8 사이의 피보나치 수는 0, 1, 1, 2, 3, 5, 8입니다. 즉, 총 개수는 7입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
범위를 생성하려면 시작 및 끝 번호를 입력하세요.
-
fib1을 0으로, fib2를 1로, fib3을 1로 선언하고 초기화합니다.
-
임시 변수 res를 선언하고 0으로 초기화
-
fib1이 끝보다 작거나 같은 동안 루프 시작
-
루프 내에서 fib1이 시작보다 크거나 같은지 확인한 다음 res를 1만큼 증가시킵니다.
-
fib1을 fib2로, fib2를 fib3으로, fib3을 fib1 + fib2로 설정
-
반환 해상도
-
결과 인쇄
예시
#include <bits/stdc++.h>
using namespace std;
// function to count fibonacci numbers in range
// from start to last
int count_fibonacci(int start, int last){
// First three Fibonacci Numbers
int fib1 = 0, fib2 = 1, fib3 = 1;
// res to count the number of fibonacci
int res = 0;
while (fib1 <= last){
if (fib1 >= start){
res++;
}
fib1 = fib2;
fib2 = fib3;
fib3 = fib1 + fib2;
}
return res;
}
// main function
int main(){
int start = 6, last = 100;
cout << "Number of fibonacci Numbers in the series are "
<< count_fibonacci(start, last);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Number of fibonacci Numbers in the series are 6