项目有关Fibonacci数

问题描述

我不得不写程序，将显示Fibonacci数的最小量其总和等于 K 数目的用户写入的程序。

因此​​，例如，用户写入 1070 而该程序会显示 987 89 -5 -1 （因为所有这些数字是斐波那契数（您可以添加或substract以获得所需的款项）。

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

我写了code，以获得0所有Fibonacci数为46。

 的#include＆LT;的iostream＆GT;
无符号长长Fibbo [47];
虚空preapare（）
{
        Fibbo [0] = 0;
        Fibbo [1] = 1;
        I = 2;
        而（ⅰ＆所述; 47）
        {
              Fibbo [I] = Fibbo [I  -  1] + Fibbo [I  -  2];
              我++;
        }
}
诠释的main（）
{
    preapare（）;
    INT K = 0;
    给std :: cin＆GT;＆GT; K表;
}
 

我会很高兴的任何帮助。您可以使用Fibonacci数多次随你便。例如，你可以做到1 + 1 + 1 + 1 + 1

解决方案

 的#include＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT; stdlib.h中＆GT;
使用名字空间std;

虚空prepare（矢量＆lt; INT＆GT;＆安培; fibos）{...} //大意，我们在OPS code见

INT findClosest（INT N，矢量＆lt; INT＆GT;＆安培; fibos）{//返回最近的斐波那契数为n
  INT F1 = 0;
  对于（标准::矢量＆lt; INT＆GT;：迭代它= fibos.begin（！）;它= fibos.end（）; ++吧）{
    如果（ABS（*它 -  N）其中，ABS（FI  -  N））{
      网络= *它;
    }
  }
  返回网络连接;
}

//算法：
//查找最接近的网络连接，增加了签署的条款
//降低N，调整的迹象，并调用递归
虚空之和（INT N，矢量＆lt; INT＆GT;＆安培; fibos，矢量＆lt; INT＆GT;与条款，INT标志= 1）{
  如果（N == 0）收益;
  INT F1 = findClosest（N，fibos）;
  terms.push_back（*号FI）;
  和（？ABS（N  -  FI），fibos，术语，正 -  Fi无线网络和GT; 0登录：-sign）;
}

诠释的main（）{
  矢量＆lt; int的＆GT; fibos;
  prepare（fibos）;
  矢量＆lt; int的＆GT;条款;
  INT N = 1070;
  和（N，fibos，术语）;
  COUT＆LT;＆LT; N'LT;＆LT; =;
  对于（标准::矢量＆lt; INT＆GT;：迭代它= terms.begin（！）;它= terms.end（）; ++吧）{
    COUT＆LT;＆LT; ＆LT;＆LT; *它;
  }
  COUT＆LT;＆LT; ENDL;
  返回0;
}
 

I am obliged to write program that will show minimal quantity of Fibonacci numbers which sum is equal to k number which user write into program.

So for example user writes 1070And the program will show 987 89 -5 -1 (because all of these numbers are Fibonacci numbers (you can add or substract to get desired sum).

I have problem to think about solution to this problem.

I wrote code to get all Fibonacci numbers from 0 to 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;
}

I will be glad for any help. You can use Fibonacci Number as many times as you will. For example you can do 1+1+1+1+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;
}

这篇关于项目有关Fibonacci数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！