中北大学软件学院算法实验报告附截图Word版

《中北大学软件学院算法实验报告附截图Word版》由会员分享，可在线阅读，更多相关《中北大学软件学院算法实验报告附截图Word版（51页珍藏版）》请在装配图网上搜索。

1、传播优秀Word版文档 ，希望对您有帮助，可双击去除！ 中北大学软件学院 实验报告专 业：_方 向：_课程名称：_班 级：_学 号：_姓 名：_辅导教师：_ 2016年3月制 成绩： 实验时间2016年4月7日8时至10时学时数21.实验名称实验一 串匹配程序设计2.实验目的(1) 熟练掌握串匹配的含义(2) 掌握BF算法匹配的过程并编程实现(3) 熟悉C+编译环境的基本操作3.实验内容 给定两个字符串S和T，用BF算法，在主串S中查找字串T，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图 基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者

2、的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。 设串S长度为n，串T长度为m，在匹配成功的情况下，考虑最坏情况，即每趟不成功的匹配都发生在串T的最后一个字符。设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)m次，第i趟成功的匹配共比较了m次，所以总共比较了im次，因此平均比较次数是： 最坏情况是O（nm）。或者写书上P39页的伪代码描述。5.实验过程或源

3、代码#include int BF(char S, char T) int index = 0; /主串从下标0开始第一趟匹配 int i = 0, j = 0; /设置比较的起始下标 while (Si != 0) & (Tj != 0) /模式匹配没有结束 printf(-从主串的第%d个位置开始与模式串进行匹配:（只输出回溯信息）n,i); if (Si = Tj) /相同位置字符相同 i+; j+; /向后匹配 else /相同位置字符不同 printf(由于主串下标i为%d的字符%c和模式串下标j为%d的字符%c失配,i,Si,j,Tj); index+; i = index; j

4、= 0; /i和j分别回溯 printf(所以i和j分别回溯到%d,%d重新开始匹配n,i,j); if (Tj = 0) return index + 1; /返回本趟匹配的开始位置（不是下标） else return 0;int main()char S100,T100;printf(请输入主串S(不超过100个字符):);scanf(%s,S);printf(请输入子串T(不超过100个字符):);scanf(%s,T);int index=BF(S,T);if(index = 0)printf(模式匹配失败！);elseprintf(模式匹配成功，子串%s在主串%s中首次匹配的位置是%

5、d,T,S,index);return 0; 6.实验结论及心得 通过本次实验我理解了使用蛮力法解决问题的特点，蛮力法的设计思想是直接基于问题本身的描述来设计算法，即不采用任何方法来精简计算过程、运算次数或者设法简化问题本身。所以蛮力法设计的算法虽然简单易懂，但是效率却往往不是很令人满意，比如串的模式匹配问题中采用BF算法效率低下的主要原因就在于BF算法一旦主串和子串匹配失败就会产生回溯，如果能利用已有的匹配结果来减少回溯就可以提高效率，如KMP算法。 成绩： 实验时间2016年4月7日8时至10时学时数21.实验名称实验二 排序问题程序设计2.实验目的(1) 掌握选择排序和起泡排序的基本思想

6、 (2) 掌握两种排序方法的具体实现过程(3) 在掌握的基础上编程实现两种排序方法3.实验内容 输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图 书上P42页选择排序想法三点抄上去 书上P43页冒泡排序想法三点抄上去5.实验过程或源代码/-选择排序-#include /对含有n个数的数组进行遍历 void visit(int r,int n)for(int i=0;in;i+)printf(%4d ,ri);printf(n);/选择排序 void SelectSort(int r , int n)

7、 int i, j, index, temp;int compare = 0,move = 0; for (i = 0; i n - 1; i+) /对n个记录进行n-1趟选择排序index = i; for (j = i + 1; j n; j+) /在无序区中查找最小记录if (rj rindex) index = j;compare+; /比较次数增加1 if (index != i) /交换记录temp = ri; ri = rindex; rindex = temp; move+=3; /交换一次移动3次 visit(r,10);printf(在本次排序中共比较了%d次，移动了%d次

8、。n,compare,move);int main()int r10=0;printf(请依次输入10个整数，用空格隔开：n); for(int i=0;i10;i+)scanf(%d,&ri);printf(排序之前的记录：n); visit(r,10);printf(进行选择排序：(每趟排序后的结果如下所示)n); SelectSort(r,10);printf(排序之后的记录：n); visit(r,10);return 0;/-选择排序-#include/对含有n个数的数组进行遍历 void visit(int r,int n)for(int i=0;in;i+)printf(%4d

