题意：输入正整数n(1<=n<=1000)，问最少需要几次乘除法可以从x得到x的n次方，计算过程中x的指数要求是正的。
题解：这道题，他的结果是由1经过n次加减得到的，所以最先想到的就是暴力回溯，其中的剪枝函数，首先不能得到重复的数，其次深度有上限，上限是n-1,还有，如果当前序列的最大数乘以2的(dep-cnt)(dep与cnt分别表示深度上限和当前深度)次方小于n，则剪枝。但是这样的时间复杂度还是特别高，所以又想到了另外的方法，就是先列出深度，然后找在这个深度里是否存在一个方法得到n
代码：
#include<math.h>
#include<vector>
#include<string.h>
#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=;
int n,minn,dep;
int ans[maxn]; bool dfs(int num,int cnt){
if(cnt==dep){
if(num==n)
return ;
return ;
}
if(num*(<<(dep-cnt))<n) return ;
for(int i=cnt;i>=;i--){
ans[cnt+]=ans[i]+num;
if(dfs(ans[i]+num,cnt+)){
return ;
}
if(ans[i]<num){
ans[cnt+]=num-ans[i];
if(dfs(num-ans[i],cnt+)){
return ;
}
}
else if(ans[i]<num){
ans[cnt+]=ans[i]-num;
if(dfs((ans[i])-num,cnt+))
return ;
}
}
return ;
} //bool dfs(int num,int cnt){
// if(num==n){
// return 1;
// }
// if(cnt==dep){
// return 0;
// }
// if(num*(1<<dep-cnt)<n) return 0;
// for(int i=0;i<=cnt;i++){
// for(int j=1;j<=2;j++){
// if(j==1){
// ans[cnt+1]=num+ans[i];
// if(dfs(num+ans[i],cnt+1)){return 1;}
// }
// else{
// ans[cnt+1]=num-ans[i];
// if(num-ans[i]<0) continue;
// if(dfs(num-ans[i],cnt+1)) return 1;
// }
// }
// }
// return 0;
//} int main(){
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)&&n){
minn=;
memset(ans,,sizeof(ans));
ans[]=;
for(dep=;dep<=;dep++){
if(dfs(,))
break;
}
printf("%d\n",dep);
}
}