POJ 3134 Power Calculus 题解《挑战程序设计竞赛》

POJ 3134 Power Calculus 

幂运算：用最少的乘法和除法计算xⁿ。

4.5开动脑筋智慧搜索 

剪枝 

算法主框架是DFS，同底数幂的乘除法分别视作指数的加减法。定义exp[i] = n表示某状态下xⁿ的计算次数=i，然后搜索有限步数即可。

exp[d + 1] = exp[i] + exp[d]; // 乘法
exp[d + 1] = exp[d] - exp[i]; // 除法

关键之处在于剪枝策略，对每个n，都估计一个步数上界。上界的估计方法如下：

对任意数，将其二进制拿到，统计二进制中的1的个数，以及最高的1离末尾的距离：

2 00000000000000000000000000000010 1 2
3 00000000000000000000000000000011 2 2
4 00000000000000000000000000000100 1 3
5 00000000000000000000000000000101 2 3
6 00000000000000000000000000000110 2 3
7 00000000000000000000000000000111 3 3
8 00000000000000000000000000001000 1 4
9 00000000000000000000000000001001 2 4
10 00000000000000000000000000001010 2 4
11 00000000000000000000000000001011 3 4
12 00000000000000000000000000001100 2 4
13 00000000000000000000000000001101 3 4
14 00000000000000000000000000001110 3 4
15 00000000000000000000000000001111 4 4
16 00000000000000000000000000010000 1 5

上界等于=1的个数+最高位距离-2 。因为最高位距离代表迭代x*x=x^2， x^2*x^2=x^4……的次数，1的个数代表{x的奇数次方除以x得到x的偶数次方}的次数，而最后一位其实就是x本身，算了两遍，所以要减去2。

拿13举个例子

13 00000000000000000000000000001101 3 4

13的二进制中一共有3个1，最高位是从右往左第4位，最低位算了2次，所以上界为3+4-2=5。这5次运算分别是

13-1=12
12/2=6
6/2=3
3-1=2
2/2=1

代码

#include <cstdio>

#define MAX_N 1024
#define MAX_D 20
int exp[MAX_D] = {1}, ans[MAX_N];

void dfs(int d)
{
    if (d > MAX_D)
    {
        return;
    }
    for (int i = 0; i <= d; i++)
    {
        exp[d + 1] = exp[i] + exp[d]; // 乘法
        if (exp[d + 1] < MAX_N && ans[exp[d + 1]] >= d + 1)
        {
            ans[exp[d + 1]] = d + 1;
            dfs(d + 1);
        }
        exp[d + 1] = exp[d] - exp[i]; // 除法
        if (exp[d + 1] > 0 && ans[exp[d + 1]] >= d + 1)
        {
            ans[exp[d + 1]] = d + 1;
            dfs(d + 1);
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    for (int i = 2; i < MAX_N; i++)
    {
        //每个n的上界=除法+乘法
        ans[i] = __builtin_popcount(i) + (30 - __builtin_clz(i));
    }
    dfs(0);

    int n;
    while (~scanf("%d", &n), n)
    {
        printf("%d\n", ans[n]);
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

其中__builtin_popcount返回1的个数，__builtin_clz返回最高位从左往右的位数。

二者都是GCC限定的。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3134 Power Calculus 题解《挑战程序设计竞赛》