C++迭代加深——Addition Chains（ZOJ 1937）详解引言题目描述 Addition Chains思路详解代码

69 阅读 0 评论 46 点赞

我是靠谱客的博主紧张唇膏，最近开发中收集的这篇文章主要介绍C++迭代加深——Addition Chains（ZOJ 1937）详解引言题目描述 Addition Chains思路详解代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

引言

茕茕孑立，迭代加深。。。

题目描述

Addition Chains

已知一个数列（其中）。对于每个，需要满足（，这里  与  可以相等）。

现给定  的值，要求  的最小值（并不要求输出），及这个数列每一项的值（可能存在多个数列，只输出任一个满足条件的就可以了）。

输入格式

多组数据，每行给定一个正整数  。

输入以  结束。

输出格式

对于每组数据，输出满足条件的长度最小的数列。

样例

样例输入
5
7
12
15
77
0
样例输出
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 小于等于 100

思路详解

一拿到这道好题，就可以知道，搜索！那该怎么搜？爆搜？非也，就要用到迭代加深

他既要搜索又要深度小，那么就用迭代加深，限制一个深度，如果不行，限制放大，一次一次的进行搜索

首先初始化 a[1] = 1 , a[2] = 2 , 然后要让一个 a[x] = a[i] + a[j] ，且最后一项为 n，项数又要最小

先用贪心思想，要最小，每一个 a[i] 都为前一个数两倍，求出贪心的最小长度


while( a[1] < n ) {
		a[1] *= 2 ;
		len ++ ;
	}

然后就慢慢地进行搜索...

每一次在当前层搜索正解，如果不行，长度增加、

for( len ; ; ++ len ) {
			dfs( 1 );
			if( flag )
				break;
		}

最后就是搜索部分我们知道，要让这个序列成立，那么这个就需要是递增的，即 a[dep+1] > a[dep] ，那么搜索枚举 a[dep+1] 时，必须保证 a[i] + a[j] > a[dep] ，且 a[dep+1] 后的最后项的最大值不能小于 n

代码

理解消化啊啊啊

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int n , a[10007] , len ;
bool flag ;

void dfs( int dep ) {
	if( dep > len ) return ;
	if( dep == len && a[dep] == n ) {//找到解
		for(int i = 1 ; i <= dep ; ++ i ) 
			printf("%d ", a[i] );
		printf("n");
		flag = 1 ;
		return ;
	}
	for(int i = dep ; i >= 1 ; -- i ) {//枚举 a[dep+1] 的组成
		for(int j = dep ; j >= i ; -- j ) {
			if( a[i]+a[j] > a[dep] && a[i]+a[j] <= n ) {//是否成立
				a[dep+1] = a[i]+a[j] ;
				int x = a[dep+1] ;
				for(int k = dep+2 ; k <= len ; ++ k )//最后一项的最大值
					x *= 2 ;
				if( x < n )//剪枝
					continue ;
				dfs( dep+1 );
				if( flag ) return ;
			}
		}
	}
}

int main()
{
	while( scanf("%d", &n ) != EOF ) {
		len = 1 ;
		memset( a , 0 , sizeof( a ) );
		a[1] = 1 ;
		a[2] = 2 ;
		if( n == 0 )
			break;
		int x = 1 ;
		while( x < n ) {//最小的长度
			x *= 2 ;
			len ++ ;
		}
		for( len ; ; ++ len ) {//迭代加深
			dfs( 1 );
			if( flag )
				break;
		}
		flag = 0 ;
	}
	return 0;
}