poj2248 Addition Chains--------dfs
#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>using namespace std;int n,MIN;int a[10005];int temp[10005];void dfs(int pos){ if(pos>=MIN) return ; for(int i=0;i<pos;i++) { int t=temp[i]+temp[pos-1]; if(t==n) { if(pos<MIN) { MIN=pos; for(int j=0;j<pos;j++) a[j]=temp[j]; } return ; } if(t<n) { temp[pos]=t; dfs(pos+1); temp[pos]=0; } }}int main(){ while(scanf("%d",&n),n) { if(n==1) {puts("1");continue;} memset(temp,0,sizeof(temp)); memset(a,0,sizeof(a)); a[0]=1; temp[0]=1; MIN=99999; dfs(1); for(int i=0;i<MIN;i++) { if(i==0) printf("%d",a[i]); else printf(" %d",a[i]); } printf(" %d",n); puts(""); }}
