资源预览内容
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
亲,该文档总共10页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第一章 算法初步 一、算法与程序框图一、算法与程序框图 1.算法算法 : 算法指的是用阿拉伯数字进行算术运算的过程。在数学中,算法通常是指按照一定规则解决某一类问题的明确 和有限的步骤。算法通常可以编成计算机程序,让计算机执行并解决问题。 2.算法与计算机算法与计算机 : 计算机解决任何问题都要依赖于算法。只有将解决问题的过程分解为若干个明确的步骤,即算法,并 用计算机能够接受的“语言”准确地描述出来,计算机才能够解决问题。 3.算法的特征算法的特征:有限性:一个算法的步骤序列是有限的,必须在有限操作之后停止,不能是无限的。 确定性:算法中的每一步应该是确定的,并且能有效地执行且得到确定的结果。 可行性:算法从初始步骤开始,分为若干明确的步骤,每一个步骤只能有一个确定的后继步骤,前一步是后一步的 前提,只有执行完前一步才能进行下一步,并且每一个都准确无误才能完成问题。 不唯一性:求解某一个问题的解法不一定是唯一的,对于一个问题可以由不同的算法。 普遍性:一个算法应该适用于求某一类问题的解,而不是只用来解决一个具体的问题。 【注意:有限性、确定性和可行性是算法特征里最重要的特征,是检验一个算法的主要依据。 】 4.程序框图程序框图:程序框图又称流程图,是一种用程序框、流程线及文字说明来表示算法的图形。 5.程序框图的组成程序框图的组成:程序框图由程序框及流程线组成;在程序框图中,一个或几个程序框的组合表示算法中的一个步骤; 带有方向箭头的流程线将程序框连接起来,表示算法步骤的执行顺序。 6.基本程序框及其功能基本程序框及其功能: 图形符号名 称功 能 终端框(起止框)表示一个算法的起始和结束 输入、输出框表示一个算法输入和输出的信息 处理框(执行框)赋值、计算 判断框 判断某一条件是否成立,成立时在出口处表明“是”或 “Y” ;不成立时表明“否”或“N” 流程线连接程序框 连接点连接程序框图的两部分 【注意 : 起、止框是任何流程不可少的,表明程序的开始和结束。输入和输出可用在算法中任何需要输入、输出的位置。 算法中间要处理数据或计算,可分别写在不同的处理框内。一个算法步骤到另一个算法步骤用流程线连接。如果一个 框图需要分开来画,要在断开处画上连接点,并标出连接的号码。 】 7.程序框图的画法程序框图的画法: 画一个算法的程序框图,应先对问题进行算法分析,必要时可先用自然语言设计该问题的算法,弄清算法的流程, 然后把算法步骤逐个转化为框图表示,最后用流程线依步骤顺序连接成程序框图。 画程序框图的规则:使用标准的框图符号; 框图一般按从上到下、从左到右的方向画; 除判断框外,大多数框图符号只有一个进入点和一个退出点,判断框是具有超过一个退出点的唯一符号; 一种判断框是“是”与“不是”两分支的判断,而且有且仅有两个结果;另一种公式多分支判断,有几种不同的结 果。 在图形符号内描述的语言要非常简练清楚。 8.算法的基本逻辑结构算法的基本逻辑结构:顺序结构顺序结构:顺序结构是由若干个依次执行的步骤组成的,其特点是步骤与步骤之间,框与 框之间是按从上到下的顺序依次执行,不会引起程序步骤的“跳转” ,它是任何一个算法都离不开的基本结构。 条件结构条件结构:概念:在一个算法中,经常会遇到一些条件的判断,算法的流程根据条件是否成立有不同的流向,这 种先根据条件作出判断,再决定执行哪一种操作的结构称为条件结构。这是一种依据指定条件选择执行不同指令的指 控结构。 结构形式 否 是 否 是 循环结构循环结构:概念:在一些算法中,经常会出现从某处开始,按照一定的条件反复执行某些步骤的情况,这就是循 环结构,反复执行的步骤称为循环体。 结构形式 否 是 是 否 .直到型循环的结构特征直到型循环的结构特征:在执行了一次循环体后,对条件进行判断,如果条件不满足,就继续执行循环体,直到条 件满足时终止循环。 .当型循环的结构特征当型循环的结构特征:在每次执行循环体前,先对条件进行判断,当条件满足时,执行循环体,否则终止循环。 二、基本算法语句二、基本算法语句 1.任何一种程序设计语言中都包含五种基本的算法语句,它们分别是输入语句、输出语句、赋值语句、条件语句、循环 语句。 2.输入语句输入语句:输入语句是指程序运行中由用户输入数据的语句。它的一般格式是 INPUT “提示内容” ;变量。 【注意: “提示内容”一般是提示用户输入什么样的信息;输入语句中,提示内容要写在“ ”中,并且与变量 之间要用“;”隔开;一个输入语句可以输入多个变量,中间用“, ”隔开;输入语句不仅能够输入具体的常数, 还可以输入单个或多个字符,但不能是函数、变量或表达式。 】 3.输出语句输出语句:输出语句是将程序运行的信息显示出来的语句。它的一般格式是 PRINT “提示内容” ;表达式。 【注意 : “提示内容”一般是提示用户输出什么样的信息 ; 输出语句中,提示内容与表达式之间要用“ ; ”隔开 ; 一个输出语句可以输出多个变量的值,中间用“, ”隔开;输出语句中的表达式是指程序要输出的数据,输出语句可 以输出常量、变量或表达式的值,输出语句具有计算功能。 】 4.赋值语句赋值语句:赋值语句是赋给某一个变量一个具体的确定值的语句。它的一般格式是变量=表达式。其中, “=”叫做赋 值号,其作用是先计算“=”右边表达式的值,然后把这个值赋给“=”左边的变量,使该变量的值等于表达式的值。 【注意:赋值号左边只能是变量名字,而不是表达式;赋值号左右两边不能对换。赋值语句是将赋值号右边的表 达式赋给赋值号左边的变量 ; 不能利用赋值语句进行代数式(或符号)的演算 ; 赋值号与数学中的等号的意义不同, 赋值号左边的变量如果原来没有值,则在执行赋值语句后,获得一个值,如果原已有值,则执行该语句后,以赋值号 右边表达式的值代替该变量的原值,即将原值“冲掉” 。 】 5.语句中的常用符号语句中的常用符号 运算符号运算符号 循环体 满足条件? 满足条件? 循环体 满足条件? 步骤 A 满足条件? 步骤 A步骤 B 加减运算:,在程序语句中还是写为,;abababab 乘法运算:在程序语句中写作;a ba b 除法运算:或在程序语句中写作;ab a b /a b 乘方运算:在程序语句中写作,也可用连乘的形式。 b aab 函数符号函数符号 算术平方根:表示; SQR xx 绝对值:表示; ABS x|x 取整:表示不大于的最大整数。 INT xx 6.条件语句条件语句:概念概念:条件语句是处理条件结构的算法语句。 条件语句的格式条件语句的格式: 否 是 否 是 与图一相对应的条件语句的格式是 IFTHENELSE 格式 与图二相对应的条件语句的格式是 IFTHEN 格式 其功能是:当计算机执行上述语句时,首先对 IF 后的条 其功能是:当计算机执行上述语句时,首先对 IF 后的条 件进行判断,如果(IF)条件符合,那么(THEN)执行 件进行判断,如果(IF)条件符合,那么(THEN)执行 语句体 1,否则(ELSE)执行语句体 2。 语句体,否则执行 END IF 之后的语句。 两种条件语句的区别与联系两种条件语句的区别与联系 共同点共同点:两种语句都首先对条件进行判断,然后才执行相应的语句体;执行完语句体后退出条件结构。从形式上看, 都以 IF 开始,最后以 END IF 结束。 区别区别:第一种语句包含两个语句体,满足条件时执行一个语句体,不满足条件时执行另一个语句体;而第二种语句只 有一个语句体,是满足条件时执行的语句体。 【注意:利用条件语句编写程序应该:明确该程序解决什么问题,这个问题有几种不同的情况,每一种情况成立的 条件是什么;确定需要使用几个条件语句来设计程序,每一个条件语句能解决问题的哪一种情况,可以先设计解决 问题的算法,画出相应的程序框图,然后把算法步骤及框图内容使用相应语句描述。 】 7.循环语句循环语句: 循环语句的格式与功能循环语句的格式与功能: 1.直到型循环结构对应的直到型循环结构对应的 UNTIL 语句语句 满足条件?满足条件? 步骤 A步骤 A步骤 B 图一图二 IF 条件 THEN 语句体 END IF IF 条件 THEN 语句体 1 ELSE 语句体 2 END IF 满足条件? 图三图四 否 是 是 否 与直到型循环结构(图三)相对应的程序语句称为 UNTIL 与当型循环结构(图四)相对应的程序语句为 WHILE 语句,它的一般格式是: 语句,它的一般格式是: 功能:当计算机执行上述语句时,先执行一次 DO 和 UNTIL 功能:当计算机遇到 WHILE 语句时,先判断条件的真 之间的循环体,再对 UNTIL 后的条件进行判断。如果条件不 假,如果条件符合,就执行 WHILE 和 WEND 之间的循 符合,继续执行循环体;然后再检查上述条件,如果条件仍不 环体;然后再检查上述条件,如果条件仍符合,再次执 符合,再次执行循环体,直到条件符合时为止。这时,计算机 行循环体,这个过程反复进行,直到某一次条件不符合 不再执行循环体,直到跳到 UNTIL 语句后,接着执行 UNTIL 为止。这时,计算机将不执行循环体,直接跳到 WEND 语句之后的语句。 语句后,接着执行 WEND 之后的语句。 WHILE 语句和语句和 UNTIL 语句的关系语句的关系: UNTILWHILE 先执行循环体,在判断条件,然后再循环体, 再条件,反复执行,直到条件满足 先判断条件,再执行循环体,然后再判断 条件,再循环体,反复执行,直至条件不 满足 计算机的执行顺序 “UNTIL 先循环后判断,WHILE 先判断后循环” 此语句中条件是循环结束的条件, 即满足此条 件时,循环结束,执行循环结构后面的语句; 不满足时,才执行循环体 此语句的条件是执行循环体的条件,即满 足条件时,执行循环体;不满足时,退出 循环,执行循环结构后面的语句 条件的内容 “WHILE 满足就循环,UNTIL 满足就停止” 区 别 对循环体的执行次数 此语句由于先执行循环体, 后判断条件, 因此, 在任何一个这样的语句中, 循环体至少要执行 一次 此语句由于现判断条件,后执行循环体, 因此循环体可以一次也不执行而退出循环 结构 联 系 这两种语句都可以实现计算机反复执行循环体的目的,一般来说,WHILE 语句与 UNTIL 语句都可以相互转化 几种对应关系几种对应关系: 变量初始值与循环体中变量值的对应。初始值有时会直接影响循环体中的变量值。 变量的初始值与循环条件的对应。一般来讲,初始值可以确定循环条件。 三、算法案例三、算法案例 1.辗转相除法辗转相除法:辗转相除法是求两个正整数的最大公约数的方法。 2.辗转相除法具体算法辗转相除法具体算法:用两个数中较大的数除以较小的数判断玉树是否为 0,若不为 0,则用较小的数除以余数再判 断余数是否为 0,反复进行上述步骤,直到余数为 0 为止。这时的除数就是最大公约数。 3.更相减损术更相减损术:更相减损术是求两个正整数的最大公约数的方法。 4.更相减损术的内容更相减损术的内容:任意给定两个正整数,判断它们是否都是偶数。若是,用 2 约简;若不是,则以较大的数减去较 小的数,接着把所得的差与较小的数比较,并以大数减去小数。继续这个操作,直到所得的数相等为止,这个数就是 所求的最大公约数。 5.更相减损术与辗转相除法比较更相减损术与辗转相除法比较:更相减损术是作减法运算,而辗转相除法是作除法运算;更相减损术运算次数较多, 但每一次的计算都较简单。 6.秦九昭算法秦九昭算法:秦九昭算法是能求多项式函数值的一种算法。 DO 循环体 LOOP UNTIL 条件 WHILE 条件 循环体 WEND 循环体 满足条件? 循环
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号