撰写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
You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.
For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.</a0,>输入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.输出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.
样例输入
5 7 12 15 77 0
样例输出
1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77
题意：
x[1]=1;
x[m]=n;
x序列严格递增；
对于每个k(2<=k<=m)都存在两个整数i和j（1<=i,j<=k-1,i和j可以相等），使得x[k]=x[i]+x[j];
题解：
- 优化搜索顺序
- 为了让序列中的数尽快逼近n，在枚举i，j时从大到小枚举
- 排除等效冗余
- 对x[i]+x[j]进行判重
- 经过
题解观察分析我们发现，m不会大于10，直接迭代加深。 - 以下代码好像不是我自己的那版，我记得我写了个能A题目但是有bug的代码。
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B){
(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B){
(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='?'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='?')?-1:1;
ret=(c=='?')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
inline void outt(int x) {
if(x>9) outt(x/10);
putchar(x%10+'0');
}
int n,lim;
int x[20];
bool v[102];
bool dfs(int now){
if(now==lim){
if(x[now]==n)for(int i=1;i<=lim;i++)printf("%d%c",x[i],i==lim?'\n':' ');
return x[now]==n;
}
for(int i=now;i;--i){
for(int j=i;j;--j){
int num =x[i]+x[j];
if(num<=n&&num>x[now]&&!v[num]){
v[num]=1;
x[now+1]=num;
if(dfs(now+1))return true;
v[num]=0;
}
}
}
return 0;
}
int main()
{
x[1]=1;
while(scanf("%d",&n),n){
lim=1;
while(!dfs(1))memset(v,0,sizeof v),lim++;
}
return 0;
}