ในปัญหานี้ เราได้รับตัวเลข K ภารกิจของเราคือ หาพจน์ฟีโบนัชชีขั้นต่ำที่ผลรวมเท่ากับ K
ชุดฟีโบนัชชีสร้างตัวเลขถัดไปโดยการบวกสองตัวเลขก่อนหน้า ชุดฟีโบนัชชีเริ่มจากสองตัวเลข - F0 และ F1 ค่าเริ่มต้นของ F0 และ F1 สามารถ取เป็น 0, 1 หรือ 1, 1 ตามลำดับ
ชุดฟีโบนัชชีคือ 0 1 1 2 3 5 8 13
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
K = 5
เอาต์พุต
2
คำอธิบาย
ผลรวม 5 สามารถทำได้โดยใช้ 3 และ 2
วิธีการแก้ปัญหา
ด้วยการใช้ตัวเลขฟีโบนัชชี เราสามารถได้ผลรวมเป็นตัวเลขใดก็ได้เพราะ 1 เป็นตัวเลขฟีโบนัชชี การบวก 1 n ครั้งสามารถให้ผลรวมเป็น n ภารกิจของเราคือลดจำนวนตัวเลขฟีโบนัชชีที่ให้ผลรวม เราสามารถบรรลุคำตอบโดยใช้ฐานจากปัญหาเหรียญกึ่งหนึ่งที่เหรียญมีค่าเป็นตัวเลขฟีโบนัชชี ในภาษาโปรแกรม เทคนิคการแก้ปัญหานี้เรียกว่า greedy approach
ในตอนแรก เราบวกตัวเลขฟีโบนัชชีจนกว่าจะน้อยกว่าหรือเท่ากับผลรวม n จากนั้นเริ่มจากพจน์สุดท้าย เราลบพจน์นั้นออกจาก n จนกว่า n > พจน์ที่ k และนับจำนวนพจน์ไปด้วย เมื่อ n < พจน์ที่ k ให้ไปยังพจน์ฟีโบนัชชีที่อยู่ติดกันซึ่งน้อยกว่าหรือเท่ากับ n และพิมพ์ค่าของจำนวนนั้น
อัลกอริทึม
สร้างฟังก์ชันคำนวณพจน์ฟีโบนัชชี
คำนวณพจน์ฟีโบนัชชีทั้งหมดที่น้อยกว่าหรือเท่ากับ n
ถ้าพจน์ถัดไปมากกว่า n อย่าใส่ในเวกเตอร์และคืนค่า
สร้างฟังก์ชันหาจำนวนพจน์ฟีโบนัชชีขั้นต่ำที่ผลรวมเท่ากับ n
เริ่มต้นเวกเตอร์เก็บพจน์ฟีโบนัชชี
ลบพจน์ฟีโบนัชชีออกจากผลรวม n จนกว่าผลรวม > 0
หารผลรวม n ด้วยพจน์ฟีโบนัชชีที่ j เพื่อหาจำนวนพจน์ที่มีส่วนร่วมในผลรวม
พิมพ์จำนวนที่ได้เป็นผลลัพธ์
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#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