9、,ri);printf(n);void BubbleSort(int r , int n)int count1 = 0, count2 = 0; /count1和count2记载比较次数和移动次数 int bound, exchange = n - 1; /第一趟起泡排序的区间是0, n-1 while (exchange != 0) /当上一趟排序有记录交换时bound = exchange; exchange = 0; for (int j = 0; j rj+1) /注意不能写作count1+int temp = rj; rj = rj + 1; rj + 1 = temp;count2

10、 = count2 + 3; /1次交换是3次移动操作exchange = j; /记载每一次记录交换的位置visit(r,10); /每趟排序输出一次，观察记录的变动情况 printf(本次排序中的比较次数为%d,移动次数为%d。n,count1,count2);int main()int r10=0;printf(请依次输入10个整数，用空格隔开：n); for(int i=0;i10;i+)scanf(%d,&ri);printf(排序之前的记录：n); visit(r,10);printf(进行冒泡排序：(每趟排序后的结果如下所示)n); BubbleSort(r, 10);print

11、f(排序之后的记录：n); visit(r,10);return 0;6.实验结论及心得 通过本次实验我理解了选择排序和起泡排序的基本思想。选择排序和起泡排序都是通过将待排序记录划分成有序区和无序区，然后通过交换扩大有序区，缩小无序区，最终达到排序的目的。两者又有区别，选择排序可以直接选出无序区的最小记录并一次插入到合适的位置上，之后不再调整，而冒泡排序则是通过两两交换实现移动的，由于很多移动无法将记录一次放置到合适的位置上，所以存在很多“无效”的移动操作，从实验结果可以看出，起泡排序的移动次数明显比选择排序要多就是因为这样的“无效”的移动操作浪费了时间。 成绩： 实验时间2016年4月7日8

12、时至10时学时数21.实验名称实验三 数字旋转方阵程序设计2.实验目的(1) 掌握分治法的设计思想 (2) 掌握数字旋转方阵的具体实现过程(3) 熟练掌握二维数组的使用方法(4) 在掌握的基础上编程实现数字旋转方阵的实现过程3.实验内容 给出一个初始数据，在此数据的基础上由外层向里层填写数据，完成一个数字旋转方阵，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图 用二维数组dataNN表示NN的方阵，观察方阵中数字的规律，可以从外层向里层填数。 设变量size表示方阵的大小，则初始时size = N，填完一层则size = size - 2；设变量begin表示每一层的起始位置

13、，变量i和j分别表示行号和列号，则每一层初始时i = begin，j = begin。 将每一层的填数过程分为A、B、C、D四个区域，则每个区域需要填写size 1个数字，填写区域A时列号不变行号加1，填写区域B时行号不变列号加1，填写区域C时列号不变行号减1，填写区域D时行号不变列号减1。 显然，递归的结束条件是size等于0或size等于1。【写不下就算了】数字旋转方阵算法描述： 输入：当前层左上角要填的数字number，左上角的坐标begin，方阵的阶数size输出：数字旋转方阵1. 如果size等于0，则算法结束；2. 如果size等于1，则databeginbegin = numbe

14、r，算法结束；3. 初始化行、列下标i = begin, j = begin；4. 重复下述操作size 1次，填写区域A 4.1 dataij = number; number+; 4.2 行下标i+; 列下标不变；5. 重复下述操作size 1次，填写区域B 5.1 dataij = number; number+; 5.2 行下标不变；列下标j+;6. 重复下述操作size 1次，填写区域C 6.1 dataij = number; number+; 6.2 行下标i-; 列下标不变；7. 重复下述操作size 1次，填写区域D 7.1 dataij = number; number+;

15、 7.2 行下标不变，列下标j-;8. 调用函数Full在size-2阶方阵中左上角begin+1处从数字number开始填数；5.实验过程或源代码#include int data100100=0;int maxsize = 0;void printData(int size)for(int i=0;isize;i+)for(int j=0;jsize;j+)printf(%4d ,dataij);printf(n);printf(n);void Full(int number, int begin, int size) /从number 开始填写size 阶方阵，左上角的下标为(begin

