程序准备算法的概念.ppt

《程序准备算法的概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、绪论程序设计基础知识本章要点什么是程序设计什么是算法，如何设计算法结构化程序设计的思想和方法共29页第3页计算机是如何工作的？Program的中文词义：名词：程序、次序、计划、节目单、说明书动词：为….编制程序、设计、制定大纲、为….安排节目Microsoft?共29页第4页计算机语言：是规则和符号的集合，是与计算机交流的工具程序：用某种计算机能够识别的语言(符号)编写的求解问题的指令序列软件：以程序为主要表现的：数据结构+算法+文档的集合概念共29页第5页懂得计算机是如何工作的；掌握一种计算机语言；学会问题的分解与复合；学会一种思考方法。本课程的目标

2、：共29页第6页算法：完成一项任务的具体步骤1.算法的概念二、算法和算法的表示“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。”任何解决问题的过程都是由一定的步骤组成的，把解决问题确定的方法和有限的步骤称作为算法。共29页第7页例1：计算一元二次方程求的根。分析：这是一个初中数学问题。我们已经知道：a不能为0，否则就不是一元二次方程了，在这个前提下可以使用求根公式，同时还必须注意到：若没有实根；依据此公式计算出两个实根。共29页第8页①将a、b、c和x的值输入到计算机；②判断a≠0?如果条件成立，否则退出；③计

3、算的值，(设用符号T代表该值)④判断：若T<0？则本方程无实根，然后执行第⑦步；⑤否则，可以使用求根公式计算⑥输出的值；⑦算法结束。这是用自然语言描述的算法分步求解的过程：共29页第9页例2：计算函数M(x)的值。函数M(x)为：算法分析：这是一个数值运算问题。其中M代表要计算的函数值，有两个不同的表达式，根据x的取值决定采用哪一个算式。根据计算机具有逻辑判断的基本功能，用计算机解题的算法如下：共29页第10页①将a、b、c和x的值输入到计算机；②判断x≤a?如果条件成立，执行第③步，否则执行第④步；③按表达式bx+a2计算出结果存放到M中，然后执行第

4、⑤步；④按表达式a(c-x)+c2计算出结果存放到M中，然后执行第⑤步；⑤输出M的值；⑥算法结束。这是用自然语言描述的算法共29页第11页例：有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在了黑墨水瓶子里，要求将其互换。算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以，解决这一问题的关键是需要引入第三个墨水瓶。设第三个墨水瓶为白色，其交换步骤如下：共29页第12页①将蓝瓶中的黑墨水装入白瓶中②将黑瓶中的蓝墨水装入蓝瓶中③将白瓶中的黑墨水装入黑瓶中④交换结束共29页第13页2.常用算法简介（1）交换两个变量的值采

5、用间接交换方法atb(2)计数器和累加器计数器：用于统计循环的次数。如：i=i+1累加器：用于实现数值求和。如：sum=sum+x共29页第14页（3）枚举法（穷举法或试凑法）根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况验证完。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。如：8角的硬币组成问题。(4)递推法（迭代法）利用问题本身所具有的某种递推关系求解问题。从初值出发，归纳出新值与旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重

6、复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。如：牛顿公式问题。共29页第15页（5）求最大值、最小值问题采用如同打擂台的方法。在n个数中，先假设第一个数为最大值，成为擂主，依次同第2，3，……n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。求最小值问题则先假设第一个数为最小值。……共29页第16页3.算法的基本特征算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。算法的基本特征：有穷性：算法必须在执行有限个操作后终止；确定性：算法中每一步的含义必须是确切的，不可出现任何二义性；有效性：算法中的

7、每一步操作都应该能有效执行，一个不可执行的操作是无效的；有零个或多个输入；有一个或多个输出。共29页第17页4.算法的表示可以用不同的方法表示算法，常用的有：自然语言传统流程图结构化流程图伪代码PAD图共29页第18页结束共29页第19页(1)用流程图表示算法美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号：起止框判断框处理框输入/输出框注释框流向线连接点共29页第20页例：有50个学生，要求将他们之中成绩在80分以上者打印出来。用g代表学生成绩，gi代表第i个学生成绩。算法可表

8、示如下：S1：1iS2：如果gi80，则打印gi，否则不打印S3：i+1iS4:如果i