通信算法复习总结
题型：简答、问答、填空、计算
疑似重点：内积、线性空间、正交因子白噪声、宽平稳、OFDM多路计算、预测算法过程最大参数设定、LMS算法优势。
第一章
概念：向量空间正交性表示信号正交基随机过程参数模型ARMA DFT公式复基带表示
二阶矩：广义平稳均值方差广义联合平稳自相关性质功率谱密度自相关矩阵
高斯白噪声为什么称为“白”噪声
解释：什么是遍历性
~
第二章
1.什么是维纳滤波器
假定线性滤波器的输入为有用信号和噪声之和，两者均为广义平稳过程且知它们的二阶统计特性，根据最小均方误差准则(滤波器的输出信号与需要信号之差的均方值最小)，求得了最佳线性滤波器的参数，这种滤波器被称为维纳滤波器。
2. 维纳滤波实现前提条件：
Linear（线性）、WSS（广义宽平稳）
3.维纳滤波优缺点
维纳滤波器的优点是适应面较广，无论平稳随机过程是连续的还是离散的，是标量的还是向量的，都可应用。维纳滤波器的缺点是: [1]不能用于噪声为非平稳的随机过程，[2]要求得到半无限时间区间内的全部观察数据的条件很难满足.
4.维纳理论来解决的问题：
|
前向预测和后向预测
维纳滤波和LS的一些公式时间充分的话建议大家自己看一下。
第三章：自适应横向滤波器
主要内容：MSE准则、LMS算法及其收敛、RLS算法及其收敛、LMS算法的比较和RLS算法的比较，自适应滤波算法根据的最佳准则为最小均方误差准则。
1. LMS算法全称Least mean square 最小均方算法。
是线性自适应滤波算法，包括滤波过程和自适应过程。
基于最速下降法的LMS算法的迭代公式如下：
e ( n) = d ( n)- w ( n - 1) x ( n) （1）
`
w ( n) =w ( n - 1) + 2μ( n) e ( n) x ( n) （2）
式中，x ( n)为自适应滤波器的输入；d ( n)为参考信号；e ( n)为误差；w ( n)为权重系数；μ( n)为步长。
LMS算法收敛的条件为：0 <μ< 1/λmax ，λmax是输入信号自相关矩阵的最大特征值。
算法的优缺点
由于LMS算法具有结构简单，计算复杂度小，性能稳定等特点，缺点：在收敛速率、跟踪速率和稳态误差特性之间的要求是相互矛盾的，不能同时得到满足，其性能由步长来控制。主要应用：广泛地应用于自适应均衡、语音处理、自适应噪音消除、雷达、系统辨识及信号处理等领域。
(Recursive Least Squares)递归最小二乘算法
递推最小二乘(RLS)算法是一种在自适应迭代的每一步都要求最优的迭代算法，滤波器输出信号法，滤波器输出信号 等于输入信号 与冲激响应序列 的卷积和，即：
()()()1
1M k k y n w n x n k ==*-+∑ K 1,2,...,n N =
,
误差信号 。由此可以得到自适应横向滤波器按最小均方准，则设代价函数
()()()()22
11N N i i J n e n d i y i ====-????∑∑ （）
式中()d i 与()y i 分别为自适应滤波器的期望相应于输出信号。
算法优缺点：
RLS 算法的主要优点：
[1]在数值上比直接计算的方法稳定
[2]每一步都对系数进行了估计而不仅仅在数据序列的结束
[3] λ< 1 和1/(1-λ) 时收敛速度快
【
其缺点是计算量比较大。
第四章 无线链路
1. 什么是多径效应（multipath effect ）：
由电波传播信道中的多径传输现象所引起的干涉延时效应。在实际的无线电波传播信道中(包括所有波段)，常有许多时延不同的传输路径，称为多径现象。 多径效应是衰落的重要成因。多径效应对于数字通信、雷达最佳检测等都有着十分严重的影响。
2.多径效应产生的原因
由电波传播信道中的多径传输现象所引起的干涉延时效应。（可能是这个吧～）
3. .多径效应的影响
》
多径会导致信号的衰落和相移。
多径对信道产生的负面影响就是会产生符号间干扰（Inter Symbol Interference ）。
4. 频率选择性衰落
是指在不同频段上衰落特性不一样。
多径效应在不同条件会使传输信号发生平坦衰落、时间选择性衰落和频率选择性衰落，主要还是频率选择性衰落，抗干扰措施：
假设信号码元长度为T ，第i 条传输路径的信号时延与信号平均时延这差为△t,则二者的不同组合可产生三种不同的衰落现象。
〔1〕当信号码元长度T 较小，且△t< 〔2〕当信号码元长度T 较长，且△t< & 〔3〕当信号码元长度T 比较小，而△t 比较大，且不满足△t< 5.时间选择性衰落 是指在不同的时间衰落特性不同的现象。 由于相对速度的变化引起频移度也随之变化这是即使没有多径信号，接受到的同一路信号的载频范围随时间不断变化引起时间选择性衰落。交织编码可以克服时间选择性衰落。 6. .多普勒频移（Doppler shift） 在存在相对运动发射机与接收机之间,接收信号的频率正在经历一个相对于发送信号频率的转变，称为多普勒频移。（话比较罗嗦，自己精炼啊） 由多普勒效应产生。当声源与接收体之间有相对运动时，接收体接收的声波频率f'与声源频率f存在多普勒频移Δf(Doppler shift)，即：Δf=f'-f 当接收体与声源相互靠近时，接收频率f'大于发射频率f即：Δf>0 — 当接收体与声源相互远离时，接收频率f'小于发射频率即：Δf<0 可以证明若接收体与声源相互靠近或相互远离的速度为v，声速为c，则接收体接收声波的多普勒频率为：f'= f?(c+-v1)/(c-+v2) 括号中分子和分母的加、减运算分别为“接近”和“远离”之意。 7.怎样克服多径效应 在数字无线通信系统中，多径效应产生的符号间干扰（inter-symbol-interference，ISI）会影响到信号传输的质量。时域均衡、正交频分复用（OFDM）和Rake接收机都能用于对抗由多径产生的干扰。 8.无线电 是用来描述一个电磁场在自由空间的传播。 用于无线电传输的频率范围从大约100Hz-几十GHz. # 为了实现一个高效的辐射的电磁能量，天线必须至少等于1/10的载波波长。 9. 在一个数字传输系统多路径的影响取决于符号周期的相对时延和信道冲激响应。 第五章信号的数字表示 1. 模拟传输和数字传输模型 2.语音编码 编码速率：用比特/秒（b/s或bps）来度量，用I表示， I=R ?fs ,R代表每个语音采样值编码所需的比特数；fs是采样频率。 当fs=8kHz，每个采样值用8比特位来编码，则编码速率为64kb/s。 — 3.均匀量化 把输入信号的取值域等间隔分割的量化称为均匀量化。 4.非均匀量化（重点） 非均匀量化是一种在输入信号的动态范围内量化间隔不相等的量化。换言之，非均匀量化是根据输入信号的概率密度函数来分布量化电平，以改善量化性能。 优点：一、当输入量化器的信号具有非均匀分布的概率密度时，非均匀量化器的输出端可以较高的平均信号量化噪声功率比; 二、非均匀量化时，量化噪声对大、小信号的影响大致相同，即改善了小信号时的量化信噪比。 分类：常见的非均匀量化有A律和μ率。 5. A律13折线法 13段折线法，过程为： 、 第一步：把x（x>0 部分）划分为不均匀的8段。第一分点取在V/2处，然后每段都是剩下部分的1/2。；依次取第八段为V~V/2,第七段为V/2~V/4；第一段为V/128~0。 第二步：把每段均匀划分为16等份，每一份表示一个量化级，显然8段共16x8=128= 2^7 个量化级，需要二进制7位编码表示。可以看出每个量化级是不均匀的。在小信号的量化台阶很小，使小信号时量化噪声减小。如果按均匀量化计算，以最小台阶(1/128)*(1/16)为单位，最大信号需用L=128X16=2048= 2^11 个量化级表示，既需要11位编码。这样非均匀编码使小信号量化台阶缩小了16倍，相当于小信号信噪比改善了20dB。 第三步：把y轴均匀划分为8段，每段均匀分为16分。这样y也分为128个量化级，与x轴的128个量化级对应。因此，压扩特性各段的斜率k=Δy/Δx是不同的。第一段斜率k1=y1/x1=（1/8）/(1/128)=16. 其他段为: k2=16，k3=8，k4=4，k5=2，k6=1，k7-1/2，k8=1/4。 以上分段为x取正值时的情况。而x取负值时，压扩特性与x取正值成奇对称。在正8段和负8段中，正1，2段和负1，2段斜率相同，合为一段。所以原来的16段折线变为13段折线，故又称A律13折线。 6.语音信号频率范围：300-3400Hz，采样频率=8000Hz，每个样本编码8bit，故有编码速率为64kb/s。 7. 编码技术 （1）波形编码； 《 是将时间域信号直接变换为数字代码，力图使重建语音波形保持原语音信号的波形形状。 脉冲编码调制（PCM）、差分脉冲编码调制（DPCM）、自适应差分脉冲编码调制（ADPCM）、增量调制（△M）、自适应增量调制（ADM）都属于此范畴。 （2）频域编码； 8. 通常一个编码技术是严格相关的应用程序，取决于各种因素：信号类型(例如演讲、音乐、声音带数据,信号等)；最大容许延迟；实现的复杂性。 第六章调制原理 1.调制理论是什么 调制：由信源产生的信息在传输的过程中，转变成一个适合在物理信道上传输的信号。在一些情况下，信道的改变可能产生失真、干扰、噪声。 ? 数字信号的传输：信息表现为信源产生的是一个序列的二进制位，或者是模拟信号的数字编码。 2.什么是判决准则 。。。。。。 3.什么是后验概率准则 后验概率准则：出发点是如何使译码后的错误概率PE为最小。其基本思路为：收到yj 后，对于所有的后验概率P(x1|yj), P(x2|yj), …, P(xi | yj), …，若其中P(x*|yj)具有最大值，则将x*判决为yj的估值。 由于这种方法是通过寻找最大后验概率来进行译码的，故又常称之为最大后验概率准则。 最大后验概率译码方法是理论上最优的译码方法，但在实际译码时，既要知道先验概率又要知道后验概率，而后验概率的定量计算有时比较困难，需要寻找更为实际可行的译码准则。4．什么是最大似然准则 ， 最大似然准则：在P(yj |x1)，P(yj |x2), …, P(yj |xM), …中，若存在一个P(yj |x*)为其中的最大值，则g(yj) = x*必然符合最小错误概率准则。这种由最大的信道传输概率P(yj|x*)直接将yj译成x*的方法，称为最大似然译码准则。这种方法的特点是只要知道传输概率P(yj |xi)就可以了，而使信源空间变为等概是有很多办法的。 第七章符号间干扰 1.什么是符号间干扰（ISI） 由于系统传输总特性（包括收、发滤波和信道的特性）不理想，导致前后码元的波形畸变、展宽，并使前面波形出现很长的拖尾，蔓延到当前码元的抽样时刻上，从而对当前码元的判决造成干扰。 符号间干扰指的是下面的含义：在无线信道中,由于存在多径传播问题,对数据传输也会产生ISI。当数据速率提高时，数据间的间隔就会减小，到一定程度符号重叠无法区分，产生ISI。 码间干扰定义：(1)在一个数字传输系统中接收到的信号失真，这种失真被在时间的传播中显现和作为结果与单个脉冲交迭到达接收器不能可靠的区分状态交换（例如，在单个信号原始之间）的程度。(2)来自这个信号的外部能量在一个或更多电键间隔中，接收这个信号的干扰在另一个电键间隔中。(3)由外部能量引起的骚乱来自一个或更多电键间隔的信号，接收这个信号的干扰在另一个电键间隔中。码间干扰是数字通信系统中除噪声干扰之外最主要的干扰，它与加性的噪声干扰不同，是一种乘性的干扰。造成码间干扰的原因有很多，实际上，只要传输信道的频带是有限的，就会造成一定的码间干扰。 第八章OFDM " 1. 关于OFDM概念 OFDM(Orthogonal Frequency Division Multiplexing)即正交频分复用技术，实际上OFDM是MCM Multi-CarrierModulation，多载波调制的一种。其主要思想是：将信道分成若干正交子信道，将高速数据信号转换成并行的低速子数据流，调制到在每个子信道上进行传输。正交信号可以通过在接收端采用相关技术来分开，这样可以减少子信道之间的相互干扰ICI 。每个子信道上的信号带宽小于信道的相关带宽，因此每个子信道上的可以看成平坦性衰落，从而可以消除符号间干扰。而且由于每个子信道的带宽仅仅是原信道带宽的一小部分，信道均衡变得相对容易。 技术的最大优点是 1>.对抗频率选择性衰落或窄带干扰。在单载波系统中，单个衰落或干扰能够导致整个 通信链路失败，但是在多载波系统中，仅仅有很小一部分载波会受到干扰。对这些子信道还可以采用纠错码来进行纠错。 2>.可以有效地对抗信号波形间的干扰，适用于多径环境和衰落信道中的高速数据传输。当信道中因为多径传输而出现频率选择性衰落时，只有落在频带凹陷处的子载波以及其携带的信息受影响，其他的子载波未受损害，因此系统总的误码率性能要好得多。 3>. OFDM技术抗窄带干扰性很强，因为这些干扰仅仅影响到很小一部分的子信道 4>.在窄带带宽下也能够发出大量的数据，信道利用率很高，这一点在频谱资源有限的无线环境中尤为重要。 3.缺点: " (1)对相位噪声和载波频偏十分敏感这是OFDM技术一个非常致命的缺点，整个OFDM系统对各个子载波之间的正交性要求格外严格，任何一点小的载波频偏都会破坏子载波之间的正交性，引起ICI，同样，相位噪声也会导致码元星座点的旋转、扩散，从而形成ICI。而单载波系统就没有这个问题，相位噪声和载波频偏仅仅是降低了接收到的信噪比SNR，而不会引起互相之间的干扰。 (2)峰均比过大OFDM信号由多个子载波信号组成，这些子载波信号由不同的调制符号独立调制。同传统的恒包络的调制方法相比，OFDM调制存在一个很高的峰值因子。因为OFDM信号是很多个小信号的总和，这些小信号的相位是由要传输的数据序列决定的。对某些数据，这些小信号可能同相，而在幅度上叠加在一起从而产生很大的瞬时峰值幅度。而峰均比过大，将会增加A/D和D/A的复杂性，而且会降低射频功率放大器的效率。同时，在发射端，放大器的最大输出功率就限制了信号的峰值，这会在OFDM频段内和相邻频段之间产生干扰。 (3)所需线性范围宽由于OFDM系统峰值平均功率比(PAPR)大，对非线性放大更为敏感，故OFDM调制系统比单载波系统对放大器的线性范围要求更高。 4.信道均衡技术（Channel equalization） 是指为了提高衰落信道中的通信系统的传输性能而采取的一种抗衰落措施。它主要是为了消除或者是减弱宽带通信时的多径时延带来的码间串扰（ISI）问题。其机理是对信道或整个传输系统特性进行补偿，针对信道恒参或变参特性，数据速率大小不同，均衡有多种结构方式。大体上分为两大类：线性与非线性均衡。对于带通信道的均衡较为困难，一般都是待接收端解调后在基带进行均衡，因此基带均衡技术有广泛应用。在实际中一般是加入自适应滤波器来实现信道均衡。 的相关计算 The steps:（计算步骤与相关参数固定关系） The time delay spreading decides the length of guard time, which should be 2-4 times than rms value. | The symbol length should be 4-5 times than guard time. The subcarrer width is the Reciprocal of symbol length. FFT number is an 2M integer decided by (system width)/(subcarrier width) Modulation type can be calculated by transmission rate. Design an OFDM system, system width is less than 15MHz, time delay spreading is 200ns, the data transmission rate is more than 20Mbit/s. 求保护时隙的长度: Set guard time=4*tms=800ns （保护时隙一般是时延扩展的4倍） 符号长度:Symbol length=6*800ns= ` 无保护时间的符号长度Symbol length(without GT)=4us 子载波宽度:Subcarrier width=1/4us=250kHz FFT number: 15MHz/250KHz=60, choose 64 Each subcarrier data rate should be rapid than 20M/64=s, that means each symbol should carry *= data. -------------------------------------------------------------------- 1111.如何决定一个OFDM系统的参数(重要) 已知的:OFDM的系统带宽（15MHz）、时间延迟传播（200ns）、数据传输速率（20Mbit/s），确定：FFT点数和调制方式 步骤:： 。 时间延迟传播时间的长度决定保护时间间隔，这应该是均方根值的2 - 4倍，符号长度应该是保护时间间隔的4 - 5倍，子载波的宽度是符号长度的倒数，FFT的点数（2m）是整数通过(系统宽度)/(副载波宽度) 决定，调制类型有传输速率决定。 真题： 设计一个OFDM系统,系统宽度小于15 MHz,延迟时间是200ns,数据传输速率是超过20 Mbit / s。设保护时间为：4 * tms = 800ns，符号长度为：800 ns * 6 * 800ns= 微秒，符号长度(没有保护时间)=4微秒，子载波宽度= 1/4us = 250 khz。 解：FFT点数:15 mhz / 250千赫= 60,选择64阶 每个子载波速率应该超过20M/ 64 = kb / s,这意味着每个符号应该携带* = 位数据。 如果考虑到纠错编码(1/2率),可以使用8 psk进行。 } 第九章CDMA CDMA (Code Division Multiple Access) 又称码分多址，是在无线通讯上使用的技术。 1.扩频与解扩 扩频系统可以看作是两个调制过程，第一步，使用传统的调制方式调制有效信号；第二步，使用扩频编码调制载波，使其扩展到一个非常大的带宽内，实现频谱展宽。解扩相反 多址系统：CDMA多址方式用不同码型的地址码来划分信道，每一地址码对应一个信道，每一信道对时间及频率都是共享的。 窄带干扰抑制 2直接序列系统 。 所谓直接序列(DS)扩频，就是直接用具有高码率的扩频码序列在发端去扩展信号的频 ＤB1B2 B2 D 信息调制扩频解扩解调 PN码发生器 图直序扩频系统原理图 直序扩频技术直序扩频技术的原理是使用快速变化的二进制比特流调制射频载波信号，这种二进制比特流看上去是随机的，实际上是按照特定的算法由数字电路产生的，称为伪随机码（Pseudo noise）。在伪随机码的调制下，载波的相位在0度～180度之间跳跃变化，被调制后的载波又同有效信息进行混合，通过发射机发射。相应的接收机内能够产生相同的伪随机码，按照发射的逆过程解调，解析出有效信息信号。 3 扩频- 优势 （1）抗干扰能力。强扩频通信系统扩展的频谱越宽，处理增益越高，抗干扰能力就越强。简单地说，如果信号频谱展宽10倍，那么干扰方面需要在更宽的频带上去进行干扰，分散了干扰功率，从而在总功率不变的条件下，其干扰强度只有原来的1／10。另外，由于接收端采用扩频码序列进行相关检测，空中即使有同类信号进行干扰，如果不能检测出有用信号的码序列，干扰也起不了太大作用，因此抗干扰性能强是扩频通信的最突出的优点。（2）码分多址能力强。由于扩频通信中存在扩频码序列的扩频调制，充分利用各种不同码型扩频序列之间优良的自相关特性和互相关特性，在接收端利用相关检测技术进行解扩，则在分配给不同用户不同码型的情况下，系统可以区分不同用户的信号，这样在同一频带上许多对用户可以同时通话而互不干扰。 （3）高速可扩展能力强。由于独占信道且码分多址，所以速率很高。由于在标准中，11位随机码元中只有1位用来传输数据，因此吞吐量的扩展能力强。相对于通用标准采用的相位变化DQPSK/DPSK调制技术，增强型采用了直序/脉冲位置调制（DS/PPM）技术。PPM技术使用了预置的8位码元中的3位传输数据，这就使传输率产生了飞跃。 4.软切换 所谓软切换是指移动台需要切换时，先与新的基站连通再与原基站切断联系，而不是先切断与原基站的联系再与新的基站连通。软切换只能在同一频率的信道间进行，因此，模拟系统、TDMA系统不具有这种功能。软切换可以有效地提高切换的可靠性，大大减少切换造成的掉话，因为据统计，模拟系统、TDMA系统无线信道上的掉话90%发生在切换中。5.软容量： 在FDMA、TDMA系统中，当小区服务的用户数达到最大信道数，已满载的系统再无法增添一个信号，此时若有新的呼叫，该用户只能听到忙音。而在CDMA系统中，用户数目和服务质量之间可以相互折中，灵活确定。例如系统运营者可以在话务量高峰期将某些参数进行调整，例如可以将目标误帧率稍稍提高，从而增加可用信道数。同时，在相邻小区的负荷较轻时，本小区受到的干扰较小，容量就可以适当增加。 （以上为上届整理资料） 今天上课老师说了下，那些估计会考的我大概记了下，如下： 1.解释、理解说明下图： 2．Wiener-hopf方程 3. 频率衰落、调制理论、OFDM计算参数 4. CDMA抗干扰原理及求相关参数、扩频增益等！ （我就只记到了这么多） 网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311. 第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 大学算法分析与设计复习总结 为了拿大学的那悲剧的学分，好好弄懂以下所有知识点吧。把老师的复习的提纲，特意汇总了所有考点，方便童鞋们复习。不喜勿喷！！！ 这本书是《算法设计与分析》王红梅编著 一共有以下12章，我们学了1、3、4、5、6、7、8、9 分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法 第1章绪论 考点： 1、算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1. 自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2. 流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3. 程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 伪代码优点：表达能力强，抽象性强，容易理解 3、了解非递归算法的时间复杂性分析。(P13) 要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是： （1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。 （3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。 [例1.4]：求数组最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]; for (i=1; i 算法案例 【学习目标】 1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序； 3.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质； 4.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换. 【要点梳理】 要点一、辗转相除法 也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到一个商q 0和一个余数r ； 第二步：若r 0=0，则n为m，n的最大公约数；若r ≠0，则用除数n除以余数r 得到一个 商q 1和一个余数r 1 ； 第三步：若r 1=0，则r 为m，n的最大公约数；若r 1 ≠0，则用除数r 除以余数r 1 得到一个 商q 2和一个余数r 2 ； …… 依次计算直至r n =0，此时所得到的r n－1 即为所求的最大公约数. 用辗转相除法求最大公约数的程序框图为： 程序： INPUT “m=”;m INPUT “n=”;n IF m WEND PRINT n END 要点诠释： 辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m 表示，把较小的数用变量n 表示，这样式子 )0(n r r q n m <≤+?=就是一个反复执行的步骤，因此可以用循环结构实现算法. 要点二、更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之. 翻译出来为： 第一步：任意给出两个正整数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)就是所求的最大公约数. 理论依据： 由r b a r b a +=→=-，得b a ,与r b ,有相同的公约数 更相减损术一般算法： 第一步，输入两个正整数)(,b a b a >； 第二步，如果b a ≠，则执行3S ，否则转到5S ； 第三步，将b a -的值赋予r ； 第四步，若r b >，则把b 赋予a ，把r 赋予b ，否则把r 赋予a ，重新执行2S ； 第五步，输出最大公约数b . 程序: INPUT “a=”，a INPUT “b=”，b WHILE a<>b 自动寻峰 由于谱结构的复杂和统计涨落的影响，从谱中正确地找到全部存在的峰是比较困难的。尤其是找到位于很高本底上的弱峰，分辨出相互靠得很近的重峰更为困难。 谱分析对寻峰方法的基本要求如下： (1)比较高的重峰分辨能力。能确定相互距离很近的峰的峰位。 (2)能识别弱峰，特别是位于高本底上的弱峰。 (3)假峰出现的几率要小。 (4)不仅能计算出峰位的整数道址，还能计算出峰位的精确值，某些情况下要求峰位的误差小于0.2道。 很多作者对寻峰方法进行了研究，提出了很多有效的寻峰方法。 目的： 判断有没有峰存在 确定峰位(高斯分布的数学期望)，以便把峰位对应的道址，转换成能量 确定峰边界为计算峰面积服务(峰边界道的确定，直接影响峰面积的计算) 分为两个步骤：谱变换和峰判定 要求：支持手动/自动寻峰，参数输入，同时计算并显示峰半高宽、精确峰位、峰宽等信息，能够区分康普顿边沿和假峰 感兴区内寻峰 人工设置感兴趣大小，然后在感兴区内采用简单方法寻峰 重点研究：对感兴区内的弱峰寻峰、重峰的分解 对于一个单峰区，当峰形在峰位两侧比较对称时，可以由峰的FWHM计算峰区的左、右边界道址。峰区的宽度取为3FWHM,FWHM的值可以根据峰位m p由测量系统的FWHM 刻度公式计算。由于峰形对称，左、右边界道和峰位的距离都是 1.5FWHNM mi L =INT(m p -1.5FWHM 0.5) m R=INT(m p1.5FWHM 0.5) 式中m p是峰位，INT的含义是取整数。 对于存在有低能尾部的峰，其峰形函数描述(参见图)。 y m =H EXP[ —(^ —m p r / 2^2 ] m》mp 一 J 2 y m =HEXP[J(2m-2m p J)/2；「] , m< m p_ J 式中H为峰高，mp为峰位，匚是高斯函数的标准偏差，J为接点的道址和峰位之间的距离。在峰位的左侧，有一个接点，其道址为mp-J。在接点的右侧，峰函数是高斯函数。在接点的左侧，峰函数用指数曲线来描述。这时峰区的左、右边界道址为 m L=INT(m p-1.12FWHM 2/ J -0.5J 0.5) m R =INT(m p 1.5FWHM 0.5) 全谱自动寻峰 基于核素库法：能量刻度完成后，根据核素库中的能量计算对应的道址，在各个道址附 近(左右10道附近)采用简单的寻峰方法(导数法) 方法： 根据仪器选择开发 IF函数法/简单比较法(适于寻找强单峰，速度快) 算法设计心得体会 算法设计与分析学习心得 班级：物联网1201 姓名：刘潇学号：29 一、实验内容： 这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。 二、学习掌握： 基本程序描述： 货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解 费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本 思想是对包含具有约束条件的最优化问题的所有可行解的解空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。 Mfc：在下拉列表框中添加内容程序，在下拉列表对应的函数中利用addstring添加需要的内容。首先定义下拉列表框为ccombox型，并定义其属性名，利用addstring函数可以任意添加需要的内容。a排序问题:快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n 2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。b 对话框下拉列表：这个项目简单易懂，轻松实现。 三.疑问与总结： 货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方 【高中必修3数学算法案例总结】高中数学必修1 在高中数学必修3算法教学中，为帮助学生理解案例的数学本质,安排了算法案例一节内容，下面是小编给大家带来的高中必修3数学算法案例总结，希望对你有帮助。 高中必修3数学算法案例 高中数学学习方法 抓好基础是关键 数学习题无非就是数学概念和数学思想的组合应用，弄清数学基本概念、基本定理、基本方法是判断题目类型、知识范围的前提，是正确把握解题方法的依据。只有概念清楚，方法全面，遇到题目时，就能很快的得到解题方法，或者面对一个新的习题，就能联想到我们平时做过的习题的方法，达到迅速解答。弄清基本定理是正确、快速解答习题的前提条件，特别是在立体几何等章节的复习中，对基本定理熟悉和灵活掌握能使习题解答条理清楚、逻辑推理严密。反之，会使解题速度慢，逻辑混乱、叙述不清。 严防题海战术 做习题是为了巩固知识、提高应变能力、思维能力、计算能力。学数学要做一定量的习题，但学数学并不等于做题，在各种考试题中，有相当的习题是靠简单的知识点的堆积，利用公理化知识体系的演绎而就能解决的，这些习题是要通过做一定量的习题达到对解题方法的展移而实现的，但，随着高考的改革，高考已把考查的重点放在创造型、能力型的考查上。因此要精做习题，注意知识的理解和灵活应用，当你做完一道习题后不访自问：本题考查了什么知识点?什么方法?我们从中得到了解题的什么方法?这一类习题中有什么解题的通性?实现问题的完全解决我应用了怎样的解题策略?只有这样才会培养自己的悟性与创造性，开发其创造力。也将在遇到即将来临的期末考试和未来的高考题目中那些综合性强的题目时可以有一个科学的方法解决它。 归纳数学大思维 调研分析总结报告 一、题目：深入理解傅氏与拉氏变换 二、完成人：第六组 杨锦涛PPT讲解及完成两个变换的意义与作用 岳雄完成PPT制作及实例的寻找 易全政完成调研分析总结报告与资料的修改补充 易雪媛完成寻找两个变换之间的联系和区别 尹柯立完成实例的筛选与补充 三、摘要 从时域到频域的分析方法是我们在实际问题解决过程中常用的 方式。对于一个杂乱无章的信号，当从时域方面很难开展的时候我们就会考虑从频域方面来进行相关的研究，以便找到相关的特征。而对于普通的函数通过傅里叶变换便可以得到一些我们所需求的东西，但是有类似于ex这样的衰减函数，我们就需要通过使用拉普拉斯变换，转化到复频域上面找到相关的特征。而本调研报告里面我们就是通过理解傅氏与拉氏变换，探讨两种变化间的区别及联系，以及在实际问题中的应用来加强我们对这两个变换的理解与应用。 四、引言 时域到实频域，这是傅氏变换；时域到复频域，这是拉氏变换。理解这两个变换的区别与联系，在实际应用中来谈论这两种变换的应用。以前在其他们课程里面了解过了很多关于傅里叶的知识，但是对于拉普拉斯却有些陌生，通过此次调研报告，我们将更加深入的理解 这两个变换给我们的学习、生活带来的便利。 五、调研材料分析 一）傅立叶变换 1）定义： 表示能将满足一定条件的某个函数表示成三角函数（正弦和/或 余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。最初傅立叶分析是作为热过程的解析分析的工具被提出的。 2）性质： 3）意义： 傅里叶变换在物理、数论、组合数学、信号处理等方面都有广泛的应用（例如在信号处理里面，傅里叶变换的典型用途是将信号分为幅度分量和频率分量）。 傅里叶变换就是将一个信号分解成无数的正弦波信号，通过合成得到相应的信号。对一个信号做傅里叶变换就可以得到其频域特性（幅度与相位两个方面）。 傅里叶变换简单通俗理解就是把看似杂乱无章的信号考虑成由 一定振幅、相位、频率的基本正弦（余弦）信号组合而成，傅里叶变换的目的就是找出这些基本正弦（余弦）信号中振幅较大（能量较高）信号对应的频率，从而找出杂乱无章的信号中的主要振动频率特点。如减速机故障时，通过傅里叶变换做频谱分析，根据各级齿轮转速、齿数与杂音频谱中振幅大的对比，可以快速判断哪级齿轮损伤。 二）拉普拉斯变换 1）定义： 拉普拉斯变换法是通过积分变换，把已知的时域函数变换为复频域函数，从而把时域微分方程变换为复频域代数方程。 2）性质： 人教版高中数学必修三 知识点梳理 重点题型（常考知识点）巩固练习 算法案例 【学习目标】 1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序； 3.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质； 4.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换. 【要点梳理】 要点一、辗转相除法 也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0； 第二步：若r0=0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1； 第三步：若r1=0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2； …… 依次计算直至r n=0，此时所得到的r n－1即为所求的最大公约数. 用辗转相除法求最大公约数的程序框图为： 程序： INPUT “m=”;m INPUT “n=”;n IF m 大学算法分析与设计复习总结 第1章绪论 考点： 1、算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1.自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码优点：表达能力强，抽象性强，容易理解 3、了解非递归算法的时间复杂性分析。(P13) 要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是： （1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。 （3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。 [例1.4]：求数组最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]; for (i=1; i 通用分支递归式： 使用扩展递归技术求解下列递推关系式（1） （2） Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业2013级计算机应用技术 届次 学生姓名 学号2０１31１0６57 二○一三年一月十五日 算法分析与设计学习总结 本学期通过学习算法分析与设计课程，了解到:算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。 设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。(2)确定性。算法的每一个步骤必须有确切的定义。(3)输入。一个算法有0个或多个输入,作为算法开始执行前的初始值，或初始状态。(4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5)可行性。在有限时间内完成计算过程。 算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。 经典的算法主要有: 1、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。 穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行,其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。 2、迭代算法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组)的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为ｆ(ｘ)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0。 (2)将ｘ0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。 (3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（２）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。 3、递推算法 递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系,从而达到目的。 4、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模 必修3 第一章算法初步全章小结 【知识内容结构】 割圆术 【重点知识梳理与注意事项】 『算法与程序框图』 ◆算法 算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的明确的计算序列，并且这样的步骤或序列能够解决一类问题。 描述算法可以有不同的方式。可以用自然语言和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。 ◆程序框图 ◇概念：通常用一些通用图形符号构成一张图来表示算法，这种图称作程序框图（简称框图）。 ◇常用图形符号： 注意：i）起、止框是任何流程不可少的； ii）输入和输出可用在算法中任何需要输入、输出的位置； iii）算法中间要处理数据或计算，可分别写在不同的处理框内； iv）当算法要求对两个不同的结果进行判断时，判断条件要写在判断框内； v）如果一个框图需要分开来画，要在断开处画上连接点，并标出连接的号码。 ◇画程序框图的规则： （1）使用标准的框图的符号； （2）框图一般按从上到下、从左到右的方向画； （3）除判断框外，其他框图符号只有一个进入点和一个退出点，判断框是具有超过一个退出点的唯一符号； （4）一种判断框是二择一形式的判断，有且仅有两个可能结果；另一种是多分支判断，可能有几种不同的结果； （5）在图形符号内描述的语言要非常简练清楚。 ◆算法的三种基本逻辑结构 ◇顺序结构：描述的是最简单的算法结构，语句与语句之间，框与框之间按从上到下的顺序进行。 例： ◇条件分支结构：是依据指定条件选择执行不同指令的控制结构。 例： ◇循环结构：根据指定条件决定是否重复执行一条或多条指令的控制结构。 这本书是《算法设计与分析》王红梅编著 一共有以下12章，我们学了1、3、4、5、6、7、8、9 分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法 第1章绪论 考点： 1、算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1. 自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2. 流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3. 程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 伪代码优点：表达能力强，抽象性强，容易理解 3、了解非递归算法的时间复杂性分析。(P13) 要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是： （1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。 （3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。 [例1.4]：求数组最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]; for (i=1; i return min; } 问题规模：n 基本语句：a[i] XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： X X X X 大学 目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (8) 题目2 切割木材 (10) 2.1题目描述 (10) 2.2算法文字描述 (10) 2.3算法程序流程 (11) 2.4算法的程序实现代码 (15) 题目3 设计题 (17) 3.1题目描述 (17) 3.2 输入要求 (17) 3.3输出要求 (17) 3.4样例输入 (17) 3.5样例输出 (17) 3.6测试样例输入 (17) 3.7测试样例输出 (18) 3.8算法实现的文字描述 (18) 3.9算法程序流程 (19) 3.10算法的程序实现代码 (20) 算法分析与设计课程总结 (23) 参考文献 (24) 题目1 电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。 输入要求： 输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n<=30，2<=f1 第一章概述 算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 算法的特征： 可终止性：算法必须在有限时间内终止； 正确性：算法必须正确描述问题的求解过程； 可行性：算法必须是可实施的； 算法可以有0个或0个以上的输入； 算法必须有1个或1个以上的输出。 算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束； 程序可以没有输出,而算法则必须有输出； 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的有限性性质。 算法描述方式：自然语言，流程图，伪代码，高级语言。 算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。 一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。 算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。 第二章递归与分治 分治法的基本思想： 求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。 分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。 分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。 使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。） 递归的概念： 习题解析 第1章 1. 解析： 算法主要是指求解问题的方法。计算机中的算法是求解问题的方法在计算机上的实现。 2. 解析： 算法的五大特征是确定性、有穷性、输入、输出和可行性。 3. 解析： 计算的算法，其中n是正整数。可以取循环变量i的值从1开始，算i的平方，取平方值最接近且小于或者等于n的i即可。 4. 解析： 可以使用反证法，设i=gcd(m, n)=gcd(n, m mod n)，则设m=a*i，n=b*i，且a与b互质，这时m mod n=（a-x*b）*i，只需要证明b和a-x*b互质，假设二者不互质，可以推出a与b不互质，因此可以得到证明。 5. 解析： 自然语言描述：十进制整数转换为二进制整数采用“除2取余，逆序排列”法。 具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。 流程图：如图*.1 图*.1 十进制整数转换成二进制整数流程图 6. 解析： a.如果线性表是数组，则可以进行随机查找。由于有序，因此可以进行折半查找，这样可以在最少的比较次数下完成查找。 b.如果线性表是链表，虽然有序，则只能进行顺序查找，从链表头部开始进行比较，当发现当前节点的值大于待查找元素值，则查找失败。 7. 解析： 本题主要是举例让大家了解算法的精确性。过程中不能有含糊不清或者二义性的步骤。大家根据可行的方式总结一下阅读一本书的过程即可。 8. 解析： 数据结构中介绍的字典是一种抽象数据结构，由一组键值对组成，各个键值对的键各不相同，程序可以将新的键值对添加到字典中，或者基于键进行查找、更新或删除等操作。由于本题已知元素唯一，因此大家可以据此建立一个自己的字典结构。实现字典的方法有很多种： ?最简单的就是使用链表或数组，但是这种方式只适用于元素个数不多的情况下； ?要兼顾高效和简单性，可以使用哈希表； ?如果追求更为稳定的性能特征，并且希望高效地实现排序操作的话，则可以使用更为复杂的平衡树。 算法分析与设计习题集 基础篇 1、算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？ 2、算法的时间复杂度指的是什么？如何表示？ 3、算法的空间复杂度指的是什么？如何表示？ 4、设某一函数定义如下： 编写一个递归函数计算给定x的M（x）的值。 本函数是一个递归函数，其递归出口是： M（x）= x-10x>100 递归体是： M（M（x+11））x ≤100 实现本题功能的递归函数如下： intm ( intx ) { int y; if ( x>100 )return(x-10 ); else { y =m(x+11) ; return (m (y )); } } 5、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相 同的元素。 本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下： voiddel ( seqlist*a ) { inti=0, j; while ( i ①计算结点总数 int CountNode(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&rooot->rchild==Null) return(1); else { num1=CountNode(root->lchild); num2=CountNode(root->rchild); return(num1+num2+1); } } ②计算叶子总数 int CountLeafs(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&root->rchild==Null) return(1); else { num1=CountLeafs(root->lchild); num2=CountLeafs(root->rchild); return(num1+num2); } } 分治术 7、有金币15枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假 的金币找出来，试设计一种算法（方案），使在最坏情况下用天平的次数最少。 8、利用分治策略，在n个不同元素中找出第k个最小元素。 9、设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 （1）每个选手必须与其它n-1选手各赛一次； （2）每个选手一天只能赛一次。 10、已知序列{503，87，512，61，908，170，897，275，652，462}，写一个自底向上的 归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。 void Merge(ElemType *r，ElemType *rf，int u，int v，int t) { f or(i=u，j=v，k=u；i算法分析与设计复习题及参考答案
算法分析与设计总结
算法设计与分析复习题目及答案
大学算法分析与设计复习总结
【精品】高中数学 必修3_算法案例_知识点讲解+巩固练习(含答案)_提高
多道γ能谱分析软件中寻峰算法比较总结
算法设计心得体会(2)
【高中必修3数学算法案例总结】高中数学必修1
算法设计与分析调研分析总结
人教版高中数学【必修三】[知识点整理及重点题型梳理]_算法案例_基础
大学算法分析与设计复习总结
算法设计与分析基础课后习题答案
算法设计与分析学习总结
算法初步全章总结
算法设计与分析_总结0
算法分析资料报告与设计-课程设计资料报告材料
算法分析与设计知识点总结
算法分析及设计及案例习题解析
算法分析与设计习题集
相关主题
文本预览