整数变换问题
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 行是相应的变换序列。
Samples
Sample #1
Input
15 4
Output
4
gfgg
分析:
深度搜索+剪枝算法
#include<iostream>
#include <climits>
#include<vector>
using namespace std;
char a[1010];
int n,m,k=0,c=0;
bool dfs(int step,int num){
if(step>k) return false;//当前步骤比当前记录的最少步骤多,直接返回
if(num==m) return true;//输入的值与目标相同
//这一步完成后得到结果 或 通过递归得知这条是通往最终结果的路径
if(3*num==m||dfs(step+1,num*3)){//f(n)=m
a[c++]='f';
return true;
}
if(num/2==m||dfs(step+1,num/2)){//g(n)=m
a[c++]='g';
return true;
}
return false;
}
int main(){
cin>>n>>m;
while(!dfs(1,n))//从第一层开始搜索
k++;//总共所需的步骤
cout<<k<<endl;
for(int i=0;i<c;i++)
cout<<a[i];
return 0;
}