C++에서 합이 K와 같은 최소 피보나치 항

<시간/>

이 문제에서는 숫자 K가 주어집니다. 우리의 임무는 합이 K와 같은 최소 피보나치 항을 찾는 것입니다. .

피보나치 수열은 두 개의 이전 숫자를 더하여 후속 숫자를 생성합니다. 피보나치 수열은 F0과 F1의 두 숫자로 시작합니다. F0 및 F1의 초기 값은 각각 0, 1 또는 1, 1을 취할 수 있습니다.

피보나치 수열은 0 1 1 2 3 5 8 13입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

K = 5

출력

설명

The sum 5 can be made using 3 and 2.

해결 방법

피보나치 수를 사용하면 1이 피보나치 수이므로 모든 수의 합을 얻을 수 있습니다. 1 n 번 더하면 합이 n이 될 수 있습니다. 우리의 임무는 합을 제공하는 피보나치 수의 개수를 최소화하는 것입니다. 동전이 피보나치 수 값을 갖는 동전 변경 문제에서 기반을 취하여 솔루션을 달성할 수 있습니다. 프로그래밍 언어에서는 이 문제를 해결하는 기술을 탐욕적 접근이라고 합니다.

처음에는 합 n보다 작거나 같을 때까지 피보나치 수를 합산합니다. 그런 다음 마지막 항에서 시작하여 n>k번째 항이 될 때까지 n에서 해당 항을 뺍니다. 그리고 나란히 용어 수를 늘립니다. 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