Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ của chúng ta là tạo một Chương trình để tìm hai chữ số cuối của số Fibonacci thứ N trong C ++.
Mô tả vấn đề
Chúng ta cần tìm hai chữ số cuối cùng (tức là hai 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 :81
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à hai chữ số cuối cùng lặp lại chính nó sau 300 điều khoản. I E. Hai chữ số cuối của số hạng 75 giống với số hạng thứ 975.
Điều này có nghĩa là làm việc cho đến năm 300 sẽ cung cấp cho chúng tôi 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 tôi sẽ tìm mod của số với 300.
Ví dụ
#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 findLastTwoDigitNterm(int N) {
N = N % 300;
return ( fibo(N)%100);
}
int main() {
int N = 683;
cout<<"The last two digits of "<<N<<"th Fibonacci term are "<<findLastTwoDigitNterm(N);
return 0;
} Đầu ra
The last two digits of 683th Fibonacci term are 97