home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

โปรแกรม C++ เพื่อค้นหา Nth Non Fibonacci Number

ในปัญหานี้ เราได้รับค่าจำนวนเต็ม N งานของเราคือการใช้โปรแกรม C + + เพื่อค้นหา Nth Non Fibonacci Number .

Fibonacci Series สร้างตัวเลขที่ตามมาด้วยการบวกตัวเลขก่อนหน้าสองตัว อนุกรมฟีโบนักชีเริ่มต้นจากตัวเลขสองตัว - 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 ที่ไม่ใช่ Fibonacci ลบจำนวนก่อนหน้าออกจาก 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