ในปัญหานี้ เราได้รับหมายเลข N หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาหลักสุดท้ายของหมายเลข Nth Fibonacci ใน C++
คำอธิบายปัญหา
เราจำเป็นต้องค้นหาตัวเลขสุดท้าย (เช่น LSB ) ของหมายเลข Fibonacci ที่ N
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต:N =120 เอาต์พุต:1
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ ก็คือการใช้สูตรฟีโบนักชีโดยตรงเพื่อค้นหาเทอมที่ N แต่วิธีนี้จะเป็นไปไม่ได้เมื่อ N เป็นจำนวนที่มาก เพื่อเอาชนะสิ่งนี้ เราจะใช้คุณสมบัติของ Fibonacci Series ที่หลักสุดท้ายซ้ำตัวเองหลังจาก 60 เทอม เช่น. หลักสุดท้ายของเทอมที่ 75 เหมือนกับของเทอมที่ 135
ซึ่งหมายความว่าการทำงานจนถึง 60 จะทำให้เรามีชุดค่าผสมที่เป็นไปได้ทั้งหมด และเพื่อค้นหาคำที่จะใช้ เราจะพบม็อดของตัวเลขที่มี 60
ตัวอย่าง
#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;
} ผลลัพธ์
The last digit of 683th Fibonacci term is 1
