UVA 529 Addition Chains(迭代搜索)

  Addition Chains 

An addition chain for n is an integer sequence UVA 529 Addition Chains(迭代搜索) with the following four properties:

  • a0 = 1
  • am = n
  • a0<a1<a2<...<am-1<am
  • For each k ( UVA 529 Addition Chains(迭代搜索)) there exist two (not neccessarily different) integers i and j ( UVA 529 Addition Chains(迭代搜索)) 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 Specification

The input file will contain one or more test cases. Each test case consists of one line containing one integer  n  (  UVA 529 Addition Chains(迭代搜索) ). 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;
}
上一篇:Spring 属性注入(四)属性键值对 - PropertyValue


下一篇:ftp下载目录下所有文件及文件夹内(递归)