【题意】 给出 n,问说至少计算几步得到 x^n。

【解题方法】 迭代深搜,枚举步数,然后深搜判断是否可行。需要优化,当当前数 now 按照最大方案执行后仍然小于 n,则说明不可行。紫书上说, 为了尽快接近目标应该先枚举较大的数,再枚举较小的数,我试了一下,先枚举小的数跑得比先枚举大的还要快100ms,大概是数据分布,是通过小的状态搜到的较多吧。


//
//Created by BLUEBUFF 2016/1/8
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 12;
const int maxm = 2e5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
//int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
int n, maxd, A[35];
bool dfs(int cur, int now)
{
    if(cur > maxd || now <= 0 || now << (maxd - cur) < n) return false;
    if(now == n || now << (maxd - cur) == n) return true;
    A[cur] = now;
    for(int i = cur; i >= 0; i--){
        if(dfs(cur + 1, now + A[i])) return true;
        if(dfs(cur + 1, now - A[i])) return true;
    }
    return false;
}
int main()
{
    while(scanf("%d", &n) && n)
    {
        for(maxd = 0; !dfs(0, 1); ++maxd);
        cout << maxd << endl;
    }
    return 0;
}