16、, begin) int i, j, k; if (size = 0) /递归的边界条件，如果size等于0，则无须填写 return; if (size = 1) /递归的边界条件，如果size等于1 databeginbegin = number; /则只须填写number printData(maxsize); return; i = begin; j = begin; /初始化左上角下标 for (k = 0; k size - 1; k+) /填写区域A，共填写size - 1个数 dataij = number; /在当前位置填写number number+; i+; /行下标加1

17、 for (k = 0; k size - 1; k+) /填写区域B，共填写size - 1个数 dataij = number; /在当前位置填写number number+; j+; /列下标加1 for (k = 0; k size - 1; k+) /填写区域C，共填写size - 1个数 dataij = number; /在当前位置填写number number+; i-; /行下标减1 for (k = 0; k size - 1; k+) /填写区域D，共填写size - 1个数 dataij = number; /在当前位置填写number number+; j-; /列下

18、标减1 printData(maxsize); Full(number, begin + 1, size - 2); /递归求解，左上角下标为begin + 1int main() int size;printf(输入方阵的大小：);scanf(%d,&size);maxsize = size;printf(开始填充之前的数字旋转方阵：n);printData(maxsize);printf(填充过程：n);Full(1,0,size);printf(最终填充完成的结果是：n);printData(maxsize);return 0;6.实验结论及心得 通过本次实验，我理解了分治法解决问题的基

19、本思想和一般过程，分治法的基本思想是“分而治之”，将大的复杂的问题分解成结构同、规模小的子问题，分解子问题要足够小以至于可以直接得出子问题的解，然后对子问题的解进行合并，最终得到原问题的解。由于程序中采用了递归技术，需要设置递归终止的条件，在数字旋转方阵问题中，递归结束的条件是size等于0或者1。 递归问题的解决分为回溯和递推两个阶段，通过这两个过程可以求解本次实验的问题。 成绩： 实验时间2016年4月8日8时至10时学时数21.实验名称实验四 排序中分治法的程序设计2.实验目的(1) 掌握归并排序和快速排序的划分方法(2) 掌握归并排序和快速排序的具体分治策略(3) 在掌握的基础上编程两

20、种排序方法的实现过程3.实验内容 给出一个初始序列，分别用归并排序和快速排序两种分治法将所给序列变换为有序序列，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图 二路归并排序的分治策略是：（1）划分：将待排序序列r1, r2, , rn划分为两个长度相等的子序列r1, , rn/2和rn/21, , rn；（2）求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；（3）合并：将这两个有序子序列合并成一个有序序列。快速排序的分治策略是：（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1 ri-1和ri+1 rn，前一个子序列中记录的值均小于或等于

21、轴值，后一个子序列中记录的值均大于或等于轴值；（2）求解子问题：分别对划分后的每一个子序列递归处理；（3）合并：由于对子序列r1 ri-1和ri+1 rn的排序是就地进行的，所以合并不需要执行任何操作。【写不下就不写了】以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；（2）右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若ij，则将基准记录与j指向的记录进行交

22、换；（3）左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若ij，则将基准记录与i指向的记录交换；（4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。5.实验过程或源代码/-归并排序-#include/对含有n个数的数组进行遍历 void visit(int r,int n)for(int i=0;in;i+)printf(%4d ,ri);printf(n);void Merge(int r, int r1, int s, int m, int t) /合并子序列int i =

23、s, j = m + 1, k = s;printf(合并子序列r%dr%d,r%dr%d：n,s,m,m+1,t);printf(r :); visit(r,10);while(i = m & j = t) if(ri = rj) /取ri和rj中较小者放入r1kr1k+ = ri+; else r1k+ = rj+; while(i = m) /若第一个子序列没处理完，则进行收尾处理r1k+ = ri+; while(j = t) /若第二个子序列没处理完，则进行收尾处理r1k+ = rj+; printf(r1:); visit(r1,10); void MergeSort(int r,

24、 int s, int t) int m;int r11000 = 0;if(s = t) return; /递归的边界条件else m = (s + t)/2; /划分printf(将序列r%dr%d划分成r%dr%d、r%dr%d两个子序列进行求解：n,s,t,s,m,m+1,t);MergeSort(r, s, m); /求解子问题1，归并排序前半个子序列MergeSort(r, m+1, t); /求解子问题2，归并排序后半个子序列Merge(r, r1, s, m, t); /合并解，合并相邻有序子序列for(int i = s; i = t; i+)ri = r1i; int ma

