- 1、本文档共13页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
常用算法
基本概念:
算法:就是解决问题方法的精确描述。并不是所有问题都有算法,有些问题经研究可行,则相应有算法;而有些问题不能说明可行,则表示没有相应算法。
算法具有以下性质:是一有穷动作的序列;
动作序列仅有一个初始动作;
序列中每个动作的后继动作是确定的;
序列的终止表示问题得到解答或问题没有解答
算法的分类:数值的和非数值的
数值的算法是以数学方式表示的问题求数值解的方法,如:代数方程计算、矩阵计算、线性方程组求解、函数方程求解等;
非数值的算法是求非数值解的方法,如排序查找、模式匹配、排列模拟、表格处理、文字处理等。
算法设计:主要是针对各类具体问题设计良好的算法及研究设计算法的规律和方法。
常用的算法设计方法:
数值算法:迭代法、递归法、插值法等;
非数值算法:分治法、贪婪法、回溯法等。
算法分析:是对设计出的每一个具体的算法,利用数学工具,讨论各种复杂度。算法的复杂度分时间复杂度和空间复杂度。
常用数值计算算法
迭代法
迭代法适用于方程(或方程组)求解,是使用间接方法求方程近似根的一种常用算法。(参见清华版《PASCAL程序设计P89练习4.23》
设方程f(x)=0,该方法将方程表示为等价形式:x=g(x),或一般地将f(x)拆成两个函数f1、f2,即f(x)= f1(x)-f2(x) =0,因而有f1(x)=f2(x)。其中f1(x)是这样一个函数,对于任意数c,容易求出f1(x)=c的精确度很高的实根。迭代法求解算法如下:
首先选一个x的近似根x0,从x0出发,代入右面函数,并解方程f1(x)=f2(x0)得到下一个近似根x1;
将上次近似根x1代入右面函数,并解方程f1(x)=f2(x1),得到又一个近似根x2
重复(2)的计算,得到一系列近似根x0,x1,x2,…,xi,xi+1,…,xn,…;
若方程有根,这数列收敛于方程的根,若满足,则认为xn是方程的近似根。
例1:迭代计算n!、Fibonacci(斐波那契)数列 (详见清华版《PASCAL程序设计》P59-62例4.3,4.4)
例2:计算直到最后一项的绝对值小于10-7时停止计算,x由键盘输入。(详见清华版《PASCAL程序设计》P72例4.11)
练习:清华版《PASCAL程序设计习题与选解》P18习题4.23,4.38
递推法
递推法实际上是需要抽象为一种递推关系求解,此方法通常表现为两种方式:方式一是从简单推到一般;
方式二是将一个复杂问题逐步推到一个已知解的简单问题。这两种方式反映了两种不同的递推方向,前者往往用于计算级数,后者与“回归”配合成为一种特殊的算法――递归法。
递归法
在数学中几个熟知的递归定义:
树结构:a)O是树(空树);b)若t1和t2是树,则是树。
例3:递归计算n!;(详见清华版《PASCAL程序设计》P108例5.8)
例4:第二届初中组一、6
第二届初中组一、7
提示:利用y=((((ANX+AN-1)X+AN-2)X+AN-3)+……+A1)X+A0
第七届初中组三、1
练习:计算Fibonacci(斐波那契)数列
插值法
也称为内插法。在实际问题中出现的函数f(x),往往只知道它在某区间中若干点的函数值,这时作出适当的特定函数,使得在这些点上取已知值,并且在这区间内其它各点上就用这特定函数所取的值作为函数f(x)的近似值,这方法称为“插值法”。如果这特定函数是多项式,就称之为“插值多项式”或“内插多项式”。(常见用于高等代数中的计算)
常用非数值计算算法
穷举有哪些信誉好的足球投注网站法
穷举所有可能情形,并从中找出符合要求的解。最直观的是联系循环的算法。
例5:百钱买百鸡问题;第一届初中组3(也可用累加法)
第七届初中组四、2
输出1-100内的素数;验证哥德巴赫猜想 (详见清华版《PASCAL程序设计》P82-86例4.16,4.17)
例6:找出n个自然数(1,2,3,……,n)中r个数的组合
当n=5,r=3时,约定前一个数应大于后一个数,
有:543 542 541 532 531 521 432 431 421 321
可简单地用三重循环进行有哪些信誉好的足球投注网站,算法如下:
for i:=5 downto 1 do
for j:=5 downto 1 do
for k:=5 downto 1 do
if ((ij) and (ik) and (jk) and (ij) and (jk))
then writeln(i,j,k);
或者
for i:=5 downto 3 do
for j:=i-1 downto 3-1 do
for k:=j-1 downto 1 do
if ((ij) and (ik) and (jk) and (ij) and (jk))
then writeln(i,j,k);
递归法
例如
文档评论(0)