Description
Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:
x2 = xxx, x3 = x2xx, x4 = x3xx, ... , x31 = x30xx.
The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:
x2 = xxx, x3 = x2xx, x6 = x3xx3, x7 = x6xx, x14 = x7xx7,
x15 = x14xx,
x30 = x15xx15,
x31 = x30xx.
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 = xxx,
x4 = x2xx2,
x8 = x4xx4,
x10 = x8xx2,
x20 = x10xx10,
x30 = x20xx10,
x31 = x30xx.
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 x31 with six operations (five multiplications and one division):
x2 = xxx,
x4 = x2xx2,
x8 = x4xx4,
x16 = x8xx8,
x32 = x16xx16,
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 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
解题思路：
题目大意：求用一个x，如何在最小的步数使用已经用过的凑出x^n，其中n是1~1000的，可以搜索，很容易想到，<=0和>=2000的点应该直接剪掉。
这个题目方根就是搜索的时候控制搜索的层数即可。
if(a[c]*(1<<(t-c))<n)
return false; //这个约束条件必须加，剪枝，这个点按最大比例每次都乘以2扩充也扩充不到n，那么就剪掉。
程序代码：
#include <iostream>
using namespace std;
int a[];
int t,b,n;
bool funt(int c)
{
if(c>t)
return false;
if(a[c]==n)
return true;
if(a[c]<=||a[c]>)
return false;
if(a[c]*(<<(t-c))<n)
return false;
for(int i=;i<=c;i++)
{
a[c+]=a[c]+a[i];
if(funt(c+))
return true;
a[c+]=a[c]-a[i];
if(funt(c+))
return true;
}
return ;
} int main()
{
while(cin>>n&&n)
{
if(n==)
cout<<<<endl;
else
{
t=;
while()
{
a[]=;
if(funt())
break;
t++;
}
cout<<t<<endl;
}
}
return ; }