整数变换问题
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem 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所需要的最少变换次数。
试设计一个算法,对于给定的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
Sample Output
4 gfgg
Hint
Source
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n,m; 4 int depth;//子集树的深度 5 string str; 6 bool dfs(int n,int curDepth){ 7 if(curDepth>depth) return false;//当前的深度 不能使n变成m 当前搜索层 超过 子集树的深度,返回,继续下一深度 的搜索 8 int sum=n;// 进行 两步操作 n*3, n/2; 9 for(int i=0;i<2;i++){ 10 i==0?sum=n*3:sum=n/2; 11 if(sum==m||dfs(sum,curDepth+1)){ 12 i==0?str+="f":str+="g";//或者 外面定义一个数组 i==0?a[cn++]='f':a[cn++]='g'; 13 return true;//满足条件 就可以返回了 14 } 15 } 16 return false; 17 } 18 int main() 19 { 20 cin>>n>>m; 21 depth=1;//采用子集树,一层一层的找,否则的话,一直在递归 ,先是第一层,然后 第二层,第三层 ... 22 str="";//记录 递归的顺序的 递归 到 最后 ,然后 回溯的记录结果 23 while(!dfs(n,1)){//当dfs 返回 false,没有找到,!false 为真,继续下一层循环:(从第一层开始 到 depth这个 深度) 24 depth++;//深度 就是 最小的变换次数 25 } 26 cout<<depth<<endl; 27 cout<<str<<endl; 28 return 0; 29 }
depth=1 时 第一层 n 返回false depth=2 时 第一层 n 第二层 n*3 n/2 不满足 返回 false; depth=3 时 第一层 n 第二层 n*3 n/2 第三层 n*3*3 n*3/2 n/2*3 n/2/2 不满足 返回 false; . . . 类推 当深度 depth=x时 找到了 结果 第一层 n 第二层 n*3 n/2 第三层 n*3*3 n*3/2 n/2*3 n/2/2 .... n*3...*3 n*3...*3/2(假设 这个 找到了 ==m),则进行回溯,回到上一层,最后到根) .... ... n/2....*3 n/2.../2
最小次数 就是 搜索的深度