ในปัญหานี้ เราได้รับค่าจำนวนเต็ม N ภารกิจของเราคือ หาพจน์ที่ N ของเลขฟีโบนัชชีคู่
ชุดฟีโบนัชชีสร้างตัวเลขถัดไปโดยการบวกสองตัวเลขก่อนหน้า ชุดฟีโบนัชชีเริ่มจากสองตัวเลข - F0 และ F1 ค่าเริ่มต้นของ F0 และ F1 สามารถ取เป็น 0, 1 หรือ 1, 1 ตามลำดับ
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input : N = 4 Output : 144
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการใช้ข้อเท็จจริงว่าทุกๆ ตัวเลขที่สามในลำดับฟีโบนัชชีเป็นเลขคู่ และลำดับของเลขคู่ก็ยังปฏิบัติตามสูตรเวียนเกิด
สูตรเวียนเกิดสำหรับลำดับฟีโบนัชชีคู่คือ -
Ef(n)= 4Ef(n-1) + Ef(n-2) โดยที่ Ef(0)=0 และ Ef(1)=2
เรารู้ว่าทุกๆ ตัวเลขฟีโบนัชชีตัวที่สามเป็นเลขคู่ ดังนั้น f(n-3) และ f(n-6) ทั้งคู่เป็นเลขคู่ ดังนั้น เราจะพิจารณา f(n) เป็นองค์ประกอบที่ k และเรียกว่า Ef(k) หาก f(n) เป็น Ef(k) แล้ว f(n-3) คือเลขคู่ก่อนหน้า เรียกว่า Ef(k-1) และดังนั้น f(n-6) คือก่อนหน้าของ Ef(k-1) นั่นคือ Ef(k-2)
ดังนั้น f(n)=4f(n-3)+f(n-6)
หรือ Ef(k)=4Ef(k-1) + Ef(k-2)
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include<iostream> using namespace std; int findNthEvenFiboNum(int n){ if (n < 1) return n; if (n == 1) return 2; return ((4 * findNthEvenFiboNum(n-1)) + findNthEvenFiboNum(n- 2)); } int main (){ int n = 5; cout<<n<<"th even fibonacci number is "<<findNthEvenFiboNum(n); return 0; }
เอาต์พุต
5th even fibonacci number is 610
