# [POJ 3134] Power Calculus【IDDFS】

• 2018-01-02
• 0
• 0

## Problem:

 Time Limit: 5000MS Memory Limit: 65536K

Description

Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:

x2 = x × xx3 = x2 × xx4 = x3 × x, …, x31 = x30 × x.

The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:

x2 = x × xx3 = x2 × xx6 = x3 × x3x7 = x6 × xx14 = x7 × x7x15 = x14 × xx30 = x15 × x15x31 = x30 × x.

This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:

x2 = x × x, x4 = x2 × x2x8 = x4 × x4x10 = x8 × x2x20 = x10 × x10x30 = x20 × x10x31 = x30 × x.

If division is also available, we can find a even shorter sequence of operations. It is possible to compute x31 with six operations (five multiplications and one division):

x2 = x × xx4 = x2 × x2x8 = x4 × x4x16 = x8 × x8x32 = x16 × x16x31 = x32 ÷ x.

This is one of the most efficient ways to compute x31 if a division is as fast as a multiplication.

Your mission is to write a program to find the least number of operations to compute xn by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence should be x to a positive integer’s power. In others words, x−3, for example, should never appear.

Input

The input is a sequence of one or more lines each containing a single integer nn is positive and less than or equal to 1000. The end of the input is indicated by a zero.

Output

Your program should print the least total number of multiplications and divisions required to compute xn starting with x for the integer n. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.

Sample Input

```1
31
70
91
473
512
811
953
0```

Sample Output

```0
6
8
9
11
9
13
12```

Source

Japan 2006

## Solution:

DFS 能方便地记录路径，且节省空间，而 BFS 能高效地求出最小步数

Code #1 已经能通过 POJ 上的所有数据，但效率并不可观。

Code #2 相比于 Code #1 效率有较大提升。

## Code #1: O(玄学) [168K, 3813MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int n, maxdep;
int p, topp;
bool vis, flag;

inline bool IDDFS(int cur, int dep, int maxp){
if(cur == n) return 1;
if(dep >= maxdep) return 0;
if(cur + (maxp << maxdep - dep) < n) return 0;
if(cur - (maxp << maxdep - dep) > n) return 0;  // Feasibility pruning
for(register int i = 1; i <= topp; i++){
if(cur + p[i] < 2000 && !vis[cur + p[i]]){
vis[cur + p[i]] = 1, p[++topp] = cur + p[i];
flag = IDDFS(cur + p[i], dep + 1, max(maxp, p[topp]));
vis[cur + p[i]] = 0, topp--;
if(flag) return 1;
}
if(cur > p[i] && !vis[cur - p[i]]){
vis[cur - p[i]] = 1, p[++topp] = cur - p[i];
flag = IDDFS(cur - p[i], dep + 1, max(maxp, p[topp]));
vis[cur - p[i]] = 0, topp--;
if(flag) return 1;
}
}
return 0;
}

int main(){
while(scanf("%d", &n) != EOF && n){
for(maxdep = 0;; maxdep++){
p[topp = 1] = 1;
vis = 1;
if(IDDFS(1, 0, 1)){
printf("%d\n", maxdep);
break;
}
}
}
return 0;
}
```

## Code #2: O(玄学) [172K, 875MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int n, maxdep;
int p, topp, vis;
bool flag;

inline bool IDDFS(int cur, int dep, int maxp){
if(cur == n) return 1;
if(dep >= maxdep) return 0;
if(cur + (maxp << maxdep - dep) < n) return 0;
if(cur - (maxp << maxdep - dep) > n) return 0;  // Feasibility pruning
for(register int i = 1; i <= topp; i++){
if(cur + p[i] < 2000 && dep <= vis[cur + p[i]]){
vis[cur + p[i]] = dep, p[++topp] = cur + p[i];
flag = IDDFS(cur + p[i], dep + 1, max(maxp, p[topp]));
topp--;
if(flag) return 1;
}
if(cur > p[i] && dep <= vis[cur - p[i]]){
vis[cur - p[i]] = dep, p[++topp] = cur - p[i];
flag = IDDFS(cur - p[i], dep + 1, max(maxp, p[topp]));
topp--;
if(flag) return 1;
}
// Feasibility pruning: not to backdate, but to record the minimum steps
/*
Reason:
The attempt of former calculating failed,
and this time we get the same condition again taking more steps.
What's worse is that those extra intermediate steps can't lead to the answer in another way
because of the characteristic of IDDFS which is going further step by step.
*/
}
return 0;
}

int main(){
while(scanf("%d", &n) != EOF && n){
for(maxdep = 0;; maxdep++){
p[topp = 1] = 1;
memset(vis, 0x3f, sizeof(vis)), vis = 0;
if(IDDFS(1, 0, 1)){
printf("%d\n", maxdep);
break;
}
}
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai