Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:
x 2 = x x x, x 3 = x 2 x x, x 4 = x 3 x x, ... , x 31 = x 30 x x.The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute x 31 with eight multiplications:
x 2 = x x x, x 3 = x 2 x x, x 6 = x 3 x x 3, x 7 = x 6 x x, x 14 = x 7 x x 7,This is not the shortest sequence of multiplications to compute x 31. There are many ways with only seven multiplications. The following is one of them:
x 15 = x 14 x x, x 30 = x 15 x x 15, x 31 = x 30 x x.
x 2 = x x x, x 4 = x 2 x x 2, x 8 = x 4 x x 4, x 10 = x 8 x x 2,There however is no way to compute x 31 with fewer multiplications. Thus this is one of the most efficient ways to compute x 31 only by multiplications.
x 20 = x 10 x x 10, x 30 = x 20 x x 10, x 31 = x 30 x x.
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):
x 2 = x x x, x 4 = x 2 x x 2, x 8 = x 4 x x 4, x 16 = x 8 x x 8, x 32 = x 16 x x 16, x 31 = x 32÷ x.This is one of the most efficient ways to compute x 31 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#include #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; }