首页 > 代码库 > 2541 幂运算
2541 幂运算
2541 幂运算
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
从m开始，我们只需要6次运算就可以计算出m31：
m2=m×m，m4=m2×m2，m8=m4×m4，m16=m8×m8，m32=m16×m16，m31=m32÷m。
请你找出从m开始，计算mn的最少运算次数。在运算的每一步，都应该是m的正整数次方，换句话说，类似m-3是不允许出现的。
输入描述 Input Description
输入为一个正整数n
输出描述 Output Description
输出为一个整数，为从m开始，计算mn的最少运算次数。
样例输入 Sample Input
样例1
1
样例2
31
样例3
70
样例输出 Sample Output
样例1
0
样例2
6
样例3
8
数据范围及提示 Data Size & Hint
n（1<=n<=1000）
数据没有问题，已经出现过的n次方可以直接调用
分类标签 Tags 点此展开
深度优先搜索 搜索
题解：
迭代加深搜索的含义：
就是dfs前，先规定好dfs的深度，如果到了这个深度还没有结果，就退出dfs，
没找到，在这个题目中深度就指的是计算的次数，实现规定好计算的次数，在这个次数内没有出现结果，就返回没找到，对于那种没有搜索边界的题目，可以这样做
因为这个题目没有说最多对计算多少次，那么如果对于一个结果一直dfs计算下去，不仅没有边界，而且计算的次数也不一定是最少次数。所以用迭代加深搜索。
这样，对于每次的搜索 我们限制最多能做几次运算
这样搜索的规模就大大减小
同样的维护已经得到的mi数组
数组的大小对应做了几次运算
加上几个剪枝：
如果mi中最大的<<(limit-k)都到不了n 搜索失败
生成新的mi的时候 尽量组合数大的 这样也可以减小规模
AC代码：
#include<cstdio>#define max(a,b) a>b?a:busing namespace std;const int N=101;int n,a[N];bool dfs(int k,int limit){ if(a[k]==n) return 1; if(k==limit) return 0; int maxx=0; for(int i=0;i<=k;i++) maxx=max(maxx,a[k]); /*剪枝，如果每次把指数*2，这是最大的增长方式，如果这样还是比n小，就退出吧*/ if(maxx<<(limit-k)<n) return 0; for(int i=k;i>=0;i--){/*这里采用倒序循环可以加快速度，先选出比较大的数计算，可以加快扩展速度*/ a[k+1]=a[i]+a[k]; if(dfs(k+1,limit)) return 1; a[k+1]=a[k]-a[i]; if(dfs(k+1,limit)) return 1; } return 0;}int find(){ if(n==1)return 0; a[0]=1; for(int i=1;i<=20;i++) if(dfs(0,i)) return i;/*依次加深深度*/}int main(){ scanf("%d",&n); printf("%d\n",find()); return 0;}
2541 幂运算
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。