算法设计与分析课程设计题目 整数变换问题姓名： 班级： 学号： 日期： 一、算法问题描述整数变换问题关于整数i的变换f和g定义如下：f(i)=3i； g(i)=i/2试设计一个算法，对于给定的2个整数n和m,用最少的f和g变换次数将n变换 为m例如，可以将整数15用4次变换将它变换为整数4： 4=gfgg(15)当整数n不可 能变换为整数m时，算法应如何处理？'算法设计：对任意给定的整数n和m,计算将整数n变换为整数m所需要的最少变换次数二、 算法问题形式化表示三、 期望输入与输出输入: 由文件 input.txt 给出输入数据第一行有 2 个正整数 n 和 m输出：将计算出的最少变换次数以及相应的变换序列输出到文件output.txt文件的第 一行是最少变换次数文件的第2 行是相应的变换序列四、算法分析与步骤描述static void compute(){k=1;while(!search(1,n)){k++;init();}if(found) output();else System.out.println("No Solution!");}static boolean search(int dep,int n){ if(dep>k) return false;for(int i=0;i<2;i++){int n1 = f(n,i);if(n1==m|| search(dep+1,n1)){ found = true;out(); return true;}}}五、问题实例及算法运算步骤1. 为了找最短变换序列，用逐步加深的回溯搜索2. search 实现回溯搜索六、算法运行截图七、算法复杂度分析算法的时间复杂度为：O(n)。