25、in() int r10=0;printf(请依次输入10个整数，用空格隔开：n); for(int i=0;i10;i+)scanf(%d,&ri);printf(排序之前的记录：n);visit(r,10); MergeSort(r,0,9);printf(归并排序之后的记录：n);printf(r :); visit(r,10); return 0;/-快速排序-#include /对含有n个数的数组进行遍历 void visit(int r,int n)for(int i=0;in;i+)printf(%4d ,ri);printf(n);int Partition(int r, in

26、t first, int end) /划分 int i = first, j=end; /初始化待划分区间 while(i j) while(i j & ri = rj) j-; /右侧扫描 if(i j) int temp = ri; ri = rj; rj = temp; /将较小记录交换到前面i+; printf(r :); visit(r,10); while(i j & ri = rj) i+; /左侧扫描 if(i j)int temp = ri; ri = rj; rj = temp; /将较大记录交换到后面 j-; printf(r :); visit(r,10); retur

27、n i; / 返回轴值记录的位置void QuickSort(int r, int first, int end) /快速排序int pivot;if(first end) pivot = Partition(r, first, end); /划分，pivot是轴值在序列中的位置printf(将序列r%dr%d划分成r%dr%d、r%dr%d两个子序列进行求解，轴值是r%d=%d.nn,first,end,first,pivot-1first?first:pivot-1, pivot+1,end,pivot,rpivot);printf(r :); visit(r,10);QuickSort(

28、r, first, pivot-1);/求解子问题1，对左侧子序列进行快速排序QuickSort(r, pivot+1, end); /求解子问题2，对右侧子序列进行快速排序 int main()int r10=0;printf(请依次输入10个整数，用空格隔开：n); for(int i=0;i10;i+)scanf(%d,&ri);printf(排序之前的记录：n);printf(r :); visit(r,10);printf(n选取r0=%d作为轴值进行第一趟快速排序:n,r0); QuickSort(r,0,9);printf(快速排序之后的记录：n);printf(r :); vi

29、sit(r,10);return 0;6.实验结论及心得 通过本次实验，我理解了归并排序和快速排序的基本思想，两者都是将序列分为若干子序列，通过对子序列的排序，合并子序列，最终得到一个有序序列，这体现了分治法“分而治之”的思想。 这两种排序方法划分子序列的方式有所不同，归并排序按记录在序列中的位置进行划分，而快速排序则按照记录的值对序列进行划分，这就是两种排序方法在划分子序列上的不同之处。 成绩： 实验时间2016年4月8日8时至10时学时数21.实验名称实验五 汉诺塔问题的程序设计2.实验目的(1) 掌握递归的有关概念 (2) 掌握汉诺塔问题的具体求解过程(3) 在掌握的基础上编程实现汉诺塔

30、的具体实现过程3.实验内容 在A上有按大小排序好的n个金碟，借助B的帮助，将A上的碟子移动到C上，在移动的过程中要严格按照大小顺序，不能将碟子放在比它小的上面，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图汉诺塔问题可以通过以下三个步骤实现：（1）将塔A上的n-1个碟子借助塔C先移到塔B上。（2）把塔A上剩下的一个碟子移到塔C上。（3）将n-1个碟子从塔B借助塔A移到塔C上。 显然，这是一个递归求解的过程。【下方示意图画不下可省略】5.实验过程或源代码#includevoid Hanoi(int n, char A, char B, char C)if (n = 1) /将碟

31、子从A移到C上，递归结束printf(%c - %cn,A,C); else Hanoi(n-1, A, C, B); /将n-1个碟子从A借助C移到B上 printf(%c - %cn,A,C); /将碟子从A移到C上 Hanoi(n-1, B, A, C); /将n-1个碟子从B借助A移到C上int main()char A,B,C;Hanoi(3,A,B,C);printf(n);return 0;运行结果：A - CA - BC - BA - CB - AB - CA - C6.实验结论及心得 递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试

32、程序带来很大方便，是算法设计中的一种强有力的工具。但是，因为递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。 成绩： 实验时间2016年4月8日8时至10时学时数21.实验名称实验六 查找中减治法的程序设计2.实验目的(1) 掌握减治法的设计思想 (2) 掌握折半查找和二叉查找的思想及实现过程(3) 在掌握的基础上编程实现两种查找方法的具体实现过程3.实验内容 给出一个序列及要查找的值，分别用两种查找方法实现，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图 折半查找基本思想：在有序表中，取中

