《算法分析与设计》实验报告
实验二 分治法算法设计
姓名 贺程 学号 1009040130 班级 电子商务1002班
时间 2013/3/12 地点 文波机房 同 组 人 无 指导教师 朱少林 实验目的
a) 掌握分治法算法设计的一般思想和方法。
b) 理解并掌握二分查找、归并分类、快速分类算法。 c) 能熟练运用分治法求解问题。
a) 实验中所准备的数据是有代表性的。 实验内容
a) 写一个顺序查找算法，将其与二分查找算法一起转换成程序，上机验证。 b) 选择不同规模的数据集运行上述二程序，统计它们的时间开销并比较。 c) 归并分类、快速分类算法转换成程序并验证之。
d) 选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。 相关内容
（1）分治策略的抽象化控制
Procedure DANDC(p, q)
Global n, A(1:n); integer m,p,q //1≤p≤q≤n// If SMALL(p,q)
Then return(G(p,q))
Else m←DIVIDE(p,q) //p≤m＜q//
Return(COMBINE(DANDC(p,m),DANDC(m+1,q))) Endif endDANDC
（2）二分检索算法
Procedure BINSRCH(A,n,x,j)
//给定一个按非降次序排列的元素数组A(1:n)，n≥1，判断x是否出现。// //若是，置j，使得x=A(j)，若非，j=0// Integer low, high, mid, j, n ; low←1;high←n while low≤high do
mid←int((low+high)/2) case
:xA(mid): low←mid+1
:else: j←mid; return Endcase Repeat j←0
endBINSRCH （3）归并分类算法
Procedure MERGESORT(low, high)
//A(low : high)是一个全程数组，它含有high-low+1≥0个待分类的元素// Integer low, high; If low < high then
mid ← int((low+high)/2) //求这个集合的分割点// call MERGESORT(low, mid) //将一个子集合分类// call MERGESORT(mid+1, high)//将另一个子集合分类// CALL MERGE(low,mid,high) //归并两个已分类的子集合// Endif
endMERGESORT
Procedure MERGE(low, mid, high) //A(low : high)是一个全程数组，它含有两个放在A（low : mid）和A（mid+1 : high）中的已分类的子集合。目标是将这两个已分类的集合归并成一个集合，并存放到A(low : high)中// //使用一个辅助数组B(low : high)//
Integer h, I, j, k, low, mid, high; //low≤mid while h≤mid and j≤high do //当两个集合都没有取尽时// if A(h)≤A(j) then B(i) ←A(h); h←h+1 else B(i) ←A(j); j←j+1 endif i←i+1 repeat if h>mid then for k←j to high do //处理剩余的元素// B(i) ←A(k);i←i+1 repeat Else for k←h to mid do B(i) ←A(k); i←i+1 repeat endif for k← low to high do //将已归并的集合复制到A// A(k) ← B(k) repeat endMERGE （4）改进的归并分类算法 Procedure MERGESORT1(low, high, p) // 利用辅助数组LINK(low : high)将全程数组A(low : high)按降序分类。 LINK中的值表示按分类次序给出A的下标的表，并把p置于指示这表的开始处// Global A(low : high), LINK(low : high) If high-low+1 < 16 Then call INSERTIONSORT(A, LONK, low, high, p) Else mid ← int((low+high)/2) call MERGESORT(low, mid, q) //返回q表// call MERGESORT(mid+1, high, r)//返回r表// CALL MERGE(q, r, p) //将表q和r归并成表p// Endif endMERGESORT1 Procedure MERGE1(low, mid, high) //q和r是全程数组LINK(1 : n)中两个表的指针，这两个表可用来获得全程数组A（1 : n）中已分类的子集合。此算法执行后构造出一个由p所指示的新表，利用此表可以得到按非降次序把A中元素分好类的元素表，同时q和r所指示的表随之消失。假定LINK（0）被定义，且假定表由0所结束。// //使用一个辅助数组B(low : high)// Global n, A（1 : n）LINK（0 : n） Local integer i, j, k i ←q; j←r; k←0 //新表在LINK（0）处开始// while i≠0 and j≠0 do //当两表皆非空时// if A(h)≤A(j) //找较小的关键字// then LINK(k) ←i; k←i; i←LINK(i) //加一个新关键字到此表// else LINK(k) ←j; k←j; j←LINK(j) endif i←i+1 repeat if i=0 then LINK(k) ←j //处理剩余的元素// Else LINK(k) ←i endif p←LINK(0) endMERGE1 （5）快速分类算法 Procedure QUICKSORT(p, q) //将全程数组A(1 : n)中元素A(p)，…，A(q)按递增的方式分类，认为A(n+1)已被定义，且大于或等于A(p : q)的所有元素，即A(n+1)=+∞// Integer p, q; global n, A(1 : n) If p Then j←q+1 call PARTITION(p,j) call QUICKSORT(p,j-1) //j是划分元素的位置// call QUICKSORT(j+1,q) endif endQUICKSORT Procedure PARTITION(m , p) //在A（m），A（m+1），…，A（p-1）中的元素按如下方式重新排列：如果最初t= A（m），则在重新排列后，对于m和p-1之间的某个q，有A（q）=t，并使得对于m≤k Integer m, p, i; global A(m : p-1) v←A(m);i←m; //A（m）是划分元素// loop loop i←i+1 until A(i)≥v repeat // i由左向右移// loop p←p-1 until A(p)≤v repeat //p由右向左移// if i then call INTERCHANGE(A(i), A(p)) //A（i）和A（p）换位// else exit endif repeat A(m)←A(p);A(p)←v endPARTITION 实验步骤 a) 准备一定规模的数据集用于实验。此数据集越大越有得于验证算法，可以考虑最终 的数据个数超过10000个。 b) 编写归并分类、快速分类程序，将上数据集中的数据分类。可以使用较少的数据调 试程序时。 c) 用规模从小到大的数据集运行上述程序，统计它们的运行时间，并作对比分析。 d) 编写顺序查找、二分查找程序。 e) 将查找程序与分类程序结合起来，用不同规模的数据集运行，统计程序运行时间。 附加实验与思考 （1）写一个自底向上的归并分类算法，并编程调试通过。用不同个数的数据运行该程序， 给出程序执行时间曲线。 （2）设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 ①每个选手必须与其它n-1选手各赛一次； ②每个选手一天只能赛一次。 （3）任选一个可以用分治法求解的问题并用分治思想设计算法求解，将所设计算法转换 成程序上机验证。 实验步骤 首先用种子生成器生成100000个整型数写到test.txt中，下面用到的测试数据均从text.txt中取，文件key.txt中只存放一个整型数800，用作查找的关键字，将排好序的数据写到文件sortResult.txt中。 key.txt中的内容： 800 文件test.txt和sortResult.txt中包含有100000行数据，这里就不便显示。 1． 顺序查找 #include FILE *f1,*f2; int t1,t2; int search_seq(int key,int n[]) { int i = 0; while(key != n[i] && i < len) i++; if(key == n[i]) return i; else return -1; } void main() { int key,i=0,j,data,n[len]; f1 = fopen(\//读操作 f2 = fopen(\ fscanf(f1,\ while(i < len){ //这里用数组存放文件中的数据，占用了额外的存储空间，但是可以方便对不同算法进行时间复杂度分析 fscanf(f2,\ n[i++] = data; } fclose(f1); fclose(f2); t1 = clock(); for(j = 0;j < N;j++) i = search_seq(key,n); t2 = clock(); if(i == -1) 搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新经管营销1009040130-贺程-实验2 全文阅读和word下载服务。
相关推荐：
轻烟薄雾