翻译英文原文的LEACH算法的详细信息
LEACH的运作以“轮”来实现，每一轮开始是簇头的建立阶段，其次传输数据到基站的稳态阶段。为了尽量减少开销，稳态阶段比簇建立阶段时间长。
5.1簇选举阶段
簇头选举初始阶段，每个节点根据所建议网络簇头的百分比（事先确定）和节点已经成为簇头的次数来确定自己是否当选为簇头。每个节点产生一个0-1的随机数字，如果该数字小于阈值T（N），节点成为当前轮的簇头。阈值
T（n）=?
?
?
?
?
∈-
其它
,0
,
)]
/1
mod(
[*
1
G
n
p
r
p
p
其中，P为预期的簇头百分比（例如，p= 0.5），r为当前轮数，G是最近1/p轮里没有成为簇头的节点的集合。使用这个阀值，每个节点会在1/p轮的某一轮成为簇头。在0轮（r = 0），每个节点都有一个成为簇头的概率P。当选为簇头的节点不能在未来的1/ P轮当选为簇头。因此，只有较少的节点有资格当选为簇头节点，剩余节点成为簇头的概率必然增加。1/p-1回合后对任意还没当选为簇头的节点T（n）=1，可见，1/ P的回合后，所有节点都再次有资格成为簇头。以后的工作中，我们会考虑到非均匀能量节点的以能量为基础的阀值。在这种情况下，我们假设所有节点具有相同初始数量的能量，每个簇头也消耗大约相同的能量。非簇头节点必须保持他们的接收器在此选举阶段听到所有的簇头节点的广告。这一阶段完成后，每个非簇头节点决定在本轮中加入哪一个簇头节点。这一决定是基于对广告的接收信号强度。假设是对称的传播信道，收到发送的广告信号强度最大的簇头就是要加入的簇头，与其通信需要的能量最小。稳定之后表示簇头的随机选举完成了。
5.2簇建立阶段
在每个节点已决定它属于哪个簇之后，它必须告知簇头节点，它将成为该簇的成员节点。每个节点再次使用CSMA MAC协议发送这个信息反馈给簇头。在这个阶段，所有的簇头节点必须保持他们的接收器打开。
5.3 时间表的创建
簇头节点收到所有想加入该簇的节点的消息。基于这个簇的节点的数量，簇头节点创建一个TDMA时间表告诉所有节点什么时候能开始传输数据。这个时间表广播给所有该簇的成员节点。
5.4 数据传输
一旦簇创建和TDMA的时间表是固定的，数据传输可以开始了。假设节点有数据要发送，他们在分配给它们的传输时间内发送给簇头。这种传输使用少量的能源（选择基于收到簇头广告的强度）。每个非簇头节点的无线电可以关闭，直到分配给节点的传输时间到来，
从而减少在这些节点的能量消耗。簇头节点必须保持其接收机接收到簇内所有节点的所有数据。当所有的数据已经收到，簇头节点进行数据融合。例如，如果簇头收到数据音频或地震信号，簇头节点将这些收到的单个信号融合为一个复合信号。然后将这种复合信号发送到基站。但是由于基站远，这种传输是一种高能量的传输。以上是LEACH协议网络的稳定运行状态。经过一定时间后，下一轮开始，每个节点决定这轮自己是否能成为簇头，然后广播这一消息，如5.1节所述。
5.5。多个簇
前面的讨论中介绍了如何在单个簇头内部之间进行通信的问题。然而，无线电本质上是一种广播媒介。正因为如此，在一个簇中的传输会影响（因此降低）附近的簇通信。例如，图13显示了一个电台的通信范围。节点A的传输的目的节点是B，这会干扰任何传输到节点C的通信，为了减少这种类型的干扰，每个集群通信使用不同的CDMA码。因此，当一个节点决定成为簇头，从扩频码的列表中随机选择。它通知在簇的所有节点传输，使用这种扩频码。簇头会过滤所有收到的能源使用扩频码。因此邻近簇的无线电信号将被过滤掉，而不会干扰临近簇的数据传输。即使有一个中央控制中心，可以执行必要的算法，高效的信道分配也是一个棘手的问题。使用CDMA的代码，虽然不一定是带宽最有效的解决方案，但解决了多个分布式的方式接入的问题。
5.6。层次聚类
本文中所描述的LEACH版本延伸，形成层次集群。在这种情况下，在簇头节点的沟通与“超级簇”节点，并依此类推，直至层次结构的顶层，此时，数据将被发送到基站。对于较大的网络，这个层次可以节省巨大的能源量。在今后的研究中，我们将探讨细节不使用任何支持的情况下实施该协议从基站，通过模拟来确定可以节省多少能源。
专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日
48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n AAC解码算法原理详解 原作者：龙帅 (loppp138@https://www.doczj.com/doc/f55377237.html,) 此文章为便携式多媒体技术中心提供，未经站长授权，严禁转载，但欢迎链接到此地址。 本文详细介绍了符合ISO/IEC 13818-7(MPEG2 AAC audio codec) , ISO/IEC 14496-3(MPEG4 Audio Codec AAC Low Complexity)进行压缩的的AAC音频的解码算法。 1、程序系统结构 下面是AAC解码流程图： AAC解码流程图 在主控模块开始运行后，主控模块将AAC比特流的一部分放入输入缓冲区，通过查找同步字得到一帧的起始，找到后，根据ISO/IEC 13818-7所述的语法开始进行Noisless Decoding(无噪解码)，无噪解码实际上就是哈夫曼解码，通过反量化(Dequantize)、联合立体声（Joint Stereo），知觉噪声替换（PNS）,瞬时噪声整形（TNS），反离散余弦变换（IMDCT），频段复制（SBR）这几个模块之后，得出左右声道的PCM码流，再由主控模块将其放入输出缓冲区输出到声音播放设备。 2. 主控模块 主控模块的主要任务是操作输入输出缓冲区，调用其它各模块协同工作。其中，输入输出缓冲区均由DSP控制模块提供接口。输出缓冲区中将存放的数据为解码出来的PCM数据，代表了声音的振幅。它由一块固定长度的缓冲区构成，通过调用DSP控制模块的接口函数，得到头指针，在完成输出缓冲区的填充后，调用中断处理输出至I2S接口所连接的音频ADC芯片（立体声音频DAC和DirectDrive 耳机放大器）输出模拟声音。 3. 同步及元素解码 同步及元素解码模块主要用于找出格式信息，并进行头信息解码，以及对元素信息进行解码。这些解码的结果用于后续的无噪解码和尺度因子解码模块。 AAC的音频文件格式有以下两种： ADIF：Audio Data Interchange Format 音频数据交换格式。这种格式的特征是可以确定的找到这个音频数据的开始，不需进行在音频数据流中间开始的解码，即它的解码必须在明确定义的开始处进行。故这种格式常用在磁盘文件中。 ADTS：Audio Data Transport Stream 音频数据传输流。这种格式的特征是它是一个有同步字的比特流，解码可以在这个流中任何位置开始。它的特征类似于mp3数据流格式。 AAC的ADIF格式见下图： 3.1 ADIF的组织结构 AAC的ADTS的一般格式见下图： 3.2 ADTS的组织结构 图中表示出了ADTS一帧的简明结构，其两边的空白矩形表示一帧前后的数据。ADIF和ADTS的header是不同的。它们分别如下所示： 仿真一：在100*100的区域内随机生成100个节点 （matlab仿真代码： clear; xm=100;%x轴范围 ym=100;%y轴范围 sink.x=0.5*xm;%基站x轴 50 sink.y=0.5*ym;%基站y轴 50 n=100; E0=0.02; for i=1:1:n S(i).xd=rand(1,1)*xm; S(i).yd=rand(1,1)*ym; S(i).G=0;%每一周期结束此变量为0 S(i).E=E0;%设置初始能量为E0 S(i).type='N';%节点类型为普通 plot(S(i).xd,S(i).yd,'o'); hold on; end %设置SINK节点的坐标 S(n+1).xd=sink.x; S(n+1).yd=sink.y; plot(S(n+1).xd,S(n+1).yd,'*');%绘制基站节点仿真结果图片：（‘O’代表随机散布的节点，‘*’代表SINK节点） 仿真二：LEACH 分簇效果图（matlab 代码见附件） 仿真结果：(p=0.1) 1、簇头个数14. 0102030405060708090100 2、簇头个数：11 3、簇头个数：12 0102030405060708090100 4、簇头个数：10 10 20 30 40 50 60 70 80 90 100 (p=0.05) 1、簇头=6 10 20 30 40 50 60 70 80 90 100 2、簇头=7 3、簇头=12 4、簇头=8 10 20 30 40 50 60 70 80 90 100 5 、 010203040 5060708090 100 102030405060708090100x y LEACH 分簇算法成簇效果图 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i LEACH算法的学习摘要 一、LEACH的定义 LEACH:低功耗自适应路由算法 二、LEACH算法的工作流程 1.总述 LEACH路由协议主要分为两个阶段：即簇建立阶段(setup phase)和稳定运行阶段(ready phase)。簇建立阶段和稳定运行阶段所持续的时间总和为一轮(round)。为减少协议开销，稳定运行阶段的持续时间要长于簇建立阶段。 2.簇建立阶段 在簇建立阶段，传感器节点随机生成一个0，1之间的随机数，并且与阈值T(n)做比较，如果小于该阈值，则该节点就会当选为簇头。T(n)按照下列公式计算： 式中：P为节点成为簇头节点的百分数，r为当前轮数，G为在最近的1/p 轮中未当选簇头的节点集合。簇头节点选定后，广播自己成为簇头的消息，节点根据接收到的消息的强度决定加入哪个簇，并告知相应的簇头，完成簇的建立过程。然后，簇头节点采用TDMA的方式，为簇内成员分配传送数据的时隙。 3.稳定阶段 在稳定阶段，传感器节点将采集的数据传送到簇头节点。簇头节点对采集的数据进行数据融合后再将信息传送给汇聚节点，汇聚节点将数据传送给监控中心来进行数据的处理。稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一轮的簇重建，不断循环。 三、LEACH算法的优点 1.LEACH算法属于分层路由协议，节点之间反应速度快，簇头进行轮转性选举，能够保证无线传感器网络中各个节点能量均衡的消耗，从而有效地延长无线传感网络的生命周期，低功耗的目的。 2.各个节点之间不再是无序的建立通信路由，数据信息的传递具有一定的规则，普通节点只能向上一级簇头传送数据信息，一级粗托只能向二级簇头传送数据信息。很大程度上节省了能量，减少了能量的浪费。 3.相近的节点之间接收到的数据信息有可能相同或相近，这就需要簇头进行必要的数据融合。更好的提升了能量的利用率。 4.每个簇头都要进行数据融合，因为每个簇头接收到的都是局部数据信息，所以数据信息都是比较相关，给数据的融合带来了较快的速度。 5.LEACH路由算法采用TDMA和CDMA的MAC层机制进行各个节点间的数据信息的传递，保证了簇内各个节点有序的跟簇头节点的传递数据，也保证了簇头Sink节点进行有序的信息传递，从而避免了簇内和簇间的相互通信冲突。 6.LEACH路由协议感应外界的环境信息，是周期性的进行检测，各个周期之间不间断地进行。LEACH协议非常适合长期、连续性的进行环境的检测。为野外长时间、不间断地检测提供了保证。 7.有些检测不需要随时获取检测的数据信息，只是当环境中有意外、异常情况发生时，才进行必要的检测盒数据信息的传递。这种不需要周期性的信息传递，减少了无线传感器网络的能量消耗，提高了网络的生命周期。 8.每进行完一轮数据信息的传送，网络进行重新的簇头选举，保证了各个节点之间能量的均衡消耗，提高了能量的利用率。 四、LEACH算法的缺点 1.LEACH路由协议算法中没有说明簇头节点如何进行选举分配，才能保证网络数 智能车P I D算法实现 原理讲解 为了实现PID控制所需要的等间隔采样，我们使用了一个定时中断，每2ms进行一次数据采样和PID计算。与此并行，系统中还设计了一个转速脉冲检测中断，从而实现了转速检测。为了调试的需要，程序中还在main{}函数中加入了相关的调试代码，这部分代码有最低的优先级，可以在保证不影响控制策略的情况下实现发送调试数据等功能。检测环节对整个控制系统的质量起到至关重要的作用 4.3.2 PID控制调整速度 本系统采用的是增量式数字PID控制，通过每一控制周期（10ms）读入脉冲数间接测得小车当前转速vi_FeedBack，将vi_FeedBack与模糊推理得到的小车期望速度vi_Ref比较，由以下公式求得速度偏差error1与速度偏差率d_error。 error1 = vi_Ref– vi_FeedBack; （公式3） d_error = error1 –vi_PreError; （公式4）公式4中, vi_PreError为上次的速度偏差。考虑到控制周期较长，假设按2.5m/s的平均速度计算，则一个控制周期小车大概可以跑过2.5cm，如果按这种周期用上述PID调节速度，则会导致加速减速均过长的后果，严重的影响小车的快速性和稳定性。为了解决这个问题，可以在PID调速控制中加入BANG-BANG控制思想：根据error1的大小，如果正大，则正转给全额占空比；如果负大，则自由停车或给一个反转占空比；否则就采用PID计算的占空比。 PID控制算法 为了使赛车平滑得保持在黑线中央，即使赛车的偏移量平滑地保持在0，实用了PID控制算法。 P为比例参数，D为微分参数。基准值为0，PID输入为水平偏移量X0，PID输出为转角，转角方向：向左转为正，向右转为负。 P参数在智能车控制器中表示水平偏差量的权，D参数在智能车控制器中表示水平偏差速度的权。 水平偏差量直接反映了赛车偏离黑线的程度，例如赛车偏向黑线的左边越厉害，则赛车的右转角度将越大。水平偏差量，是PID控制器的P部分。 水平偏差速度则直接反映了赛车的运动倾向，因为有了赛车的水平偏差速度，对赛车的掌握，将更加精确。例如赛车偏向黑线左边，然而它的运动方向是向右的，那么，他的转角将比向左运动时的转角要小，因为，我知道赛车已经开始朝正确的方向调整了。水平偏差速度，是PID控制器的D部分。 通过两个相隔一定采样时间的水平偏差量的差，来得到赛车的水平偏差速度。然而，这个时间间隔多少比较合适呢？ 无线传感器网络LEACH算法的综合改进 陈楠，徐塞虹 北京邮电大学计算机科学与技术学院，北京（100876） E-mail：chennan6062@https://www.doczj.com/doc/f55377237.html, 摘要：本文通过研究无线传感器网络的层次型路由协议LEACH算法，指出了其存在的一些缺点，并对其某些改进算法进行深入研究，在此基础上进一步改进，吸取已有算法的优点，弥补其中的不足，提出了一种新的分簇算法及簇的维护算法。 关键词：无线传感器网络，层次型路由协议，LEACH算法，改进 中图分类号：TP393 1.引言 传感器技术、通信技术和计算机技术是现代信息技术的三大支柱，它们分别完成对被 测量对象的信息提取、信息传输及信息处理。将这三种技术融合在一起的无线传感器网络技术给人们生活的各个领域带来了极大的影响。作为一种全新的技术，无线传感器网络给科技工作者提出了很多具有挑战性的课题，其中路由协议就是热点之一，传统网络的路由协议远远不能满足无线传感器网络的特点和要求，因此，该领域具有很大的研究价值[1]。本论文在已经提出来的分层次路由协议的基础上进行进一步改进，从而使网络性能又进一步的提升。 2.研究背景 无线传感器网络是由大量功率低、体积小、价格便宜的传感器节点组成的，这些节点实时监测、感知和采集网络分布区域内的各种环境或者被监测对象等诸多用户所感兴趣的信息，并对这些信息进行分布式处理，随后传递给用户，使用户随时随地都可以获取所需的信息。由于传感器网络所具有的特点，其应用前景十分广泛。 但是由于无线传感器网络这些特点的存在，导致节点能量资源、计算能力和带宽等资源都非常有限，尤其是其有限的能量直接影响传感器网络的生命周期以及网络的信息质量。因此，设计有效的策略，降低节点能源损耗，提高网络生命周期成为无线传感器网络的核心问题。 影响节点能源损耗的因素有很多，其中最重要的就是路由协议以，但是传统的那些路由协议应用于无线传感器网络中在某些方面存在一定的缺陷，所以基于传统路由协议，W.R Heinzelman等人提出了低功耗自适应集群型分层路由协议（Low Energy Adaptive Clustering Hierarchy Protocol），LEACH协议[2]是第一个在无线传感器网络中提出的层次式路由协议，其后的大部分层次式路由协议都是在它的基础上发展而来的。该算法主要是通过随机选择簇头，平均分担中继通信业务来实现能量消耗的减少，与一般的平面多跳路由协议和静态成簇算法相比，LEACH可以将网络的生命周期延长15%。 3.LEACH算法概述 LEACH（Low energy adaptive clustering hierarchy）是一种以最小化传感器网络能量损耗为目标的分层式协议，它既可以作为一种传感器网络的基本路由协议，也可以作为传感器网络的拓扑控制算法，因为协议在形成分层式拓扑结构的同时，也确定了簇首，决定了网络的路由。 leach_mit结构图 从wireless.tcl文件中分析leach的具体流程 在wireless.tcl文件中首先初始化了很多无限仿真的配置。引用了一些外部脚本——source tcl/lib/ns-mobilenode.tcl（主要是包含移动节点类Node/MobileNode的一些otcl类函数的定义）、source tcl/lib/ns-cmutrace.tcl（trace文件的tcl脚本）、 source tcl/mobility/$opt(rp).tcl（将几种不同的协议的具体应用的外部脚本引用，$opt(rp)是协议名称）。当一些变量初始化过后，通过 elseif { [string compare $opt(rp) "leach"] == 0} { for {set i 0} {$i < $opt(nn) } {incr i} { leach-create-mobile-node $i 建立我们仿真的节点，最主要的函数是leach-create-mobile-node（这个函数的定义在uamps.tcl中） 分析uamps.tcl中是如何定义节点的？？？ 在uamps.tcl中初始化了bsnode的应用类型（Application/BSApp）、定义了二个能量传输模型（自由信道和多径衰落、Efriss_amp和Etwo_ray_amp）和很多参数。而真正创建节点是在函数leach-create-mobile-node中。而这个函数中调用了uamps.tcl中的sens_init，这个函数的功能是清除上一次模拟时留下的trace文件。在创建节点时候，sens_init函数调用一次。leach-create-mobile-node函数解释如下： 1、节点定义： if {$id != $opt(nn_)} { puts -nonewline "$id " set node_($id) [new MobileNode/ResourceAwareNode] #将前opt(nn_)-1个点定义为一般节点 } else { puts "($opt(nn_) == BS)" set node_($id) [new MobileNode/ResourceAwareNode $BS_NODE] #将第 opt(nn_)个节点定义为最终的sink节点 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; 《算法与程序设计》导学 一、编程的步骤： 启动VB——标准EXE——对象——属性——代码——调试——保存——生成EXE 1、VB窗口组成：控件工具箱、对象窗口、工程窗口、属性窗口、代码窗口 2、对象：标签（Label）、文本框（text）、命令按钮（command） 计时器（timer）、简单图形（shape） 3、属性：caption(标题) 4、保存：窗体文件(.frm)、工程文件(.vbp) 二、算法的特征： 1、有穷性 2、确定性 3、能行性 4、有0个或多个输入 5、有1个或多个输出 三、算法的表示： 1、自然语言 2、流程图 （1）标准：GB1526—89、ISO5807-1985 （2）常用符号： 3、计算机语言（伪代码） 四、算法的三种基本结构： 1、顺序模式： 2、选择模式： 3、循环模式： 五、四种基本算法： 1、枚举算法：（循环模式的应用） （1）、把问题所有可能的解全部列举出来，在列举的过程式中根据条件进行判断，满足条件的则是问题真正的解，不满足的去掉。 （2）、包装问题的分析及流程图： 2、解析算法：（公式求解的过程） 3、排序： （1）、冒泡排序：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。 （2）、选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。 冒泡排序、选择排序都是比较排序。 4、查找： （1）、顺序查找：序列的最头走到最尾，挨个和目标进行比较，如果找到了，就停止遍历，如果走完了，还没找到，那么表示失败了 （2）、对分查找：对分查找是效率很高的查找方法，但被查找的数据必须是有序的。A，首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。B，在新确定的范围内，继续按上述方法进行查找，直到获得最终结果 六、VB基本数据类型： * https://www.doczj.com/doc/f55377237.html, * * Created on: 2011-4-17 * Author: syj */ #include 算法是，对特定问题求解方法和步骤的一种描述，它是有限指令的有限序列，其中每个指令表示一个或多个操作。 算法与程序的比较 ?算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。 ?程序是用某种程序设计语言对算法的具体实现。 ?程序 = 数据结构 + 算法 算法的特性 一个算法必须具备以下五个重要特性： ?有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ?确定性算法中每一条指令必须有确切的含义，没有二义性，在任何条件下只有唯一的一条执行路径，即对相同的输入只能得到相同的输出。 ?可行性算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 ?输入一个算法有零个或多个输入 ?输出一个算法有一个或对个输出 算法设计有正确性（Correctness）、可读性（Readability）、健壮性（Robustness）、高效性（Efficiency）的基本要求。 一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。 算法效率分析 算法效率主要从一下两个方面来考虑： 1.时间效率：指的是算法所耗费的时间； 2.空间效率：指的是算法执行过程中所耗费的存储空间。 时间效率和空间效率有时候是矛盾的。 时间效率分析 一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行简单操作次数的乘积。 算法运行时间 = 一个简单操作所需的时间 x 简单操作次数， 也就是算法中每条语句的执行时间之和 每条语句执行一次所需的时间，一般是随机器而异的，取决于机器的指令性能、速度以及编译的代码质量，是由机器本身软硬件环境决定的，它与算法无关。所以，可以假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可以转化为讨论改算法中所有语句的执行次数了。 例如：两个n x n矩阵相乘的算法课描述为： for(i=1;i<=n;i++) //n+1次 for(j=1;j<=n;j++) //n(n+1)次 { c[i][j]=0; //n*n次 for(k=0;k Dijkstra算法原理详细讲解 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等） 算法执行步骤如下表： Dijkstra算法的完整实现版本之算法的源代码 样例图: 输入格式: 输出格式: 输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起 始点 比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径 Dijkstra算法的完整实现版本，算法的源代码 /* Dijkstra.c Copyright (c) 2002, 2006 by ctu_85 All Rights Reserved. */ #include "stdio.h" #include "malloc.h" #define maxium 32767 #define maxver 9 /*defines the max number of vertexs which the programm can handle*/ #define OK 1 struct Point { char vertex[3]; struct Link *work; struct Point *next; }; struct Link { char vertex[3]; int value; struct Link *next; }; struct Table /*the workbannch of the algorithm*/ { int cost; int Known; char vertex[3]; 目录 一、Leach协议与NS的关系 (2) 二、算法设计思想 (3) 三、簇头建立算法流程图 (5) 四、难点解决 (6) 五、算法运行结果分析 (9) 参考文献 (9) 一、Leach协议与NS的关系 为了实现leach 协议，对ns进行扩展。在ns中增加了一个事件驱动模拟器支持模拟无线传感器网络协议。这些扩展包括MAC协议，用于计算和交互的能量分配模型和leach协议的体系结构。 网络拓扑结构可以通过简单的Nodes, Links, Agents和Applications 描述。Nodes相当于网络中的终端主机，Links 是用于Nodes交互的连接器, Agent 用来实现不同网络协议，是支持分组产生和丢弃的节点。Applications用来产生数据和实现不同的应用函数。一旦网络拓扑结构建立起来后，模拟通过启动节点上的Applications运行。 为了在ns中支持无线传感器网络，在ns中增加了mobile nodes, MAC协议和信道传播模型Channel 。 Applications类的头文件用Tcl语言写的，节点中的其他函数功能用C++语言写成的。 数据包的发送过程： Applications创建数据包（data packets）,然后发送给Agent. Agent执行协议栈中运输层和网络层的功能，将数据包发送给CMUTrace,。CMUTrace将packets 的统计数据写到trace 文件，然后将packets发至Connector。Connector将数据包传送给用于数据链路处理的链路层(LL).经过一小段时间的延迟后，数据包由LL 发送给Queue缓冲队列。如果是还没有传送过的数据包，Queue将以队列进行存储。然后Queue将数据包出队列，发送到MAC层。然后开始运行MAC（媒体访问控制）协议。最终，packets被发送到网络接口层(Network Interface),网络接口层将packets加上正确的传输能量，然后将packets发送到Channel. Channel将packets进行拷贝，并发往连接信道的每一个节点。 发送过程可参考如下图1 数据包的接收过程： 数据包被节点的网络接口接收，并被向上传送至MAC层，Link-Layer, 第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的 输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 1）.数据：运算序列中作为运算对象和结果的数据?2）.运算：运算序列中的各种运算：赋值,算术和逻辑运算 3）.控制和转移：运算序列中的控制和转移. 算法分类 从解法上：数值型算法：算法中的基本运算为算术运算；非数值型算法：算法中的基本运算为逻辑运算. 从处理方式上：串行算法：串行计算机上执行的算法；并行算法：并行计算机上执行的算法 算法的五个重要的特性 （1）有穷性: 在有穷步之后结束。 （2）确定性: 无二义性。 （3）可行性: 可通过基本运算有限次执行来实现。 （4）有输入 f表示存在数据处理 （5） 伪代码 有输出A 程序设计语言（PDL），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言 （例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1）使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2）以自然语言的自由语法描述了处理过程；3）数据声明应该既包括简单的也包括复杂的数据 结构；4）使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n阶方阵的相加C=A+B的算法如下，分析其时间复杂度。 #define MAX 20 //定义最大的方阶 void matrixadd (int n,int A[MAX][MAX], int B[MAX][MAX],i nt C[MAX][MAX]) { int i,j; for (i=0;i LEACH协议的改进算法 夏北浩 （湖南大学信息科学与工程学院长沙410082） 摘要：首先介绍了LEACH协议的工作原理，性能分析以及不足。之后介绍了LEACH的改进算法。 关键词：无线传感器网络,LEACH协议,改进算法,能量消耗 Improved algorithm of LEACH Xia Beihao (The College of Information Science and Engineering, Hunan University 410082) Abstract: This paper firstly introduce the content of the working principle of LEACH , the analysis of performance and discourages,following the introduction of the improved algorithm LEACH . Key: wireless sensor networks, LEACH protocol,Improved Algorithm,Energy consumption 1 引言 近年来，由于无线技术、计算机技术与传感器技术的迅猛发展和快速融合，无线传感器网络应运而生。无线传感器网络技术作为一种新型网络技术受到研究者的普遍重视和广泛研究。但传感器网络也有一些固定的缺点：能量利用率低、生存周期短、抗干扰能力差。通过良好的算法不仅可以减少传感器节点的能耗，还可以降低通信干扰，提高mac协议和路由协议的效率。因此，提出一个高效稳定合理的算法便成为迫切需要解决的问题。 2 LEACH协议的介绍 2.1 LEACH协议 LEACH是WSN中第一个基于分簇的路由算法，它将网络中的节点分为簇头节点和簇内节点。由于簇头节点需要协调簇内节点的工作，负责数据的融合和转发，能量消耗相对较大，所以LEACH采用周期性地随机选择簇头节点以均衡网络中节点能量消耗。从而达到延长网络生命周期目的。LEACH协议以“轮”作为运 算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业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、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模AAC解码算法原理详解
LEACH算法仿真结果
算法分析与设计习题集整理
LEACH算法的学习摘要
智能车PID 算法实现原理讲解
无线传感器网络LEACH算法的综合改进
Leach算法分析
数据结构与算法分析习题与参考答案
算法理论详细讲解
LEACH算法源代码
算法与算法分析
Dijkstra算法原理详细讲解
Leach代码分析
算法分析与设计
LEACH算法的改进
算法设计与分析学习总结
相关主题
文本预览