Trong bài toán này, chúng ta được cung cấp một số N. Nhiệm vụ của chúng ta là tạo một Chương trình để tìm chữ số cuối cùng của số Fibonacci thứ N trong C ++.
Mô tả vấn đề
Chúng tôi cần tìm chữ số cuối cùng (tức là LSB) của số Fibonacci thứ N.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào:N =120 Đầu ra:1
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản sẽ là sử dụng công thức Fibonacci trực tiếp để tìm số hạng thứ N. Nhưng phương pháp này sẽ không khả thi khi N là một số lớn. Vì vậy, để khắc phục điều này, chúng tôi sẽ sử dụng thuộc tính của Chuỗi Fibonacci mà chữ số cuối cùng lặp lại chính nó sau 60 số hạng. I E. Chữ số cuối cùng của số hạng thứ 75 giống với chữ số của số hạng thứ 135.
Điều này có nghĩa là làm việc đến năm 60 sẽ cho chúng ta tất cả các kết hợp có thể có và để tìm thuật ngữ nào cần sử dụng, chúng ta sẽ tìm mod của số với 60.
Ví dụ
#include
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;
} Đầu ra
The last digit of 683th Fibonacci term is 1