Số hạng Fibonacci tối thiểu có tổng bằng K trong C ++

Trong bài toán này, chúng ta được cho một số K. Nhiệm vụ của chúng ta là tìm các số hạng Fibonacci nhỏ nhất có tổng bằng K .

Chuỗi Fibonacci tạo ra các số tiếp theo bằng cách thêm hai số trước đó. Chuỗi Fibonacci bắt đầu từ hai số - F0 &F1. Các giá trị ban đầu của F0 &F1 có thể được lấy tương ứng là 0, 1 hoặc 1, 1.

Chuỗi Fibonacci là 0 1 1 2 3 5 8 13

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

K = 5

Đầu ra

Giải thích

The sum 5 can be made using 3 and 2.

Phương pháp tiếp cận giải pháp

Bằng cách sử dụng số Fibonacci, chúng ta có thể nhận được tổng là bất kỳ số nào vì 1 là số Fibonacci. Cộng 1 n lần có thể cho tổng là n. Nhiệm vụ của chúng ta là giảm thiểu việc đếm số Fibonacci mang lại tổng. Chúng ta có thể đạt được giải pháp bằng cách lấy cơ sở từ vấn đề thay đổi tiền xu trong đó các đồng xu có giá trị số fibonacci. Trong ngôn ngữ lập trình, kỹ thuật để giải quyết vấn đề này được gọi là cách tiếp cận tham lam.

Lúc đầu, chúng tôi tính tổng các số Fibonacci cho đến khi nhỏ hơn hoặc bằng tổng n. Sau đó bắt đầu từ số hạng cuối cùng ta lấy số hạng n trừ đi cho đến khi n> số hạng thứ k. Và cạnh nhau, tăng số lượng các điều khoản. Tại điểm khi n

Thuật toán

Tạo một hàm để tính toán các số hạng Fibonacci.
Tính tất cả các số hạng Fibonacci nhỏ hơn hoặc bằng n.
Nếu số hạng tiếp theo lớn hơn n, không đẩy nó vào vector và trả về.
Tạo một hàm để tìm số thuật ngữ Fibonacci tối thiểu có tổng bằng n.
Khởi tạo một vectơ để lưu trữ các thuật ngữ Fibonacci.
Trừ các số hạng Fibonacci từ tổng n cho đến tổng> 0.
Chia tổng n cho số hạng Fibonacci thứ j để tìm số hạng đóng góp vào tổng.
In số lượng thu được dưới dạng đầu ra.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

Minimum Fibonacci terms with sum equal to K is 2