题目：

整数变换问题。关于整数i的变换f和变换g的定义如下：f(i)=3i; g(i)=└i/2┘。试设计一个算法，对于给定的两个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15用4次变换为整数4，即4=gfgg(15)。
    具体变换如下：g(15)=7  g(7)=3  f(3)=9  g(9)=4
    
// f函数
inline int f(int i)
{
    return 3*i;
}

// g函数
inline int g(int i)
{
    return (i>>1);
}

// 函数接口
// [in]n   -- 待转换正整数 (0<n<=1000)
// [in]m   -- 目标正整数   (0<m<=1000)
// [out]fs -- 存放转换步骤，比如 15=>4 为 "gfgg" （请一定加上字符串结束标志符'\0'）
// [return]-- 转换的最少步数（当无解时，返回INT_MAX）
int transform(int n, int m, char *fs);

//  下面是两种解法

// 1. 对“太没劲了”的程序稍作修改

// 通过f函数和g函数的组合，把n经过若干步转换成m。求最少的转换步数以及转换过程
// [in]n   -- 待转换正整数
// [in]m   -- 目标正整数
// [out]fs -- 存放转换步骤
// [return]-- 转换的最少步数
#define MAXBUFFSIZE1   262144
#define MAXBUFFSIZE2   256

int transform(int n, int m, char *fs)
{
    static int ref[MAXBUFFSIZE1], parent[MAXBUFFSIZE1];
    int   lnuml[MAXBUFFSIZE2], 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(int i=lnuml[lnum_cur-2] ; !getflag && i<lnuml[lnum_cur-1]; ++i)
        {
            int src = ref[i],curv;

   curv = (src<<1);
   if(!getflag && curv<MAXBUFFSIZE1 && !parent[curv])
    ref[refcur++] = curv, parent[curv] = src, getflag= (curv==n);
   if(!getflag && (++curv)<MAXBUFFSIZE1 && !parent[curv])
    ref[refcur++] = curv, parent[curv] = src, getflag= (curv==n);

   curv = src / 3;
            if( !getflag && (curv*3==src) && !parent[curv] )
                ref[refcur++] = curv, parent[curv] = src, getflag= (curv==n);
        }
        if( getflag != 0 )
        {
            int  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<MAXBUFFSIZE2);

    return(num);
}

// 2。“太没劲了”采用的是从后往前倒退方式进行宽度优先搜索。

// 下面的函数仿照“太没劲了”的函数利用队列，采用从前往后方式进行宽度优先搜索

#define MAXBUFFSIZE1  262144

#define MAXBUFFSIZE2  32768

int transform(int n, int m, char *fs)
{
    static int parent[MAXBUFFSIZE1];
 static int q[MAXBUFFSIZE2];
 int   curv;
 int   temp;
 int   f, r;

 memset((void*)parent, 0, sizeof(int)*MAXBUFFSIZE1);
 f = r = 0;
 q[r++] = n;

 parent[n] = INT_MAX;
 while(f != r)
 {
  temp = q[f++];
  f = (f == MAXBUFFSIZE2)?0:f;

  curv = temp >> 1;
  if(curv == m)
   break;

  if(curv > 0 && !parent[curv])
  {
   parent[curv] = temp;
   q[r++] = curv;
   r = (r == MAXBUFFSIZE2)?0:r;
  }

  curv = temp * 3;
  if(curv == m)
   break;
        if( curv < MAXBUFFSIZE1 && !parent[curv] )
  {
            parent[curv] = temp;
   q[r++] = curv;
   r = (r == MAXBUFFSIZE2)?0:r;
  }
 }

 int  i = 0;
 fs[i++] = 'f' + (temp>m);
    while(temp != n)
 {
  m = temp;
  temp = parent[temp];
  fs[i++] = 'f' + (temp>m);
    }
 fs[i] = 0;
    return(i);
}

评论