D - 整数变换问题 Description 整数变换问题。关于整数i的变换f和g定义如下：f(i)=3i； 试设计一个算法，对于给定的2 个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15用4 次变换将它变换为整数4：4=gfgg(15)。当整数n不可能变换为整数m时，算法应如何处理? 对任意给定的整数n和m，计算将整数n变换为整数m所需要的最少变换次数。 Input 输入数据的第一行有2 个正整数n和m。n≤100000，m≤1000000000。 Output 将计算出的最少变换次数以及相应的变换序列输出。第一行是最少变换次数。第2 行是相应的变换序列。 Sample Input 15 4 Output 4 gfgg Hint
代码语言：javascript复制#include <iostream>
using namespace std;
int Max;
int n,m;
char fn[101];//这里不能用vector queue代替，a[step]会被重写，前面两个容器不适合
int search(int step,int x)
{
if(step > Max) return 0;//步数不够
if(x*3 == m||search(step 1, x*3))
{
fn[step]='f';
return 1;
}
if(x/2 == m||search(step 1, x/2))
{
fn[step] = 'g';
return 1;
}
return 0;//此路不通
}
int main()
{
cin>>n>>m;
Max = 1;
while(!search(1, n))//试探
{
Max ;
}
cout<<Max<<endl;
for(int i=Max;i>=1;i--)
{
cout<<fn[i];
}cout<<endl;
return 0;
}
