精选资料算法设计与分析上机指导

1、算法设计与分析课程上机指导上机常见错误与对策 1上机指导1 2上机指导2 5计算机与信息学院2011-1014上机常见错误与对策创建工程时，选错工程类型（应选择倒数第三个“ Win32 Console Application”）；创建源程序文件时，选错文件类型。要修改程序，应打开工作区（dsw）文件，而不是源程序（cpp）文件。在 VC+ 系统中，程序是用西文字符（ ASCII 码；来描述的，汉字只能出现在 字符串常数或注释中。请注意汉字双引号和西文双引号的区别 请注意汉字单引号和西文单引号的区别 请注意汉字分号和西文分号的区别 请注意汉字园括号和西文园括号的区别在一般情况下，一个工作区只有一

2、个工程，一个工程对应一个程序。当一个 程序完成，编制下一个程序时，一定要新建工程（不要修改系统默认设置“创 建新工作区”）。最简单的方法是：退出 VC+集成环境后，重新进入 VC+。 当系统出现不可解释的现象时，此时应选择编译”-重建全部”然后执行。若还不行，则重新启动计算机，利用硬盘保护卡功能恢复系统。操作步骤： 重新启动计算机后，出现菜单画面。选中 Windows 2000 Professional在按住Ctrl”键的同时，按R”健。对于系统提问，按Y ”键回答。源程序若有错误，编译系统会在输出区显示错误信息。由于识别错误能力有 限，指示的错误信息有时不一定完全正确，但至少提供了线索。双击

3、错误信息 条目，指针会自动指向出错语句，编程者可逐字符查找错误。算法设计与分析上机指导 1（每个）程序书写要求/ */ *工 程 名：103.dsp/ *程 序 名：103.cpp/ *主要功能：自底向上合并排序法/ *学号姓名：57053001 某某某/ *编制时间：2011年7月 13日/*#include void main()/#include /using namespace std;/int main()/ / return 0;/实习内容习题一（工程名为 101、源程序名为 101） 选择排序法的伪代码描述如下： 算法 1.4 SelectionSor（t 参见 Page 8）

4、输入：数组 A1.n 输出：按升序排列的数组 A1.n1. for iJ 1 to n-12. Selection(i)3. end for过程 Selection(i)1. kJi2. for j J i+1 to n3. if Aj0) and (Ajx)4. Aj+1JAj5. j Jj-16. end while7. Aj+1 Jx用 C 语言实现上述算法并上机通过。 选做题：用递归方法(归纳法)实现插入排序法习题三(工程名为 103、源程序名为 103) 自底向上合并排序法的伪代码描述如下：算法 1.6 BottomUpSort( Page 10) 输入： n 个元素的数组 A1.n

5、 输出：按升序排列的数组 A1.n1. tJ 12. while tn3. k t : t J 2s :iJ 04. while i+t n5. Merge(A,i+1,i+s,i+t) /Merge(A,p,q,r)6. iJi+t7. end while8. if i+ss 表示剩余的元素个数大于被合并的子序列长度过程 Merge(A1.m,p,q,r)1. comment:Bp.r是个辅助数组2. sJp : tJq+1 : kJp3. while (s q) and (t r)4./或 B1.ms和t分别指向数组A二个子数组元素k指向数组B当前空白元素位置if As At then B

6、k J As : sj s+15. else BkJAt : tJt+16. end if7. kJk+18. end while9. if s=q+1 then Bk.rJAt.r10. else Bk.rJAs.q11. end if12. Ap.rJ Bp.r 用 C 语言实现上述算法并上机通过。/指向数组 B 下一个空白位置说明子数组Ap.q元素已处理完否则t=r+1，说明子数组Aq+1.r已处理元选做题：用递归方法（分治法）实现自底向上合并排序法。习题四(工程名为 104、源程序名为 104) 参考下列程序，对习题一和习题三的程序作适当修改。通过上机运行，实验测 评二种排序算法运行效

7、率，以期在理论和实践上得出一致的结论。 选择排序算法修改#include #include #include #include #include #define N 65536*2void Selection(short,int);void main()short AN+1;srand(time(NULL);for(int i=1;i=N;i+)Ai=rand()%10000;time_t t1,t2;struct tm *pt; time(&t1);pt=gmtime(&t1); coutsetfill(0);coutvv排序开始时间：； coutsetw(2)tm_hour+8)%24:s

8、etw(2)tm_mintm_secvvendl； coutvvSelectionSort排序中vvflush;for(i=1；iv=N-1；i+)if(i%2048=0)coutvv.vvflush;Selection(A,i);coutvvendlvv排序结束时间:; time(&t2);pt=gmtime(&t2);coutvvsetw(2)vv(pt-tm_hour+8)%24vv:vvsetw(2)vvpt-tm_minvv:setw(2)tm_sec#include vstdlib.h#include viomanip.h#include vconio.h#include vtim

9、e.hconst int N=65536*2;void BottomUpSort(short,int);void Merg(short,int,int,int);void main()short AN+1;srand(time(NULL);for(int i=1;iv=N;i+)Ai=rand()%1000;time_t t1,t2;struct tm *pt;time(&t1);pt=gmtime(&t1);coutvvsetfill(0);coutvv排序开始时间:;coutvvsetw(2)vv(pt-tm_hour+8)%24vv:vvsetw(2)vvpt-tm_minvv :vvs

10、etw(2)vvpt-tm_secvvendl;coutvvMergeSort 排序中vvflush;BottomUpSort(A,N);time(&t2);pt=gmtime(&t2);coutvvendlvv排序结束时间:; coutvvsetw(2)vv(pt-tm_hour+8)%24vv:vvsetw(2)vvpt-tm_minvv:vvsetw(2)vvpt-tm_secvvendl;coutvv排序耗费时间=t2-t1endl;/ getch();void BottomUpSort(short A,int n)int i,t=1,s;while(tn)coutvv.vvflush

11、;s=t;t=2*s;i=0;程序运行结果SelectionSort斑E:ly FileS08-09学年第二学期算法设计与分析选择排序法Debug3. exe 腓序开始时间：21咱1：39iongoFt 排序中鼬垦吉$&t（B：21：02：25腓序耗费时可胡MergeSort輕E:Iy FileS08-09学年第二学期算法设计与分析I归并排序法Debug4. exe邑E序开始时MepgeSoit可：20：58：23F序中可：20：58：37可=14提交方式首先建立个人目录，目录名为 学号姓名”例“5705300某某某”在目录“5705300某某某”中，建立子目录1 （本次实习）。在目录“570

12、5300某某某1”中，应具有如下文件：101.cpp 101.exe 102.cpp 102.exe103.cpp 103.exe 104.cpp 104.exe算法设计与分析上机指导 2（每个）程序书写要求/*/ * 工 程 名： 103.dsp/ * 程 序 名： 103.cpp/ * 主要功能：自底向上合并排序法/ * 学号姓名： 57053001某某某/ * 编制时间： 2011年7月 13日/ *#include void main()/#include /using namespace std;/int main()/ / return 0;/实习内容习题一(工程名为 201、源程

