题意
求 \(x\) 至少经过多少次操作可以得到 \(x^n\)。可以进行的合法操作包括：
1.将已经得到的两个数相乘；
2.将已经得到的两个数相除。
需要保证操作得到的数的幂次为正整数。
如，已经通过若干次操作得到了 \(x,x^2,x^4,x^8,x^6\)。此时 \(x^6*x^6,x^8*x^6,x^6÷x\) 就是合法的操作，但 \(x^4÷x^6\) 就不是合法次操作。
数据范围
\(1 \leq n \leq 1000\)。
思路
很显然是一道搜索题，但是直接爆搜的时间复杂度接近于 \(O(n!)\)。即使在爆搜的基础上加上一些常用的剪枝技巧，还是会超时。
此时就可以想到用迭代加深搜索（IDA*）求解。事实上，如果用二进制来表示 \(n\)，那么就存在一种期望次数为 \(O(\log n)\) 的变换方法。（例如 \(n=(110010)_2\)，先用 \(6\) 次操作得到最高位的 \(1\)，再通过 \(2\) 次操作将剩余两位上的 \(1\) 加上即可）
虽然这种变换方法不一定为最优解，但是保证了最优解的变换次数很少，这也是为什么本题可以用 IDA* 求解。
code：
#include<cstdio>
using namespace std;
const int N=20;
int n,a[N];
bool ok;
void IDA_star(int now,int step,int tot)
{
if(now==n)
{
ok=true;
return ;
}
if(step>tot||ok||now<=0||now<<(tot-step+1)<n) return ;//最后一个判断是可行性剪枝
a[step-1]=now;
for(int i=0;i<step;i++)
{
IDA_star(now+a[i],step+1,tot);
IDA_star(now-a[i],step+1,tot);
}
}
int main()
{
while(scanf("%d",&n),n)
{
int ans=0;ok=n==1;//特判 n=1 的情况
while(!ok) IDA_star(1,1,++ans);
printf("%d\n",ans);
}
return 0;
}