实验2追赶法算法设计及MATLAB实现
数值计算方法
实
验
报
告
实验序号：实验二
实验名称：追赶法算法设计及MATLAB实现
实验人：
专业年级：
教学班：
学号：
实验时间：
实验二追赶法算法设计及MATLAB实现
一、实验目的
１．初步掌握算法设计规则；
２．初步掌握MATLAB程序设计规则．
二、实验内容
1．构造利用追赶法求解三对角线性方程组的算法；
2．在MATLAB环境下编写追赶法的程序（函数）；
3．自由选择若干个三对角线性方程组求解。
三、实验步骤
1．追赶法算法：
算法名称：thomas
输入参数：向量a,b,c,f
输出参数：输出解信息x
算法的自然语言：
Step1：u
1=b
1
,y
1
=b
1
;
Step2：对于i=2,3,….n;
Step2.1：当u
1-i
≠，否则转step5
l i =a
i
/u
1-i
;
u
i =b
i
-l
i
*c
1-i
；
y
i =f
i
-l
i
*y
1-i
；
Step3：当u
n
≠时，x
n
=y
n
/u
n
，否则转step5
Step4：对于：i=n-1,n-2,…..,2,1，转step6
x
i =(y
i
-c
i
*x
1+i
)/u
i
Step5：无解信息，转step7
Step6：输出x
Step7：关机
2．MATLAB程序
function [x,L,U]=thomas(a,b,c,f) n=length(b);
% 对A进行分解
u(1)=b(1);
for i=2:n
if(u(i-1)~=0)
l(i-1)=a(i-1)/u(i-1);
u(i)=b(i)-l(i-1)*c(i-1);
else
break;
end
end
L=eye(n)+diag(l,-1);
U=diag(u)+diag(c,1);
x=zeros(n,1);
y=x;
% 求解Ly=b
y(1)=f(1);
for i=2:n
y(i)=f(i)-l(i-1)*y(i-1);
end
% 求解Ux=y
if(u(n)~=0)
x(n)=y(n)/u(n);
end
for i=n-1:-1:1
x(i)=(y(i)-c(i)*x(i+1))/u(i);
end
3．求解实例例1．方程组
例2．方程组
例3．方程组
??
?
?
?
?
?
?
?
=
??
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
1
1
3
1
1
3
2
1
3
2
1
3
4
3
2
1
x
x
x
x
四、实验结论
对于追赶法我最先写的是如下的程序：
但是出现了如上截图中的错误，后来与同学讨论还是没能解决我的问题，最后借鉴了她的算法得到了正确的结果。Thomas算法在课堂上老师就已经给我们详细地讲解并指导了我们如何用Matlab编程，但是并没有解决a矩阵的a1如何处理，对于这个问题，我很快解决了。
我最大的问题就是如上所示，说明我的编程能力还是比较差，需要多练习。对于如上的错误希望老师看过之后能够给予指导，谢谢！
算法分析与设计实验指导书
《算法分析与设计》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。 （3）、上机结束后，整理出实验报告。 实验报告应包括： 1）问题分析 2）算法描述 3）运行结果、 4）算法性能分析。 实验一 实验名称：贪心算法应用及设计 实验学时：6学时 实验类型：验证 实验目的： 1.理解贪心算法的基本思想 2.掌握利用贪心算法求解问题的求解步骤 实验容 1.活动选择问题（2学时） 问题描述： 设有11个会议等待安排，用贪心法找出满足目标要求的会议集合，这些会议按结束时间的非减序排列如下表。 实验实现提示： １)数据结构设计： 将会议开始时间存储在数组B中，结束时间存储在数组E中，数组下标为会议的代码。结果存储在数组A中，其元素A[i]==true，表示会议i被选中。 ２）算法： void GreedySelect(int n, struct time B[], struct time E[], bool A[]) { int i,j;
A[1]=true; j=1; i=2; while( i<=n) if (B[i]>=E[j]) { A[i]=true; j=i;} else A[i]=false; } 思考题：证明所得的解是最优解？ 2.单源点最短路径问题。（2学时） 问题描述 如图所示的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。并对算法进行性能分析。 实现提示 1）数据结构设计： 将图存储在邻接矩阵C中，结点个数为n，源点编号为u, 源点u到其余顶点的最短路径长度存储在dist[],最短路径存储在p[]。 2) 算法 void Dijkstra(int C[n][n], int n,int u,float dist[],int p[]) { bool s[n]; for( int i=1; i<=n; i++) { dist[i]=C[u][i]; s[i]=false; if (dist[i]=∞) p[i]=-1; else p[i]=u; } p[u]=-1; s[u]=true; for( i=1; i<=n; i++) { int temp= ∞; int t=u; for( int j=1;j<=n;j++)
实验二 Matlab程序设计基本方法1
实验二Matlab程序设计基本方法 覃照乘自092 电气工程学院 一、实验目的： 1、熟悉MATLAB 程序编辑与设计环境 2、掌握各种编程语句语法规则及程序设计方法 3、函数文件的编写和设计 4、了解和熟悉跨空间变量传递和赋值 二、实验基本知识： ◆for循环结构 语法：for i＝初值：增量：终值 语句1 …… 语句n end 说明：1．i＝初值：终值，则增量为1。 2．初值、增量、终值可正可负，可以是整数，也可以是小数，只须符合数学逻辑。 ◆while 循环结构 语法：while 逻辑表达式 循环体语句 end 说明：1、whiIe结构依据逻辑表达式的值判断是否执行循环体语勾。若表达式的值为真，执行循环体语句一次、在反复执行时，每次都要进行判断。若表达 式的值为假，则程序执行end之后的语句。 2、为了避免因逻辑上的失误，而陷入死循环，建议在循环体语句的适当位 置加break语句、以便程序能正常执行。（执行循环体的次数不确定； 每一次执行循环体后，一定会改变while后面所跟关系式的值。） 3、while循环也可以嵌套、其结构如下：
while逻辑表达式1 循环体语句1 while逻辑表达式2 循环体语句2 end 循环体语句3 end ◆if-else-end分支结构 if 表达式1 语句1 else if 表达式2(可选) 语句2 else(可选) 语句3 end end 说明：1.if结构是一个条件分支语句，若满足表达式的条件，则往下执行；若不满足，则跳出if结构。 2．else if表达式2与else为可选项，这两条语句可依据具体情况取舍。 3．注意：每一个if都对应一个end，即有几个if，记就应有几个end。 ◆switch-case结构 语法：switch表达式 case常量表达式1 语句组1 case常量表达式2 语句组2 …… otherwise 语句组n end
《应用计算方法教程》matlab作业二
6-1 试验目的计算特征值，实现算法 试验容：随机产生一个10阶整数矩阵，各数均在-5和5之间。 （1） 用MATLAB 函数“eig ”求矩阵全部特征值。 （2） 用幂法求A 的主特征值及对应的特征向量。 （3） 用基本QR 算法求全部特征值（可用MATLAB 函数“qr ”实现矩阵的QR 分解）。 原理 幂法：设矩阵A 的特征值为12n ||>||||λλλ≥???≥并设A 有完全的特征向量系12,,,n χχχ???(它们线性无关)，则对任意一个非零向量0n V R ∈所构造的向量序列1k k V AV -=有11()lim ()k j k k j V V λ→∞ -=， 其中()k j V 表示向量的第j 个分量。 为避免逐次迭代向量k V 不为零的分量变得很大（1||1λ>时）或很小（1||1λ<时），将每一步的k V 按其模最大的元素进行归一化。具体过程如下： 选择初始向量0V ，令1max(),,,1k k k k k k k V m V U V AU k m +===≥，当k 充分大时1111,max()max() k k U V χλχ+≈ ≈。 QR 法求全部特征值： 111 11222 111 ,1,2,3,k k k k k A A Q R R Q A Q R k R Q A Q R +++==????==??=???? ??????==?? 由于此题的矩阵是10阶的，上述算法计算时间过长，考虑采用改进算法——移位加速。迭 代格式如下： 1 k k k k k k k k A q I Q R A R Q q I +-=?? =+? 计算k A 右下角的二阶矩阵() () 1,1 1,() (),1 ,k k n n n n k k n n n n a a a a ----?? ? ??? 的特征值()()1,k k n n λλ-，当()()1,k k n n λλ-为实数时，选k q 为()()1,k k n n λλ-中最接近(),k n n a 的。 程序
计算方法_全主元消去法_matlab程序
%求四阶线性方程组的MA TLAB程序 clear Ab=[0.001 2 1 5 1; 3 - 4 0.1 -2 2; 2 -1 2 0.01 3; 1.1 6 2.3 9 4];%增广矩阵 num=[1 2 3 4];%未知量x的对应序号 for i=1:3 A=abs(Ab(i:4,i:4));%系数矩阵取绝对值 [r,c]=find(A==max(A(:))); r=r+i-1;%最大值对应行号 c=c+i-1;%最大值对应列号 q=Ab(r,:),Ab(r,:)=Ab(i,:),Ab(i,:)=q;%行变换 w=Ab(:,c),Ab(:,c)=Ab(:,i),Ab(:,i)=w;%列变换 n=num(i),num(i)=num(c),num(c)=n;%列变换引起未知量x次序变化for j=i:3 Ab(j+1,:)=-Ab(j+1,i)*Ab(i,:)/Ab(i,i)+Ab(j+1,:);%消去过程 end end %最后得到系数矩阵为上三角矩阵 %回代算法求解上三角形方程组 x(4)=Ab(4,5)/Ab(4,4); x(3)=(Ab(3,5)-Ab(3,4)*x(4))/Ab(3,3); x(2)=(Ab(2,5)-Ab(2,3)*x(3)-Ab(2,4)*x(4))/Ab(2,2); x(1)=(Ab(1,5)-Ab(1,2)*x(2)-Ab(1,3)*x(3)-Ab(1,4)*x(4))/Ab(1,1); for s=1:4 fprintf('未知量x%g =%g\n',num(s),x(s)) end %验证如下 %A=[0.001 2 1 5 1; 3 -4 0.1 -2 2;2 -1 2 0.01 3; 1.1 6 2.3 9 4]; %b=[1 2 3 4]'; %x=A\b; %x1= 1.0308 %x2= 0.3144 %x3= 0.6267 %x4= -0.0513
算法设计与分析实验报告贪心算法
算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 算法设计与分析课程实验项目目录 学生姓名：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号 201 实验项目类型设计实验地点机房 学生姓名学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间 2012年 3月 1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要内容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验内容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人给出的： S END +MORE MONEY . 这 里有两个前提假设：第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。 3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 该算法程序代码如下： #include "" #include "" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 算法设计与分析 学院：计算机科学与技术 学号：129074106 姓名：张淼淼 2014 11 14 1、 当问题规模100 N 时，快速排序和插入排序各需多少时间？写清机器配置，列出五种 快速排序所需时间(ms) 插入排序所需时间（ms ） 两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=1000000 53.500000 117.700000 -64.200000 Window 7 32位 Cpu ：Inter(R) Core(TM) i3-2120 cpu@3.30GHz AMD Radeon HD 6450 Graphics 程序： #include int b[1000000]; void QuickSort(int low ,int high) { long i,j; int x; i=low; j=high; x=a[i]; while(i 1，编写M 函数实现求一个数是否为素数，再编写一主程序（脚本文件），要求通过键盘输入一个整数，然后调用判断素数函数，从而确定它是否素数。 x=input('请输入一个整数x:'); if myprime(x) disp('您输入的整数x是一个素数。') else disp('您输入的数x不是一个素数。') end function y=myprime(x) y=1; for i=2:fix(sqrt(x)) if mod(x,i)==0 y=0; end end 2，编写M 函数统计一数值中零的个数，然后编写脚本文件，实现统计从1—2007 中零的总个数。 function num=number0(a) %统计十进制数值中0的个数 sa=num2str(a);%将数值装化为字符串 num=length(find(sa=='0'));% ));%求取字符串中'0’的个数 y=0; for a=1:2006 num=number0(a); y=num+y; end disp(y) 504 3，编写程序计算x∈[-3,3],字长0.01：并画出曲线x = -3:0.01:3; y=zeros(size(x)); for i = 1:length(x) if -3<= x(i)& x(i)<=-1 y(i)=(-x(i).^2-4*x(i)-3)/ 2; elseif -1<= x(i) & x(i)<=1 y(i)=-x(i).^2+1; elseif 1<=x(:,i)<=3 y(i)=(-x(i).^2+4*x(i)-3)/2; end end plot(x,y) -3-2-10123 《计算机算法设计与分析》实验指导书（第一版） 前言 计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。 前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。 开发环境不限，本书采用C/C++语言的集成开发环境等。 实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。 总实验学时为16学时。 目录 预备实验验证算法的方法 (4) 实验目的： (4) 实验课时： (4) 实验原理： (4) 实验题目： (6) 基本题： (6) 提高题： (6) 实验一递归与分治 (7) 实验目的： (7) 实验课时： (7) 实验原理： (7) 实验题目： (7) 基本题： (7) 提高题： (8) 思考问题： (8) 实验二动态规划算法 (9) 实验目的： (9) 实验课时： (9) 实验原理： (9) 实验题目： (9) 基本题： (9) 提高题： (10) 思考问题： (10) 实验三贪心选择算法 (11) 实验目的： (11) 实验课时： (11) 实验原理： (11) 实验题目： (11) 基本题： (11) 提高题： (12) 思考问题： (12) 实验四回溯算法 (13) 实验目的： (13) 实验课时： (13) 实验原理： (13) 实验题目： (14) 基本题： (14) 提高题： (14) 思考问题： (14) 实验六 高层绘图操作 %第一题： 程序代码如下： x=linspace(0,2*pi,101); y=(0.5+3*sin(x)./(1+x.^2)).*cos(x); plot(x,y) 01234567 -1 -0.5 0.5 1 1.5 %第二题： %（1） 程序代码如下： x=linspace(-2*pi,2*pi,100); y1=x.^2; y2=cos(2*x); y3=y1.*y2; plot(x,y1,'b-',x,y2,'r:',x,y3,'y--'); text(4,16,'\leftarrow y1=x^2'); text(6*pi/4,-1,'\downarrow y2=cos(2*x)'); text(-1.5*pi,-2.25*pi*pi,'\uparrow y3=y1*y2'); -8 -6 -4 -2 2 4 6 8 -30-20 -10 10 20 30 40 %（2） 程序代码如下： x=linspace(-2*pi,2*pi,100); y1=x.^2; y2=cos(2*x); y3=y1.*y2; subplot(1,3,1);%分区 plot(x,y1); title('y1=x^2');%设置标题 subplot(1,3,2); plot(x,y2); title('y2=cos(2*x)'); subplot(1,3,3); plot(x,y3); title('y3=x^2*cos(2*x)'); -10 10 0510 15202530 35 40y1=x 2 -10 10 -1-0.8 -0.6 -0.4-0.200.20.4 0.6 0.8 1y2=cos(2*x) -10 10 -30-20 -10 10 20 30 40 y3=x 2*cos(2*x) %（3） 程序代码如下： x=linspace(-2*pi,2*pi,20); y1=x.^2; subplot(2,2,1);%分区 bar(x,y1); title('y1=x^2的条形图');%设置标题 subplot(2,2,2); stairs(x,y1); title('y1=x^2的阶梯图'); subplot(2,2,3); stem(x,y1); title('y1=x^2的杆图'); subplot(2,2,4); fill(x,y1,'r');%如果少了'r'则会出错 title('y1=x^2的填充图'); %其他的函数照样做。 实验一、归并排序及各种排序算法性能比较 一、实验实习目的及要求 了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。 二、实验实习设备（环境）及要求（软硬件条件） 计算机eclipse软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明) 项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。 内容及步骤： (1)归并排序：将序列每次分成两组，再进行合并，直到递归完成； 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组 3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后 只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个 元素交换，直到最后只有一个元素时结束。 1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一 个元素互换，调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当 所有的元素插入完毕时，就排好序了； 1、从第二个元素开始，与之前序列比较，插入到合适的位置。 2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右 边比它大，然后对左右两边进行递归； 1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看， 找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。 《算法分析与设计》实验指导书 《算法分析与设计》课程是计算机专业的一门必修课程。开设算法分析与设计实验，目的就是为了使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 《算法分析与设计》课程实验的目的：是为了使学生在课程学习的同时，通过实验环境中的实际操作，对部分算法的具体应用有一个初步的了解，使学生加深了解和更好地掌握《算法分析与设计》课程教学大纲要求的内容。 《算法分析与设计》课程实验的注意事项：在《算法分析与设计》的课程实验过程中，要求学生做到： (1)预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出 现的情况提前作出思考和分析。 (2)认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分 析。 (3)遵守机房纪律，服从辅导教师指挥，爱护实验设备。 (4)实验课程不迟到。如有事不能出席，所缺实验一般不补。 《算法分析与设计》课程实验的验收：实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第二部分是提交电子的实验报告。 实验一算法实现一 一、实验目的与要求 熟悉C/C++语言的集成开发环境； 通过本实验加深对分治法、贪心算法的理解。 二、实验内容: 掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。 三、实验题 1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的 任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。 2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售 货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。 a)实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 四、实验程序 五、实验结果 六、实验分析 MATLAB 程序设计实验报告 一、实验目的 1. 通过实验熟悉MATLAB 仿真软件的使用方法； 2. 掌握用MATLAB 对连续信号时域分析、频域分析和s 域分析的方法，利用绘图命令绘制出典型信号的波形，了解这些信号的基本特征； 3. 掌握用MATLAB 对离散信号时域分析、频域分析和z 域分析的方法，利用绘图命令绘制出典型信号的波形，了解这些信号的基本特征； 4. 通过绘制信号运算结果的波形，了解这些信号运算对信号所起的作用。 二、实验设备 1. 计算机 ： 2. MATLAB R2007a 仿真软件 三、实验原理 对系统的时域分析 信号的时域运算包括信号的相加、相乘，信号的时域变换包括信号的平移、反折、倒相及信号的尺度变换。 （1）信号的相加和相乘：已知信号)(1t f 和)(2t f ，信号相加和相乘记为 )()(1t f t f =)(2t f +；)()(1 t f t f =)(2t f *。 （2）信号的微分和积分：对于连续时间信号，其微分运算是用diff 函数来完成的，其语句格式为：diff(function,’variable’,n)，其中function 表示需要进行求导运算的信号，或者被赋值的符号表达式；variable 为求导运算的独立变量；n 为求导的阶数，默认值为求一阶导数。连续信号的积分运算用int 函数来完成，语句格式为：diff(function,’variable’,a,b)，其中function 表示需要进行被积信号，或者被赋值的符号表达式；variable 为求导运算的独立变量；a,b 为积分上、下限，a 和b 省略时为求不定积分。 （3）信号的平移、翻转和尺度变换 信号的平移包含信号的左移与右移，信号的翻转包含信号的倒相与折叠，平移和翻转信号不会改变信号)(t f 的面积和能量。信号的尺度变换是对信号)(t f 在时间轴上的变化，可使信号压缩或扩展。)(at f 将原波形压缩a 倍，)/(a t f 将原波形扩大a 倍。 ￥ 对系统频率特性的分析 昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include 常用计算方法 1．超越方程的求解 一超越方程为 x (2ln x – 3) -100 = 0 求超越方程的解。 [算法]方法一：用迭代算法。将方程改为 01002ln()3 x x =- 其中x 0是一个初始值，由此计算终值x 。取最大误差为e = 10-4，当| x - x 0| > e 时，就用x 的值换成x 0的值，重新进行计算；否则| x - x 0| < e 为止。 [程序]P1_1abs.m 如下。 %超越方程的迭代算法 clear %清除变量 x0=30; %初始值 xx=[]; %空向量 while 1 %无限循环 x=100/(2*log(x0)-3); %迭代运算 xx=[xx,x]; %连接结果 if length(xx)>1000,break ,end %如果项数太多则退出循环（暗示发散） if abs(x0-x)<1e-4,break ,end %当精度足够高时退出循环 x0=x; %替换初值 end %结束循环 figure %创建图形窗口 plot(xx,'.-','LineWidth',2,'MarkerSize',12)%画迭代线'.-'表示每个点用.来表示，再用线连接 grid on %加网格 fs=16; %字体大小 title('超越方程的迭代折线','fontsize',fs)%标题 xlabel('\itn','fontsize',fs) %x 标签 ylabel('\itx','fontsize',fs) %y 标签 text(length(xx),xx(end),num2str(xx(end)),'fontsize',fs)%显示结果 [图示]用下标作为自变量画迭代的折线。如P0_20_1图所示，当最大误差为10-4时，需要迭代19次才能达到精度，超越方程的解为27.539。 [算法]方法二：用求零函数和求解函数。将方程改为函数 100()2ln()3f x x x =-- MATLAB 求零函数为fzero ，fzero 函数的格式之一是 x = fzero(f,x0) 其中，f 表示求解的函数文件，x0是估计值。fzero 函数的格式之二是 x = fzero(f,[x1,x2]) 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 实验七Matlab 程序设计 实验目的： 1、掌握建立和执行M 文件的方法； 2、掌握实现选择结构的方法； 3、掌握实现循环结构的方法。 实验内容： 1. 编写用 5 次多项式拟合函数y=sin(x), x [0, 2 ]的脚本M 文件，要求绘图观察拟合的效果。 function shiyan1 x=0:0.5:2*pi y=sin(x) p=polyfit(x,y,5) x1=0:0.2:2*pi y1=polyval(p,x1) plot(x,y, 'b' ,x1,y1, '*r' x = Columns 1 through 9 0 0.5000 1.0000 1.5000 2.0000 2.5000 3.0000 3.5000 4.0000 Columns 10 through 13 4.5000 5.0000 5.5000 6.0000 y = Columns 1 through 9 0 0.4794 0.8415 0.9975 0.9093 0.5985 0.1411 -0.3508 -0.7568 Columns 10 through 13 -0.9775 -0.9589 -0.7055 -0.2794 p = -0.0056 0.0881 -0.3967 0.2671 0.8902 0.0029 x1 = Columns 1 through 10 0 0.2000 0.4000 0.6000 0.8000 1.0000 1.2000 1.4000 1.6000 1.8000 Columns 11 through 20 2. 2.2000 2.4000 2.6000 2.8000 3.0000 3.2000 3.4000 3.6000 1.8001 Columns 21 through 30 4.0 4.2000 4.4000 4.6000 4.8000 5.0000 5.2000 5.4000 5.6000 5.8000 Columns 31 through 32 6.0 6.2000 y1 = Columns 1 through 10 0.29 0.1886 0.3786 0.5585 0.7172 0.8461 0.9391 0.9926 1.0048 0.9761 Columns 11 through 20 0.9083 0.8048 0.6701 0.5098 0.3301 0.1381 -0.0590 -0.2538 -0.4389 -0.6073 Columns 21 through 30 -0.7524 -0.8685 -0.9505 -0.9949 -0.9991 -0.9626 -0.8863 -0.7732 -0.6288 -0.4606 Columns 31 through 32 1、Newdon迭代法求解非线性方程 function [x k t]=NewdonToEquation(f,df,x0,eps) %牛顿迭代法解线性方程 %[x k t]=NewdonToEquation(f,df,x0,eps) %x:近似解 %k:迭代次数 %t:运算时间 %f:原函数，定义为内联函数 ?:函数的倒数，定义为内联函数 %x0:初始值 %eps:误差限 % %应用举例： %f=inline('x^3+4*x^2-10'); ?=inline('3*x^2+8*x'); %x=NewdonToEquation(f,df,1,0.5e-6) %[x k]=NewdonToEquation(f,df,1,0.5e-6) %[x k t]=NewdonToEquation(f,df,1,0.5e-6) %函数的最后一个参数也可以不写。默认情况下，eps=0.5e-6 %[x k t]=NewdonToEquation(f,df,1) if nargin==3 eps="0".5e-6; end tic; k=0; while 1 x="x0-f"(x0)./df(x0); k="k"+1; if abs(x-x0) < eps || k >30 break; end x0=x; end t=toc; if k >= 30 disp('迭代次数太多。'); x="0"; t="0"; end 2、Newdon迭代法求解非线性方程组 function y="NewdonF"(x) %牛顿迭代法解非线性方程组的测试函数 %定义是必须定义为列向量 y(1,1)=x(1).^2-10*x(1)+x(2).^2+8; y(2,1)=x(1).*x(2).^2+x(1)-10*x(2)+8; return; function y="NewdonDF"(x) %牛顿迭代法解非线性方程组的测试函数的导数 y(1,1)=2*x(1)-10; y(1,2)=2*x(2); y(2,1)=x(2).^+1; y(2,2)=2*x(1).*x(2)-10; return; 以上两个函数仅供下面程序的测试 function [x k t]=NewdonToEquations(f,df,x0,eps) %牛顿迭代法解非线性方程组 %[x k t]=NewdonToEquations(f,df,x0,eps) %x:近似解 %k:迭代次数 %t:运算时间 %f:方程组（事先定义） ?:方程组的导数（事先定义） %x0:初始值 %eps:误差限 % %说明：由于虚参f和df的类型都是函数，使用前需要事先在当前目录下采用函数M文件定义% 另外在使用此函数求解非线性方程组时，需要在函数名前加符号“@”，如下所示 % %应用举例： %x0=[0,0];eps=0.5e-6; %x=NewdonToEquations(@NewdonF,@NewdonDF,x0,eps) %[x k]=NewdonToEquations(@NewdonF,@NewdonDF,x0,eps) %[x k t]=NewdonToEquations(@NewdonF,@NewdonDF,x0,eps) %函数的最后一个参数也可以不写。默认情况下，eps=0.5e-6 %[x k t]=NewdonToEquations(@NewdonF,@NewdonDF,x0,eps) 计算机算法设计与分析实验报告 目录 实验一 (1) [实验题目] (1) [问题描述] (1) [算法设计] (1) [算法分析] (1) [源代码] (1) [运行结果] (2) 实验二 (2) [实验题目] (2) [问题描述] (2) [算法设计] (2) [算法分析] (2) [源代码] (2) [运行结果] (4) 实验三 (5) [实验题目] (5) [问题描述] (5) [算法设计] (5) [算法分析] (5) [源代码] (5) [运行结果] (6) 实验一 [实验题目] 2-7集合划分问题 [问题描述] n个元素的集合{1，2，…，n}可以划分为若干非空子集。例如，当n=4时，集合{1，2，3，4}可以划分为15个不同的非空子集。 [算法设计] 给定正整数n，计算出n个元素的集合{1，2，…，n}可以划分为多少个不同的非空子集。 [算法分析] 本算法实现采用分治法思想，F(n,m)=F(n-1,m-1)+m*F(n-1,m)。假设将m个元素分解到n 个集合中，首先考虑将(m – (n - 1))个元素分到第一个集合中，将余下的(n - 1)个元素分别分配到余下的(n - 1)个集合中，然后再考虑将(m – (n - 2))个元素分配到第一个集合中，将余下的(n - 2)个元素分别分配到余下的(n - 1)集合中，依此类推，直到后面的有一个集合中的元素个数比第一个集合中的元素个数多为止。 [源代码] #include 算法设计与分析实验报告
算法分析与设计实验报告
实验3MATLAB程序设计
《算法分析与设计》实验指导书
刘卫国版MATLAB程序设计与应用课后实验六八九
算法分析与设计实验报告
算法分析与设计实验指导书
MATLAB程序设计实验报告
算法分析与设计 实验二 哈夫曼编码
(整理)matlab16常用计算方法.
算法设计与分析实验报告
Matlab程序设计实验报告
matlab用于计算方法的源程序
算法分析与设计实验报告
- 算法分析与设计实验报告 完整版
- 算法设计与分析实验报告
- 算法分析与设计实验报告76421
- 算法设计与分析实验报告 统计数字问题
- 计算机算法设计与分析实验指导书
- 算法分析与设计实验报告
- 《算法设计与分析》实验二
- 算法分析与设计实验报告 (2)
- 算法设计与分析习题与实验题(12.18)
- 算法分析与设计实验二动态规划
- 算法分析与设计实验报告
- 算法设计与分析实验报告二
- 算法设计与分析实验报告
- 算法设计与分析实验报告
- 算法设计与分析实验(第2、3章)
- 算法分析与设计-实验二-哈夫曼编码
- 算法设计与分析实验
- 算法分析与设计 实验二 哈夫曼编码
- 算法设计与分析实验报告2
- (完整word版)计算机算法与设计分析实验报告