Addition Chains

83 阅读 0 评论 55 点赞

我是靠谱客的博主昏睡大船，最近开发中收集的这篇文章主要介绍Addition Chains，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

An addition chain for n is an integer sequence <a0, a1,a2,…,am> with the following four properties:

a0 = 1
am = n
a0 < a1 < a2 < … < am-1 < am
For each k (1 <= k <= m) there exist two (not necessarily different) integers i and j (0 <= i, j <= k-1) 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.

solution

iddfs入门题
iddfs就是限制dfs的深度，然后加减枝，当然一定要保证有解。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=10005;
int a[N],n,m,dep;
int p[30];
void work(int t){
	printf("%d",1);
	fo(i,1,t) {
		printf(" %d",a[i]);
	}
	printf("n");
}
bool dfs(int x){
	if (x-1==dep) return a[x-1]==n;
	fd(i,x-1,0) {
		fd(j,i,0){
			a[x]=a[i]+a[j];
			if (a[x]>n) continue;
			if (a[x]<=a[x-1]) break;
			if (a[x]*p[dep-x]<n)  return 0;
			if (dfs(x+1)) return 1;
		}
	}
	return 0;
}
int main(){
//	freopen("data.in","r",stdin);
	
	p[0]=1; fo(i,1,20) p[i]=p[i-1]*2;
	
	while (scanf("%d",&n) && n){
		
		a[0]=1; 
		m=n; dep=0;
		while (m){
			m/=2; dep++;
		}
		
		dep--;
		
		for(;;){
			if (dfs(1)) {
				work(dep);
				break;
			}
			dep++;
		}
	
	}
}