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