Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:
x2 = x x x, x3 = x2 x x, x4 = x3 x x, ...
, x31 = x30 x x.
The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute x31 with
eight multiplications:
x2 = x x x, x3 = x2 x x, x6 = x3 x x3, x7 = x6 x x, x14 = x7 x x7,
x15 = x14 x x, x30 = x15 x x15, x31 = x30 x 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 x, x4 = x2 x x2, x8 = x4 x x4, x10 = x8 x x2,
x20 = x10 x x10, x30 = x20 x x10, x31 = x30 x x.
There however is no way to compute x31 with fewer multiplications.
Thus this is one of the most efficient ways to compute x31 only by multiplications.
If division is also available, we can find a shorter sequence of operations. It is possible to compute x31with six operations (five multiplications and one division):
x2 = x x x, x4 = x2 x x2, x8 = x4 x x4, x16 = x8 x x8, x32 = x16 x x16, x31 = 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 of operations should be x to a positive integer's power. In other words, x-3,
for example, should never appear.
Input
The input is a sequence of one or more lines each containing a single integer n. n 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 xnstarting 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
题意：给定n，求出从1变换到n的最小步数，根据题意。
思路：迭代深搜。要剪枝。如果当前最大的不断自加到不了n，这种情况就没必要搜下去
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
const int N = 55;
const int mi[11] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
int n, D, h[N], hn, ans[1001];
void init() {
for (int i = 0; i <= 10; i ++)
if (n <= mi[i]) {
D = i;
break;
}
}
bool dfs(int d, int sum) {
if (d == D) {
if (sum == n)
return true;
return false;
}
for (int i = hn - 1; i >= 0; i --) {
int Max = 0;
for (int j = 0; j < hn; j ++)
Max = max(Max, h[j]);
if (((Max + sum)<<(D - d - 1)) < n) return false;
h[hn++] = sum + h[i];
if (dfs(d + 1, sum + h[i])) return true;
if (sum - h[i] > 0) {
h[hn - 1] = sum - h[i];
if (dfs(d + 1, sum - h[i])) return true;
}
hn--;
}
return false;
}
int solve() {
for (;;D++) {
memset(h, 0, sizeof(h));
h[0] = 1; hn = 1;
if (dfs(0, 1))
break;
}
return D;
}
int main() {
while (~scanf("%d", &n) && n) {
init();
printf("%d\n", solve());
}
return 0;
}