이 문제에서는 숫자 K가 주어집니다. 우리의 임무는 합이 K와 같은 최소 피보나치 항을 찾는 것입니다. .
피보나치 수열은 두 개의 이전 숫자를 더하여 후속 숫자를 생성합니다. 피보나치 수열은 F0과 F1의 두 숫자로 시작합니다. F0 및 F1의 초기 값은 각각 0, 1 또는 1, 1을 취할 수 있습니다.
피보나치 수열은 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>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