ในปัญหานี้ เราได้รับค่าจำนวนเต็ม N ภารกิจของเราคือการใช้ โปรแกรม C++ หาพจน์ที่ N ของเลขไม่ใช่ฟีโบนัชชี
ชุดฟีโบนัชชีสร้างตัวเลขถัดไปโดยการบวกสองตัวเลขก่อนหน้า ชุดฟีโบนัชชีเริ่มจากสองตัวเลข - F0 และ F1 ค่าเริ่มต้นของ F0 และ F1 สามารถ取เป็น 0, 1 หรือ 1, 1 ตามลำดับ
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
N = 5
เอาต์พุต
10
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการหาตัวเลขฟีโบนัชชีแล้วพิมพ์ตัวเลข n ตัวแรกที่ไม่อยู่ในตัวเลขฟีโบนัชชี
อีกวิธีหนึ่งคือการใช้สูตรตัวเลขฟีโบนัชชีแล้วค่อยๆ บวกช่องว่างระหว่างสองตัวเลขฟีโบนัชชีติดกัน ในที่สุด ค่าของผลรวมของช่องว่างทั้งหมดจะได้ผลลัพธ์ที่ต้องการ ที่นี่เราจะใช้แนวคิดที่สมเหตุสมผลสำหรับการแก้ปัญหา
อัลกอริทึม
สร้างตัวแปรสามตัวที่จะติดตามองค์ประกอบปัจจุบัน องค์ประกอบก่อนหน้า และองค์ประกอบก่อนหน้าสองครั้ง
ในขณะที่จำนวนเลขไม่ใช่ฟีโบนัชชียังไม่เป็นลบ ใช้สูตรง่ายของตัวเลขฟีโบนัชชี - Fib(n)=Fib(n-1)+Fib(n-2)
เพื่อให้ได้จำนวนเลขไม่ใช่ฟีโบนัชชีโดยใช้สูตร n=n+(curr-prev-1)
ตอนนี้เพื่อให้ได้เลขไม่ใช่ฟีโบนัชชีตัวที่ n ให้ลบตัวเลขก่อนหน้าออกจาก n
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include<iostream> using namespace std; int findNthNonFiboNumber(int n){ int lastLastVal = 1, lastVal = 2, currVal = 3; while (n > 0){ lastLastVal = lastVal; lastVal = currVal; currVal = lastLastVal + lastVal; n = n - (currVal - lastVal - 1); } n = n + (currVal - lastVal - 1); return (lastVal + n); } int main(){ int n = 7; cout<<"Nth non fibonacci number is "<<findNthNonFiboNumber(n); return 0; }
เอาต์พุต
Nth non fibonacci number is 12
