ACM 迭代深搜法 Power Calculus

逃离我推掉我的手 2022-06-12 11:16 125阅读 0赞

滴，集训第五天打卡。

今天是紫书第七章训练2，感觉难度很大呀...

A和E是迭代深搜法，C是背包我首A的哈哈哈哈后续更新~

这里贴E题..

**UVA 1374 Power Calculus**

**![20170722101906761][]**

**![20170722101927099][]**

题目大意：给定一个数n，让你求从1至少要做多少次乘除才可以从 x 得到 x^n。

思路： 从小到大枚举深度上限，剪枝：（当每次取最大的两个数相加仍然小于n时要剪枝 。因为以最快的方式增长的话其指数是按照2的幂次增加的，所以当前序列最大的数乘以2^(maxd-d)之后仍小于n，则剪枝 。）

#include<stdio.h>     
    int vis[2010];  
    int flag,deep,n;    
    void dfs(int pos)  
    {  
        int t;  
        if(pos>deep || (vis[pos]<<(deep-pos))<n || flag) return;  
        //剪枝:如果大于当前限制的深度or当前的数通过自身相乘(即指数相加 最快方式)都不能达到n,停止搜索。
        if(vis[pos]==n)  
        {  
            flag=1;  
            return;  
        }  
        for(int i=1;i<=pos;i++)  
        {  
            if(flag) return;  
            t=vis[pos]+vis[i];  //乘法 
            if(t>0 && t<2000)  
            {  
                vis[pos+1]=t;  
                dfs(pos+1);  
            }  
            t=vis[pos]-vis[i];  
            if(t>0 && t<2000)  //除法 
            {  
                vis[pos+1]=t;  
                dfs(pos+1);  
            }  
        }  
    }  
    int main()  
    {  
        while(scanf("%d",&n)&&n)  
        {  
            deep=0,flag=0;  
            vis[1]=1;  
            while(!flag)  
            {  
                deep++;  
                dfs(1);  
            }  
            printf("%d\n",deep-1);  
        }  
        return 0;  
    }

当然也可以打表做

#include <stdio.h>
    int ans[]={0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,6,6,7,6,6,5,6,6,
    7,6,7,7,7,6,7,7,7,7,7,7,7,6,7,7,7,7,8,7,8,7,8,8,8,7,8,7,7,6,7,7,8,7,8,8,8,7,8,8,8,8,
    8,8,8,7,8,8,8,8,8,8,9,8,9,8,9,8,8,8,8,7,8,8,8,8,9,8,9,8,9,9,9,8,9,9,9,8,9,9,9,9,9,9,9,8,
    9,9,9,8,9,8,8,7,8,8,9,8,9,9,9,8,9,9,9,9,9,9,9,8,9,9,9,9,9,9,10,9,9,9,9,9,9,9,9,
    8,9,9,9,9,9,9,10,9,10,9,10,9,10,10,10,9,10,10,10,9,10,10,10,9,10,9,10,9,9,9,9,8,
    9,9,9,9,10,9,10,9,10,10,10,9,10,10,10,9,10,10,10,10,10,10,10,9,10,10,10,10,10,10,
    10,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,9,10,10,10,10,10,10,10,9,10,10,
    10,9,10,9,9,8,9,9,10,9,10,10,10,9,10,10,11,10,11,10,10,9,10,10,11,10,11,10,10,10,
    10,10,10,10,10,10,10,9,10,10,10,10,10,10,11,10,10,10,11,10,11,11,11,10,11,10,11,10,
    11,10,11,10,11,10,10,10,10,10,10,9,10,10,10,10,10,10,11,10,11,10,11,10,11,11,11,10,11,11,11,
    10,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,
    10,11,11,11,10,11,11,11,10,11,10,11,10,10,10,10,9,10,10,10,10,11,10,11,10,11,11,11,10,11,
    11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,11,
    11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,10,11,11,11,11,11,
    11,11,11,11,11,11,11,12,11,12,11,11,11,12,11,12,11,11,11,11,11,11,11,11,11,11,10,11,11,
    11,11,11,11,11,11,11,11,12,11,12,11,11,10,11,11,12,11,12,11,11,10,11,11,11,10,11,10,10,9,10,
    10,11,10,11,11,11,10,11,11,12,11,12,11,11,10,11,11,12,11,12,12,11,11,12,12,12,11,12,11,11,10,
    11,11,12,11,12,12,12,11,11,12,12,11,12,11,12,11,11,11,12,11,12,11,11,11,12,11,11,11,11,11,11,10,11,
    11,11,11,11,11,12,11,11,11,12,11,12,12,12,11,12,11,12,11,12,12,12,11,12,12,12,12,12,
    12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,11,12,11,
    12,11,11,11,11,11,11,10,11,11,11,11,11,11,12,11,12,11,12,11,12,12,
    12,11,12,12,12,11,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,11,12,12,
    12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,12,12,12,12,
    12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,11,12,12,12,11,12,
    11,12,11,11,11,11,10,11,11,11,11,12,11,12,11,12,12,12,11,12,12,12,11,12,12,12,12,
    12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,13,12,12,12,
    12,11,12,12,12,12,13,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,13,12,12,12,13,12,13,12,12,12,13,12,12,12,12,12,12,11,12,12,12,12,12,
    12,13,12,12,12,13,12,13,12,12,12,13,12,13,12,13,12,12,12,12,12,12,12,12,12,
    12,11,12,12,12,12,12,12,12,12,12,12,13,12,13,12,13,12,13,12,13,12,13,12,13,12,13,
    13,13,12,13,13,13,12,13,12,13,12,13,13,13,12,13,13,13,12,13,12,13,12,12,12,13,12,
    13,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,13,12,13,12,
    12,12,12,12,13,12,13,13,13,12,13,13,13,12,13,12,12,11,12,12,13,12,13,13,13,12};
    int main()
    {
        int n;
        while(scanf("%d",&n) == 1 && n)
            printf("%d\n", ans[n-1]);
        return 0;
    }

[20170722101906761]: /images/20220612/7757d486fb6f45a1b5b4937f6c1d9a78.png
[20170722101927099]: /images/20220612/88ba8fe2720e4452aa599e0b9aef5daf.png