13、序名为 201) 快速排序法的伪代码描述如下：算法 6.6 Quicksort (参见 Page 114输入：有 n 个元素的数组 A1.n 输出：按升序排列的数组 A1.n1. QuickSort(A,1,n)过程 QuickSort(A1.n,low,high)1. if lowhigh then2. w=Split(A,low,high)3. QuickSort(A,low,w-1)4. QuickSort(A,w+1,high)5. ens if过程 procedure Split(A1.n,low,high)1. iJlow初始时i指向Alow2.xj Alow处理过程中有：Alow

14、.iw x=Alow3.for jj low+1 to high/j 指向当前处理的元素4.if Aj x=Alow5.6.iji+1 if j then 互换 Ai和 Aj7. end if8. end for9. if lowM i then 互换 Alow和 Ai10. wji11. return w用 C 语言实现上述算法并上机通过。习题二(工程名为 202、源程序名为 202) 解最长公共子序列问题的伪代码描述如下：算法 LCSRec (递归算法)输入：字符串A和B,设A和B的长度分别为n和m。输出： A 和 B 的最长公共子序列的长度1. LCSRec(n,m)过程 procedu

15、re LCSRec(i,j)1. if i=0 or j=0 then return 02. else3. if Ai=Bj then4. return LCSRec(i-1,j-1)+15. else6. return max(LCSRec(i,j-1),LCSRec(i-1,j)7. end if8. end if用C语言实现上述算法并上机通过。选做题：给出最长公共子序列问题的非递归算法(动态规划法) ,并上机通过习题三（工程名为 203、源程序名为 203） 解背包问题的伪代码描述如下： 算法 7.4 Knapsack (参见 Page 139输入：背包容量C、物品体积集合S = Sl,S2,.,Sn、物品价值集合V = v1,V2,.,Vn 输出：可装入背包物品的最大总价值/背包容量为 0/背包未装入任何物品物品ui的体积s超过容量j,不装入。/取上一次的计算结果物品ui的体积s不超过容量j,可装入1. for iJ0 to n Vi,0 02. for j J 0 to C V0,j J 03. for iJ1 to n4. for j J1 to C5. if si j then6. Vi,j JVi-1,j7. else8. Vi,jJmax(Vi-1,j,Vi-1,j-s i+vi)9. end if10. end for11. end for12. retur