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 盒输入差
数值实验报告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的二阶中心差分格式替代精确值，最终得到了相对满意的结果。 教 师 评 语 指导教师：年月日
本科生实验报告 实验课程信息论与编码 学院名称信息科学与技术学院 专业名称通信工程 学生姓名 学生学号 指导教师谢振东 实验地点6C601 实验成绩 二〇一五年十一月二〇一五年十一月
实验一：香农（Shannon ）编码 一、实验目的 掌握通过计算机实现香农编码的方法。 二、实验要求 对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。 三、实验基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1、将信源消息符号按其出现的概率大小排列 )()()(21n x p x p x p ≥≥≥ 2、确定满足下列不等式的整数码长K i ； 1)(l o g )(l o g 22+-<≤-i i i x p K x p 3、为了编成唯一可译码，计算第i 个消息的累加概率 ∑ -== 1 1 )(i k k i x p p 4、将累加概率P i 变换成二进制数。 5、取P i 二进制数的小数点后K i 位即为该消息符号的二进制码。 四、源程序： #include int i,j; for(i=0;i 工程电磁场 实验报告 ——有限差分法 用超松弛迭代法求解 接地金属槽内电位的分布 一、实验要求 按对称场差分格式求解电位的分布 已知： 给定边值：如图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．理解分治法的方法； 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) 实验二Huffman 信源编码. (5) 实验三Shannon 编码 (9) 实验四信道容量的迭代算法 (12) 实验五率失真函数 (15) 实验六差错控制方法 (20) 实验七汉明编码 (22) 实验一信源熵值的计算 、实验目的 1 进一步熟悉信源熵值的计算 2 熟悉Matlab 编程 、实验原理 熵(平均自信息)的计算公式 q q 1 H(x) p i log2 p i log2 p i i 1 p i i 1 MATLAB实现：HX sum( x.* log2( x))；或者h h x(i)* log 2 (x(i )) 流程：第一步：打开一个名为“ nan311”的TXT文档，读入一篇英文文章存入一个数组temp，为了程序准确性将所读内容转存到另一个数组S，计算该数组中每个字母与空格的出现次数( 遇到小写字母都将其转化为大写字母进行计数) ，每出现一次该字符的计数器+1；第二步：计算信源总大小计算出每个字母和空格出现的概率；最后，通过统计数据和信息熵公式计算出所求信源熵值(本程序中单位为奈特nat )。 程序流程图： 三、实验内容 1、写出计算自信息量的Matlab 程序 2、已知：信源符号为英文字母(不区分大小写)和空格输入：一篇英文的信源文档。输出：给出该信源文档的中各个字母与空格的概率分布，以及该信源的熵。 四、实验环境 Microsoft Windows 7 五、编码程序 #include"stdio.h" #include 实验十三差分编译码实验 一、实验目的 掌握差分编码/译码原理 二、实验内容 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，差分码的编码时钟为码速率的四倍，根据实验观察得到的规律，画出差分码波形。 实验一 绘制二进熵函数曲线（2个学时） 一、实验目的： 1. 掌握Excel 的数据填充、公式运算和图表制作 2. 掌握Matlab 绘图函数 3. 掌握、理解熵函数表达式及其性质 二、实验要求： 1. 提前预习实验，认真阅读实验原理以及相应的参考书。 2. 在实验报告中给出二进制熵函数曲线图 三、实验原理： 1. Excel 的图表功能 2. 信源熵的概念及性质 ()()[] ()[]())(1)(1 .log )( .) ( 1log 1log ) (log )()(10 , 110)(21Q H P H Q P H b n X H a p H p p p p x p x p X H p p p x x X P X i i i λλλλ-+≥-+≤=--+-=-=≤≤? ?????-===??????∑ 单位为 比特/符号 或 比特/符号序列。 当某一符号xi 的概率p(xi)为零时，p(xi)log p(xi) 在熵公式中无意义，为此规定这时的 p(xi)log p(xi) 也为零。当信源X 中只含有一个符号x 时，必有p(x)=1，此时信源熵H （X ）为零。 四、实验内容： 用Excel 和Matlab 软件制作二进熵函数曲线。根据曲线说明信源熵的物理意义。 （一） Excel 具体步骤如下： 1、启动Excel 应用程序。 2、准备一组数据p 。在Excel 的一个工作表的A 列（或其它列）输入一组p ，取步长为0.01，从0至100产生101个p （利用Excel 填充功能）。 3、取定对数底c，在B列计算H(x) ,注意对p=0与p=1两处，在B列对应位置直接输入0。Excel中提供了三种对数函数LN(x),LOG10(x)和LOG(x,c)，其中LN(x)是求自然对数，LOG10(x)是求以10为底的对数，LOG(x,c)表示求对数。选用c=2,则应用函数LOG(x,2)。 在单元格B2中输入公式：=-A2*LOG(A2,2)-(1-A2)*LOG(1-A2,2) 双击B2的填充柄，即可完成H(p)的计算。 4、使用Excel的图表向导，图表类型选“XY散点图”，子图表类型选“无数据点平滑散点图”，数据区域用计算出的H(p)数据所在列范围，即$B$1:$B$101。在“系列”中输入X值(即p值)范围，即$A$1:$A$101。在X轴输入标题概率，在Y轴输入标题信源熵。 （二）用matlab软件绘制二源信源熵函数曲线 p = 0.0001:0.0001:0.9999; h = -p.*log2(p)-(1-p).*log2(1-p); plot(p,h) 五、实验结果 实验报告 课程名称：计算方法 院系：数学科学系 专业班级：数应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.doczj.com/doc/1613156284.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 游程编码实现有效性提高的原理及通用编码的思想 康乐203201505020 摘要：信源编码的目的是提高信息传输效率，其思想是去除消息中的冗余成分。在无失真的信源编码中，根据信源的统计特性进行编码称为统计编码，而在信源统计特性未知的情况下，就需要一种新的编码方法，称之为通用编码。本文对统计编码中的游程编码进行了分析，说明其有效性，给出其具有有效性的原理论述，对游程编码的截断效应进行了仿真；同时分析了通用编码的存在性与构造方法，还以字典码为例进行了仿真。 关键词：信源编码游程编码通用编码字典码 一、信源编码概述 通信的根本问题是将信源的输出在接收端精确的或近似的重现出来。为此需要解决两个问题。其一是信源的输出应如何描述，及如何计算它产生的信息量；其二是如何表示信源的输出，即信源编码问题。由于信源可以根据信息输出的形式分为离散信源和连续信源，因此信源编码也就可以分为离散信源和连续信源。 根据通信的要求，可以将信源编码分为无失真信源编码和限定失真的信源编码。若要求精确的重现信源的输出，就要保证信源产生的 全部信息无损的传递给信宿，这时的信源编码就是无失真信源编码。许多实际情况下，并不要求完全精确地复制出信源的输出，而且在有干扰的情况下，这也是不可能的。一般对信源-信宿要定出可接收准则或保真度准则，这就是限定失真的信源编码。 离散信源的输出可以用如下符号序列表示： 21012,,,,,U U U U U -- 其中l U 表示在第l 时刻产生的符号，l 为整数。l U 为一随机变量，它 在有限字母集{}1,k A a a =中选取。如果使用D 字母的集合 {}1,d B b b =作为码表，那么如果组成码字的码符号数目相等，我们就称之为等长编码，否则称之为非等长编码。 非等长编码则可以根据编码是否依赖信源的统计特性分为统计编码与通用编码。 二、 游程编码 2.1 游程编码概念 游程编码（RLC, Run Length Coding ），又称“运行长度编码”或“行程编码”，是一种统计编码，该编码属于无损压缩编码，是栅格数据压缩的重要编码方法。 游程编码中的游程是指字符序列中各个字符连续重复出现而形成的字符串长度，编码方法是将字符序列映射成字符串长度和位置的标志序列，那么对于M 元序列： 011{,,,}M u u u - 学生实验报告实验课程名称偏微分方程数值解 开课实验室数统学院 学院数统年级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 信息论与编码实验报告-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII 实验一关于硬币称重问题的探讨 一、问题描述： 假设有N 个硬币，这N 个硬币中或许存在一个特殊的硬币，这个硬币或轻 或重，而且在外观上和其他的硬币没什么区别。现在有一个标准天平，但是无刻度。现在要找出这个硬币，并且知道它到底是比真的硬币重还是轻，或者所有硬币都是真的。请问： 1）至少要称多少次才能达到目的； 2）如果N=12，是否能在3 次之内将特殊的硬币找到；如果可以，要怎么称？ 二、问题分析： 对于这个命题，有几处需要注意的地方： 1）特殊的硬币可能存在，但也可能不存在，即使存在，其或轻或重未知； 2）在目的上，不光要找到这只硬币，还要确定它是重还是轻； 3）天平没有刻度，不能记录每次的读数，只能判断是左边重还是右边重，亦或者是两边平衡； 4）最多只能称3 次。 三、解决方案： 1.关于可行性的分析 在这里，我们把称量的过程看成一种信息的获取过程。对于N 个硬币，他们 可能的情况为2N+1 种，即重（N 种），轻（N 种）或者无假币（1 种）。由于 这2N+1 种情况是等概率的，这个事件的不确定度为： Y=Log(2N+1) 对于称量的过程，其实也是信息的获取过程，一是不确定度逐步消除的过程。 每一次称量只有3 种情况：左边重，右边重，平衡。这3 种情况也是等概率 的，所以他所提供的信息量为： y=Log3 在K 次测量中，要将事件的不确定度完全消除，所以 K= Log(2N+1)/ Log3 根据上式，当N=12 时，K= 2.92< 3 所以13 只硬币是可以在3 次称量中达到 设计课题 设计一个具有恒流偏置的单端输入-单端输出差分放大器。 学校：延安大学 一： 已知条件 正负电源电压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. 定义结构体类型或类，用以在函数的返回值同时返回数组的最大值和最小值。 实验报告 学院：专业：班级： 姓名：学号：实验日期： 实验名称： 实验一：唯一可译码判别准则的代码实现 实验二：霍夫曼编码的代码实现 实验目的： 实验一： 1.进一步熟悉唯一可译码判别准则； 2.掌握C 语言字符串处理程序的设计和调试技术。 实验二： 1.进一步熟悉Huffman 编码过程； 2.掌握C 语言递归程序的设计和调试技术。 实验仪器： 装有visual studio 2010 的电脑一台 实验原理： 实验一： 根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。 算法：1、考察 C 中所有的码字，若Wi 是Wj 的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1 中； 2、考察C 和Fi 俩个集合，若Wi ∈C 是Wj∈F 的前缀或Wi ∈F 是Wj∈C 的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1 中； 3、F=∪Fi 即为码C 的尾随后缀集合； 4、若F 中出现了C 中的元素，算法终止，返回假（C 不是唯一可译码）；否 则若F 中没有出现新的元素，则返回真。 实验二： 1.将q 个信源符合按概率大小递减排列; 2.用“0,1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1 个符号的新信源，称为缩减信源s 1； 3.把缩减信源s1的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2 个信源符号的缩减信源s 2； 4.依次继续下去，直至信源符号最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示； 5.然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即对应的码字。 实验内容与步骤： 实验一： 1.已知：信源符号数和码字集合C； 2.输入：任意的一个码，码字的个数和每个具体的码字在运行时从键盘输入； 3.输出：判决（是唯一可译码/不是唯一可译码）；循环（若继续判决则输入1 循环判决，否则输入0 结束运行）。 实验二： 1. 输入：信源符号个数r、信源的概率分布P； 2. 输出：每个信源符号对应的Huffman 编码的码字。 实验数据： 实验一源代码： #include有限差分法实验报告
_实验1分治法
差分法求解偏微分方程MAAB
信息论与编码实验报告材料
差分编译码实验报告
信息论与编码实验报告
差分方法实验报告
分治法实验报告一
信息论实验报告
一维波动方程的有限差分法
分治算法实验(用分治法实现快速排序算法)
信息论与编码实验报告
(完整word版)差分放大器设计的实验报告
-实验1分治法
信息论实验报告
相关主题
文本预览