n 번째 피보나치 수가 10의 배수인지 확인하는 효율적인 방법은 무엇입니까?

여기에서 n번째 피보나치 항이 10의 배수인지 여부를 확인하는 한 가지 효율적인 방법을 볼 것입니다. 피보나치 항이 {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987}이라고 가정합니다. 여기 15 입니다. (0부터 계산) 피보나치 항은 10으로 나눌 수 있습니다. 16의 경우 true를 반환합니다.

가장 쉬운 방법 중 하나는 주어진 항까지 피보나치 수를 생성하고 10으로 나눌 수 있는지 여부를 확인하는 것입니다. 그러나 이 솔루션은 더 큰 기간에는 작동하지 않기 때문에 좋지 않습니다.

또 다른 좋은 접근 방식은 아래와 같습니다 -

피보나치 항 - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

이 숫자(굵은 글씨로 표시)는 2로 나눌 수 있습니다. 그리고 그 간격은 3개의 피보나치 항입니다. 마찬가지로 다음을 확인하십시오 -

피보나치 항:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

모든 5번째 항은 5로 나눌 수 있습니다. 이제 3과 5의 LCM은 15입니다. 따라서 우리는 매 15 ^번째 라고 말할 수 있습니다. 피보나치 항은 10으로 나눌 수 있습니다.

아이디어를 얻을 수 있는 알고리즘을 살펴보겠습니다.

알고리즘

fiboDivTen(용어)

Begin
   if term is divisible by 15, then
      return true
   end if
   return false
End

예시

#include<iostream>
using namespace std;
bool fiboDivTen(int term) {
   if(term % 15 == 0){
      return true;
   }
   return false;
}
int main() {
   int term = 45;
   if (fiboDivTen(term))
      cout << "Divisible";
   else
      cout << "Not Divisible";
}

출력

Divisible