抱歉，标题少了个第二题了。

关于这个题有个有趣的现象：
我用fenix124的程序把转换步数大于等于60的所有的1000以内的组合列出来了。总共47个组合，最大步数为62。其中30个组合第二个数均为476（最大步数都在这种组合中）；15个组合第二个数为952（476×2＝952），2个组合第二个数为953（第一个数分别为256和512）。
第一个数也是非常有规律：
128－130  （3个）   128*1--第二个数均为476
256－260  （11个）  128*2--均可对应476和952，256还可以对应953
512－521  （21个）  128*4--均可对应476和952，512还可以对应953
768－779  （12个）  128*6--第二个数均为476

楼主能不能帮我测下下面这个代码的花费时间？

int transform(int n, int m, char *fs)
{
    static short ref[32768], parent[32768];
    short lnuml[256],lnum_cur,refcur=0;
    char getflag;
    int num=INT_MAX;

    memset(parent,0,sizeof(parent));
    ref[0] = m, refcur = 1;
    getflag=0, lnum_cur=0;
    lnuml[lnum_cur++] = 0, lnuml[lnum_cur++]=1;
    do
    {
        for(short i=lnuml[lnum_cur-2] ; !getflag && i<lnuml[lnum_cur-1]; ++i)
        {
            short src = ref[i],curv;

            for(int k=0; !getflag && k<2; ++k)
            {
                if( !getflag && (curv=src*2+k)>src && !parent[curv] )
                    ref[refcur++] = curv, parent[curv] = src, getflag= (curv==n);
            }
            if( !getflag && (curv=src/3) && !(src%3) && !parent[curv] )
                ref[refcur++] = curv, parent[curv] = src, getflag= (curv==n);
        }
        if( getflag )
        {
            short j=refcur-1,cur,prev,k;

            cur = ref[j];
            for(k=0; j>0 && (k+2)<=lnum_cur; ++k)
            {
                prev = parent[cur];
                fs[lnum_cur-k-2] = 'f'+(cur>prev), cur = parent[cur];
            }

            fs[k] = 0, num = k;
        }
        else lnuml[lnum_cur++] = refcur;
    } while(!getflag && lnum_cur<250);

    return(num);
}

貌似作对了的跟贴有分...

.....
太没劲了 讲讲你二楼的算法


