Description
An addition chain for n is an integer sequence <a0, a1,a2,...,am="">with the following four properties:
- a0 = 1
- am = n
- a0 < a1 < a2 < ... < am-1 < am
- For each k (1<=k<=m) there exist two (not necessarily different) integers i and j (0<=i, j<=k-1) with ak=ai+aj
Input
The input will contain one or more test cases. Each test case consists of one line containing one integer n (1<=n<=100). Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line containing the required integer sequence. Separate the numbers by one blank. Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.
Sample Input
571215770
Sample Output
1 2 4 51 2 4 6 71 2 4 8 121 2 4 5 10 151 2 4 8 9 17 34 68 77 迭代加深,注意剪枝(见代码中):
#include<iostream>
#include<cstdio>#include<cstring>using namespace std;bool q=false;int n,best,deep;int v[105],ans[105];void dfs(int x){ if(q==false)//这里一定要判断,不然超时(读者自行思考) { if(v[x]==n) { best=x; for(int i=0;i<=x;i++) ans[i]=v[i]; q=true; return ; } else if(x<deep) { for(int i=x;i>=0;i--) { if(v[i]*2>v[x])//剪枝1 for(int j=x;j>=0;j--) if(v[i]+v[j]>=v[x]&&v[i]+v[j]<=n)//剪枝2 { v[x+1]=v[i]+v[j]; dfs(x+1); } } } } return ;}int main(){ while(~scanf("%d",&n)&&n>0) { memset(v,0,sizeof(v)); memset(ans,0,sizeof(ans)); q=false; deep=1;best=n; while(q==false) { v[0]=1; dfs(0); deep++; } for(int i=0;i<=best;i++) printf("%d ",ans[i]); printf("\n"); } return 0;}