算法分析教学案设计实验报告.docx
- 文档编号:16133658
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:30
- 大小:282.70KB
算法分析教学案设计实验报告.docx
《算法分析教学案设计实验报告.docx》由会员分享,可在线阅读,更多相关《算法分析教学案设计实验报告.docx(30页珍藏版)》请在冰点文库上搜索。
算法分析教学案设计实验报告
****
院系:
计算机科学学院
专业:
计算机科学与技术
年级:
课程名称:
算法设计与分析基础
班号:
组号:
指导教师:
年月日
组员
学号
姓名
实验名称
算法实验整体框架的构建
实验室
实
验
目
的
或
要
求
1.实验题目
算法实验主菜单的设计。
2.实验目的
⑴熟悉实验环境VC++6.0;
⑵复习C、C++语言以及数据结构课程的相关知识,实现课程间的平滑过度;
3.实验要求
1)设计的主菜单可以是图形模式的,也可以是控制台模式的。
以控制台为例,主菜单大致如下:
-------------------------
《算法设计与分析》实验
-------------------------
1.算法分析基础——Fibonacci序列问题
2.分治法在数值问题中的应用——最近点对问题
3.减治法在组合问题中的应用——8枚硬币问题
4.变治法在排序问题中的应用——堆排序问题
5.动态规划法在图问题中的应用——全源最短路径问题
99.退出本实验
-------------------------
请输入您所要执行的操作(1,2,3,4,5,99):
2)点击操作后进入相应的实验项目或是相应项目的下一级菜单;
3)可以反复执行,直到退出实验。
程
序
代
码
voidMeun()
{
printf("\n\t\t-------------------------\n");
printf("\n\t\t《算法设计与分析》实验\n");
printf("\n\t\t-------------------------\n");
printf("\n\t\t1、算法分析基础——Fibonacci序列问题\n");
printf("\n\t\t2、分治法在数值问题中的应用——矩阵相乘问题\n");
printf("\n\t\t3、减治法在组合问题中的应用——枚硬币问题\n");
printf("\n\t\t4、变治法在排序问题中的应用——堆排序问题\n");
Printf("\n\t\t4、动态规划法在图问题中的应用——全源最短路径问题\n");
动态规划法在图问题中的应用——全源最短路径问题
printf("\n\t\t99、退出本实验\n");
printf("\n\t\t-------------------------");
printf("\n\t\t请输入您所要执行的操作(1,2,3,4,5,99):
");
}
voidmain()
{
inta;
while
(1)
{
Meun();//调用菜单函数显示菜单
scanf("%d",&a);
switch(a)
{
case1:
{
printf("\n\t\tFibonacci序列问题\t\t\n");
fibonacci();
break;
}
case2:
{
printf("\n\t\t分治法在数值问题中的应用——矩阵相乘问题\t\t\n");
matrix();
break;
}
case3:
{
printf("\n\t\t减治法在组合问题中的应用——8枚硬币问题\t\t\n");
COINFAKE();
break;
}
case4:
{
printf("\n\t\t变治法在排序问题中的应用——堆排序问题\t\t\n");
HEAP();
break;
}
case5:
{
printf("\n\t\t动态规划法在图问题中的应用——全源最短路径问题\t\t\n");
break;
}
case99:
{
printf("你选择退出本实验‘\n");
exit(0);
}
}
}
}
实
验
结
果
及
分
析
实验名称
算法分析基础——Fibonacci序列问题
实验室
实
验
目
的
或
要
求
实验题目
给定一个非负整数n,计算第n个Fibonacci数
实验目的
1)理解递归算法和迭代算法的设计思想以及递归程序的调式技术
2)掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法;
3)理解这样一个观点:
不同的算法可以解决相同的问题,这些算法的解题思路不同,复杂程度不同,效率也不同;
实验要求
1)使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得第n个Fibonacci数不超过计算机所能表示的最大整数,并给出具体的执行时间;
2)对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间,并同1)的执行时间进行比较;
3)对于输入同样的非负整数n,比较上述两种算法基本操作的执行次数;
4)对1)中的迭代算法进行改进,使得改进后的迭代算法其空间复杂度为Θ
(1);
5)设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。
实
验
原
理
(算
法
基
本
思
想)
1、递归法基本思想
递归就是定义一个函数,让它自己调用自己。
Fib(intn)
//输入整数n,输出第n个斐波那契数
{if(n=0)return0;
Elseif(n=1)return1;
ElsereturnFib(n-1)+Fib(n-2)
}
2、迭代法
这种方法相对于递归法来说在时间复杂度上减小了不少,但代码相对就要复杂些了。
Fib(intn)
//输入整数n,输出第n个斐波那契数
{if(n=0)return0;
Elseif(n=1)return1;
Else
F0←0;
F1←1;
for(i=2;i { F2=f1+f0;//f1表示当前的值 F0←F1 F1←F2; } ReturnF2; } 程 序 代 码 intFib(inti) { if(i<2) returni; else returnFib(i-1)+Fib(i-2); } voidDiGui() { intf=0,i=0,t=0; doublestart,end; start=clock(); while(2*t>=0) { t=f; f=Fib(i); printf("%d",f); i++; } printf("\n计算机最大可表示第%d个斐波拉契数\n",i); end=clock(); printf("运行时间为%f秒\n",(end-start)/1000); } voidDieDai() { longshu[3],count; doublestart,end; start=clock(); shu[0]=0; shu[1]=1; printf("%ld",shu[0]); for(count=1;shu[1]>=shu[0];count++) { printf("%ld",shu[1]); shu[2]=shu[1]+shu[0]; shu[0]=shu[1]; shu[1]=shu[2]; } printf("\n计算机最大可表示第%d个斐波拉契数\n",count); end=clock(); printf("运行时间为%f毫秒\n",end-start); } voidFibonacci() { printf("\n迭代算法: \n"); DieDai(); printf("\n递归算法: \n"); DiGui(); } 实 验 结 果 及 分 析 通过比较两种方法求Fibonacci数列所用的时间,可以发现迭代法的效率明显高于递归法。 同时也明白了不同的算法可以解决相同的问题,这些算法的解题思路不同,复杂程度不同,效率也不同。 实验名称 分治法在数值问题中的应用 ——矩阵相乘问题 实验室 实 验 目 的 或 要 求 实验题目 设M1和M2是两个n×n的矩阵,设计算法计算M1×M2的乘积。 实验目的 1)提高应用蛮力法设计算法的技能; 2)深刻理解并掌握分治法的设计思想; 3)理解这样一个观点: 用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对其进行改进,以提高算法的效率。 实验要求 1)设计并实现用BF方法求解矩阵相乘问题的算法; 2)设计并实现用DAC方法求解矩阵相乘问题的算法; 3)以上两种算法的输入既可以手动输入,也可以自动生成; 4)对上述两个算法进行时间复杂性分析,并设计实验程序验证 分析结果; 5)设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。 实 验 原 理 (算 法 基 本 思 想) 1)蛮力法求解 蛮力法比较简单,直接使用矩阵相乘公式计算矩阵的每行每列的值,很容易就能得出答案 2)分治法求解 分治法思想 将问题实例划分为同一问题的几个较小的实例。 对这些较小实例求解,通常使用递归方法,但在问题规模足够小时,也会使用另一种算法。 如果有必要,合并这些问题的解,以得到原始问题的解。 求解矩阵相乘的DAC算法,使用了strassen算法。 DAC(A[],B[],n) { Ifn=2使用7次乘法的方法求得解 Else Divide(A)//把A分成4块 Divide(B)//把B分成4块 调用7次strassen算法求得解的4块 合并这4块得到解并返回 } 程 序 代 码 //矩阵相乘问题 voidmatric(intn,floatA[N][N],floatB[N][N],floatC[N][N]) { LARGE_INTEGERstartTime; LARGE_INTEGERendTime; QueryPerformanceCounter(&startTime); inti,j,k; for(i=0;i { for(j=0;j C[i][j]=0; } for(i=0;i for(j=0;j for(k=0;k C[i][j]+=A[i][k]*B[k][j]; QueryPerformanceCounter(&endTime); LARGE_INTEGERtotalTime; totalTime.QuadPart=endTime.QuadPart-startTime.QuadPart; printf("%ld\n",totalTime.QuadPart); } voidMATRIX_MULTIPLY(floatA[][N],floatB[][N],floatC[][N])//按通常的矩阵乘法计算C=AB的子算法(仅做2阶) { inti,j,t; for(i=0;i<2;i++)//计算A*B-->C for(j=0;j<2;j++) { C[i][j]=0;//计算完一个C[i][j],C[i][j]应重新赋值为零 for(t=0;t<2;t++) C[i][j]=C[i][j]+A[i][t]*B[t][j]; } } voidMATRIX_ADD(intn,floatX[][N],floatY[][N],floatZ[][N])//矩阵加法函数X+Y—>Z { inti,j; for(i=0;i for(j=0;j Z[i][j]=X[i][j]+Y[i][j]; } voidMATRIX_SUB(intn,floatX[][N],floatY[][N],floatZ[][N])//矩阵减法函数X-Y—>Z { inti,j; for(i=0;i for(j=0;j Z[i][j]=X[i][j]-Y[i][j]; } voidSTRASSEN(intn,floatA[][N],floatB[][N],floatC[][N]) { floatA11[N][N],A12[N][N],A21[N][N],A22[N][N]; floatB11[N][N],B12[N][N],B21[N][N],B22[N][N]; floatC11[N][N],C12[N][N],C21[N][N],C22[N][N]; floatm1[N][N],m2[N][N],m3[N][N],m4[N][N],m5[N][N],m6[N][N],m7[N][N]; floatAA[N][N],BB[N][N],MM1[N][N],MM2[N][N]; inti,j; if(n==2) MATRIX_MULTIPLY(A,B,C); else { for(i=0;i for(j=0;j { A11[i][j]=A[i][j]; A12[i][j]=A[i][j+n/2]; A21[i][j]=A[i+n/2][j]; A22[i][j]=A[i+n/2][j+n/2]; B11[i][j]=B[i][j]; B12[i][j]=B[i][j+n/2]; B21[i][j]=B[i+n/2][j]; B22[i][j]=B[i+n/2][j+n/2]; } MATRIX_ADD(n/2,A11,A22,AA); MATRIX_ADD(n/2,B11,B22,BB); STRASSEN(n/2,AA,BB,m1); MATRIX_ADD(n/2,A21,A22,AA); STRASSEN(n/2,AA,B11,m2); MATRIX_SUB(n/2,B12,B22,BB); STRASSEN(n/2,A11,BB,m3); MATRIX_SUB(n/2,B21,B11,BB); STRASSEN(n/2,A22,BB,m4); MATRIX_ADD(n/2,A11,A12,AA); STRASSEN(n/2,AA,B22,m5); MATRIX_SUB(n/2,A21,A11,AA); MATRIX_ADD(n/2,B11,B12,BB); STRASSEN(n/2,AA,BB,m6); MATRIX_SUB(n/2,A12,A22,AA); MATRIX_ADD(n/2,B21,B22,BB); STRASSEN(n/2,AA,BB,m7); MATRIX_ADD(n/2,m1,m4,MM1); MATRIX_SUB(n/2,m5,m7,MM2); MATRIX_SUB(n/2,MM1,MM2,C11); MATRIX_ADD(n/2,m3,m5,C12); MATRIX_ADD(n/2,m2,m4,C21); MATRIX_ADD(n/2,m1,m3,MM1); MATRIX_SUB(n/2,m2,m6,MM2); MATRIX_SUB(n/2,MM1,MM2,C22); for(i=0;i for(j=0;j { C[i][j]=C11[i][j]; C[i][j+n/2]=C12[i][j]; C[i+n/2][j]=C21[i][j]; C[i+n/2][j+n/2]=C22[i][j]; } }//elsefinished } voidSHUru(intn,floatA[N][N],floatB[N][N]) {inti,j; printf("请输入A数据: \n"); for(i=0;i {for(j=0;j {scanf("%f",&A[i][j]); } } printf("请输入B数据: \n"); for(i=0;i {for(j=0;j {scanf("%f",&B[i][j]); } } } voidSHUIji(intn,floatA[N][N],floatB[N][N]) {inti,j; for(i=0;i {for(j=0;j {A[i][j]=(float)(n*rand()/(RAND_MAX+1.0)); } } printf("数组A中数据为: \n"); for(i=0;i {for(j=0;j {printf("%4f",A[i][j]); } printf("\n"); } for(i=0;i {for(j=0;j {B[i][j]=(float)(n*rand()/(RAND_MAX+1.0)); } } printf("数组B中数据为: \n"); for(i=0;i {for(j=0;j {printf("%4f",B[i][j]); } printf("\n"); } } voidprint1(intn,floatC[N][N]) {inti,j; printf("结果数组C中数据为: \n"); for(i=0;i {for(j=0;j {printf("%4f",C[i][j]); } printf("\n"); } } voidJz() {intn; floatA[N][N],B[N][N],C[N][N]; inti,j; printf("本程序用于计算M1×M2的乘积\n"); printf("输入矩阵阶数n: \n"); scanf("%d",&n); charflag; for(i=0;i {for(j=0;j C[i][j]=0; } printf("---1手动输入---\n"); printf("---2自动生成---\n"); printf("---3确定---\n"); while (1) {printf("请输入选择\n\n"); fflush(stdin); flag=getch(); switch(flag) {case'1': printf("手动输入\n"); SHUru(n,A,B); printf("\n");break; case'2': printf("自动生成\n"); SHUIji(n,A,B); printf("\n");break; case'3': gotocon; default: printf("按键错误\n"); } } con: printf("---1用BF方法----\n"); printf("---2用DAC方法---\n"); printf("---3结束-------\n"); while (1) {printf("请输入选择\n\n"); fflush(stdin); flag=getch(); switch(flag) {case'1': matric(n,A,B,C); printf("用BF方法得出的结果\n"); print1(n,C); printf("\n");break; case'2': STRASSEN(n,A,B,C); printf("用DAC方法得出的结果\n"); print1(n,C); printf("\n");break; case'3': return; default: printf("按键错误\n"); } } } 实 验 结 果 及 分 析 经过这个实验,我明白了蛮力法几乎可以解决所有的问题,但是算法的效率不高。 对蛮力法进行改进,经过适当的努力后,算法的效率可以得到提高。 实验名称 减治法在组合问题中的应用——8枚硬币问题 实验室 实 验 目 的 或 要 求 实验题目 在8枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道假币与真币相比较轻还是较重。 可以通过一架天平来任意比较两组硬币,设计一个高效的算法来检测这枚假币。 实验目的 1)深刻理解并掌握减治法的设计思想并理解它与分治法的区别; 2)提高应用减治法设计算法的技能。 3)理解这样一个观点: 建立正角的模型对于问题的求解是非常重要的。 实验要求 1)设计减治算法实现8枚硬币问题; 2)设计实验程序,考察用减治技术设计的算法是否高效; 3)扩展算法,使之能处理n枚硬币中有一枚假币的问题。 实 验 原 理 (算 法 基 本 思 想) 减治法主要有三种变种 减去一个常量 减去一个常量因子 减可变规模 与分治法的区别: 分治
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 教学 设计 实验 报告