测试数据都通过的高手都讲讲自己的算法`分享一下

to 太没劲了：
我测试了1000组数据，并和fenix124的数据进行了比对。
你的数据都正常，但fenix124的程序在n=916，m=652时结果错误，fenix124的结果为26，你的结果为16(gggggfggfgfggfff)。fenix124的其他999组数据和你的一致。速度上fenix124的1000组数据耗时560ms，你的耗时760ms。

请太没劲了介绍一下你的算法思想。我认为从总体上你的算法性能超过了fenix124。

大家帮忙看看这个为什么不对.
/*
仿照fenix124的算法，用空间换时间。
算法介绍；
先制作一个表（用结构数组表示），里面存储了由待转换正整数n所能转换到的MAXSIZE个正整数（MAXSIZE取10000）。
结构包含三个成员变量：int step;  //由n转换到该元素所需的最小步数
      int prior; //该元素的前驱
      char tag; //由该元素的前驱转换到该元素采取的方法，f（）或g（）。
然后从元素vf[m]开始，遍历其前驱，提取字符f或g，存储到fs[]中。
最后返回 vf[m].step.
*/
#include <iostream>
#include <time.h>
using namespace std;

const int MAXSIZE = 30000;
struct vNode{
      int step;  //由n转换到该元素所需的最小步数
      int prior; //该元素的前驱
      char tag; //由该元素的前驱转换到该元素采取的方法，f（）或g（）。
} ;

int transform(int n, int m, char *fs);
void SetInf(vNode vf[], int num, int len);

int main()
{
      time_t startTime;
    time_t endTime;

    time(&startTime);
      char fs[MAXSIZE];

      cout << transform(345, 67, fs) << endl;
      cout << fs << endl;
      time(&endTime);

    cout << difftime(endTime, startTime) << endl;
    getchar();
    return 0;
}



int transform(int n, int m, char *fs)
{
      if (n == m)
      {
            fs[0] = '\0';
            return 0;
      }
      vNode vf[MAXSIZE];
      for (int i=0; i<MAXSIZE; i++) //结构数组初始化
            vf[i].step = 0;

      SetInf(vf, n, 0);//创建信息表

      int top = 0;
      int i = m;
      while (i != n)//提取字符
      {
            fs[top++] = vf[i].tag;
            i = vf[i].prior;
      }
      fs[top] = '\0';
       //如果vf[m].step == 0 表示无解
      return (vf[m].step > 0) ? vf[m].step : INT_MAX;
}

void SetInf(vNode vf[], int num, int len)
{
      if (len < MAXSIZE)//递归调用主函数，直到len == MAXSIZE
      {
            int next = num * 3; //next为num的后继，存储由待转换正整数n转换到next所需最少步数
            if (next < MAXSIZE && (vf[next].step==0 || vf[next].step > vf[num].step + 1))
            {
                  vf[next].step = vf[num].step + 1;
                  vf[next].prior = num;
                  vf[next].tag = 'f';
                  SetInf(vf, next, len+1);
            }

            next = num >> 1;
            if (next > 0 && (vf[next].step==0 || vf[next].step > vf[num].step + 1))
            {
                  vf[next].step = vf[num].step + 1;
                  vf[next].prior = num;
                  vf[next].tag = 'g';
                  SetInf(vf, next, len+1);
            }
      }
}

似乎找到原因了,
修该函数void SetInf(vNode vf[], int num, int len)
改成void SetInf(vNode vf[], const int N, int num, int len)其中N表示待转换正整数n.
把if (next < MAXSIZE && (vf[next].step==0 || vf[next].step > vf[num].step + 1))
改成if (next!=N && next < MAXSIZE && (vf[next].step==0 || vf[next].step > vf[num].step + 1))

贴上修改后的代码:
/*
仿照fenix124的算法，用空间换时间。
算法介绍；
先制作一个表（用结构数组表示），里面存储了由待转换正整数n所能转换到的MAXSIZE个正整数（MAXSIZE取30000）。
结构包含三个成员变量：int step;  //由n转换到该元素所需的最小步数
      int prior; //该元素的前驱
      char tag; //由该元素的前驱转换到该元素采取的方法，f（）或g（）。
然后从元素vf[m]开始，遍历其前驱，提取字符f或g，存储到fs[]中。
最后返回 vf[m].step.
*/
#include <iostream>
#include <time.h>
using namespace std;

const int MAXSIZE = 30000;
struct vNode{
      int step;  //由n转换到该元素所需的最小步数
      int prior; //该元素的前驱
      char tag; //由该元素的前驱转换到该元素采取的方法，f（）或g（）。
} ;

int transform(int n, int m, char *fs);
void SetInf(vNode vf[], const int N, int num, int len);

int main()
{
    int i,j,n;
    char ch[100];
    while(scanf("%d %d",&i,&j) != EOF)
    {
        n = transform(i,j,ch);
        printf("%d %s\n",n,ch);
        memset(ch,0,100);
    }
    getchar();
    return 0;
}



int transform(int n, int m, char *fs)
{
      if (n == m)
      {
            fs[0] = '\0';
            return 0;
      }
      vNode vf[MAXSIZE];
      for (int i=0; i<MAXSIZE; i++) //结构数组初始化
            vf[i].step = 0;

      SetInf(vf, n, n, 0);//创建信息表

      int top = 0;
      int i = m;
      while (i != n)//提取字符
      {
            fs[top++] = vf[i].tag;
            i = vf[i].prior;
      }
      fs[top] = '\0';
       //如果vf[m].step == 0 表示无解
      return (vf[m].step > 0) ? vf[m].step : INT_MAX;
}

void SetInf(vNode vf[], const int N, int num, int len)
{
      if (len < MAXSIZE)//递归调用主函数，直到len == MAXSIZE
      {
            int next = num * 3; //next为num的后继，存储由待转换正整数n转换到next所需最少步数
            if (next!=N && next < MAXSIZE && (vf[next].step==0 || vf[next].step > vf[num].step + 1))
            {
                  vf[next].step = vf[num].step + 1;
                  vf[next].prior = num;
                  vf[next].tag = 'f';
                  SetInf(vf, N, next, len+1);
            }

            next = num >> 1;
            if (next!=N && next > 0 && (vf[next].step==0 || vf[next].step > vf[num].step + 1))
            {
                  vf[next].step = vf[num].step + 1;
                  vf[next].prior = num;
                  vf[next].tag = 'g';
                  SetInf(vf, N, next, len+1);
            }
      }
}

大虾们，可以说一下你的次数为什么是最少的吗？（证明一下那数学过程）
谢谢，小弟实在想不出最少的求法。

[quote]速度上fenix124的1000组数据耗时 560ms，你的耗时760ms。[/quote]

谢谢楼主又帮俺测了一下，能达到这个程度俺已经比较满意了，我这个压根没有做缓冲，@fenix124 那样的方式在大数据量时理应快些的。能达到一个数量级估摸跟你那测试数据还有关系，他说总共也就几秒遍历整个，俺这个可不成。具体算法我明天简单说说，其实我的两个代码里都有一个 bug，不过在你这个输入范围内暴露不出来，为了快点俺就没改，:P

第 9 楼 @Atins
[quote]大虾们，可以说一下你的次数为什么是最少的吗？（证明一下那数学过程）[/quote]

俺得说俺证明不了，因为我那中间丢弃了所有大于有符号 short 上限（32767）的分支（@fenix124 是丢弃了大于 20000 的部分），这样的话不验证所有的我只能说我那程序在多数情况下是次数最少的，从 @boxertony  后面的测试结果来看，这么个上限设定很有可能是完全正确的（在 [1,1000] 内）。

[quote]这个题你的程序出现错误的原因估计是因为你的程序限制最大值不能超过20000造成的，从上面的数据可以看到数据完全可以超出20000的。[/quote]

到我那上限是 0x7fff（32767）。

我那就是个树的“广度遍历”，我是想法子得出从 m 到 n，而后再反向输出，m 就是树根，而后 *2、*2+1、/3（这个必须在 %3==0 的情况才生成） 得出下一级所有分枝，一次循环生成一层，如果在生成一层的过程中遇到 n 就表明已经得到目标，生成整个步骤（逆向输出到 fs）而后退出循环。

两个代码都是上面的方法，区别在于剪枝部分，因为广度遍历，生成的子枝太多，不剪的话内存可能都会成问题。

如下三种情况需要剪掉（k是当前节点）：

1、如果 k%3 不是 0，不存在对应 /3 分枝。
2、如果 k*2、k*2+1 小于 k 表明已经超过了 signed short 上限（规定剪除）。
3、如果已经得到节点集合中已经包括了 k*2、k*2+1、k/3，表明已经生成过这个点，丢弃。这种只可能导致更大长度的生成方案。

其中上面 3 剪枝速度效率跟具体的实现相关，不同的实现速度差别比较大，我开始提交的是用 map 来查找已生成点，时间复杂度是 O(log2n)，而后后来的方法是用“桶排序”类的方式来保存对应生成点，O(1) 复杂度，快很多，并且代码也能简洁些。因为开始没有注意到 2 条件带来的另一个好处，所以开始没有想到后面的方法。

在做 2 代码时觉得前面实现的结构体比较讨厌，想到只是需要其中的 op （操作函数名）才弄成那个样子，如果没有它用具体的数值也能得出来，就在第二个版本中丢弃了，改成用前后两个数的大小来得相关操作函数名（*2、*2+1 肯定会导致分枝点比上级父节点大，而 /3 生成的肯定小），这样在保存已生成节点父节点和对应操作函数记号部分也可能做得快些，因为不必做 vector add 部分操作了。

[quote]所以，冠军还是属于你，还是有你主持下次比赛吧。[/quote]

楼主大人真是英明！呵呵

俺的两个代码的共同 bug 是应该把如下：

} while(!getflag && lnum_cur<250);

改成

} while(!getflag && lnum_cur<250 && lnuml[lnum_cur-1]>lnuml[lnum_cur-2]);

否则有可能形成死循环。

才看到 @iAkiak 的代码和如下注释

// A*了，不知道是否有数学方法

晕，这个法子太复杂了点，楼主这题特点就是数值的范围比较小，可以试规定中间值也比较小，利用这个就简单好些。