Addition Chains ZOJ - 1937

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.

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.

Sample Input

5
7
12
15
77
0

Sample Output

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

题意：n的加法链是一个整数序列<a0，a1，a2，…，am>，具有以下四个属性：
a0=1
am=n
a0<a1<a2<a2…<am-1<am
对于每个k（1<=k<=m），存在两个（不一定不同的）整数i和j（0<=i，j<=k-1），其中ak=ai+aj
我们给你一个整数n，你的任务是为n构造一个最小长度的加法链。如果有多个这样的序列，任何一个都可以接受。
思路：这个数列增长最快的话是可以到指数级别的，而n只有100.所以我们考虑一下迭代加深。还有我们可以从大到小枚举前面的数，可以更快的达到N。
当当当~~~

AC代码如下：

#include<stdio.h>
int a[1100],c[1100],w[1100],n,minn;
void dfs(int step)
{
    if(step>=minn)return;//剪枝
    if(a[step-1]==n)
    {
        minn=step;
        for(int i=1;i<step;i++)
            w[i]=a[i];
        return;
    }
    int s[1100],k=0;
     for(int i=step-1;i>=1;i--)//必须这样写，节省时间
        for(int j=i;j>=1;j--)
    {
        if(a[i]+a[j]<=a[step-1])break;//直接退出
        if(a[i]+a[j]<=n)
            s[k++]=a[i]+a[j];
    }
    for(int i=0;i<=k-1;i++)// 从后往前搜，时间复杂度会降低很多
    {
        a[step]=s[i];
        dfs(step+1);
    }
    return;
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        minn=0x3f3f3f3f;
        a[1]=1;//从一开始
        dfs(2);
        for(int i=1;i<minn-1;i++)
            printf("%d ",w[i]);
        printf("%dn",w[minn-1]);
    }
    return 0;
}```

最后

以上就是丰富小鸽子为你收集整理的Addition Chains ZOJ - 1937 详细的解释Addition Chains ZOJ - 1937的全部内容，希望文章能够帮你解决Addition Chains ZOJ - 1937 详细的解释Addition Chains ZOJ - 1937所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。