วิธีที่มีประสิทธิภาพในการตรวจสอบว่าเลขฟีโบนักชีที่ n คูณด้วย 10 หรือไม่

ในที่นี้เราจะมาดูวิธีที่มีประสิทธิภาพในการตรวจสอบว่าเทอมฟีโบนักชีที่ n มีจำนวนทวีคูณของ 10 หรือไม่ สมมติว่าเงื่อนไขฟีโบนักชีคือ {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987} แล้วนี่วันที่ 15 ^th (นับจาก 0) เทอม Fibonacci หารด้วย 10 ลงตัว สำหรับ 16 จะคืนค่าเป็นจริง

วิธีที่ง่ายที่สุดวิธีหนึ่งคือการสร้างตัวเลขฟีโบนักชีตามเงื่อนไขที่กำหนด และตรวจสอบว่าหารด้วย 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 ลงตัว ตอนนี้ LCM ของ 3 และ 5 คือ 15 เราจึงกล่าวได้ว่าทุกๆ 15 ^th เงื่อนไขฟีโบนักชีหารด้วย 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