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