Power Calculus 快速幂计算 (IDA*/打表)

原题：1374 - Power Calculus

题意：

求最少用几次乘法或除法，可以从x得到x^n。（每次只能从已经得到的数字里选择两个进行操作）

举例：

x^31可以通过最少6次操作得到(5次乘，1次除)

x^2 = x*x

x^4 = (x^2)*(x^2)

x^8 = (x^4)*(x^4)

x^16 = (x^8)*(x^8)

x^32 = (x^16)*(x^16)

x^31 = (x^32)÷x

分析：

可以看到，每次从已得到的数字中选取两个操作，这样就有了枚举的思路。

这道题又是没有明显的枚举次数上限，所以很自然想到了用迭代加深搜索算法。

因为n的数据范围是1～1000，所以可以通过计算，预设最大的枚举层次数上限MAXD是13.

而且可以发现如果当前的数字num*2^(MAXD-d) < n,就没有继续搜的必要了，回溯(num是通过前d步得到的数字)

所以我们的IDA*算法思路基本上就完全了。

进一步优化：

如果只依靠上述的思路，写出来的程序要跑2.7s(上限是3s)，所以属于刚刚好AC.

我们这里有很多种优化方法，我就说两个我用了的。

1. 寻找幂的时候，我们每次不应该从已得到数字里任意抽两个，这样效率很低。而且很容易出一道，我们每一次都是操作上一步得到的数字，所以这样只需要枚举另一个操作数就够了。

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 const int MAXD = 13;
 5 int n, f[1<<(MAXD - 1)], maxd, a[15];
 6 
 7 bool dfs(int d) {
 8     if (a[d] == n) return true;
 9     if (d < maxd && (a[d]<<(maxd - d)) >= n) {
10         for (int i = d; i >= 0; i--)
11             for (int j = 0; j < 2; j++) {
12             int nextn = j ? a[d] + a[i] : a[d] - a[d - i];
13             if (nextn <= 0 || f[nextn]) continue;
14             f[nextn] = 1;
15             if (nextn <= 0) continue;
16             a[d + 1] = nextn;
17             if (dfs(d + 1)) return true;
18             f[nextn] = 0;
19         }
20     }    
21     return false;
22 }
23 int main() {
24     a[0] = 1; 
25     while (scanf("%d", &n) == 1 && n) {
26         if (n == 1) { printf("0
"); continue;}
27         for (maxd = 1; maxd < MAXD; maxd++) {
28             memset(f, 0, sizeof(f));
29             f[1] = 1;            
30             if (dfs(0)) break;
31         }
32         printf("%d
", maxd);
33     }
34     return 0;
35 }

2.打表。

因为n的范围是1～1000，所以我们可以用稍微慢一点的算法，提前算出来结果，保存到文件里，然后再粘贴到提交的代码里。

比如我的代码是

 1 int main() {
 2     freopen("ans_table", "w", stdout);
 3     /*
 4         some code.
 5     */
 6     for(n = 1; n <= 1000; n++) {
 7         if (n == 1) { printf("ans[%d] = 0;
", i); continue;}
 8         for (maxd = 1; maxd < MAXD; maxd++) {
 9         /*
10             some code.
11         */
12             if (dfs(0, 1)) break;
13         }
14         printf("ans[%d] = %d;
", i, maxd);
15     }
16     return 0;
17 }

这样我们就本地生成了文件"ans_table"。

里面的答案都是形如

ans[1] = 0;
ans[2] = 1;
ans[3] = 2;
ans[4] = 2;
ans[5] = 3;
ans[6] = 3;
ans[7] = 4;
ans[8] = 3;
ans[9] = 4;
ans[10] = 4;
ans[11] = 5;
ans[12] = 4;