首页 > 代码库 > POJ 3134 IDDFS
POJ 3134 IDDFS
链接：
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 }
POJ 3134 IDDFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。