c++ - 关于斐波那契数列的程序

Question

我必须编写程序来显示最小数量的斐波那契数，总和等于用户写入程序的 k 数。

例如用户写1070并且程序将显示 987 89 -5 -1(因为所有这些数字都是斐波那契数列(您可以添加或减去以获得所需的总和)。

我有问题想解决这个问题。

我编写了代码来获取从 0 到 46 的所有斐波那契数。

#include <iostream>
unsigned long long Fibbo[47];
void preapare()
{
        Fibbo[0] = 0;
        Fibbo[1] = 1;
        i = 2;
        while (i<47)
        {
              Fibbo[i] = Fibbo[i - 1] + Fibbo[i - 2];
              i++;
        }    
}
int main()
{
    preapare();
    int k=0;
    std::cin >> k;
}

我很乐意提供任何帮助。您可以多次使用斐波那契数列。例如你可以做 1+1+1+1+1

Answer 1

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;

void prepare( vector<int> & fibos ) {  ... }  // along the lines we see in OPs code

int findClosest( int n, vector<int> & fibos ){ // return Fibonacci number closest to n
  int fi = 0;
  for( std::vector<int>::iterator it = fibos.begin() ; it != fibos.end(); ++it){
    if( abs(*it - n) < abs(fi - n) ){
      fi = *it;
    }
  }
  return fi;
}

// The algorithm:
// lookup closest Fi, add "signed" to terms
// reduce n, adjust sign and call recursively 
void sum( int n, vector<int> & fibos, vector<int> & terms, int sign = 1 ){
  if( n == 0 ) return;
  int fi = findClosest( n, fibos );
  terms.push_back( sign*fi );
  sum( abs(n - fi), fibos, terms, n - fi > 0 ? sign : -sign );
}

int main() {
  vector<int> fibos;
  prepare( fibos );
  vector<int> terms;
  int n = 1070;
  sum( n, fibos, terms );
  cout << n << " =";
  for( std::vector<int>::iterator it = terms.begin() ; it != terms.end(); ++it){
    cout << " " << *it;
  }
  cout << endl; 
  return 0;
}