http://poj.org/problem?id=3134
给你一个n，让你从x出发只用乘除法，求最小的次数算出x^n，所有的使用乘方必须已知即曾经计算出来。
迭代加深搜索。n不超过1000，所以最深出现答案的层数不会太深，可以试用跌代加深搜索。即每次设定搜索层数，判断该层是否有解。若有解输出改成即可。需要剪枝操作。
31 int st[MAXN], top; 32 int n; 33 34 bool dfs(int num, int depth) { 35 if (num > depth) return false; 36 if (st[top] == n) return true; 37 if (st[top] << (depth - num) < n) return false; 38 top++; 39 rep(i, 0, top) { 40 st[top] = st[top - 1] + st[i]; 41 if (dfs(num + 1, depth)) return true; 42 st[top] = abs(st[top - 1] - st[i]); 43 if (dfs(num + 1, depth)) return true; 44 } 45 top--; 46 return false; 47 } 48 49 int main() { 50 while (cin >> n, n) { 51 rep(i, 0, MAXN) { 52 st[top = 0] = 1; 53 if (dfs(0, i)) { 54 cout << i << endl; 55 break; 56 } 57 } 58 } 59 return 0; 60 }
原文：http://www.cnblogs.com/baocong/p/6785070.html