ในปัญหานี้ เราได้รับตัวเลข K หน้าที่ของเราคือ ค้นหาเงื่อนไข Fibonacci ขั้นต่ำที่มีผลรวมเท่ากับ K .
Fibonacci Series สร้างตัวเลขที่ตามมาด้วยการบวกตัวเลขก่อนหน้าสองตัว อนุกรมฟีโบนักชีเริ่มต้นจากตัวเลขสองตัว - F0 &F1 ค่าเริ่มต้นของ F0 &F1 สามารถรับได้ 0, 1 หรือ 1, 1 ตามลำดับ
Fibonacci Series คือ 0 1 1 2 3 5 8 13
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
K = 5
ผลผลิต
2
คำอธิบาย
The sum 5 can be made using 3 and 2.
แนวทางการแก้ปัญหา
โดยใช้ตัวเลขฟีโบนักชี เราจะได้รับผลรวมเป็นตัวเลขใดๆ เนื่องจาก 1 เป็นจำนวนฟีโบนักชี การบวก 1 n ครั้งสามารถให้ผลรวมเป็น n งานของเราคือการลดจำนวนตัวเลขฟีโบนักชีที่ให้ผลรวม เราสามารถแก้ไขปัญหาได้โดยการนำฐานจากปัญหาการเปลี่ยนเหรียญที่เหรียญมีค่าตัวเลขฟีโบนักชี ในภาษาการเขียนโปรแกรม เทคนิคในการแก้ปัญหานี้เรียกว่าวิธีการโลภ
ในตอนแรก เรารวมตัวเลขฟีโบนักชีจนน้อยกว่าหรือเท่ากับผลรวม n จากนั้นเริ่มจากเทอมสุดท้าย เราลบเทอมนั้นจาก n ถึง n>k เทอม และเพิ่มจำนวนเทอมควบคู่กันไป เมื่อถึงจุดที่ n
สร้างฟังก์ชันเพื่อคำนวณเงื่อนไขฟีโบนักชี
คำนวณเงื่อนไขฟีโบนักชีทั้งหมดที่น้อยกว่าหรือเท่ากับ n
หากเทอมถัดไปมากกว่า n อย่าผลักมันในเวกเตอร์แล้วย้อนกลับ
สร้างฟังก์ชันเพื่อค้นหาจำนวนเงื่อนไขฟีโบนักชีขั้นต่ำที่มีผลรวมเท่ากับ n
เริ่มต้นเวกเตอร์เพื่อเก็บเงื่อนไขฟีโบนักชี
ลบเงื่อนไขฟีโบนักชีจากผลรวม n จนถึงผลรวม>0
หารผลรวม n ด้วยเทอม Fibonacci เพื่อหาจำนวนพจน์ที่ส่งผลต่อผลรวม
พิมพ์จำนวนที่ได้รับเป็นผลลัพธ์
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเราอัลกอริทึม
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void findFiboTerms(vector<int>& fiboVals, int K){
int i = 3, nextTerm;
fiboVals.push_back(0);
fiboVals.push_back(1);
fiboVals.push_back(1);
while (1) {
nextTerm = fiboVals[i - 1] + fiboVals[i - 2];
if (nextTerm > K)
return;
fiboVals.push_back(nextTerm);
i++;
}
}
int findTermForSum(int K){
vector<int> fiboVals;
findFiboTerms(fiboVals, K);
int termCount = 0, j = fiboVals.size() - 1;
while (K > 0) {
termCount += (K / fiboVals[j]);
K %= (fiboVals[j]);
j--;
}
return termCount;
}
int main(){
int K = 11;
cout<<"Minimum Fibonacci terms with sum equal to K is "<<findTermForSum(K);
return 0;
} ผลลัพธ์
Minimum Fibonacci terms with sum equal to K is 2
