Fibonacci[山东省第七届ACM大学生程序设计竞赛 B题]

题目链接
Problem Description

Fibonacci numbers are well-known as follow:

Now given an integer N, please find out whether N can be represented as the sum of several Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.
Input

Multiple test cases, the first line is an integer T (T<=10000), indicating the number of test cases.
Each test case is a line with an integer N (1<=N<=10⁹).
Output

One line per case. If the answer don’t exist, output “-1” (without quotes). Otherwise, your answer should be formatted as “N=f1+f2+…+fn”. N indicates the given number and f1, f2, … , fn indicating the Fibonacci numbers in ascending order. If there are multiple ways, you can output any of them.

Sample Input

4
5
6
7
100

Sample Output

5=5
6=1+5
7=2+5
100=3+8+89

Hint

Source

“浪潮杯”山东省第七届ACM大学生程序设计竞赛

#include<bits/stdc++.h>
using namespace std;
//一般就是定义为最大的变量 + 10,开始定义为visited[44]错了多少次,我吉吉都付不清了......
long long int a,b,k,flag,f[50],fx[50],visited[50];
void dfs(long long int ans){
    //由于只需要输出一组,所以定义一个flag变量,如果已经进行完一组,直接返回if(flag)return;if(ans == b){
    flag = 1;printf("%lld=",b);for(int i = k - 1;i >= 0;i--){
    if(i == k - 1)printf("%lld",fx[i]);elseprintf("+%lld",fx[i]);}printf("\n");return;}for(int i = 44;i >= 1;i--){
    //从大往小找,节省时间//题目要求不能连续,即必须相差一个,因此!visited[i - 1] && !visited[i + 1]也必须要判断if(ans + f[i] <= b && !visited[i] && !visited[i - 1] && !visited[i + 1]){
    visited[i] = true;fx[k++] = f[i];dfs(ans + f[i]);if(flag)//如果进行完一组,直接返回,不用向下递归return;visited[i] = false;k--;//回溯}}return;
}
int main(){
    f[1] = 1,f[2] = 2;for(int i = 3;i <= 44;i++)f[i] = f[i - 1] + f[i - 2];//先进行打表while(~scanf("%lld",&a)){
    while(a--){
    memset(fx,0,sizeof(fx));memset(visited,0,sizeof(visited));scanf("%lld",&b);flag = 0,k = 0;dfs(0);if(!flag)printf("-1\n");}}return 0;
}