In The End

个人博客

0%

UVA1374题：快速幂计算（IDA*+打表秒过）

发表于 更新于 分类于 ，

又是一题IDA*的题目，这题目很像埃及分数。

题意

传送门：https://vjudge.net/problem/UVA-1374

给定一个数n，让你求从1至少要做多少次乘除才可以从 x 得到 x的n次方。

如图

我们首先应该很快可以想到这道题本身跟乘法除法幂次计算并没有什么关系，因为很明显可以看出只要忽略掉x对指数部分进行加减运算就行了。但是，由于这种枚举的上限又是无限的，所以又得用到IDA*算法了。

熟悉我前几篇文章的应该都知道大概的方向了（我现在对于是否需要使用IDA*也基本上很清楚了），我们只需对加减（后面都叫加减了，上问我提到了省略x对指数部分作加减）的数量进行枚举便可，这就是IDA*的大方向。

细节部分也需要注意，因为我们每次只能使用前面加出来的数字进行相加，所以我们需要一个数组来保存，我在做这题的时候试过使用vector存储+dfs，但是极其不方便的一点在于我每次dfs相当与将vector拷贝了一遍，后来相当了使用一个指针指向数组的末尾，当我枚举下一个的时候就把指针往后移，然后递归枚举完了再将指针移回来，非常快速完成回溯。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int N=1010;
int target,maxd;
int ready[N];

bool dfs(int d,int ans,int last){
    if(d==maxd)
        return ans == target ? true : false;
    int mx=-1;
    for(int i=0;i<last;i++)
        mx=max(mx,ready[i]);
    if(mx*pow(2,maxd-d)<target)
        return false;
    for(int i=last-1;i>=0;i--){
        last++;
        ready[last-1]=ans+ready[i];
        if(dfs(d+1,ready[last-1],last))
            return true;
        ready[last-1]=abs(ans-ready[i]);
        if(dfs(d+1,ready[last-1],last))
            return true;
        last--;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>target&&target){
        for(maxd=0;;maxd++){
            ready[0]=1;
            if(dfs(0,1,1)){
                cout << maxd << endl;
                break;
            }
        }
    }
    return 0;
}

标题上提到了打表的方法哈，因为是刘汝佳老师在书中提到的，所以我特地搞了一下打表，一开始我以为是避免重复输入所以提前算出0-1000的答案（题中说了范围小于1000），后来写了之后反而更慢了，后来我才发现原来是下面这种操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;

int check[]={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(cin>>n&&n){
        cout << check[n-1] <<endl;
    }
    return 0;
}

用另外一个程序算出答案粘贴到这个提交的程序中，实在是666啊！

正常的程序（第一个用IDA*的速度，IDA*挺快的）：

打表提交的程序（时间都没有了，毕竟o(1)的效率）：

ok，我们下一篇见！