分治法实验报告
算法实验报告一分治法实验
一、实验目的及要求
利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步
骤。
要求：设计十进制的大整数乘法，必须利用分治的思想编写算法，利用c语言（或者c++
语言）实现算法，给出程序的正确运行结果。（必须完成）
设计二进制的大整数乘法，要求利用分治的思想编写递归算法，并可以实现多位数的乘
法（利用数组实现），给出程序的正确运行结果。（任选）
二、算法描述
1、
输入两个相同位数的大整数u，v 输出uv的值
判断大整数的位数i；
w=u/10^(i/2);
y=v/10^(i/2);
x=u-w*10^(i/2);
z= v-y*10^(i/2);
然后将w,x,y,z代入公式求得最后结果
uv=wy10^i+((w+x)(y+z)-wy-xz)10^(i/2)+xz
三、调试过程及运行结果
在实验中我遇到的问题：
原来以为这两个大整数的位数不同，结果题目要求是相同位数的大整数在写10的多少
次方时，写的是10^(i/2),10^(i)，结果不对，我就将它改成了for循环语句
四、实验总结
在本次实验中，我知道了分治算法，以及分治算法的基本思想。我还掌握了编写大整数
乘法的算法与步骤，以及如何修改在编写程序时遇到的问题。
五、附录（源程序代码清单）
1、#include<iostream.h> int weishu(int x)
{
int i;
while(x!=0)
{ x=x/10;
i++;
}
return i;
}
void main()
{
int u,v;
cout<<输入两个位数相同的大整数:<<endl; cin>>u;
cin>>v;
int i,j,m,n;
int p,x,y,z,w;
int a=1;
int b=1;
i=weishu(u);
for(int k=1;k<=i;k++)
{
a=a*10;
}
for(int q=1;q<=i/2;q++) {
b=b*10;
}
w=u/b;
y=v/b;
x=u-w*b;
z=v-y*b;
p=w*y*a+((w+x)*(y+z)-w*y-x*z)*b+x*z; cout<<u<<*<<v<<=<<p; }
教师评语：
成绩：√优良中及格不及格
算法实验报告二动态规划法实验
一、实验目的及要求
利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步
骤。
要求：设计0/1背包问题的动态规划算法，要求输出背包内物品的最大价值以及选入背
包的物品种类。利用c语言（c++语言）实现算法，给出程序的正确运行结果。
二、算法描述
输入：各物品的体积、价值，背包容量
输出：放入背包的物品的体积，放入物品的最大价值
for i<-0 to n
v[i,0]<-0
end for
for j<-0 to c
v[j,0]<-0
end for
for i<-1 to n
for j<-1 to c
v[i,j]<-v[i-1,j]
if(si<=j and v[i-1,j-si]+vi)>v[i,j] ) v[i,j]<-v[i-1,j-si]+vi
item[j]=i
end for
end for
for i<-c downto 1 (i=i-item[i]的体积) printf(s[item[i]])
end for
return v[n,c]
三、调试过程及运行结果
在定义数组时数组的大小不能是变量，也不能定义一个变量从键盘输入一个常数，再用
这个变量定义数组，只能直接用常量定义数组或者用宏定义的量来定义数组。
在进行多个for循环时，不管他们之间有没有关系，循环中定义的变量不能一样。
在定义数组v[][]时，数组大小必须是n+1、c+1。
四、实验总结
在进行本次实验时，我知道了背包程序的算法以及它的基本的意思，算法想要做什么。
我还掌握了一些在学c++时没有注意到的一些小问题。如在定义数组时数组的大小不能是变
量，也不能定义一个变量从键盘输入一个常数，再用这个变量定义数组，只能直接用常量定
义数组或者用宏定义的量来定义数组。在进行多个for循环时，不管他们之间有没有关系，
循环中定义的变量不能一样。在定义数组v[][]时，数组大小必须是n+1、c+1。
五、附录（源程序代码清单）
#include<iostream.h> #define n 10
#define c 12
void main()
{
int s[n],v[n];
int v[n+1][c+1];
int item[c];
cout<<物品的体积:<<endl; for(int f=0;f<n;f++)
cin>>s[f]; cout<<物品的价值:<<endl; for(int h=0;h<n;h++)
cin>>v[h];
for(int k=0;k<=n;k++)
{
v[k][0]=0;
}
for(int m=0;m<=c;m++)
{
v[0][m]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;j++)
{
v[i][j]=v[i-1][j];
if(s[i]<=j && v[i-1][j-s[i]]+v[i]>v[i][j]) { v[i][j]=v[i-1][j-s[i]]+v[i]; item[j]=i; }
}
} cout<<放入背包的物品的体积:<<endl; for(int
p=c;p>=1;p=p-s[item[p]])
{
cout<<s[item[p]];
cout<<endl;
}
cout<<背包的最大价值:; cout<<v[n][c]<<endl; }
教师评语：
成绩：√优良中
及格不及格篇二：分治算法实验报告
本科学生综合性实验报告
姓名＿＿＿刘春云学号＿ 0103918＿＿
＿
专业＿＿软件工程＿＿班级＿ 103＿＿
实验项目名称＿二分搜索问题的分治算法实验指导教师及职称＿＿＿＿＿赵晓平＿＿
＿＿＿开课学期 2011 至＿ 2012 学年＿ 3 ＿学期
上课时间 2012 年 2 月 18 日
学生实验报告（1）
一、问题描述
二分查找又称折半查找，即在一串已排好序的需要处理的数据中多次用折半的方法查找
出要搜索出的数据。
二、解题思路
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如
果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置
记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以
上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
三、算法描述
用一个数组来存储数据，具体的结构体为： typedef struct list { double elem[100]; int length; }list；其中length是数据的总个数
比较表中间位置记录的关键字与查找关键字的大小，逐步缩小查找范围实现代码为：
while(low<high)
{ mid=(low+high)/2; if(l.elem[mid]==key) { } else if(l.elem[mid]<key) low=mid;
outfile<<你所要搜索的数据在第<<mid+1<<个位置<<endl;
break;
else
high=mid;
if(high==low+1) {
outfile<<抱歉!你所要搜索的数据不在你所输入的数据中break; <<endl;
范围
}
}在上段代码中low表示搜索区间的最小范围，hiah则表示搜索区间的最大
在代码中出现的int init_list(list&l)是一个初始函数用于从input.txt文件中
读入
数据并判断数据是否升序排列。int search(int low,int high,list&l)是查找函数
用于折半查找。
四、算法实现
#include <iostream> #include<fstream> using namespace std; typedef
struct list {
double elem[100]; int length; }list; int init_list(list&l)//初始化函数 { } int search(int low,int high,list&l)//查找函数 { int search(int low,int high,list&l); int n=0; ifstream infile; cout<<请输入数据(必须是从小到大排序的)<<endl;
infile.open(input.txt,ios::in); ofstream outfile; outfile.open(output.txt,ios::app); while(infile>>l.elem[n])//从文件中输入已排序数组，直到文件中无数据读取
n++; infile.close(); l.length=n; for(int i=0;i<l.length-1;i++)//判断输入的数据是否有序 { if(l.elem[i]>l.elem[i+1]) { } outfile<<朋友请不要玩我!<<endl; return 0; }//判断输入的数据是否有序
cout<<二分查找中......<<endl; search(0,l.length-1,l); return 1;
ofstream outfile;
outfile.open(output.txt,ios::app); int mid=0;//中点篇三：分治法实验报告
石家庄经济学院
《算法设计与分析》实验报告
姓名：
班级：
学号：
指导教师：
完成日期：
一、实验名称
分治法实验
二、实验目的
1. 掌握分治法的基本思想、求解问题的基本步骤；
2. 掌握分支算法的一般模式；
3. 根据问题采取有效的分解和合并的方式，能够分析确定问题的阈值；
4. 掌握分治算法的时间复杂度，并能利用c语言实现算法。
三、实验内容及要求
1. 大整数乘法。
要求：
(1) 求解两个n位的二进制整数的乘法，设n=2k；
(2) 利用分治的思想分析和求解问题；
(3) 利用c语言实现算法，要求结果正确。
2. 矩阵相乘（选做）
(1) 求解两个n阶方阵的乘法，设n=2k；
(2) 可利用基本的分解方法或者stranssen方法求解；
(3) 利用c语言实现算法，要求结果正确。
四、问题分析及算法设计
1. 大整数乘法
问题分析：
算法设计：
算法复杂度分析：
2. 矩阵乘法
问题分析：
算法设计：
算法复杂度分析：
五、代码及运行结果
六、实验总结
（要求总结本次实验遇到的问题及解决方法，收获和不足，300字以上，提交报告时删
去此行）
教师评语：
成绩：优良中及格不及格篇四：算法-实验报告-分治法
年级 2012 学院专业班级学生姓名学号
《算法分析与设计》实验报告(1) 篇五：算法实验四分治法实验报告
算法实验四分治法实验
实验一最近点对
最近点对问题描述：对平面上给定的n个点，给出所有点对的最短距离即，输入是平面
上的n个点，输出是n点中具有最短距离的两点要求随机生成n个点的平面坐标，应用穷举
法编程计算出所有点对的最短距离要求随机生成n个点的平面坐标，应用分治法编程计算出
所有点对的最短距离。
二、实验数据及分析
平面点数为100：
平面点数为 500 平面点数为1000：
可以看出，分治法的运行效率要明显比直接法要高。
三轮DES差分分析实验报告-刘杰
DES 差分分析实验报告 四大队四队五班 刘杰 一、实验目的 差分密码分析是一种选择明文攻击，是现代分组密码分析的重要方法之一，也是理论分析密码算法和算法抗攻击测试的重要依据之一。本实验通过3轮DES 简化算法的差分分析来达到加深学员对差分分析方法原理的理解和利用该原理分析实际问题的操作能力。 二、实验内容 （1）3轮DES 简化算法的差分分析； （2）通过三组明密文对（每组两个相关明文和相应密文），利用差分原理提取密钥。 明 文 密 文 748502CD38451097 03C70306D8A09F10 3874756438451097 78560A0960E6D4CB 486911026ACDFF31 45FA285BE5ADC730 375BD31F6ACDFF31 134F7915AC253457 357418DA013FEC86 D8A31B2F28BBC5CF 12549847013FEC86 0F317AC2B23CB944 三、实验原理 设DES 两个明密文对:=00m L R ***=00m L R =33c L R *** =33c L R 计算过程: (,)(,)(,)(,)=⊕=⊕=⊕⊕322312300123R L f R k R f R k L f R k f R k
(,)(,)****=⊕⊕300123R L f R k f R k 令：*'=⊕000L L L (,)(,)(,)(* **''=⊕=⊕⊕⊕⊕333001012323R R R L f R k f R k f R k f R k 观察得：在本次实验原始数据中，明文对*=00R R ，即* '=⊕=00000000000R R R 则(,)(,)** ''=⊕=⊕⊕33302323R R R L f R k f R k 同时有：=00m L R ***=00m L R =23R L ** =23R L 则可计算出：*'=⊕000L L L *'=⊕333R R R (,)(,)* ''⊕=⊕232330f R k f R k R L 则可得出： S 盒输入差：(())(())()()* *⊕⊕⊕=⊕232333E R k E R k E L E L S 盒输出差：()*-''⊕=⊕13 0D D P R L 分析过程： 令：()()*⊕=3312345678E L E L B B B B B B B B ()-''⊕=13 012345678P R L C C C C C C C C ()=312345678E L A A A A A A A A =312345678 k J J J J J J J J ()⊕=3312345678E L k X X X X X X X X *()⊕=3312345678E L k Y Y Y Y Y Y Y Y 基本思路：（分别计算12345678J J J J J J J J ） {|,()()∈=⊕⊕=⊕=i i i i i i i J T e s t x A x y B S x S y C ,,,,,,,=12345678i 对于本次实验的3个具有明文差（*,0）的明密文对，则可构造上面的3个 Test 集合，显然 ()()( )∈12 i i i i J Test Test Test t ,,,,,,,=12345678i 一种确定Ji 的直接方法： 1.建立26=64长度的数组J[64]={0}; 2.对Testi(r)，r = 1,2,…,t ，若a ∈Testi(r)，则 J[a] = J[a] + 1。 3.若J[b] =3，则6比特串b 就是可能的密钥比特 Ji 。 四、实验环境 Microsoft visual c++ 五、实验步骤 （1）计算简化算法第3轮S 盒输入差
Poisson方程九点差分格式_米瑞琪
数值实验报告I 实验名称Poisson方程九点差分格式实验时间2016年 4 月 15 日姓名米瑞琪班级信息1303学号04成绩 一、实验目的，内容 1、理解Poisson方程九点差分格式的构造原理； 2、理解因为网格点的不同排序方式造成的系数矩阵格式的差异； 3、学会利用matlab的spdiags(),kron()函数生成系数矩阵； 二、算法描述 针对一个Poisson方程问题： 在Poisson方程五点差分格式的基础上，采用Taylor展开分析五点差分算子的截断误差，可以得到： 为了提高算子截断误差的精度，在(1)式中配凑出了差分算子的形式，将原Poisson方程代入（1）式有： 考虑，有：
将（3）代回（2）可得 得到Poisson方程的九点差分格式： 在计算机上实现（4）式，需要在五点差分格式 的基础上在等式两端分别增加一部分，将等式左侧新增的部分写成紧凑格式，有： 对于该矩阵，可以看成是两个矩阵的组合：
以及 则生成这两个矩阵可以采用Kroncker生成，方法类似于五点差分格式。 对于右端添加的关于f(x,y)的二阶导数，可以采用中心差分格式进行近似代替，即： 写成相应的紧凑格式有：
该式中的矩阵又可以分解为两个矩阵的和：
%计算误差 u_real=@(x,y)exp(pi*(x+y))*sin(pi*x).*sin(pi*y); for i=1:N1-1 u_m((i-1)*(N2-1)+1:i*(N2-1))=u_real(x(i),y); end u_v=u_m'; err_d=max(abs(u_d-u_v)); sol=reshape(u_d,N2-1,N1-1); mesh(X,Y,sol) 四. 数值结果 针对课本P93给出的问题，分别采用步长，将计算出的误差列表如下： 步长五点差分格式误差九点差分格式误差 可见采用九点差分格式可以进一步缩小误差，达到更高阶的精度。 五. 计算中出现的问题，解决方法及体会 在生成九点差分格式的时候，等号右端涉及到了对f的二阶偏导，我最初利用符号函数定义了f,随后求出其二阶偏导（仍然是符号函数）之后带入网格点，求f二阶偏导的精确解，但是代入过程相当繁琐，运行速度非常慢，最终我改变策略，选用f关于x,y的二阶中心差分格式替代精确值，最终得到了相对满意的结果。 教 师 评 语 指导教师：年月日
有限差分法实验报告
工程电磁场 实验报告 ——有限差分法
用超松弛迭代法求解 接地金属槽内电位的分布 一、实验要求 按对称场差分格式求解电位的分布 已知： 给定边值：如图1-7示 图1-7接地金属槽内半场域的网格 给定初值)()(.1j 40 100 1j p 1 2j i -= --= ??? 误范围差: 510-=ε 计算：迭代次数N ，j i ,?，将计算结果保存到文件中 二、实验思想 有限差分法 有限差分法（Finite Differential Method ）是基于差分原理的一种数值计算法。其基本思想：将场域离散为许多小网格，应用差分原理，将求解连续函数?的泊松方程的问题转换为求解网格节点上? =?= V 100 ? 0 =?0 =?
的差分方程组的问题。 泊松方程的五点差分格式 )(4 1 4243210204321Fh Fh -+++=?=-+++?????????? 当场域中,0=ρ得到拉普拉斯方程的五点差分格式 )(4 1 044321004321??????????+++=?=-+++ 差分方程组的求解方法(1) 高斯——赛德尔迭代法 ][)(,)(,)(,)(,)(,2 k 1j i k j 1i 1k 1j i 1k j 1i 1k j i Fh 4 1 -+++=+++-+-+????? (1-14) 式中：??????=??????=,2,1,0,2,1,k j i ， ? 迭代顺序可按先行后列，或先列后行进行。 ? 迭代过程遇到边界节点时，代入边界值或边界差分 格式，直到所有节点电位满足ε??<-+)(,)(,k j i l k j i 为止。 （2）超松弛迭代法 ][) (,)(,)(,)(,)(,)(,)(,k j i 2k 1j i k j 1i 1k 1j i 1k j 1i k j i 1k j i 4Fh 4 ?????α??--++++=+++-+-+ (1-15) 式中：α——加速收敛因子)21(<<α 可见：迭代收敛的速度与α有明显关系 三、程序源代码 #include
_实验1分治法
实验一分治法 一、实验目的 1．理解分治法的方法； 2. 掌握使用分治法解决一般问题的步骤； 3. 掌握分治算法求解数组的最大值和最小值的方法。 二、实验原理 在一个给定数组中查找最大值和最小值是一类常见的问题，也是解决其他一些算法的基础。 假设给定数组为a，数组中含有n个元素，一般的算法是在数组中进行直接查找，算法伪代码如下： 1. x←a[0]; y←a[0] 2. for i←2 to n 3. if a[i] 南京理工大学 课程考核论文 课程名称：高等数值分析 论文题目：有限差分法求解偏微分方程 姓名：罗晨 学号： 成绩： 有限差分法求解偏微分方程 一、主要内容 1.有限差分法求解偏微分方程，偏微分方程如一般形式的一维抛物线型方程：具体求解的偏微分方程如下： 2.推导五种差分格式、截断误差并分析其稳定性； 3.编写MATLAB程序实现五种差分格式对偏微分方程的求解及误差分析； 4.结论及完成本次实验报告的感想。 二、推导几种差分格式的过程： 有限差分法（finite-differencemethods ）是一种数值方法通过有限个微分方程近似求导从而寻求微分方程的近似解。有限差分法的基本思想是把连续的定解区域用有限个离散点构成的网格来代替；把连续定解区域上的连续变量的函数用在网格上定义的离散变量函数来近似；把原方程和定解条件中的微商用差商来近似，积分用积分和来近似，于是原微分方程和定解条件就近似地代之以代数方程组，即有限差分方程组，解此方程组就可以得到原问题在离散点上的近似解。 推导差分方程的过程中需要用到的泰勒展开公式如下： ()2100000000()()()()()()()......()(()) 1!2!! n n n f x f x f x f x f x x x x x x x o x x n +'''=+-+-++-+-(2-1) 求解区域的网格划分步长参数如下： 11k k k k t t x x h τ ++-=?? -=?(2-2) 2.1古典显格式 2.1.1古典显格式的推导 由泰勒展开公式将(,)u x t 对时间展开得 2,(,)(,)( )()(())i i k i k k k u u x t u x t t t o t t t ?=+-+-?(2-3) 当1k t t +=时有 21,112,(,)(,)( )()(())(,)()() i k i k i k k k k k i k i k u u x t u x t t t o t t t u u x t o t ττ+++?=+-+-??=+?+?(2-4) 得到对时间的一阶偏导数 1,(,)(,)()=()i k i k i k u x t u x t u o t ττ+-?+?(2-5) 由泰勒展开公式将(,)u x t 对位置展开得 223,,21(,)(,)()()()()(())2!k i k i k i i k i i u u u x t u x t x x x x o x x x x ??=+-+-+-??(2-6) 当11i i x x x x +-==和时，代入式(2-6)得 实验十三差分编译码实验 一、实验目的 掌握差分编码/译码原理 二、实验内容 1、学习差分编译码原理 2、用示波器观察差分编码结果和译码结果 三、基本原理 差分码是一种把符号‘0’和‘1’反映在相邻码元的相对变化上的波形。比如，若以相邻码元的电位改变表示符号‘1’，而以电位不改变表示符号‘0’，如图13－1所示。当然，上述规定也可以反过来。由图可见，这种码波形在形式上与单极性或双极性码波形相同，但它代表的信息符号与码元本身电位或极性无关，而仅与相邻码元的电位变化有关。差分波形也称相对码波形，而相应地称单极性或双极性波形为绝对码波形。差分码波形常在相位调制系统的码变换器中使用。 图13-1差分码波形 组成模块如下图所示： cclk d_out 端口说明： CCLK：编码时钟输入端 DIN：编码数据输入端 Diff－OUT：差分编码结果输出端 DCLK：译码时钟输入端 Diff－IN：差分译码数据输入端 DOUT：译码结果输出端 四、实验步骤 1、实验所用模块：数字编解码模块、数字时钟信号源模块。 实验连线： CCLK：从数字时钟信号源模块引入一高频时钟，如512K。 DIN：从数字时钟信号源模块引入一低频时钟，如16K。 DIFF－OUT与DIFF－IN短接。 DCLK与CCLK短接。 2、用示波器两探头同时观测DIN与DIFF－OUT端，分析差分编码规则。 3、用示波器两探头同时观测DIN与DOUT端，分析差分译码结果。 五、实验报告要求 设信息代码为1001101，码速率为128K，差分码的编码时钟为码速率的四倍，根据实验观察得到的规律，画出差分码波形。 实验报告 课程名称：计算方法 院系：数学科学系 专业班级：数应1001 学号：1031110139 学生姓名：姚海保 指导教师：沈林 开课时间：2012至2013学年第一学期 一、学生撰写要求 按照实验课程培养方案的要求，每门实验课程中的每一个实验项目完成后，每位参加实验的学生均须在实验教师规定的时间内独立完成一份实验报告，不得抄袭，不得缺交。 学生撰写实验报告时应严格按照本实验报告规定的内容和要求填写。字迹工整，文字简练，数据齐全，图表规范，计算正确，分析充分、具体、定量。 二、教师评阅与装订要求 1.实验报告批改要深入细致，批改过程中要发现和纠正学生实验报告中的问题，给出评语和实验报告成绩，签名并注明批改日期。实验报告批改完成后，应采用适当的形式将学生实验报告中存在的问题及时反馈给学生。 2.实验报告成绩用百分制评定，并给出成绩评定的依据或评分标准（附于实验报告成绩登记表后）。对迟交实验报告的学生要酌情扣分，对缺交和抄袭实验报告的学生应及时批评教育，并对该次实验报告的分数以零分处理。对单独设课的实验课程，如学生抄袭或缺交实验报告达该课程全学期实验报告总次数三分之一以上，不得同意其参加本课程的考核。 3.各实验项目的实验报告成绩登记在实验报告成绩登记表中。本学期实验项目全部完成后，给定实验报告综合成绩。 4.实验报告综合成绩应按课程教学大纲规定比例（一般为10-15%）计入实验课总评成绩；实验总评成绩原则上应包括考勤、实验报告、考核（操作、理论）等多方面成绩； 5.实验教师每学期负责对拟存档的学生实验报告按课程、学生收齐并装订，按如下顺序装订成册：实验报告封面、实验报告成绩登记表、实验报告成绩评定依据、实验报告（按教学进度表规定的实验项目顺序排序）。装订时统一靠左侧按“两钉三等分”原则装订。 宁波工程学院电信学院计算机系 实验报告 课程名称：算法设计与分析实验项目：用分治法算法解 最接近点对问题 指导教师：崔迪 实验位置：软件工程实验室姓名： 班级： 学号： 日期： 2016/10/12 一、实验目的 通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设 计和算法复杂性分析等。 二、实验环境： Eclipse 三、实验内容：用分治法解最接近点对问题 （1）问题描述 给定平面S上n个点，找其中的一对点，使得在n(n-1)/2 个点对中，该 点对的距离最小。 （2）算法设计思想 1. n较小时直接求 (n=2). 2.将S上的n个点分成大致相等的2个子集S1和S2 3.分别求S1和S2中的最接近点对 4.求一点在S1、另一点在S2中的最近点对 5.从上述三对点中找距离最近的一对. （3）程序设计（程序清单及说明） package closestpair; import java.util.Arrays; import https://www.wendangku.net/doc/7d996343.html,parator; import java.util.Random; import java.util.Scanner; //定义坐标点 class Point { double x; double y; public Point(double x, double y) { this.x = x; this.y = y; } } // 根据x坐标排序 class MyComparatorX implements Comparator 学生实验报告实验课程名称偏微分方程数值解 开课实验室数统学院 学院数统年级2013 专业班信计02班 学生姓名______________ 学号 开课时间2015 至2016 学年第 2 学期 数学与统计学院制 开课学院、实验室：数统学院实验时间：2016年6月20日 1、三层显格式建立 由于题中h 0.1, 0.1h，x 0,1 ,t 0,2，取N 10, M 200，故令网比r 0.1，h X j j h, j 0,1,2,L 10，t k k ,k O,1L ,200 ,在内网个点处，利用二阶中心差商得到如下格式: k 1 k U J 2U J 2- k 1 U j k k U j 1 2U j h2 k U j 1 o h2 略去误差项得到: k 1 U j 其中j 1,2丄9,k 对于初始条件 2 k r U J1 1,2,L ,199，局部截断误差为 U x,0 sin U J k U j k r U j 2 o k 1 U J h2。 (3) 对于初始条件-u x,0 t x，建立差分格式为： sin x j sin Jh , J 利用中心差商，建立差分格式为: 0,1,2,L 10 (4) 对于边界条件将差分格式延拓使综上（3 ）、 （4 ）、 k 1 u j 其中r山o.1 1 U J 2 1 U j 0,即U1二U j1, J 0,1,2,L 10 (5) 0,t 0,2 ，建立差分格式为： U N 0,k 0,1,L ,200 k 0为内点，代入（3）得到的式子再与（5）联立消去 1 1 2 0 ’ 2 0 1 5 r U, 1 1 r U, r J 2 J J 2 （7 ）得到三层显格式如下： U 0,t U 1,t k U0 (6 ) 、 2 k r U j 1 2 1 r2k 2 k U J r U J 1 k 1? U j , J U j （6） 1后整理得到: U j 1 (7) （局部截断误差为 1,2,L 9,k 1,2,L ,199 h2) 1 U j U J sin 1 2 0 2r U J 1 k U o X j k U N sin 2 0 r U j 0,k 0,1,2,L 10 Jh ,J 1 2r2u01, J 1,2,L 9 0,1L ,200 (8) 四?实验环境（所用软件、硬件等）及实验数据文件Matlab 算法分析与设计实验报告第四次附加实验 while (a[--j]>x); if (i>=j) { break; } Swap(a[i],a[j]); } a[p] = a[j]; //将基准元素放在合适的位置 a[j] = x; return j; } //通过RandomizedPartition函数来产生随机的划分 template vclass Type> int RandomizedPartition(Type a[], int p, int r) { int i = Random(p,r); Swap(a[i],a[p]); return Partition(a,p,r); } 较小个数排序序列的结果: 测试结果 较大个数排序序列的结果: 实验心得 快速排序在之前的数据结构中也是学过的，在几大排序算法中，快速排序和归并排序尤其是 重中之重，之前的快速排序都是给定确定的轴值，所以存在一些极端的情况使得时间复杂度 很高，排序的效果并不是很好，现在学习的一种利用随机化的快速排序算法，通过随机的确 定轴值，从而可以期望划分是较对称 的，减少了出现极端情况的次数，使得排序的效率挺高了很多， 化算法想呼应，而且关键的是对于随机生成函数，通过这一次的 学习终于弄明白是怎么回事了，不错。 与后面的随机实 验和自己的 实验得分助教签名 附录： 完整代码(分治法) //随机后标记元素后的快速排序 #i nclude 设计课题 设计一个具有恒流偏置的单端输入-单端输出差分放大器。 学校：延安大学 一： 已知条件 正负电源电压V V V V EE cc 12,12-=-+=+；负载Ω=k R L 20；输入差 模信号mV V id 20=。 二：性能指标要求 差模输入电阻Ω>k R id 10；差模电压增益15≥vd A ；共模抑制 比dB K CMR 50>。 三：方案设计及论证 方案一： 方案二 方案论证： 在放大电路中，任何元件参数的变化，都将产生输出电压的漂移，由温度变化所引起的半导体参数的变化是产生零点漂移的主要原因。采用特性相同的管子使它们产生的温漂相互抵消，故构成差分放大电路。差分放大电路的基本性能是放大差模信号，抑制共模信号好，采用恒流源代替稳流电阻，从而尽可能的提高共模抑制比。 论证方案一：用电阻R6来抑制温漂 ?优点：R6 越大抑制温漂的能力越强； ?缺点：<1>在集成电路中难以制作大电阻； <2> R6的增大也会导致Vee的增大（实际中Vee不 可能随意变化） 论证方案二 优点：（1）引入恒流源来代替R6,理想的恒流源内阻趋于无穷，直流压降不会太高，符合实际情况； （2）电路中恒流源部分增加了两个电位器，其中47R的用来调整电路对称性，10K的用来控制Ic的大小，从而调节静态工作点。 通过分析最终选择方案二。 四：实验工作原理及元器件参数确定 ?静态分析：当输入信号为0时， ?I EQ≈(Vee-U BEQ)/2Re ?I BQ= I EQ /(1+β) ?U CEQ=U CQ-U EQ≈Vcc-I CQ Rc+U BEQ 动态分析 ?已知：R1=R4,R2=R3 一、实验目的 1．理解分治法的方法； 2. 掌握使用分治法解决一般问题的步骤； 3. 掌握分治算法求解数组的最大值和最小值的方法。 二、实验原理 在一个给定数组中查找最大值和最小值是一类常见的问题，也是解决其他一些算法的基础。 假设给定数组为a，数组中含有n个元素，一般的算法是在数组中进行直接 循环的次数在算法第2行给出，为(n-2)+1=n-1次，因此，算法元素比较总次数为2(n-1)次。 现在采用分治的思想，假设数组的长度为2的整数幂，将数组分割成两半，分别为a[0…(n/2)-1]和a[n/2…n-1]，在每一半中分别查找最大值和最小值，并返回这两个最小值中的最小值以及两个最大值中的最大值。 假设给定数组为a，数组的下标上界和下界分别为low和high，则其算法伪 接比较数组的两个元素，选出最大值和最小值，此为函数的递归终止条件；代码第7行和第8行是两个递归调用，分别在数组的下标范围[low,mid]和 [mid+1,high]查找最小值和最大值，第9行比较两个最大值取其中较大者，第10行比较两个最小值取较大者。 代码的第2、9和10行涉及到元素的比较，第7、8行由于递归也产生元素比较，因此令算法总的元素比较次数为C(n)，则有 ???>+==2 2)2/(221)(n n C n n C 若若 对递推式进行求解 2 2/3 2 2)2/( 2)2(2 2 2...22)2/(2 ... 2 48)8/(824)2)8/(2(4 2 4)4/(42)2)4/(2(22)2/(2)(1 1122111-=-+=+=+++++==+++=+++=++=++=+=∑-=-----n n C n C n C n C n C n C n C n C k k j j k k k k k 得到minmax 算法的元素比较总次数为3n/2-2，优于直接比较的性能。 三、实验内容及要求 1. 编写程序使用分治算法MINMAX 求解数组的最小值和最大值，并用实际数组对算法进行测试。 2. 要求算法中元素比较的次数为3n/2-2，在程序中元素比较的地方进行记录，并在程序末尾输出数组最大值和最小值以及元素比较次数。 四、实验步骤 1. 定义结构体类型或类，用以在函数的返回值同时返回数组的最大值和最小值。 差分放大电路 实验报告 姓名：黄宝玲 班级：计科1403 学号：201408010320 实验摘要（关键信息） 实验目的：由于差分放大器是运算放大器的输入级，清楚差分放大电路的工作原理，有助于理解运放的工作原理和方式。通过实验弄清差分放大器的工作方式和参数指标。这些概念有：差模输入和共模输入；差模电压增益Avd和共模电压增益Avc；共模抑制比Kcmr。 实验内容与规划： 1、选用实验箱上差分放大电路；输入信号为Vs=300mV，f=3KHz正弦波。 2、发射极先接有源负载，利用调零电位器使得输出端电压Vo=0。（Vo=Vc1-Vc2） 3、在双端输入和单端输入差模信号情况下，分别测量双端输出的输入输出波形，计算各自的差模放大倍数Avd。 4、在双端输入共模信号情况下，分别测量双端输出的输入输出波形，计算双端输出共模放大倍数Avc。 5、计算共模抑制比Kcm R 。 最好作好记录表格，因为要记录的数据较多。电路中两个三极管都为9013。 实验环境（仪器用品等） 1.仪器：示波器（DPO 2012B 100MHZ 1GS/s） 直流电源（IT6302 0~30V,3Ax2CH/0~5V,3A） 台式万用表（UT805A） 模拟电路实验箱（LTE-AC-03B）。 2、所用功能区：单管、多管、负反馈放大电路。 实验原理和实验电路 1、实验原理： 差分电路是具有这样一种功能的电路。该电路的输入端是两个信号的输入，这两个信号的差值，为电路有效输入信号，电路的输出是对这两个输入信号之差的放大。 概念梳理： 差模和共模是对于差动放大电路的两个输入端而言的。 A ）差模输入：差动放大电路的两管基极输入的信号幅度相等、极性相反，这样的信号称为差模信号，这样的输入称为差模输入。 差模信号Vid ：即差模输入的两个输入信号之差。 B ）共模输入：差动放大电路的两管基极输入的信号幅度相等、极性相同，这样的信号称为共模信号，这样的输入称为共模输入。 共模信号Vic ：即共模输入的两个输入信号的算数平均值。 C ）差模电压增益Avd ：指差动放大电路对差模输入信号的放大倍数。差模电压增益越大，放大电路的性能越好。 = D ）共模电压增益Avc ：指差动放大电路对共模输入信号的放大倍数。共模电压增益越小，放大电路的性能越好。 = E ）共模抑制比Kcmr ：指差模电压放大倍数与共模电压放大倍数之比，它表明差动放大电路对共模信号的抑制能力。 =20lg| |（dB ） =| | 2、实验电路： SW1 SW-SPDT Q1 NPN Q2 NPN Q3 NPN R1 510 R2 510 R3 10k R4 10k R5 10k R6 10k R7 10k R8 5.1K R9 68K R10 36K RV1 100 R9(1) R10(2) A B C D AM FM + - 西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告 题目：分治法循环赛日程表 学号 姓名 专业班级 指导教师 实践日期2011年5月16日-5月20日 目录 一、综合训练目的与要求 (1) 二、综合训练任务描述 (1) 三、算法设计 (1) 四、详细设计及说明 (3) 五、调试与测试 (4) 六、实习日志 (6) 七、实习总结 (6) 八、附录：核心代码清单 (6) 一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务： （1）巩固和加深学生对算法分析课程基本知识的理解和掌握； （2）培养利用算法知识解决实际问题的能力； （3）掌握利用程序设计语言进行算法程序的开发、调试、测试的能力； （4）掌握书写算法设计说明文档的能力； （5）提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1天 利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。 三、算法设计 (1) 文字描述 假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手，根据分治法，要求n个选手的比赛日程，只要知道其中一半的比赛日程，所以使用递归最终可以分到计算两位选手的比赛日程，然后逐级合并，得出结果。 (2) 框图 数值实验报告I 、实 验目 的 ， 内 容 1、 理解Poisson 方程九点差分格式的构造原理； 2、 理解因为网格点的不同排序方式造成的系数矩阵格式的差异; 3、 学会利用matlab 的spdiags(),kron() 函数生成系数矩阵; 、算法描述 针对一个Poisson 方程问题: Au 二厂 f (x, y) 在Poisson 方程五点差分格式的基础上，采用 Taylor 展开分析五点差分算子的截断误差，可以 得到： AhU(x,> ￥j) 二 Au(xh yj) + —Jhi 厂 h2 a/ + h/ 12 亦 yj - J - 2u(x lF Yj - 1)+ u(xi -(, Yj - 1) hi^ufxn yj - J u(x jh yj) , 0u(xi,y 」)\ + hj 扩 \ h,十 Yj) 卜一 <2—癌L 时 0/ (1) 为了提高算子截断误差的精度，在⑴式中配凑出了差分算子的形式，将原Poisson 方程代入(1) 式有： yj) = ￥」) / 水 Uhi ，" 十 0(h 4) 昇舟1 ，有： /u(x I , yj) 1 i --^luxxCxj. Yj 十 1)- 2u xx (Xir yj + Uxxfxj, Vj - Jl + 0(h 『)=— hj h? u(Kj + 1, yj + 1)- 2u(x j t yj + 1)+ u(xj - v yj + i) h,护u(x lh yj 4 1) - ------- 2 考虑 h/ u(xj + ir yj) - 2u(xj. y 」)+ 12 i- Yj) 2hiVu(x b yj + 0(h 4)二 Au(x lT V J ) + — UlXi + 1 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 上机实验2：五点差分格式法 偏微分方程（Matlab ）实验报告 ——五点差分格式法 一、 实验题目 设G 是形如下图的十字形域，由五个相等的单位正方形组成，用五点差分格式求下列边值问题的数值解： 22 2 21,u u G x y ??+=-???于u=0,于G 二、 实验原理 取定沿X 轴和Y 轴方向的步长1h 和2h ，() 12 22 1 2 h h h =+,作两族与坐 标轴平行的直线：x=i 1h ,y=j 2h ,,0,1,2,i j =±± 若（,i j x y ）为正则内点，沿x,y 方向分别用二阶中心差商代替 xx yy u u 和则得 1,1,,1,1 2 212 22[ ]i j ij i j i j ij i j ij u u u u u u f h h +-+--+-+-+ = 特别取正方形网格：12h h h ==，则原差分方程可简化为 2 1,,11,,11()44 ij i j i j i j i j ij h u u u u u f --++-+++= 三、 实验程序 1）function uxy = EllIni2Uxl(x,y) format long ; uxy = 0; 2）function uxy = EllIni2Uxr(x,y) format long; uxy = y*(2-y); 3）function uxy = EllIni2Uyl(x,y) format long; uxy = 0; 4）function uxy = EllIni2Uyr(x,y) format long; if x < 1 uxy = x; else uxy = 2 - x; end 5）function u = peEllip5(nx,minx,maxx,ny,miny,maxy) format long; hx = (maxx-minx)/(nx-1); hy = (maxy-miny)/(ny-1); u0 = zeros(nx,ny); for j=1:ny u0(j,1) = EllIni2Uxl(minx,miny+(j-1)*hy); u0(j,nx) = EllIni2Uxr(maxx,miny+(j-1)*hy); end for j=1:nx u0(1,j) = EllIni2Uyl(minx+(j-1)*hx,miny); u0(ny,j) = EllIni2Uyr(minx+(j-1)*hx,maxy); end A = -4*eye((nx-2)*(ny-2),(nx-2)*(ny-2)); b = ones((nx-2)*(ny-2),1).*(-1); for i=1:(nx-2)*(ny-2) if mod(i,nx-2) == 1 if i==1 A(1,2) = 1; A(1,nx-1) = 1; b(1) = - u0(1,2) - u0(2,1); else if i == (ny-3)*(nx-2)+1 A(i,i+1) = 1; A(i,i-nx+2) = 1; 《算法分析与设计》实验报告 实验2 分治法算法设计 姓名XXX 学号XXX 班级XXXXXX 时间：XXXX-XX-XX 地点：XXX 同组人：无 指导教师：XXX 实验目的 a)掌握分治法算法设计的一般思想和方法。 b)理解并掌握二分查找、归并分类、快速分类算法。 c)能熟练运用分治法求解问题。 d)实验中所准备的数据是有代表性的。 实验内容 a)写一个顺序查找算法，将其与二分查找算法一起转换成程序，上机验证。 b)选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。 c)归并分类、快速分类算法转换成程序并验证之。 d)选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。 e)准备一定规模的数据集用于实验。此数据集越大越有得于验证算法，可以 考虑最终的数据个数超过10000个。 f)编写归并分类、快速分类程序，将上数据集中的数据分类。可以使用较少 的数据调试程序时。 g)用规模从小到大的数据集运行上述程序，统计它们的运行时间，并作对比 分析。 h)编写顺序查找、二分查找程序。 i)将查找程序与分类程序结合起来，用不同规模的数据集运行，统计程序运 行时间。 实验环境 硬件：Intel(R) Pentium(R) CPU RAM:4G 软件：Myeclipse2013 实验前准备 2、程序设计：见附1 实验步骤 a)准备一定规模的随机数据集用于实验，存于数组A中，A为全程数组，此 数据集越大越有得于验证算法，可以考虑最终的数据个数超过10000个。 使用randomInt(int min, int max, int num)方法产生不小于min，小于max 的num个随机数(其中A[0]和A[n]作为数组的上界和下界，供方便排序用，不参与实际排序)，在分析程序效率时可修改num来达到产生不同数量的随机数： b)分别编写归并分类MergeSort、快速分类程序QuickSort()，将上数据集中 的数据分类。可以使用较少的数据调试程序时。 二阶常微分方程的中心差分求解 学校:中国石油大学（华东）理学院 姓名：张道德 一、 实验目的 1、 构造二阶常微分边值问题: 22,(),(), d u Lu qu f a x b dx u a u b αβ?=-+=< 11122 222222333222122112 100121012010012 00N N N u f q h h u f q h h h u f q h h h q u f h h ---???? ??+-???? ??? ???? ???????-+-? ?????? ???????????=-+? ?????? ???????????-???? ????????-+????? ?? ????? 可以看出系数矩阵为三对角矩阵，而对于系数矩阵为三对角矩阵的方程组可以用“追赶法”求解，则可以得出二阶常微分方程问题的数值解。 四、 举例求解 我们选取的二阶常微分方程边值问题为： 2 22242,01 (0)1,(1), x d u Lu x u e x dx u u e ?=-+=-<差分法求解偏微分方程MAAB
差分编译码实验报告
差分方法实验报告
分治法实验报告一
一维波动方程的有限差分法
分治算法实验(用分治法实现快速排序算法)
(完整word版)差分放大器设计的实验报告
-实验1分治法
实验八_差分放大器实验报告
(完整word版)分治法循环赛日程表实验报告
Poisson方程九点差分格式_米瑞琪
算法分析实验报告--分治策略
偏微分方程上机实验报告.doc
实验2 分治法算法设计
偏微分中心差分格式实验报告(含matlab程序)