第二周习题F

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

x² = xxx,     x³ = x²xx,     x⁴ = x³xx,     ...  ,     x³¹ = x³⁰xx.

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

x² = xxx,     x³ = x²xx,     x⁶ = x³xx³,     x⁷ = x⁶xx,     x¹⁴ = x⁷xx⁷, 
x¹⁵ = x¹⁴xx,     x³⁰ = x¹⁵xx¹⁵,     x³¹ = x³⁰xx.

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

x² = xxx,     x⁴ = x²xx²,     x⁸ = x⁴xx⁴,     x¹⁰ = x⁸xx², 
x²⁰ = x¹⁰xx¹⁰,     x³⁰ = x²⁰xx¹⁰,     x³¹ = x³⁰xx.

There however is no way to compute  x³¹ with fewer multiplications. Thus this is one of the most efficient ways to compute  x³¹ only by multiplications.

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

x² = xxx,     x⁴ = x²xx²,     x⁸ = x⁴xx⁴,     x¹⁶ = x⁸xx⁸,     x³² = x¹⁶xx¹⁶,     x³¹ = x³² ÷ x.

This is one of the most efficient ways to compute  x³¹ 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 xⁿ 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 xⁿ 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

这道题用到回溯法，不过要进行剪枝，最有效的剪枝在于预判，所以不要试图去深搜一次来得到最小步数，这样剪枝根本无法进行，可以去枚举尝试，从一到。。。，每次的这个i步作为约束条件，即判断，i步能否到达，因为深搜的结构是一颗解答树，你可以从当前步数获得将来一定不能到达的条件，如，当前步为step，我要求dp步到达，那么还剩下dp-step步，那么最后那一步我可以到达的最大数为当前数乘以pow（2，dp-ste）
，如果这一步的数还小于我n，那么就肯定无法到达了。。。。。。。

本题非原创，完全是参考别人的。。。。。。。

#include"iostream"
#include"stdio.h"
#include"cstring"
#include"algorithm"
using namespace std;


int n;
int ans=1000000;
int a[1000];
int dp;

int DFS(int step,int x)
{
     if(a[step]==n) return 1;

    if(step>=dp) return 0;

    x=max(x,a[step]);

    if(x*(1<<(dp-step))<n) return 0;

    for(int i=0;i<=step;i++)
    {
        a[step+1]=a[step]+a[i];

        if(DFS(step+1,x)) return 1;

        if(a[step]>a[i]) a[step+1]=a[step]-a[i];
        else a[step+1]=a[i]-a[step];

        if(DFS(step+1,x)) return 1;
    }

    return 0;
    }
int main()
{
    while(cin>>n&&n)
    {
        a[0]=1;
        if(n==1) cout<<0<<endl;
        else
        {
        for(dp=1;;dp++)
        {
        if(DFS(0,1)) break;
        }
        cout<<dp<<endl;
        }
    }
    return 0;
}