第一篇：基于DSP的FFT算法实现概要
基于DSP的FFT算法实现
Realization of FFT algorithm based on DSP 艾红,常青青,邓大伟
AI Hong, CHANG Qing-qing, DENG Da-wei(北京信息科技大学自动化学院,北京 100192 摘 要:快速傅立叶变换(FFT是将信号从时域变换到频域的一种方法,广泛运用于各种信号分析领域。文中介绍了FFT算法的原理,构建了基于TMS320F2812的硬件平台,阐述了FFT算法的硬件与软件实现。利用TMS320F2812内部的ADC模块与事件管理器的定时器实现信号的实时采集,不需要使用专门的A/D转换芯片。软件上以128点FFT运算为例,在CCS环境下利用C 语言编程实现了FFT算法,程序充分利用蝶式权的周期性及FFT运算中第一级蝶式权值固定为1的特点,使得运算量与复杂度大大减小。运行结果表明TMS320F2812能够快速高效地完成FFT运算。
关键词:数字信号处理;快速傅立叶变换;信号采集
中图分类号:TP273
文献标识码:B
文章编号:1009-0134(201201(上-0017-03 Doi: 10.3969/j.issn.1009-0134.2012.01(上.07 0 引言
快速傅立叶变换(FFT在雷达、通信、电子对抗和电力系统等领域有广泛应用,特别是在电力系统的谐波检测中,FFT几乎是唯一可行的检测方法。通常提高FFT运算速度有两种途径:改进FFT 算法本身和改进运算工具。现阶段提高FFT算法本身非常困难,一般方法致力于改进运算工具。数字信号处理器DSP 是一种可编程的
高性能处理器。文中充分利用TMS320F2812 DSP强大的数据处理能力,实现了FFT运算,并提高了运算速度。系统硬件结构
系统设计以TMS320F2812处理器为核心,辅以外围电路构成。DSP负责模拟输入信号数据采集以及FFT算法实现。外围电路包括电源转换电路,时钟电路,复位电路以及外部RAM等。系统的硬件整体结构如图1所示[1]。对信号进行FFT变换,首先要对模拟信号采样将其转换为数字信号。输入的连续模拟信号经信号调理电路后输出到DSP的ADC模拟输入通道,经过ADC数据采集,模数转换的结果存放于ADC结果寄存器中。信号调理电路主要是为了信号的抗混叠滤波以及电路阻抗的匹配。信号调理电路对输入信号进行调理处理,包括信号的滤波、跟随输出以及信号的稳定。DSP 对采集的数字信号进行FFT运算处理,同时对运算结果进行相应的数据显示和数据存储。
图1 系统的硬件整体结构图 2 FFT算法原理
FFT是离散傅立叶变换(DFT的快速运算,是数字信号处理的基础。因为有些信号在时域很难看出特性,使用FFT将其变换到频域,就会很容易看出其特性。DFT算法的基本公式为[3]:
式中x(n表示时域信号,X(k表示频域信号,为运算蝶式权。
FFT算法是不断地把长序列的DFT分解成几个短序列的DFT,并利用的周期性和对称性减少DFT的运算次数。设序列x(n的长度为N(N=2M,M 为任意正整数,按n的奇偶把x(n分解成两个N/2 收稿日期:2011-08-12 基金项目:北京市教育委员会科技计划面上项目(KM200910772008 作者简介:艾红(1962-,女,四川重庆人,副教授,硕士,研究方向为检测技术与自动化装置。
点的子序列: 若
:
则
:
由此可见,若将任何一偶数点序列按下标的奇 偶性分成两个子序列,则原序列的DFT可由两子序 列的DFT线性组合得到。运算流图如图2所示。图2 运算流图
图3 蝶式运算流图
其中,A和B的距离称为翅尖距。这种方法和 直接进行DFT计算相比较,运算量减少一半。按 照这种分解运算的思想,将X1(k和X2(k继续向下 分解,直到最后变为一点序列,此时的运算量大 大减小。以8点序列X(n的FFT运算为例: 第一次分解: 第二次分解: 蝶式运算流图如图3所示。比较FFT和DFT的 运算量。假设序列点数为N,且有N=2L,当使用FFT 进行运算时,计算过程中只有蝶式运算,它的复
数乘法运算量为,复数加法运算量为;直接进行DFT运算时,复数乘
法和复数加法的运算量均为N2。由此可见,FFT运 算确实大大减小了DFT的运算量。由图3可以看出,若想得到顺序正确的频域序 列X(k,必须对时域序列进行重新排序。这里先 说明比特逆序的概念:设存储地址m,其二进制数(设m=2L为m=(m1m2m3,若有=(m3m2m1, 则称为m的L位比特逆序列。若将图4中的输入时 域序列下标转换成二进制,依次是: 000,100,010,110,001,101,011,111;而原时域序列下 标转换成二进制依次是:000,001,010,011,100,101, 110,111,将两者对比可发现,输入时域序列下标 就是原时域序列下标的比特逆序。所以FFT蝶式运 算的第一步就是对时域序列进行比特排序。3 系统软件实现以及结果分析 3.1 FFT程序实现
FFT算法主要包括比特逆序、蝶式权值的计 算、各级的蝶式运算以及FFT序列的输出。程序中
涉及到复数的运算,由于计算机无法处理复数, 故而将复数拆为实部和虚部,只需计算出实部和 虚部的数值即可。程序设计将蝶式权w[i]拆分为实 部pr[i]和虚部pi[i],将参与各级蝶式运算的序列拆 分为实部fr和虚部fi。复数进行加法运算时需将两 复数的实部与实部、虚部与虚部对应相加即可, 例如w[i]+w[i+1],所得的和的实部为pr[i]+pr[i+1], 虚部为pi[i]+pi[i+1];而复数的乘法,相对来说有 些复杂,不再是简单的虚部和实部各自相乘,例如 w[i]×w,所得的乘积的实部为pr[i]×pr+pi[i]×pi, 虚部为:(pr[i]+pi[i]×(pr+pi-(pr[i]×pr+pi[i]×pi。该程序执行的是128个点的FFT运算,共有7级蝶式 运算,每个蝶式权都可看作是的n次方, 所以在一个循环内即可计算出所有的蝶式权。每 级蝶式运算计算出新的序列值代替该级的输入序 列值,这样避免了开辟新的存储空间,有效地节 省了存储空间。
FFT算法程序设计如下所示: Uint16 ConversionCount;
Uint16 px[128];Uint16 pz[128];void kfft(pr,pi,n,k,fr,fi ,l,il { Uint16 n,k,l,il;double pr[],pi[],fr[],fi [];int it,m,is,i,j,nv,l0;
double p,q,s,vr,vi,poddr,poddi;for(it=0;it<=n-1;it++ { m=it;is=0;for(i=0;i<=k-1;i++ { j=m/2;is=2*is+(m-2*j;m=j;} fr[it]=pr[is];fi[it]=pi[is];//此循环为比特逆序的实现, pr、pi是原序列的实部与虚部 } //fr、fi是排完序后的序列
pr[0]=1.0;pi[0]=0.0;p=6.283185306/(1.0*n;pr[1]=cos(p;pi[1]=-sin(p;// pr是的实部,pi是的虚部 if(l!=0 pi[1]=-pi[1];for(i=2;i<=n-1;i++ { p=pr[i-1]*pr[1];q=pi[i-1]*pi[1];s=(pr[i-1]+pi[i-1]*(pr[1]+pi[1];pr[i]=p-q;pi[i]=s-p-q;} //此循环为权值运算实现
for(it=0;it<=n-2;it=it+2 //it是序列下标,在第一级蝶式运算中 //相邻的两个运算蝶下标相差2 { vr=fr[it];vi=fi [it];
fr[it]=vr+fr[it+1];//第一级蝶式运算中相邻两个数值进行加减运算 fi [it]=vi+fi [it+1];fr[it+1]=vr-fr[it+1];fi [it+1]=vi-fi [it+1];} //此循环为第一级蝶式运算,该级中的蝶式权均为1 m=n/2;nv=2;
for(l0=k-2;l0>=0;l0--//除去第一级,还有六级蝶式运算
{ m=m/2;nv=2*nv;// 同一级相邻的两个蝶式运算中数值的下标相差为nv for(it=0;it<=(m-1*nv;it=it+nv //it仍为数值的下标 for(j=0;j<=(nv/2-1;j++ { p=pr[m*j]*fr[it+j+nv/2];// nv/2为蝶式运算的翅间距 q=pi[m*j]*fi [it+j+nv/2];s=pr[m*j]+pi[m*j];s=s*(fr[it+j+nv/2]+fi [it+j+nv/2];poddr=p-q;poddi=s-p-q;fr[it+j+nv/2]=fr[it+j]-poddr;fi [it+j+nv/2]=fi [it+j]-poddi;r[it+j]=fr[it+j]+poddr;fi [it+j]=fi [it+j]+poddi;//计算出的新序列值代替输入序列值,节省了存储空间 }}} // fr、fi分别为计算出的FFT序列的实部和虚部 3.2 运行结果
用FFT的计算公式对单一频率的正余弦信号进行变换,可以得出单一频率的信号在频域表现为在其正负频率点上的两个脉冲。根据单频信号的这一特性可验证上述程序是否正确。将单一频率的正弦波信号接入硬件系统,打开图形观察窗口,将观察点数设置为128点,即可观察到如图4所示的波形。
图4 时域正弦波的FFT运行结果
图5 改善后的FFT运行结果
图4中上半部分波形为输入的时域正弦波,下半部分波形为经过变换后的频域波形。在图4中,由于产生的模拟信号伴有噪音,导致信号频率不单一,故而在信号的频域中,除了信号对应的频率点有脉冲外,其它频率点处也有较弱的脉冲。
对输入信号的频率进行调整,使信号的组成频率尽可能单一,可以得到更好的波形,如图5所示。可以看到在信号对应的频率点有脉冲,其它频率点的振幅为0,与理论推导结果一致,由此可验证程序设计的正确性。结论
FFT是声学、图像和信号处理等领域中一种重要的分析工具,文中阐述了硬件结构图和信号调理电路。详细介绍了FFT算法原理,采用C语言编写程序实现了FFT算法。程序运行结果表明TMS320F2812 DSP实现FFT运算速度快,精度高[4]。
参考文献: [1] 贾玮,杨录,张艳花.基于TMS320VC5416的FFT算法的实 现[J].山西电子技术,2009,2:11-13.[2] Rright Hert.Rapid algorithms of digital signal processing [M].Beijing,Electronic Industrial Press,2002.[3] 胡广书.数字信号处理[M].北京:清华大学出版社,2003.[4] 苏奎峰,吕强,耿庆锋,陈圣俭.TMS320F2812原理与开发 [M].北京:电子工业出版社,2005.2.3
反射光谱的测试
图4 ZnO纳米线阵列与原始硅片的反射光谱对比
图4是Si两种不同形貌ZnO纳米结构与原始硅片反射光谱的对比,在200-900nm波长范围内,样品C平均反射率约为5%,样品B平均反射率约为8%,均大大优于普通抛光硅片大于25%的平均反射率。样品B减反射性能略低于样品C的原因可能在于测试时入射光是垂直硅片表面人射的,相对于垂直阵列,不规则纳米结构顶部区域会使得更多的光被反射出去。结论
采用化学气相沉积的方法在p型硅片表面制备出垂直排列和不规则排列的ZnO纳米线阵列,并在此基础上制备n-ZnO纳米线/p-Si光伏器件。试验测得性能最好的器件的开路电压VOC为0.78V,短路JSC电流为6.22 mA/cm2,效率为2.6%。同时,一维结构的ZnO纳米阵列具有非常优异的减反射性能,利用这些ZnO纳米线阵列设计和制作了新型异质结纳米阵列太阳电池,其在200-900nm波长范围内,反射率约为5%。远低于原始Si片25%的反射率。
参考文献:
[1] Law,M.;Greene,L.E.;Johnson,J.C.;Saykally,R.;Yang,P.D.Nat.Mater.4,455(2005.[2] Bai,X.D.;Wang,E.G.;Gao,P.X.;Wang,Z.L.Nano Lett.3,1147(2003.[3] Wang,X.D.;Zhou,J.;Lao,C.S.;Song,J.H.;Xu,N.S.;Wang,Z.L.Ad.Mater.19,1627(2007.[4] Yang,P.D.;Yan,H.Q.;Mao,S.;Russo,R.;Johnson,J.;Saykally, R.;Morris,N.;Pham,J.;He,R.R.;Choi,H.J.Ad.Funct.Mater.12,323(2002.[5] Huang,M.H.;Mao,S.;Feick,H.;Yan,H.Q.;Wu,Y.Y.;Kind,H.;Weber,E.;Russo,R.;Yang,P.D.Science.292,1897(2001.[6] Lim,J.H.;Kang,C.K.;Kim,K.K.;Park,I.K.;Hwang,D.K.;Park, S.J.Ad.Mater.18,2720(2006.[7] Wang,Z.L.;Song,J.H.Science 312,242(2006.[8] Wang,X.;Song,J.;Liu,J.;Wang,Z.L,Science.316,102(2007.[9] B.Tian,T.J.Kempa,and C.M.Lieber,Chem.Soc.Rev.38,16(2009.[10]Hu,L.;Chen,G.Nano Lett.7,3249–3252(2007.【上接第2页】
第二篇：基于 OLSR 路由协议的 HIDA 算法概要
— 147— 36卷 第 9期
ol.36 No.9 2010年 5月
Ma 基于 OLSR 路由协议的 HIDA 算法 姚 胜,冷甦鹏
(电子科技大学通信抗干扰技术国家级重点实验室,成都 610054 摘 要:针对 Ad Hoc网络中的虫洞攻击,根据最优链路状态路由(OLSR协议的运行特点,提出检测伪邻居的 HELLO 间隔分布式算法(HIDA。仿真结果表明,在网络平均节点数大于
4、节点随机最大移动速率大于 2 m/s时, HIDA 算法能达到 80%以上的虫洞攻击检测率。关键词:无线自组织网络;邻居探测;虫洞攻击;最优链路状态路由协议;HELLO 间隔分布式算法
HIDA Algorithm Based on OLSR Routing Protocol YAO Sheng, LENG Su-peng(National Key Lab of Communication Anti-interference Technology, University of Electronic Science and Technology of China, Chengdu 610054 【 Abstract 】 Aiming at the wormhole attack in Ad Hoc network, according to Optimized Link State Routing(OLSR protocol, this paper presents a HELLO Interval Distributed Algorithm(HIDA to detect fake neighbor.Simulation results show that HIDA has wormhole attack detection rate above 80% when network average node number is greater than 4, node random maximal migration rate is greater than 2 m/s.【 Key words】 Wireless Ad Hoc Network(WANET;neighbor probing;wormhole attack;Optimized Link State Routing(OLSR protocol;HELLO Interval Distributed Algorithm(HIDA
计 算 机 工 程 Computer Engineering第 V y 2010 术·
文章编号:1000— 3428(201009— 0147— 03 文献标识码:A 中图分类号:TP393 ·安全技 1 概述
移动 Ad Hoc网络是一种自适应的自组织网络,由于它
性能优越,因此在越来越多场合得到应用。目前关于 Ad Hoc自组网的研究大多集中在基于可信任环境下的通信和路由有 效性。由于 Ad Hoc自组网无线信道的开放性,因此极易遭 到攻击。攻击方通过攻击无线网络协议,窃取传输信息使网 络无法正常工作。因此,无线网络的安全问题引起了很多关 注。路由协议是节点通信的基础,协议运行环境为移动多跳 传输,这使 Ad Hoc网络路由协议的可靠性必须依赖所有节 点协调工作。如果网络中存在节点异常工作或被攻击节点入 侵等情况, 则会导致路由协议崩溃, 整个网络不能正常工作。因此,必须提升 Ad Hoc网络的安全性能。
在移动 Ad Hoc网络中的虫洞攻击是一种很特殊的恶意 攻击形式。它通过控制路由入侵网络, 破坏性大且很难探测。一般的安全策略如加密认证很难抵御虫洞攻击,因此,本文 以最优链路状态路由(Optimized Link State Routing, OLSR协 议为模型进行针对性的改进。
虫洞攻击一般由 2个能直接通信的攻击节点协同发动, 它们之间的链路称为“隧道”(其长度大于普通节点的信号覆 盖半径,在路由上体现为 1跳距离 是发动攻击的基础 [1]。虫 洞攻击示意图如图 1所示,其中, A 和 B 是距离较远的 2个 节点,不在信号覆盖范围内;X 和 Y 是协同攻击节点,在它 们之间建立一条私密的链路形成“隧道”。在这个网络中, 通过彼此接收到对方的 HELLO 报文来确定邻居探测。当 A 向
周围邻居发送 HELLO 报文时, X 收到该报文后通过隧道 传给 Y , 由 Y 原封不动地重放到网络中, B 接收到 A 的 HELLO 报文,判定 A 为 1跳邻居。同理, A 认为 B 是自己的邻居。因此, A, B以及所有位于 X, Y传播范围内正常节点的邻居 表中均会存在伪邻居。若路由协议是以最短路径优先原则建
立路由表项, A 到 B 的最短距离为(2n +2 跳, 则 A 的 n 跳内 的邻居会通过“隧道”建立路由表项到达 B。所有节点的通 信都暴露在攻击节点下,通过路由信息的扩散传播会使网络 极大范围内的节点通信受控于攻击节点,攻击者对通过其路 径的信息进行窜改或丢弃等恶意操作使网络中部分节点无法 通信,甚至使整个网络瘫痪。
图 1 虫洞攻击示意图 2 相关研究
由于移动 Ad Hoc网络极易受到各种攻击,因此已提出 很多安全协议。虽然安全路由协议有很多,但没有一种能应 对所有恶意攻击,尤其是能绕过网络加密认证系统的虫洞攻 击,加密认证系统对虫洞攻击没有任何作用。因此,要对路 由协议单独进行针对性改进,使网络能抵御虫洞攻击。
Packet Leashes[2]是经典的抵御虫洞攻击的方法。其原理
基金项目:国家自然科学基金资助项目(60802024;教育部博士点新 教师基金资助项目(200806141014;通信抗干扰技术国家级重点实验 室基金资助项目
作者简介:姚 胜(1983-, 男, 硕士研究生, 主研方向:数据通信, 无线自组织网络,网络安全;冷甦鹏,副教授、博士 收稿日期:2009-11-28 E-mail :linmin17125@163.com 是在数据报文中附加限制报文最大传输距离的信息。这种信息可以分为 2种:位置限制和时间限制。该方法 需要网络提供一个强大的密钥管理和时钟同步系统,对网络 带宽有很高的要求。另一种检测虫洞攻击的方法是计算节点 每跳传输时延或位置信息,它通过包含虫洞链路的 2个节点 之间的传输时延远大于真实 1跳邻居传输时延进行判断。TTM [3]是针对 AODV 协议计算路由发现过程中的每跳传输时 延来检测是否有不正常链路存在。这种时延机制能有效抵御 虫洞攻击,但加重了路由协议的开销,使其效率下降。然而, 一些虫洞攻击可通过 at the bit level或 at the physical layer发 起很难被时延分析检测到。
文献 [4]提出一种针对按需的路由协议,利用路由统计信 息检测虫洞攻击,通过在源节点和目的节点之间建立多跳路 由路径来判断统计信息中是否存在嫌疑链路。这种多路径方 法很可能由于统计信息不足导致误判,效率较低。另外,一 些方法大多依赖精确时钟同步的假设或需要特殊设备,很难 应用到实际网络中。
综上所述,这些安全路由协议都存在局限性,它们一般 都对网络进行严格的假设, 建立的理论模型与实际相差较大, 并且一些提出方法需要特殊硬件设备等。由于这些机制的引 入很难在路由协议的性能表现和抵御虫洞攻击的有效性方面 取得平衡,因此需要进一步对提升它们的安全性能,降低路 由协议复杂度和网络开销。基于 OLSR 路由协议的 HIDA 算法 3.1 OLSR路由协议
移动 Ad Hoc网络中的路由协议分为表驱动路由协议和 按需路由协议。OLSR 路由协议属于表驱动链路状态路由协 议,适合应用于大型密集网络。该协议通过节点周期性地交 换各种控制信息来建立分布式计算和更新网络拓扑,节点根 据最短路径优先原则来计算路由表。
OLSR 协议运行的基础是 2种主要的控制报文:HELLO 报文和 TC(Topology Control报文。HELLO 报文在 1跳的范 围内被周期性广播,不被转发,它用于建立节点的邻居表(包 括邻居节点地址以及本节点到邻居节点的延迟 和计算节点 的多点中继集(Multipoint Relay, MPR。TC 报文包含节点 MPR 邻居的信息被广播到全网,只有属于 MPR 的邻居节点 能转发 TC 控制报文。这种机制有效地控制了 TC 报文在网络 中广播的规模,减少了网络负荷,避免形成广播风暴。节点 根据收到的 TC 报文中节点的邻居关系独立计算网络的拓扑 图,依据最短路径优先原则计算路由表。OLSR 路由协议包 括 4个主要过程:邻居探测, MPR 选择, TC 报文扩散和路 由表计算,其中,通过发送 1跳内 HELLO 报文进行邻居侦 听是该协议运行的基础。
由图 1可以看出,虫洞攻击发动时会使 2个攻击节点的 传输范围内所有正常节点相互收到 HELLO 报文,使它们成 为伪邻居。由于节点依据这种错误的拓扑关系进行路由计算, 因此破坏了 OLSR 路由协议的正常运行。伪邻居的产生是虫 洞攻击发动的基础,避免伪邻居的产生有效抵御虫洞攻击。3.2 算法实现
本文基于虫洞攻击提出一种检测伪邻居的安全路由算 法—— HELLO 间隔分布式算法(HELLO Interval Distributed Algorithm, HIDA,并对 OLSR 协议进行相应改进。本文模 型是一个大型密集的 Ad Hoc网络,节点不频繁的随机移动, 移动速率不高。改进思想是依据 OLSR 路由协议运行的特点, 通过比较正常邻居和伪邻居的产生是否导致非法拓扑结构来 判断是否存在虫洞攻击。
伪邻居的判断示意图如图 2所示,假设互为邻居的正常 节点 A, B, C都位于攻击节点 X 的覆盖范围内,并假设 Y 覆 盖范围内正常节点中存在 2跳邻居 M 和 N。当发生虫洞攻击 时,在某个 HELLO 2 s间隔内, A, B, C节点均会收到 M 和 N 的 HELLO 报文并更新各自邻居表。这时就能进行判断:新出现的 M 和 N 可不可能是 A 的正常邻居节点。若 M 和 N 均 为 A 的正常邻居节点,那么说明它们在 HELLO 间隔内均从 A 的覆盖范围之外移动到 A 覆盖范围之内。因此, A 应处于 M 和 N 的移动范围重合处,即图中阴影处。
同样, B 和 C 节点也是如此。因为在 HELLO 间隔这段时 间内,低速节点运动距离很小,这样 A, B, C 3个节点几乎同 时位于以 M 和 N 移动距离为长和宽的矩形区域内,而这个面 积相对于节点的通信覆盖范围太小,本文认为网络中不存在 这样不合理的拓扑机构,即认为 M 和 N 均是 A 的伪邻居, 网络中存在虫洞攻击。
(a判断过程
(b判断结果
图 2 伪邻居的判断示意图
依据上述分析可知, HIDA 算法的主要思想是:某节点 A 若在 HELLO 间隔这段时间内第 1次收到 2个节点 M 和 N 的 HELLO 报文, 并且这 2个节点不互为邻居, 同时检测到它们 不在 A 的 1跳和 2跳邻居表内。在 HELLO 间隔中, A 通过 接收到已存在的邻居节点的 HELLO 报文可以计算这个短时 间内收到 M 和 N 的 HELLO 报文的正常邻居节点个数, 若该 邻居节点个数大于或等于 2个,则 A 就可判定 M 和 N 为伪 邻居, 忽略它们的 HELLO 报文以及 M 和 N 邻居表中节点的 HELLO 报文,该算法从收到一个未知的新 HELLO 报文开始 启动,并在 2倍 HELLO 间隔时间内周期地进行计算。4 仿真分析
文献 [5]提出另一种基于 OLSR 路由协议的防御虫洞攻击 算法:异常拓扑分布式算法(Abnormal Topology Distributed Algorithm, ATDA,它利用拓扑分析的方法,依据网络中发 生虫洞攻击时引入的不正常节点密集度进行检测,本文对 HIDA 和 ATDA 2种算法进性仿真分析并比较性能。
本文仿真通过 NS2软件平台实现。在仿真时,对 NS2 — 148—
中 OLSR 协议模块进行相应改动,添加 HIDA 算法,完成该 协议的安全改进并建立仿真模型。本文共进行 3次仿真,其 中,前 2次仿真对 ATDA 和 HIDA 2种算法进行性能比较;第 3次仿真是对 HIDA 算法的有效性进行分析。3次仿真的 场景参数各不相同,但都是节点随机均匀分布在 800 m×800 m的矩形区域中,节点的通信距离是 100 m。
在不同节点数(节点数分别是 20, 40, 60, 80, 100, 120, 140, 160, 180, 200下,随机生成拓扑 100次,每次均进行一次虫 洞攻击,所有节点随机移动,最大移动速度是 2 m/s,仿真时 间为 20 s,不同节点数下 2种算法攻击检测率的比较结果如 图 3所示。
0.0 0.20.40.60.8 1.0 节点数
攻 击 检 测 率
图 3 不同节点数下 2种算法的攻击检测率比较
在不同的移动速率下,节点数为 100,所有节点随机移 动,速率大小服从均匀分布,最大速率分别为 0 m/s, 1 m/s, 2 m/s, 4 m/s, 6 m/s, 8 m/s, 10 m/s,随机生成拓扑 200次并进 行 100次攻击,仿真时间为 20 s。2种算法的攻击误判率、漏判率比较如图 4、图 5所示。2 4 6 8 10 0.00 0.050.100.150.20 节点最大移动速率 /(m·s-1 攻 击 误 判 率
图 4 2种算法的攻击误判率比较
节点最大移动速率 /(m·s-1 攻 击 漏 判 率 02 4 6 8 10 0.20.40.6 图 5 2种算法的攻击漏判率比较
在不同节点数、不同移动速率下,节点数分别为 60, 80, 120,节点随机移动最大速率为 0, 1 m/s, 2 m/s, 4 m/s, 6 m/s, 8 m/s, 10 m/s,仿真时间为 70 s,分析 HIDA 算法在成功检测 虫洞攻击的情况下，HIDA 算法伪邻居的误判率和漏判率结 果如图
6、图 7所示。
节点最大移动速率 /(m·s-1 伪 邻 居 误
判 率
图 6 HIDA算法的伪邻居误判率比较 0.0 0.20.40.60.8 1.0 节点最大移动速率 /(m·s-1 伪 邻 居 漏 判 率
图 7 HIDA算法的伪邻居漏判率比较 5 结束语
通过仿真比较可知,本文 HIDA 算法相对于 ATDA 算法 在网络节点分布不是很密集时性能表现更加优越,能取得更 高的检测率。在不同节点移动速率下, HIDA 算法的攻击漏 判率更低,但攻击误判率在节点高速移动下表现却稍差。在 成功检测到虫洞攻击的情况下, HIDA 算法对伪邻居的判断 在节点低速移动下也具有较高性能,但在高速移动情形下协 议还需进一步研究。
综上所述, HIDA 算法在低速密集的无线自组织网络中 对虫洞攻击的防御表现出优越性能,同时该协议的运行不会 对网络产生多余流量,保证了协议的高效性。
参考文献
[1] Hu Yih-Chun, Perrig A, Johnson D B.Wormhole Attacks in Wireless Networks[J].IEEE Journal on Selected Areas in Communications, 2006, 24(2: 370-380.[2] Hu Yih-Chun, Perrig A, Johnson D B.Packet Leashes: A Defense Against Wormhole Attacks in Wireless Ad Hoc Net-works[C]//Proc.of the 22nd Annual Joint Conference of IEEE Computer and Communications Societies.Pittsburgh, USA: IEEE Press, 2003.[3] Tran Phuong-Van, Hung Le-Xuan, Lee Young-Koo, et al.TTM: An Efficient Mechanism to Detect Wormhole Attacks in Wireless Ad Hoc Networks[C]//Proc.of CCNC’07.Las Vegas, USA: IEEE Press, 2007.[4] Qian Lijun, Song Ning, Li Xiangfang.Detecting and Locating Wormhole Attacks in Wireless Ad Hoc Networks Through Statistical Analysis of Multi-path[C]//Proc.of 2005 IEEE Wireless Communications and Networking Conference.[S.l.]: IEEE Press, 2005.[5] Maheshwari R, Gao Jie, Samir R D.Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information[C]//Proc.of INFOCOM’07.[S.l.]: IEEE Press, 2007.编辑 陆燕菲
— 149—
第三篇：算法及其实现 教学设计(第一课时)
《3.4算法及其实现》教学设计（第一课时）
一、设计思想
随着新课程改革的深入，信息技术课程理念发生了巨大的变化，具体表现为：强调培养学生的信息素养；为学生打造终身学习的平台；关照全体学生的发展；强调培养学生解决问题的能力，运用信息技术创新实践的能力，与人交流合作的能力。新课程要求教师必须改变传统的“教教材”，要 “用教材去教”，要求教学模式由以往的“以教师为主体”转变到“以学生为主体”，提倡“任务型”教学，关注学生的情感态度价值观。
本节课我根据新课标，结合学生的特点对教材的内容进行了深入的挖掘和思考，创作了学生学案，创设丰富的教学情境，提供多样的学习资源。教学以生活中的实际问题和有趣故事作为任务驱动，让学生采用自主、合作、探究、体验等学习方式，通过意义建构获得新知，充分体现学生的主体地位。
二、教材分析
《算法及其实现》是普通高中课程标准实验教科书——《信息技术基础（浙江教育出版社）》的第三章第四节内容，该教材是按照高中信息技术课程标准编写的实验教材。通过学习本节内容可以达到“初步掌握用计算机进行信息处理的几种基本方法，认识其工作过程与基本特征”的课程标准要求。
本节内容是第三章的难点，介绍了算法的基本概念和算法的表示方法。相比较前三节的内容要抽象的多，二本节又是第四节的第一课时，是第二课时《程序设计实例》的知识基础，起到承上启下的作用。本节的学习重点是算法的概念、特点及表示方法；难点是用流程图描述算法。
三、学情分析
从思维品质上来说：高一学生已有使用计算机的感性经验，已经可以 超越简单的技术操作，具备了接受更高层面文化的能力。学生的思维能力已接近成人，他们有旺盛的求知欲，较高的学习自觉性，并具备一定的自学能力，已具有较强抽象思维和逻辑推理能力。
从知识储备上来说：经过前面的学习，学生已经可以使用计算机处理一些实际问题，例如：利用计算机对文字、图片、多媒体信息的处理，但是学生还不了解了使用计算机解决问题的一般过程和解决方法，以及以何种方式来表示。
四、教学目标
（一）、知识与技能：
1、理解算法的含义；
2、了解算法的特点及表示方法；
3、学会用流程图表示算法。
（二）、过程与方法：
1、能初步利用算法解决简单的问题；
2、培养学生的理论联系实际能力和动手操作能力。
（三）、情感态度与价值观：
1、培养学生学习信息技术课程的兴趣；
2、培养学生主动探究和合作学习的意识和能力。
五、重点难点
教学重点：算法的含义、及表示方法 教学难点：用流程图描述算法
六、教学策略与方法
1、学案导学，自主学习
2、问题导入，激情引趣。
3、创设情境，任务驱动。
4、合作探究，交流提高。
七、课前准备
1．教材、教材配套的教师用书、配套光盘 2．学生学案 3．教学课件
4、多媒体教室/大屏幕投影仪
5、将学生分为4人一组，每组都有优、中、差三个不同层次的学生。
八、教学过程
（一）新课导入
同学们，上节课我们讲了声音和视频处理，都是要利用计算机内存储的应用软件来解决处理问题，同样，像我们之前学习的文字处理软件、表格处理软件、多媒体报告处理软件也都是已经编制好的软件帮助我们处理信息。
但是，也有许多问题是没有现成的软件可以借用的，因此，我们必须根据不同的问题和工作要求，设计针对特定问题的解题步骤，编制专用的软件来解决这些问题。
今天开始我们一起来看看如何实际编写一个简单的程序来解决一个特定的问题。
（二）新课教学
1、算法
（1）师生共同完成游戏
师：首先，我们一起来做一个农夫过河的游戏（游戏内容分别用文字和flash动画显示在屏幕上），请同学们按小组讨论，帮农夫设计一个具体的步骤，安全地将这三样东西带过河。
生：分组讨论过河的方案，最终得出了成功的方案。
师：让小组代表与全班同学分享各自的方案，评价各组的方案进而得出正确的步骤并总结：
同学们，这6个步骤是这个游戏中是不可缺少的动作，否则就不能完成总体目标，使问题获得圆满解决。因此，在解决某一问题时我们要把各个步骤都精确的考虑到。
上面这个例子中的解决问题的步骤其实就是编制程序的基础：算法。设计意图：游戏激发学生的兴趣，让学生在完成游戏中已经编出了一个解决问题的算法，让学生轻松进入新知识的学习。
（2）学生阅读，完成学案
师：现在请大家阅读课本3.4.1第一二自然段，完成学案1、2、3题。学生：阅读课本制定内容，完成学案。
学生完成学案时，教师要走进学生，观察学生的完成情况。完成后，学生要对学案的完成做简要展示，教师要对学生的完成情况作简要总结。
师：大家完成的都很好，请同学们告诉我有那些生活中算法的实例呢？ 生：回答（多样）
师：大家说的都很好，乐谱、菜谱、广播体操图解、搬家的次序等等都是生活中的算法，就拿“搬家”来说，是不是设计的次序不一样，搬家的效果就不一样呢？也就是说，解决同一个问题，会有很多种不同的算法，那么什么样的算法更好一点呢？
现在请大家阅读课本3.4.1剩余部分，完成学案4题。学生完成学案时教师引导：
师：方法甲和其他两个方案比较优秀在哪里？节省了什么？
我们在设计算法时应如何做呢？ 生：回答
设计意图：以学案的形式给学生一个一个的任务，让学生自己去尝试、探究，然后在教师的指导下进行小结，接下来再尝试，这样就形成螺旋式的知识学习和能力提高过程。学生的主动和教师的主导都得到充分的发挥。在本节课的教学设计中，教师重视的不应该是结果，而是过程。
2、算法的表示
（1）常见算法的表示形式
师：大家已经知道我们可以编写算法来解决生活中的问题，那么我们可以用什么形式来表示算法呢？请大家阅读课本3.4.2第1自然段，完成学案5题。
完成后要挑选学生回答。（2）流程图
师：通过大家的阅读和总结，流程图是形象直观，便于掌握的描述算法的形式，因此我们需要认真学习如何用流程图描述算法，现在请大家阅读课本3.4.2中2、3、4自然段，完成学案第6题。
生：完成学案第6题。（3）用流程图描述算法
师：我们已经知道了流程图的功能，现在我们就尝试着用流程图来表示算法，需要注意的是在用流程图描述算法之前必须能能够用自然语言描述算法，否则也无法用流程图来描述。
操作一：将大象装冰箱
操作一由老师讲解演示，学生听讲。
操作二：学校上体育课，一般在操场上课，遇到下雨或下雪，改到室内上课，用流程图表示。
操作二由学生独立完成。
生：听老师讲解完操作一之后，完成学案的第7、8题。
操作三：对任意输入的三个整数x，y和z，找出并输出其中的最大值。
操作三老师讲解。
师：操作三用自然语言描述： 1．输入变量x,y,z
2．比较x,y。如果x>y，则x存入以max命名的存储单元中；否则，y存入max 3．比较z和max。如果z>max，则将z存入max。4．输出max。用流程图描述：
课堂练习：对任意输入的三个整数x，y和z，找出并输出其中的最小值。用流程图表示。
听老师讲解后，完成学案第9、10题。
设计意图：本环节设计是充分调动学生的积极性和主动性。教学中不断的给学生新的任务，让学生主动学习，增强技能，在练习设计中注意难度的梯度，让学生不断的战胜困难，而不是一下就被困难吓倒。最后，通过不断的练习，让学生真正掌握知识和技能。
（三）课堂小结
本节课学习了算法的定义、特征、优化和算法的表示方式，并着重学习了如何用流程图表示算法。请同学们在课后完成学案第11、12题，并在小组之间交流。
九、课后作业
1、完成教材P71页上的“练一练”中的第（1）、（2）两题。
2、观察猜数字游戏，尝试画出猜数字游戏算法的流程图。
设计意图：课后作业分为课内作业和课外拓展两部分，让不同层次的学生分别完成。课外拓展部分的算法比较复杂，涉及到了循环结构，可让学生在完成思索的过程中预习第二课时的内容。
十、学生学案（另附）
【问题研讨】
1、信息技术教育，采用任务驱动的形式，围绕一个能激起学生浓厚兴趣的主题展开教学，以学生的探究过程作为学习载体，较之与传统的信息技术课教学，以单纯的计算机知识和计算机操作作为教学内容，更能激发学生强烈的学习欲望。
2、采用学案导学的方式，学生手中都有学案，方便了学习，梳理了思路，提高了效率，更主要的是真正实现了学生主动学习，教师只是引导的教学模式，更加贴近新课程改革的要求。
3、以小组协作学习方式展开教学，使学生的知识、技能的获取变成了多渠道。学生相互之间的只言片语，远胜于教师长篇大论的讲解和繁琐的演示操作，大大提高学生的学习效率和学习兴趣。同时高、中、低不同层次的学生组成小组，充分利用优秀学生资源，进行同伴互助，缩小生生间的差距,改变两极分化的现状。同时也减少教师的课堂工作量，避免了很多学生同时提问教师忙不过来的尴尬局面。
4、自主探究的学习方式，要求学生具有一定的知识准备，并不适合于所有内容的教学。当学生对所要学习的知识毫无所知时，让学生去自主探究要花费很多的时间和精力，大大降低了学生的学习效率，由于受课时限制应有选择的采用。
第四篇：C++ 八种排序算法总结及实现
八种排序算法总结之C++版本
五种简单排序算法
一、冒泡排序
【稳定的】
void BubbleSort(int* a,int Count)//实现从小到大的最终结果 { int temp;for(int i=1;i for(int j=Count-1;j>=i;j--) if(a[j] < a[j-1]) { temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; } } 现在注意，我们给出O方法的定义： 若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n)= O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！） 现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 二、交换排序 【稳定的】 void ExchangeSort(int *a,int Count){ int temp;for(int i=0;i for(int j=i+1;j if(a[j] < a[i]) { temp = a[j]; a[j] = a[i]; a[i] = temp; } } 时间复杂度为O(n*n)。 三、选择法 【不稳定的】 void SelectSort(int *a,int Count){ int temp;//一个存储值 int pos;//一个存储下标 for(int i=0;i temp = a[i]; pos = i; for(int j=i+1;j if(a[j] < temp)//选择排序法就是用第一个元素与最小的元素交换 { temp = a[j]; pos = j;//下标的交换赋值，记录当前最小元素的下标位置 } a[pos] = a[i]; a[i] = temp;} } 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n 所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。 四、插入法 【稳定的】 void InsertSort(int *a,int Count){ int temp;//一个存储值 int pos;//一个存储下标 for(int i=1;i { temp = a[i];//当前要插入的元素 pos = i-1; while(pos>=0 && temp { a[pos+1] = a[pos];//将前一个元素后移一位 pos--; } a[pos+1] = temp;} } 其复杂度仍为O(n*n)。 最终，我个人认为，在简单排序算法中，直接插入排序是最好的。 五、希尔排序法 【不稳定的】 /* * 希尔排序，n为数组的个数 */ void ShellSort(int arr[], int n){ int temp,pos;int d = n;//增量初值 do{ d = d/3 + 1; for(int i= d;i { temp = arr[i]; pos = i-d; while(pos>=0 && temp < arr[pos]){ arr[ pos + d ] = arr[pos]; pos-= d; } arr[ pos + d ] = temp; } } while(d > 1);} //实现增量为d的插入排序 三种高级排序算法 一、快速排序 辅助空间复杂度为O（1） 【不稳定的】 void QuickSort(int *a,int left, int right){ int i,j,middle,temp;i = left;j = right;middle = a[(left+right)/2 ];do { while(a[i] i++; while(a[j]>middle && j>left)//从右扫描小于中值的数 j--; if(i<=j)//找到了一对值 { temp = a[i]; a[i] = a[j]; } a[j] = temp; i++; j--;} } while(i 注意，在扫描过程中，对于给定参考值，对于向右(左)扫描，如果扫描值大(小)于或等于参考值，就需要进行交换。最终得到的结果是，j左边的值都小于参考值，而i右边的值都大于参考值，j和i之间的值都等于参考值。对j左边和i右边的分别使用递归，就可以完成最终的排序。 这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况 1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。 2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。 第一层递归，循环n次，第二层循环2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n)= n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变 成交换法（由于使用了递归，情况更糟），但是糟糕的情况只会持续一个流程，到下一个流程的时候就很可能已经避开了该中间的最大和最小值，因为数组下标变化了，于是中间值不在是那个最大或者最小值。但是你认为这种情况发生的几率有多大？？呵呵，你完全不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。 如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢 于快速排序（因为要重组堆）。 二、归并排序（两种实现方法均要掌握） 【稳定的】 归并排序是一种极好的外部排序方法，即针对数据保存在磁盘上而不是高速内存中的问题。 //以下程序参考数据结构课本P286页的模板,为使用指针链表实现的 #include struct node{ //链表的节点数据 int value;node *next;}; node * divide_from(node * head){ node * position, * midpoint, * second_half;if((midpoint=head)== NULL)//List is empty return NULL;position = midpoint->next;while(position!= NULL)//Move position twice for midpoint's one move { position = position->next; if(position!= NULL) { midpoint = midpoint->next; position = position->next; } } second_half = midpoint->next;midpoint->next = NULL;//在这里将原链拆断，分为两段 return second_half;} node * merge(node * first, node * second){ node * last_sorted;//当前已经链接好的有序链中的最后一个节点 node combined;//哑节点 last_sorted = &combined;while(first!=NULL && second!=NULL){ if(first->value < second->value){ last_sorted->next = first; last_sorted = first; first = first->next; }else { last_sorted->next = second; last_sorted = second; second = second->next; } } if(first==NULL) last_sorted->next = second;else last_sorted->next = first;return combined.next;//返回哑节点的后继指针，即为合并后的链表的头指针 } //这里的参数必须是引用调用，需要这个指引去允许函数修改调用自变量 void MergeSort(node * &head){ if(head!= NULL && head->next!= NULL)//如果只有一个元素，则不需排序 { node * second_half = divide_from(head); MergeSort(head); MergeSort(second_half); head = merge(head, second_half);} } int main(){ node a,b,c,d;node *p1, *p2, *p3, *p4,*head;p1 = &a;p2 = &b;p3 = &c;p4 = &d;a.value = 2;b.value = 4;c.value = 3;d.value = 1;a.next = p2;b.next = p3;c.next = p4;d.next = NULL;//调用归并排序前的结果 head = p1;while(head!= NULL){ cout< head = head->next;} cout< head = p1;while(head!= NULL){ cout< head = head->next;} cout< //以下程序为使用数组实现的归并排序,辅助空间复杂度为O（n） #include void Merge(int data[], int left, int mid, int right){ int n1,n2,k,i,j;n1 = midmid;int *L = new int[n1];//两个指针指向两个动态数组的首地址 int *R = new int[n2];for(i=0,k=left;i L[i] = data[k];for(i=0,k=mid+1;i R[i] = data[k];for(k=left,i=0,j=0;i if(L[i] < R[j]){ //取小者放前面 data[k] = L[i]; i++; } else { data[k] = R[j]; j++; } } if(i for(j=i;j < n1;j++,k++) } /* * left:数组的开始下标，一般为0；right：数组的结束下标，一般为（n-1）*/ void MergeSort(int data[], int left, int right){ if(left < right){ int mid = left +(right-left)/ 2;//mid=(right+left)/2，防止溢出 MergeSort(data, left, mid); MergeSort(data , mid+1, right); Merge(data , left, mid , right);} } int main(){ int data[] = {9,8,7,2,5,6,3,55,1};//排序前的输出 for(int i=0;i<9;i++) cout< for(int i=0;i<9;i++) cout< 三、堆排序 【不稳定的】 /* * 向堆中插入current元素的函数 */ void insert_heap(int data[], const int ¤t, int low, int high) data[k] = L[j];else //if(j for(i=j;i data[k] = R[i];delete []L;//回收内存 delete []R;{ int large;//元素data[low]左右儿子中，大者的位置 large = 2*low + 1;while(large <= high){ if(large < high && data[large] < data[ large+1]) large++; if(current > data[ large ])//待插入元素的值比它的两个儿子都大 break; else { data[ low ] = data[ large ];//将其左右儿子的大者上移 low = large; large = 2 * large + 1; } } data[ low ] = current;} /* * 建立堆函数，num为数组data的元素个数 * 只有一个结点的<2-树>自动满足堆的属性，因此不必担心树中的任何树叶，即 * 不必担心表的后一半中的元素。如果从表的中间点开始并从后向前工作，就 * 能够使用函数insert_heap去将每个元素插入到包含了所有后面元素的部分堆 * 中，从而创建完整的堆。*/ void build_heap(int data[], int num){ int current;for(int low = num/2-1;low>=0;low--){ current = data[ low ]; insert_heap(data, current, low, num-1);} } /* * 堆排序主函数,num为数组data的元素个数 */ void heap_sort(int data[], int num){ int current, last_sorted;build_heap(data, num);//建立堆 for(last_sorted = num-1;last_sorted>0;last_sorted--){ //逐个元素处理 current = data[ last_sorted ];//data[0]在整个数组排序结束前，存储的是待排序元素中最大的元素 data[last_sorted] = data[0]; insert_heap(data, current, 0, last_sorted-1);} } int main(){ //用于排序算法的输入输出 int a[8] = {5,7,1,2,9,4,6,3,};for(int i=0;i< sizeof(a)/sizeof(int);i++) cout< for(int i=0;i< sizeof(a)/sizeof(int);i++) cout< 《对分查找及其算法实现》教学设计 湖北省巴东县第一高级中学 刘少银 一、教材学情分析 本次课是浙江版高中信息技术选修教材《算法与程序设计》第二章算法实例第四节查找中的一部分内容。由于教材体系不适合校本实际，我们在教学过程中对教材体系作了如下调整。 讲授顺序：第一章 算法和算法的表示、第三章 面向对象的程序设计的基本知识、第四章 VB程序设计初步、第二章算法实例，第五章 算法实例的程序实现穿插在相关内容教学中完成。 因此在前期教学中学生已经初步掌握了算法基础及算法表示，VB程序设计初步等。本次课是让学生掌握对分查找的思想及算法的实现。 二、教学目标 知识与技能：理解对分查找的基本含义、方法，理解并能画出对分查找的流程图； 过程与方法：通过案例分析、直观观察，增强分析问题和解决问题的能力； 情感、态度与价值观：感受信息技术与现实生活的关联，激发对信息技术学科的求知欲，培养主动学习和使用信息技术的意识；养成科学的学习态度，不迷信书本、不迷信权威。 三、教学重难点 教学重点：对分查找的基本方法及注意事项； 教学难点：对分查找算法的实现。 四、教学策略 ·以“猜数”游戏导入，引入对分查找的概念； ·师生讨论、生生讨论、生生互助；分析、归纳、总结，理解并掌握对分查找的基本思想； ·采用分类研究、分享成果、课后练习等学习方法，理解对分查找方法及基本主要特征； ·采用自然评价、师生评价、生生评价等形式对学习进行过程性评价。 五、教学过程 1．游戏激趣，释疑对分查找 （三个程序图片） （初始界面）（人工猜数界面）（程序猜数界面） 准备：几张白纸，一支记号笔。启动猜数程序。 师：同学们好！大家看到前面的程序了吗？它是一个什么程序呢？ 同学：猜数游戏程序。 师：对，这是我用VB针对李泳主持的“幸运52”中猜商品价格环节开发的一款程序，我先来说说针对主持人的部分：当李泳宣布商品的价格范围时，比如10000元内，猜商品价格的人就可以在猜数范围栏起始栏填上“0”，终至栏填“10000”，然后再将鼠标移到猜数栏中单击，程序即提示：“准备！倒计时30秒”，当单击提示处，猜价格倒计时开始，猜价格人即可在猜数栏上填上所猜价格的数值，然后根据主持人的提示，选择“不对”重新填写商品价格或选择“正确”让所猜价格在“猜得结果”栏内显示正确结果并停止计时，提示栏中即显示“您猜了M次，对了，恭喜您”。 师：大家觉得程序光有这样的功能神奇吗？ 生：不神奇。 师：对，我也是这样认为的。这个程序神奇的地方在它能帮助猜商品价格人在规定的时间内，根据主持人的提示准确地猜出商品的价格，而且猜中率100%，所以现在“幸运52”停播了，大家知道为什么吗？ 生：不知道。 师：就是因为我开发了这个程序呀！ 生：（有的说信，有的抱着怀疑的态度不吭声，也有说不信的） 师：有同学愿意上来试试吗？ 师：你在纸上写下你的数值范围和要猜的数，然后给大家看一下，别说出来，别让电脑听见了。 师：好，操作程序让程序帮忙把写的数找出来。 （程序找到正确的数） 师：神奇吧。 师：还有那位同学愿意试一下。 师：同样，你还是先写下要猜的数和范围100～200，这次我们不让大家看到他要猜的数，请大家帮忙记下程序每次出现的数字。 师：电脑程序也猜出了正确结果：132。 程序给出的数字是： 第一个数是：150 第二个数是：12 5第三个数是：137 第四个数是：1 31第五个数是：13 4最后是：13 2大家能看出什么规律了吗？ 生：看不出 师：单纯从这几个数当中是看不出什么规律，现在我们依次把这些数放到数轴上，再看一下，大家看能找出什么规律呢？ 同学发言„„ 师：大家认为他说的怎样？为什么不鼓掌呀！ 师：对，正如刚才的同学说的那样，程序是在给定范围内依次找中点方法来找到我们要找的最终数值，这就是我们今天要讨论的一种新的查找方法：对分查找。 师：我们刚才的游戏中的数列是序的吗？ 生：是有序的，升序排列的。 师：如果是降序能用对分查找方式查找吗？ 生：能。 师：大家想一想，如果我们打乱数据的排序顺序，在没有排序的数列中能否用对分查找的方法，找到我们想找到的数据？ 同学：不能。 师：对，这就是对分查找方法的一个特征，或称为条件。因为我们是根据数据的大小找到它在数列中的位置。 【设计意图】通过游戏和对程序给出数值在数轴上的分布分析，让学生初步理解和掌握对分查找的方法及前提条件，为后一阶段对分查找算法的实现作好铺垫。 2．分析实例，实现对分查找算法 师：下面我们一起来看一下程序是怎样一步一步的给出以上数据并最终找到“132”这个数的。 师：首先在100至200之间找中点，然后再用中点值150与所要找的数132比较，得出的结论是所要找的数在100至150之间的数，一下数值的范围就缩小了一半，终止变量j的值就由200变成了150；第二次查找时，程序就给出100至150的中点值125；当程序进行第三次查找时，起始变量i的值就被修改为125，它们的中点值应该是：（125+150）/2=137.5。有小数了，怎么办？ 生：„„（有点茫然） 师：对于小数，程序可以继续查找，但有可能要增加查找次数。为了保证在整数范围内查找，我们就要对含小数的中间值进行处理：取整。大家还记得我们学过VB的取整函数吗？ 生：int。 师：对。即int（137．5），结果是多少？ 生：137。 师：所以我们查找i到j范围内的中点值的表达式应该为：m=int（（i+j）/2）。 师：依次类推，程序会依次给出131、134、132即找到了要找的数。 师：请同学们根据算法逐步求精的原则在下面画出流程图。 （展示如下流程图，然后请同学完成完善对分查找的算法流程图） 流程图补充完善后的结果： 【设计意图】通过对程序给出中间数的分析，帮助学生理解对分查找算法实现的方法，为学生顺利完成对分查找算法流程图给予理论与实践上的支持。 3．推出特例，完善对分查找算法 师：同学们，刚才我们完成的对分查找的流程图；下面请同学们用刚才的查找方法分析一下在199至200范围内要找200这个数，能找到吗？为什么？如何解决这个问题？ （将教室内学生按座位分成若干组，进行讨论。每个组推选一名小 组长，完成后作小组发言） „„ （每一小组完成发言后，老师或点评，或让学生点评） 师：根据刚才同学的讨论分析，那我们先前给出的流程图就有了一些缺陷，怎么修改？ （在同学们的发言声中，修改完善流程图） 修改后的流程图如下： 【设计意图】给出特例，让学生相互讨论、互助学习，归纳总结出上述流程图中出现问题的症结所在，并给出正确的流程图；由此可让学生体验到科学探究的方法，从而培养学生的科学态度与探索精神。 六、课后作业 师：1．在前面的取整中我们用了取整函数int，大家想一想能不能用四舍五入函数处理？如果用四舍五入函数（round）处理，流程图又将怎样修改？ 2．请看教材P40-43，比较我们所给出的流程图与教材上的流程图有什么差异？两个流程图最后结果是否一致，那个流程图的结果有问题，问题是怎么造成的？请写出一篇500—800字的小论文。 （提示：认真阅读教材P40至P43内容，并分析教材中所给算法的逻辑错误） 作业提交方式：电子邮件（校内、校外均可） 邮件名称：登分号+姓名+论文题目 作业提交地址：bdxyz@qq.com 【设计意图】作业（1）扩充课堂内容，丰富学生知识面，丰富学生分别学习内容；作业（2）通过两个流程图之间差异性比较，引导学生判别书本上所给出流程图的逻辑错误，从而培养学生：1．科学的学习态度和精神，不迷信教材、不迷信权威；2．运用论文等形式来表达自己观点；3．通过学生自己的分析、探索，找出教材中的错误。 七、教学反思 整节课充满了笑声和掌声，课堂气氛活跃，学生参与度高。老师的主导作用和学生的主体地位得到了充分的体现。学生在师生互动、生生讨论、生生互助中比较好地掌握了对分查找的思想和算法实现，教学效果好。但由于时间关系，没有将程序的源代码展示给学生，让学生有一种意犹未尽的感觉是本次课的一个缺憾。第五篇：《对分查找及其算法实现》教学设计
点击咨询 