33、间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。 由二叉排序树的定义，在二叉排序树root中查找给定值k的过程是： 若root是空树，则查找失败； 若k根结点的值，则查找成功； 否则，若k根结点的值，则在root的左子树上查找； 否则，在root的右子树上查找； 上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。5.实验过程或源代码/- 折半查找 -#include

34、 int BinSearch1(int r, int n, int k)int low = 0, high = n - 1; /设置查找区间，注意数组下标从0开始int mid;while(low = high) /当区间存在时mid = (low + high) / 2; if(k rmid) /查找在右半区间进行 low = mid + 1; else /查找成功，返回元素序号return mid; return -1; /查找失败，返回-1int main()int r=12,34,2,56,35,10,56,34,21,7,find = 0;printf(请输入您想查找的值：);sca

35、nf(%d,&find);int i=BinSearch1(r,10,find);if(i != -1)printf(查找成功！元素的序号是：%dn,i+1);elseprintf(查找失败！n); return 0;/-二叉查找树-#includetypedef struct BiNodeint data; /结点的值，假设查找集合的元素为整型BiNode *lchild, *rchild; /指向左、右子树的指针 BiNode;BiNode * insertBST(BiNode *root, int data)if(root = NULL) /空树或空子树 root = new BiNod

36、e;root-data = data;root-lchild = NULL;root-rchild = NULL;return root;if(data data) /将数据插入到左子树 root-lchild = insertBST(root-lchild, data);else /将数据插入到右子树 root-rchild = insertBST(root-rchild, data);return root; /返回根节点 BiNode * createBST(int a, int n)BiNode *T = NULL;for(int i=0; i data = k) /查找成功retur

37、n root;else if(k data) /查找左子树return SearchBST(root-lchild, k); else /查找右子树return SearchBST(root-rchild, k);int main()BiNode *root, *t;int a10=12,34,2,56,35,10,56,34,21,7,find = 0;printf(-创建二叉排序树：n);root=createBST(a,10);printf(请输入您想查找的值（整数）:);scanf(%d,&find); t=SearchBST(root,find);if(t != NULL)print

38、f(查找成功！);elseprintf(查找失败！);return 0;6.实验结论及心得 分治法是把一个大问题划分为若干个子问题，分别求解各个子问题，然后再把子问题的解合并得到原问题的解。减治法同样是把一个大问题划分成若干个子问题，但这些子问题不需要分别求解，只需求解其中一个子问题，因而也无需对子问题的解进行合并。正是因为少解了很多重复的子问题并且没有了子问题合并的过程，应用减治法处理问题的效率是很高的。 成绩： 实验时间2016年4月11日16时至18时学时数21.实验名称实验七 排序中减治法的程序设计2.实验目的(1) 掌握堆的有关概念(2) 掌握堆排序的基本思想和其算法的实现过程(3)

39、 熟练掌握筛选算法的实现过程(4) 在掌握的基础上编程实现堆排序的具体实现过程3.实验内容 给出一个记录序列，用堆排序的方法将其进行升序排列，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图 堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。 假设当前要筛选结点的编号为k，堆中最后一个结点的编号为n，并且结点k的左右子树均是堆（即rk+1 rn满足堆的条件），则筛选算法用伪代码可描述为

40、： 1. 设置i和j，分别指向当前要筛选的结点和要筛选结点的左孩子； 2. 若结点i已是叶子，则筛选完毕；否则，比较要筛选结点的左右 孩子结点，并将j指向关键码较大的结点； 3. 将要筛选结点i的关键码与结点j的关键码进行比较，有以下两种情况： 3.1 如果结点i的关键码大，则完全二叉树已经是堆； 3.2 否则将ri与rj交换；令i=j，转步骤2继续进行筛选；5.实验过程或源代码#include void visit(int r,int n)for(int i=0;i10;i+)printf(%4d ,ri);printf(n);void SiftHeap(int r, int k, int

41、n)int i, j, temp;i = k; /置i为要筛的结点，j为i的左孩子j = 2 * i +1; while (j n) /筛选还没有进行到叶子if (j n-1 & rj rj) /根结点已经大于左右孩子中的较大者break; else temp = ri; ri = rj; rj = temp; /将被筛结点与结点j交换i = j; j = 2 * i+1; /被筛结点位于原来结点j的位置void HeapSort(int r , int n)int i, temp;int count = 0; /记录堆调整的次数 for(i = (n-1)/2; i = 0; i-) /初始

