POJ2248 Addition Chains（迭代加深搜索+剪枝）
Addition Chains
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 6216 | Accepted: 3226 | Special Judge | ||
Description
An addition chain for n is an integer sequence <a0, a1,a2,...,am="">with the following four properties:
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.
- 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.
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
The input will contain one or more test cases. Each test case consists of one line containing one integer n (1<=n<=100). Input is terminated by a value of zero (0) for n.
Output
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.
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
Source
题目的大意就是说要你构造一个递增序列，保证序列第一项为1，最后一项为n，且要保证除了第一项外的每一项A[i],都有A[j]和A[k]，j,k<i，j可以等于k，使得A[j]+A[k]=A[i]。而且你要让长度尽可能小。
迭代加深搜索，因为n不大，而且是一定会有结果的，只是长度的问题，至于长度有多长，枚举呗，对于每一个长度，用所构造的数组的最后一项去加数组每一项，长度超过规定的不要，最后一项比n大的不要，把得到的数字加在所构造的数组的后面，一旦某一长度得出了结果，这就是最小长度，输出构造的数组就行了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 int cnt,ans; 6 bool flg; 7 void bfs(int A[],int n) 8 { 9 if(flg) return ; 10 if(A[n]==ans) 11 { 12 for(int i=0;i<=n;i++) 13 { 14 printf("%d",A[i]); 15 if(i==n) printf("\n"); 16 else printf(" "); 17 } 18 flg=true; 19 return ; 20 } 21 if(n==cnt) return ; 22 int tmp; 23 for(int i=0;i<=n;i++) 24 { 25 tmp=A[n]+A[i]; 26 if(tmp>ans) break; 27 A[n+1]=tmp; 28 bfs(A,n+1); 29 } 30 } 31 int main() 32 { 33 int n; 34 int A[100005]; 35 while(~scanf("%d",&n)&&n) 36 { 37 ans=n; 38 memset(A,0,sizeof A); 39 A[0]=1; 40 flg=false; 41 for(cnt=1;;cnt++) 42 { 43 bfs(A,0); 44 if(flg) break; 45 } 46 } 47 return 0; 48 }
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。