迭代加深搜索POJ 3134 Power Calculus

题意：输入正整数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);

     }

 }

巴特西

迭代加深搜索POJ 3134 Power Calculus

最新文章

热门文章