42、建堆，从最后一个分支结点至根结点SiftHeap(r, i, n) ; printf(初始建堆第%d次调整堆之后：n,+count); printf(r:);visit(r,10); printf(-建堆后：n);printf(r:);visit(r,10); for (i = 1; i 排序前的序列：n);printf(r:);visit(r,10);HeapSort(r,10);printf(-堆排序后的序列:n);printf(r:);visit(r,10);return 0;6.实验结论及心得 如何将无序序列调整为堆是堆排序算法的关键，筛选法调整是成功应用减治法的例子。在堆调整的过程中

43、，总是将根节点（即被调整结点）与左右子树的根节点进行比较，若不满足堆的条件，则将根节点与左右子树中根结点的较大者交换，所以每比较一次，需要调整的完全二叉树的问题规模就减小一半，因此，其时间性能是O(log2n)。这个自堆顶至叶子的调整过程称为筛选。 成绩： 实验时间2016年4月11日16时至18时学时数21.实验名称实验八 淘汰赛冠军问题的程序设计2.实验目的(1) 掌握减治法的设计思想 (2) 掌握淘汰赛冠军问题的具体实现过程(3) 通过这个实例进一步掌握递归技术的运用(4) 在掌握的基础上编程实现淘汰赛冠军问题的具体实现过程3.实验内容 假设有n个选手进行竞技淘汰赛，最后决出冠军的选手，

44、请设计竞技淘汰比赛的过程，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图抄书上P90页的想法5.实验过程或源代码#include int Comp(char a,char b)if(ab) /按照字符的ASCII码进行比较 return 1;else return 0;char Game(char r, int n)int i = n;while (i 1) /比赛直到剩余1人即为冠军i = i/2;for (int j = 0; j i; j+)printf(在%c与%c的比赛中，,rj+i,rj); if (Comp(rj+i, rj) /胜者存入rj中rj = rj+i

45、;printf(%c胜出!n,rj); return r0;int main()char r=ABCDEFGH;char c=Game(r,8);printf(最后的冠军是：%c,c);return 0;6.实验结论及心得 在淘汰赛冠军问题中，通过让选手两两竞争的方法，每次比赛可以去掉1/2的选手，减小了子问题的求解次数，节约了时间。将选手进行分组体现了分治法“分而治之”的思想，让选手通过两两竞争的方法减少比赛的次数的方法体现了减治法的思想。 成绩： 实验时间2016年4月11日16时至18时学时数21.实验名称实验九 数塔问题的程序设计2.实验目的(1) 掌握动态规划法的设计思想 (2) 掌

46、握数塔问题的具体实现过程(3) 熟练掌握二维数组的使用方法(4) 在掌握的基础上编程实现数塔问题的具体实现过程3.实验内容 给出一个数塔，从该数塔的顶层出发，在每一个节点可以选择向左走或向右走，一直走到该数塔的最底层，找出一条路径，使得路径上的数值和最大，输出最大数值及其路径，输出时要求有文字说明。请编写程序。4.实验原理或流程图想法：1. 求解初始子问题：底层的每个数字可以看作1层数塔，则最大数值和就是其自身；2. 再求解下一阶段的子问题：第4层的决策是在底层决策的基础上进行求解，可以看作4个2层数塔，对每个数塔进行求解；3. 再求解下一阶段的子问题：第3层的决策是在第4层决策的基础上进行求

47、解，可以看作3个2层的数塔，对每个数塔进行求解；4. 以此类推，直到最后一个阶段：第1层的决策结果就是数塔问题的整体最优解。【写不下就算了】算法：1. 初始化数组maxAdd的最后一行为数塔的底层数据： for (j = 0; j n; j+) maxAddn-1j = dn-1j;2. 从第n-1层开始直到第 1 层对下三角元素maxAddij执行下述操作： 2.1 maxAddij = dij + maxmaxAddi+1j, maxAddi+1j+1； 2.2 如果选择下标j的元素，则pathij = j，否则pathij = j+1；3. 输出最大数值和maxAdd00；4. 根据path数组确定每一层决策的列下标，输出路径信息；5.实验过程或源代码#include#define n 5void printArray(int maxAddnn,int pathnn)printf(nmaxAdd%d%d:n,n,n);for(int i = 0;i n;i+)for(int j = 0;j = i;j+)printf(%4d ,maxAddij);printf(n);printf(npath%d%d:n,n,n);for(int i = 0;i n;i+)for(int j = 0;j = i;j+)