问题描述

满足如下条件的序列X被称为“Addition Chains”:
1.$X[1]=1$
2.$X[m]=n$
3.$X[1]<X[2]<…<X[m-1]<X[m]$
4.对于每个k(2<=k<=m)都存在两个整数i,j(i,j可以相等),使得$X[k]=X[i]+X[j]$
给定一个整数n,找出符合条件长度最短的”Addition Chains”(有SPJ,输出符合要求即可)

输入

有多组数据,每组数据一个数n(n<=100)。以n=0结束输入

输出

每组数据一行,输出长度最短的“addition chains”。

思路

迭代加深搜索应该不难想到,这里就讲一下剪枝。

可以开一个vis数组记录某个数值有没有访问过,这样可以避免重复搜索某个数组。

还有另一个剪枝(但是我没有用),枚举i,j时可以从大到小枚举,这样可以优化搜索顺序,使序列中是数尽快逼近n。

代码

#include 
#include 
#include 
#define MAXN 105
using namespace std;

int n, m, num[MAXN];
bool vis[MAXN];

bool dfs(int x)
{
    if(x==m)
    {
        if(num[x]==n) return true;
        else return false;
    }
    for(int i=1; i<=x; i++)
    {
        for(int j=i; j<=x; j++)
        {
            int temp=num[i]+num[j];
            if(temp

发表评论

邮箱地址不会被公开。 必填项已用*标注