หาหลักสุดท้ายของพจน์ฟีโบนัชชีที่ N ใน C++

หาหลักสุดท้าย (LSB) ของพจน์ฟีโบนัชชีที่ N

ตัวอย่าง: N = 120 → 1

วิธีแก้ปัญหา (Pisano Period mod 10)

หลักสุดท้ายของฟีโบนัชชีซ้ำทุก 60 พจน์ (Pisano period mod 10 = 60)

คำนวณ N mod 60 แล้วหา mod 10

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

long int fibo(int N) {
    long int a = 0, b = 1, c;
    for (int i = 2; i < N; i++) {
        c = a + b; a = b; b = c;
    }
    return c;
}

int findLastDigitNterm(int N) {
    N = N % 60;
    return fibo(N) % 10;
}

int main() {
    int N = 683;
    cout << "The last digit of " << N << "th Fibonacci term is " << findLastDigitNterm(N);
    return 0;
}

Output

The last digit of 683th Fibonacci term is 1