2011年西北工业大学机试第一题

 

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int a[10005];
int n,m,book[1005] = {0};
bool flag = false;
void init(){
	//第一位一定要一个0，因为0+0+0+3+0+8+0+0+34=45，只有0可以重复出现
	//深度遍历每次必须加上一个数，加上0数值不变 
	a[0] = 0;
	a[1] = 1;
	a[2] = 1;
	int i = 2;
	while(a[i] < 10005){
		a[i+1] = a[i] + a[i-1];
		i++;
		m = i;
	}
	m--;
	//打印斐波那契数列，判断是否有误 
	for(int i = 0;i <= m;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
void dfs(int sum){
	if(sum == n){
		flag = true;//一定要加一个标记 
		return ;
	}else{
		for(int i = m;i >= 0;i--){
			if(sum + a[i] <= n&&book[i] == 0){
				if(i != 0){
					book[i] = 1;
				}
				dfs(sum + a[i]);
				if(flag){
					return ;//如果符合要求，后面不能再撤销标记了 
				}
				book[i] = 0;
			}
		}
	}
}
int main(){
	
	init();
	while(cin>>n&&n){
		
		
		flag = false;
		memset(book,0,sizeof(book));
		dfs(0);
		bool falg2 = false; 
		cout<<n<<"=";
		for(int i = m;i >= 0;i--){
		//	cout<<book[i]<<" ";
			if(book[i] == 1){
				if(falg2 == false){
					cout<<a[i];
					falg2 = true;
				}else{
					cout<<"+"<<a[i];
				}
			}
		}
		cout<<endl;
	}
	
	return 0;
}