算法设计与分析实验报告
学号
姓名 教师 庄蔚蔚 实验3 回溯 班级 上课时间 上课地点 1. 实验目的 1.1．掌握回溯法的基本思路 1.2．熟悉用回溯法策略解决图着色问题，哈密尔顿回路问题 2. 实验环境 2.1 VC6.0 2.2 Window XP 3. 实验内容 3.1 整数变换问题 3.1.1 算法设计思想 根据题意，n变成m的过程可以进行两个不同操作*3或/2，由于我们不知道n变成m需要几次进行*3或/2操作，所以我们要列出一个树，通过递归去遍历这棵树，根节点为n，对n的操作*3和/2都列成新的节点，每个节点都可以进行者两部操作以此产生新的节点，但n变成m可能不只有一种方法，所以遍历的结果可能有多个，所以我们需要另外两个数据类型记录，一个是记录最好的n变成m的方法，一个是记录递归遍历树n能变成m的结果的方法， 3.1.2 程序源码 package demo; import java.util.Scanner; public class first { } class gg{ private int n, m; private int nn; public static void main(String[] args) { } Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); gg g = new gg(n, m); g.digui(0, n, m); g.show();
private int count=0,bestcount =21; private int kl = 20; private char[] sss = new char[kl]; private char[] bestsss = new char[kl]; private int sum=0; gg(int n, int m) { } // String result() { // return this.sst; // } public void digui(int t, int nn, int m) { if(t > kl-1) { } if (nn == m) { if(count < bestcount) { } return ; for (int i = 0; i < 2; i++) { if(i==0) { sss[t]='f'; count++; digui(t+1,nn*3,m); count--; sss[t]='0'; sss[t]='g'; count++; digui(t+1,nn/2,m); count--; sss[t]='0'; bestcount = count; for(int i = 0; i < kl;i++) bestsss[i]=sss[i]; return ; for (int i = 0; i < kl; i++) { } this.n = n; this.m = m; nn = n; sss[i] = '0'; } else { }else{
} } } } } public void show() { } for (int i = kl-1; i >= 0; i--) { } System.out.println(); System.out.println(sum); if (bestsss[i] != '0') { } sum++; System.out.print(bestsss[i]); 3.1.3 实验结论 要有截图，验证最后结果（图片分布要合理）。 输入/输出应与TEST文件夹测试用例一致。 3.1.4 心得体会 这题刚开始做时有思路，感觉挺简单，但做了之后发现，死活不出来结果，只好百度，发现思路一样，写的主函数基本一样，但就差一个比较最好的遍历结果的数组因为这个树，能出结果可能有多个，加上了就过，功力不够 3.2 无优先级运算问题 3.2.1 算法设计思想 这题跟0-1背包问题很像，需要几个数组记录每次遍历子树时数字是否使用，使用的是哪些运算符,在主函数设置一个循环循环次数为数字个数，以此产生不同子树进行遍历，然后遍历时flag[]用以区分当前子树数字是否重复使用，oper[]用以判断字符当前递归是否重复使用，用递归遍历遍历子树，没有结果就
返回上个节点，将必要的结果清0，直至出现结果 3.2.2 程序源码 package demo; import java.util.Scanner; public class second { } public static boolean search(int dep) { if (dep > k) { if (found()) { getString(); System.out.println(\); static int n; static int a[]; static int m; // 数字个数 // 所给数组 // 结果数字个数 //当前数字 //判断数字的使用 static int num[]; static int flag[]; static int oper[]; //符号数组 0 1 2 3 + - * / static int k; //运算次数 static String s; //计算式字符串 public static void main(String[] args) { Scanner input = new Scanner(System.in); n = input.nextInt(); m = input.nextInt(); num = new int[n]; oper = new int[n]; flag = new int[n]; a = new int[n]; for (int p = 0; p < n; p++) { } input.close(); for (k = 0; k < n; k++) {//从传入的a数组进行依次实验+ - * /接下来的值用 } if (search(0)) { } System.out.println(k); System.out.println(s); return; a[p] = input.nextInt(); 以求出结果
} } } System.out.println(); return true; return false; } else { for (int i = 0; i < n; i++) if (flag[i] == 0) { } num[dep] = a[i]; flag[i] = 1; for (int j = 0; j < 4; j++) { oper[dep] = j; if (search(dep + 1)) return true; }//进入递归遍历树，如当前子树无结果，则该数字的使用次数清零，以便flag[i] = 0; 于其他num[i]创建新子树进行遍历 return false; public static void getString(){ } public static boolean found() { int x = num[0]; for (int i = 0; i < k; i++) { if (oper[i] == 0) { x += num[i + 1]; x -= num[i + 1]; x *= num[i + 1]; } else if (oper[i] == 1) { } else if (oper[i] == 2) { s = String.valueOf(num[0]); for (int i = 0; i < k; i++) { } if (oper[i] == 0) { } s +=(\+String.valueOf(num[i+1])); s +=(\+String.valueOf(num[i+1])); s +=(\+String.valueOf(num[i+1])); s +=(\+String.valueOf(num[i+1])); } else if (oper[i] == 1) { } else if (oper[i] == 2) { } else if (oper[i] == 3) {
实验3 回溯
