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.

 

 

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.

 

 

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.

 

 

 

13170914735128119530

 

 

 

06891191312 这道题用到回溯法，不过要进行剪枝，最有效的剪枝在于预判，所以不要试图去深搜一次来得到最小步数，这样剪枝根本无法进行，可以去枚举尝试，从一到。。。，每次的这个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))
    
     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<