放牧代码和思想
专注自然语言处理、机器学习算法

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

目录

power.fw_.png挑战程序设计竞赛第二版.jpg

POJ 3134 Power Calculus 

幂运算:用最少的乘法和除法计算xn

power.fw_.png

4.5开动脑筋智慧搜索 

剪枝 

算法主框架是DFS,同底数幂的乘除法分别视作指数的加减法。定义exp[i] = n表示某状态下xn的计算次数=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;
}
16512852 hankcs 3134 Accepted 392K 204MS G++ 945B 2017-01-23 11:10:13

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

二者都是GCC限定的。

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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机