《 算法分析与设计 》递归问题实验报告
年 月 日
实验题目 选课课号 学 院 姓 名 递归问题 (2017-2018-2)-N0842180S0-20052-1 班 级 学 号 上机指导教师 理论课教师 实验目的及要求： 实验目的： 1. 深刻理解并掌握递归设计思想。 2. 提高应用递归设计算法的技能。 实验要求： 1. 理解递归程序设计的主要思想。 2. 理解递归的三大要素。 3. 变写递归函数，且用代码实现。 操作步骤(可附主要代码)： package 递归综合; public class Test4_5 { int maxIndex = 0; public void mergeMax(int[] t, int startIndex, int endIndex) { if(startIndex == endIndex) { return; }else { int midIndex = (startIndex + endIndex) / 2; mergeMax(t, startIndex, midIndex); mergeMax(t, midIndex + 1, endIndex); merge(t, startIndex, endIndex, maxIndex); System.out.println(t[maxIndex]); } } public void mergeMax(int[] t) { mergeMax(t, 0, t.length - 1); } public void merge(int[] t, int index1, int index2, int max) { if(t[index1] > t[index2]) { if(t[index1] > t[max]) { maxIndex = index1; }else { maxIndex = max; } }else { if(t[index2] > t[max]) { maxIndex = index2; }else { maxIndex = max; } } } public static void main(String[] args) { int[] t = {2,4,3,6,8,1,0,9}; Test4_5 test = new Test4_5(); test.mergeMax(t); System.out.println(t[test.maxIndex]); } } 实验结果： package 递归综合; public class Test5_7 { int result = 0; public void mergeMul(int n, int m) { if(n == 0) { return; } result += (n % 2) * m; n /= 2; m *= 2; mergeMul(n, m); } public static void main(String[] args) { Test5_7 test = new Test5_7(); test.mergeMul(50, 65); System.out.println(test.result); } } 实验结果： package 递归综合; public class Test5_2 { int selectIndex = -1; boolean flag = false; public void mergeSelect(int[] t, int startIndex, int endIndex, int selectNum) { if (startIndex == endIndex) { return; } else { int midIndex = (startIndex + endIndex) / 2; if (t[midIndex] == selectNum) { selectIndex = midIndex; flag = true; return; } else if (t[midIndex] > selectNum) { mergeSelect(t, startIndex, midIndex, selectNum); } else { mergeSelect(t, midIndex + 1, endIndex, selectNum); } if(!flag) { if (t[startIndex] == selectNum) { selectIndex = startIndex; } if(t[endIndex] == selectNum) { selectIndex = endIndex; } } } } public void mergeSelect(int[] t, int selectNum) { mergeSelect(t, 0, t.length - 1, selectNum); } public static void main(String[] args) { int[] t = {7,14,18,21,23,29,31,35,38}; Test5_2 test = new Test5_2(); test.mergeSelect(t, 40); System.out.println(test.selectIndex); } } 实验结果： 实验心得; 递归算法应注意其执行逻辑； 本实验设计难度并不大，但实现起来鄙视很简单，在列队的结构体中，成员有数据和数据的优先级，而且在每个元素如队列时，均要与原来的每个元素进行优先级比较，并进行存放位置的相应修改，出队与顺序队列无意； 应用于物理地址连续位置的存储情况； 教师评语 成 绩