斐波那契数列的分解

Arce

#include<iostream>
#include<cmath>
#include<list>
#include<vector>
#include<fstream>
#include <map>
using namespace std;
 
void caculate_all(int data,vector<int>&tmp){//求出所有小于或等于待求解数的所有斐波那契数列
    int a = 1, b = 1,temp=0;
    tmp.push_back(a);
    tmp.push_back(b);
    for (int i = 0;; i++){
        b = a + b;
        a = b - a;
        if(data>=b)tmp.push_back(b);
        else break;
    }
}
 
void bfs(vector<int>&tmp, int data, vector<vector<int>>&total,int now,vector<int>&tp,int start){//深度回溯遍历所有解
    int size = tmp.size();
    for (int i =start; i < size; i++){
        if (i + 1 <size&&tmp[i] == tmp[i + 1])continue;
        if (now + tmp[i] == data){
            tp.push_back(tmp[i]);
            total.push_back(tp);
            tp.pop_back();
            return;//剪枝操作
        }
        if (now + tmp[i]<data){
            tp.push_back(tmp[i]);
            now += tmp[i];
            bfs(tmp,data, total, now, tp,i+1);
            tp.pop_back();
            now -= tmp[i];
        }
    }
}
 
void caculate_all_perm(vector<int>&tmp,int data,vector<vector<int>>&total){
    int size = tmp.size();
    int now=0,start=0;
    vector<int>tp;
    bfs(tmp, data, total,now,tp,0);
}
 
int main(){
    int data;
    cin>>data;
    vector<vector<int>>total;
    vector<int>tmp;
    while (data>0){
        tmp.clear();
        total.clear();
        caculate_all(data,tmp);
        caculate_all_perm(tmp,data,total);
        int t = total[0].size();
        for (int j = 1; j < total.size(); j++){
            if (t>total[j].size())t = total[j].size();
        }
        cout << t << endl;
        cin >> data;
    }
}

运行结果：