Eine effiziente Möglichkeit, zu überprüfen, ob die n-te Fibonacci-Zahl ein Vielfaches von 10 ist?

Hier sehen wir eine effiziente Möglichkeit, zu überprüfen, ob der n-te Fibonacci-Term ein Vielfaches von 10 ist. Angenommen, die Fibonacci-Terme sind {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987}. Hier ist also die 15. Fibonacci-Zahl (von 0 an gezählt) durch 10 teilbar. Für 16 wird true zurückgegeben.

Eine der einfachsten Möglichkeiten besteht darin, Fibonacci-Zahlen bis zu einem bestimmten Term zu generieren und zu prüfen, ob dieser durch 10 teilbar ist. Diese Lösung ist jedoch nicht gut, da sie bei größeren Gegenständen nicht funktioniert.

Eine weitere gute Methode ist wie folgt:

Fibonacci-Begriffe: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

Diese Zahlen (mit Fettschrift gekennzeichnet) sind durch 2 teilbar. Sie sind durch 3 Fibonacci-Begriffe getrennt. Bitte überprüfen Sie auch -

Fibonacci-Begriffe: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

jeder Alle 5 Begriffe sind teilbar durch 5. Jetzt beträgt der LCM von 3 und 5 15. Wir können also sagen, dass jeder 15^ste Fibonacci-Term durch 10 teilbar ist.

Schauen wir uns den Algorithmus an, um die Idee zu verstehen. Die chinesische Übersetzung von

algorithm

fiboDivTen(term)

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

Example

ist:

Example

#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";
}

Output

Divisible

Das obige ist der detaillierte Inhalt vonEine effiziente Möglichkeit, zu überprüfen, ob die n-te Fibonacci-Zahl ein Vielfaches von 10 ist?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!