เราได้รับช่วงที่มีตัวเลขเริ่มต้นและสิ้นสุด และภารกิจคือการคำนวณจำนวนรวมของตัวเลขฟีโบนักชีที่มีอยู่ระหว่างช่วงที่กำหนดในเวลา O(Log n) และช่องว่าง O(1)
ตัวเลขฟีโบนักชีคืออะไร
ตัวเลขฟีโบนักชีคือลำดับของตัวเลขที่เรียกว่าลำดับฟีโบนักชี โดยที่ทุกจำนวนใหม่คือผลรวมของตัวเลขสองตัวที่อยู่ก่อนหน้า
โดยที่ f(0) =0 และ f(1) =1 เช่น f(0) และ f(1) มีตำแหน่งคงที่ในลำดับและการคำนวณจะเริ่มจากตัวเลขที่สาม
สูตรที่ใช้คำนวณลำดับคือ −
Fn =Fn-1 + Fn-2
ที่ไหน
F0 =0, F1 =ล
ตัวอย่างเช่น
Input − start = 6 and last = 100 Output − Number of fibonacci Numbers in the series are 6
คำอธิบาย − ตัวเลขฟีโบนักชีระหว่าง 6 ถึง 100 คือ 8, 13, 21, 34, 55, 89 เช่น จำนวนทั้งหมดคือ 6
Input − start = 0 and last = 8 Output − Number of fibonacci Numbers in the series are 7
คำอธิบาย − ตัวเลขฟีโบนักชีระหว่าง 0 ถึง 8 คือ 0, 1, 1, 2, 3, 5, 8 เช่น จำนวนทั้งหมดคือ 7
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
ป้อนตัวเลขเริ่มต้นและสิ้นสุดเพื่อสร้างช่วง
-
ประกาศและเริ่มต้น fib1 ถึง 0, fib2 ถึง 1, fib3 ถึง 1
-
ประกาศตัวแปรชั่วคราว res และเริ่มต้นด้วย 0
-
เริ่มลูปในขณะที่ fib1 น้อยกว่าหรือเท่ากับสิ้นสุด
-
ภายในลูป ตรวจสอบว่า fib1 มากกว่าหรือเท่ากับจุดเริ่มต้นแล้วเพิ่มความละเอียดขึ้น 1
-
ตั้งค่า fib1 เป็น fib2, fib2 เป็น fib3 และ fib3 เป็น fib1 + fib2
-
ผลตอบแทน
-
พิมพ์ผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
// function to count fibonacci numbers in range
// from start to last
int count_fibonacci(int start, int last){
// First three Fibonacci Numbers
int fib1 = 0, fib2 = 1, fib3 = 1;
// res to count the number of fibonacci
int res = 0;
while (fib1 <= last){
if (fib1 >= start){
res++;
}
fib1 = fib2;
fib2 = fib3;
fib3 = fib1 + fib2;
}
return res;
}
// main function
int main(){
int start = 6, last = 100;
cout << "Number of fibonacci Numbers in the series are "
<< count_fibonacci(start, last);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Number of fibonacci Numbers in the series are 6
