UVA - 1374 Power Calculus(IDA*+剪枝)

本文主要是介绍UVA - 1374 Power Calculus(IDA*+剪枝)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
题意

求最少需要几次乘除法可以从x得到x^n?

思路

也就是求1经过最少加减可以得出n
序列初始只有1，每次选任意两数进行加减，加入序列
使用IDA*迭代加深搜索

剪枝条件

当前序列最大值*(2^max-步数) < n 即后边步数一直按最快的求法仍然比n小

优化方案

1.迭代的max值不从1开始，而是从log(n)开始
2.每次只对最大值进行加减操作
3.当最大值大于n时只进行减操作

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;int d[1001];
bool f[2001];
int len;
int m;bool ida_star(int n, int max, int now)
{if(now > max ||m*(1<<(max-now)) < n)return false;if(f[n])return true;for(int i = len-1; i >= 0 && m < n; --i){if(!f[d[i]+m]){m += d[i];d[len++] = m;f[m] = 1;if(ida_star(n, max, now+1))return true;len--;f[m] = 0;m -= d[i];}}for(int i = 0; i < len ; ++i){if(!f[m - d[i]]){d[len++] = m - d[i];f[m - d[i]] = 1;if(ida_star(n, max, now+1))return true;len--;f[m - d[i]] = 0;}}return false;
}int init(int n)
{int ans = 0;int p = 1;while(p <= n){++ans;p <<= 1;}return ans;
}int main()
{int i;while(cin>>i && i){for(int j = init(i); ; ++j){memset(f, 0, sizeof(f));len = m = d[0] = f[1] = f[0] = 1;if(ida_star(i, j, 0)){cout<<j<<endl;break;}}}return 0;
}

这篇关于UVA - 1374 Power Calculus(IDA*+剪枝)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---