UVA 529 Addition Chains（迭代搜索）

Addition Chains

An addition chain for n is an integer sequence  with the following four properties:

• a₀ = 1
• a_m = n
• a₀<a₁<a₂<...<a_m-1<a_m
• For each k ( ) there exist two (not neccessarily different) integers i and j ( ) with a_k =a_i +a_j

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 Specification

The input file will contain one or more test cases. Each test case consists of one line containing one integer  n  (  ). Input is terminated by a value of zero (0) for  n .

Output Specification

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

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，要求求出这样一条最短的满足以下条件的加法链：

1、起点为1，终点为n， 2、递增 3、每个数字可以找到该链中其他两个数字相加组成

思路：本来我的思路是直接暴力的。。果断超时。大一点的数据都跑不出来。。原因是如果直接搜。加法链的个数没有限制，直接要多很多不必要的搜索。

然后在网上看到了一种迭代搜索法。是先确定一个最小的条件。在本题中，仔细观察不难发现，如果每次都是以两倍的趋势上升，那么加法链将会最短。那么由最短的这个条件开始，进行搜索，如果这个条件搜不到，就把条件+1，继续搜索。直到出现一个满足条件的方案结束。。

不过这题要多一个优化。举个例子。比如n为16时。最短条件为5.前3个数字为1 2 3时候，最大将只能为1 2 3 6 12，是到不了16的，因此可以发现。如果一个数字，不断乘2直到到达那个条件。如果小于n，那么这条搜索多余的，直接返回。

#include <stdio.h>
#include <string.h>

int n;
int ci;
int judge;
int out[10005];
void dfs(int num)
{
    if (judge)
	return;
    if (num == ci)
    {
	if (out[num] == n)
	{
	    judge = 1;
	}
	return;
    }
    for (int i = num; i >= 0; i --)
    {
	for (int j = num; j >= i; j --)
	{
	    if (out[i] + out[j] > out[num] && out[i] + out[j] <= n)
	    {
		int sum = out[i] + out[j];
		for (int k = num + 1; k <= ci; k ++)
		{
		    sum *= 2;
		}
		if (sum < n)
		    continue;
		out[num + 1] = out[i] + out[j];
		dfs(num + 1);
		if (judge)
		    return;
	    }
	}
    }
}
int main()
{
    while (scanf("%d", &n) != EOF && n)
    {
	judge = 0;
	ci = 0;
	int sb = 1;
	while (sb < n)
	{
	    sb *= 2;
	    ci ++;
	}
	while (1)
	{
	    memset(out, 0, sizeof(out));
	    out[0] = 1;
	    dfs(0);
	    if (judge)
		break;
	    ci ++;
	}
	for (int i = 0; i < ci; i ++)
	{
	    printf("%d ", out[i]);
	}
	printf("%d\n", out[ci]);
    }
    return 0;
}

但是这个写法还是有一定问题的。。我测试了一些数据。如1111.还是要跑好一会的。。不过没超时。估计是数据的问题。。然后看了别人的代码。写了另一个。这个方法是先确定一个上限。每次找到后，把上限进行缩小。直到找到最小为止。。

#include <stdio.h>
#include <string.h>

int n;
int end;
int num[35];
int output[35];
void dfs(int star)
{
    if (star < end)
    {
	for (int i = star - 1; i >= 0; i --)
	{
	    int sum = num[star - 1] + num[i];
	    if (sum <= n)
	    {
		num[star] = sum;
		if (num[star] == n && end > star)
		{
		    for (int j = 0; j <= end; j ++)
		    {
			output[j] = num[j];
		    }
		    end = star;
		}
		int sb = sum;
		for (int j = star + 1; j <= end; j ++)
		    sb *= 2;
		if (sb < n)
		    continue;
		dfs(star + 1);
	    }

	}
    }
}
int main()
{
    while (scanf("%d", &n) != EOF && n)
    {
	memset(num, 0, sizeof(num));
	memset(output, 0, sizeof(output));
	if (n == 1)
	{
	    end = 0;
	    output[0] = 1;
	}
	else
	    end = 30;
	num[0] = 1;
	dfs(1);
	for (int i = 0; i < end; i ++)
	    printf("%d ", output[i]);
	printf("%d\n", output[end]);
    }
    return 0;
}