uva 529(暴力求解)

题意：给出了n，求从1（a0）开始到n（am）的的一个数字序列，使a1 到 am中的每一个值都可以是这个值之前前某两个值（相等或不相等都可以）的和，求最短的序列。

题解：从前往后推，1 和 1 只能得到 2， 1 和 2 能得到 3 或 4， 1 2  3-> 4 5 6 、1 2 4 ->  5 6 8，递归寻找，长度从 log (2, n) 开始递增判断，符合情况输出。剪枝1: 保证每一个数放进数组时都比前一个数字大且小于等于n 。剪枝2： 如果当前长度为len，目标长度为k，当前数字乘2的len - k次方也小于n就不再考虑。

#include <stdio.h>
#include <string.h>
#include <math.h>
const int N = 20;

int n, flag, res[N];

int init() {
	memset(res, 0, sizeof(res));
	flag = 0;
}

void dfs(int cur, int tar) {
	if (res[cur - 1] == n && cur == tar + 1) {
		flag = 1;
		return;
	}
	if (flag)
		return;
	for (int i = 0; i < cur; i++)
		for (int j = i; j < cur; j++) {
			int temp = res[i] + res[j];
			int temp1 = temp * pow(2, tar - cur);
			if (temp > res[cur - 1] && temp1 >= n && temp <= n) {
				res[cur] = temp;
				dfs(cur + 1, tar);
				if (flag)
					return;
			}
		}
}

int main() {
	int i, j;
	while (scanf("%d", &n) && n) {
		init();
		for (i = 0;; i++)
			if (n <= pow(2, i))
				break;
		res[0] = 1;
		for (j = i;; j++) {
			dfs(1, j);
			if (flag)
				break;
		}
		printf("%d", res[0]);
		for (int k = 1; k < j + 1; k++)
			printf(" %d", res[k]);
		printf("\n");
	}
}