a*算法流程图_高中数学知识点整理（6）——算法

一、算法的概念

1.算法概念∶

在数学上&＃xff0c;现代意义上的"算法"通常是指可以用计算机来解决的某一类问题是程序或步骤&＃xff0c;这些程序或步骤必须是明确和有效的&＃xff0c;而且能够在有限步之内完成2.算法的特点∶

&＃xff08;1&＃xff09;有限性∶一个算法的步骤序列是有限的&＃xff0c;必须在有限操作之后停止&＃xff0c;不能是无限I 的

&＃xff08;2&＃xff09;确定性∶算法中的每一步应该是确定的并且能有效地执行且得到确定的结果&＃xff0c;而不应当是模棱两可

&＃xff08;3&＃xff09;顺序性与正确性∶算法从初始步骤开始&＃xff0c;分为若干明确的步骤&＃xff0c;每一个步骤只能有一个确定的后继步骤&＃xff0c;前一步是后一步的前提&＃xff0c;只有执行完前一步才能进行下一步&＃xff0c;并且每一步都准确无误&＃xff0c;才能完成问题

&＃xff08;4&＃xff09;不唯一性∶求解某一个问题的解法不一定是唯一的&＃xff0c;对于一个问题可以有不同的算法

&＃xff08;5&＃xff09;普遍性∶很多具体的问题&＃xff0c;都可以设计合理的算法去解决&＃xff0c;如心算、计算器计算都要经过有限、事先设计好的步骤加以解决二、程序框图

1.程序构图的概念∶程序框图又称流程图&＃xff0c;是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形&＃xff0c;一个程序框图包括以下几部分∶表示相应操作的程序框;带箭头的流程线;程序框外必要文字说明

2.构成程序框的图形符号及其作用

3.画程序框图的规则如下∶

&＃xff08;1&＃xff09;使用标准的图形符号

&＃xff08;2&＃xff09;框图一般按从上到下、从左到右的方向画

&＃xff08;3&＃xff09;除判断框外&＃xff0c;大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号

&＃xff08;4&＃xff09;判断框分两大类&＃xff0c;一类判断框"是"与"否"两分支的判断&＃xff0c;而且有且仅有两个结果;另一类是多分支判断&＃xff0c;有几种不同的结果

&＃xff08;5&＃xff09;在图形符号内描述的语言要非常简练清楚

三、算法的三种基本逻辑结构∶顺序结构、条件结构、循环结构

1.顺序结构∶顺序结构是最简单的算法结构&＃xff0c;语句与语句之间&＃xff0c;框与框之间是按从上到下的顺序进行的&＃xff0c;它是由若干个依次执行的处理步骤组成的&＃xff0c;它是任何一个算法都离不开的一种基本算法结构

顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来&＃xff0c;按顺序执行算法步骤。如在示意图中&＃xff0c;A框和B框是依次执行的&＃xff0c;只有在执行完A框指定的操作后&＃xff0c;才能接着执行B框所指定的操作

2.条件结构∶

条件结构是指在算法中通过对条件的判断&＃xff0c;根据条件是否成立而选择不同流向的算法结构。条件P是否成立而选择执行A框或B框。无论P条件是否成立&＃xff0c;只能执行A框或B框之一&＃xff0c;不可能同时执行A框和B框&＃xff0c;也不可能A框、B框都不执行。一个判断结构可以有多个判断框

3.循环结构∶

在一些算法中&＃xff0c;经常会出现从某处开始&＃xff0c;按照一定条件&＃xff0c;反复执行某一处理步骤的情况&＃xff0c;这就是循环结构&＃xff0c;反复执行的处理步骤为循环体&＃xff0c;显然&＃xff0c;循环结构中一定包含条件结构。循环结构又称重复结构&＃xff0c;循环结构可细分为两类∶

&＃xff08;1&＃xff09;一类是当型循环结构&＃xff0c;如下图所示&＃xff0c;它的功能是当给定的条件P成立时&＃xff0c;执行A框&＃xff0c;A框执行完毕后&＃xff0c;再判断条件P是否成立&＃xff0c;如果仍然成立&＃xff0c;再执行A框&＃xff0c;如此反复执行A框&＃xff0c;直到某一次条件P不成立为止&＃xff0c;此时不再执行A框&＃xff0c;离开循环结构

&＃xff08;2&＃xff09;另一类是直到型循环结构&＃xff0c;如下右图所示&＃xff0c;它的功能是先执行&＃xff0c;然后判断给定的条件P是否成立&＃xff0c;如果P仍然不成立&＃xff0c;则继续执行A框&＃xff0c;直到某一次给定的条件P成立为止&＃xff0c;此时不再执行A框&＃xff0c;离开循环结构

四、输入、输出语句和赋值语句

1.输入语句

&＃xff08;1&＃xff09;输入语句的一般格式

&＃xff08;2&＃xff09;输入语句的作用是实现算法的输入信息功能

&＃xff08;3&＃xff09;"提示内容"提示用户输入什么样的信息&＃xff0c;变量是指程序在运行时其值是可以变化的量

&＃xff08;4&＃xff09;输入语句要求输入的值只能是具体的常数&＃xff0c;不能是函数、变量或表达式

&＃xff08;5&＃xff09;提示内容与变量之间用分号";"隔开&＃xff0c;若输入多个变量&＃xff0c;变量与变量之间用逗号"&＃xff0c;"隔开

2.输出语句

&＃xff08;2&＃xff09;输出语句的作用是实现算法的输出结果功能

&＃xff08;3&＃xff09;"提示内容"提示用户输入什么样的信息&＃xff0c;表达式是指程序要输出的数据

&＃xff08;4&＃xff09;输出语句可以输出常量、变量或表达式的值以及字符

3.赋值语句

&＃xff08;2&＃xff09;赋值语句的作用是将表达式所代表的值赋给变量

&＃xff08;3&＃xff09;赋值语句中的"&＃61;"称作赋值号&＃xff0c;与数学中的等号的意义是不同的。赋值号的左右两边不能对换&＃xff0c;它将赋值号右边的表达式的值赋给赋值号左边的变量

&＃xff08;4&＃xff09;赋值语句左边只能是变量名字&＃xff0c;而不是表达式&＃xff0c;右边表达式可以是一个数据、常量或算式

&＃xff08;5&＃xff09;对于一个变量可以多次赋值。

五、条件语句

1.条件语句的一般格式有两种∶&＃xff08;1&＃xff09;IF-THEN-ELSE语句&＃xff08;2&＃xff09;IF-THEN语句2IF-THEN-ELSE 语句

IF-THEN-ELSE 语句的一般格式为图 1&＃xff0c;对应的程序框图为图2

3、IF—THEN 语句

IF—THEN语句的一般格式为图3&＃xff0c;对应的程序框图为图4。

注意∶"条件"表示判断的条件;"语句"表示满足条件时执行的操作内容&＃xff0c;条件不满足时&＃xff0c;结束程序;END IF表示条件语句的结束。计算机在执行时首先对IF后的条件进行判断&＃xff0c;如果条件符合就执行THEN后边的语句&＃xff0c;若条件不符合则直接结束该条件语句&＃xff0c;转而执行其它语句

六、循环语句

循环结构是由循环语句来实现的。对应于程序框图中的两种循环结构&＃xff0c;一般程序设计语言中也有当型&＃xff08;WHILE型&＃xff09;和直到型&＃xff08;UNTIL型&＃xff09;两种语句结构。即WHILE语句和UNTIL语句1.WHILE 语句

&＃xff08;2&＃xff09;当计算机遇到WHILE语句时&＃xff0c;先判断条件的真假&＃xff0c;如果条件符合&＃xff0c;就执行WHILE与WEND之间的循环体;然后再检查上述条件&＃xff0c;如果条件仍符合&＃xff0c;再次执行循环体&＃xff0c;这个过程反复进行&＃xff0c;直到某一次条件不符合为止。这时&＃xff0c;计算机将不执行循环体&＃xff0c;直接跳到WEND语句后&＃xff0c;接着执行 WEND之后的语句。因此&＃xff0c;当型循环有时也称为"前测试型"循环。

2.UNTIL 语句

&＃xff08;2&＃xff09;直到型循环又称为"后测试型"循环&＃xff0c;从UNTIL型循环结构分析&＃xff0c;计算机执行该语句时&＃xff0c;先执行一次循环体&＃xff0c;然后进行条件的判断&＃xff0c;如果条件不满足&＃xff0c;继续返回执行循环体&＃xff0c;然后再进行条件的判断&＃xff0c;这个过程反复进行&＃xff0c;直到某一次条件满足时&＃xff0c;不再执行循环体&＃xff0c;跳到LOOPUNTIL语句后执行其他语句&＃xff0c;是先执行循环体后进行条件判断的循环语句

分析∶当型循环与直到型循环的区别∶&＃xff08;先由学生讨论再归纳&＃xff09;当型循环先判断后执行&＃xff0c;直到型循环先执行后判断

在WHILE语句中&＃xff0c;是当条件满足时执行循环体&＃xff0c;在UNTIL语句中&＃xff0c;是当条件不满足时执行循环

七、辗转相除法、更相减损术与秦九韶算法

1.辗转相除法

&＃xff08;1&＃xff09;定义∶就是对于给定的两个数&＃xff0c;用较大的数除以较小的数&＃xff0c;若余数不为零&＃xff0c;则将余数和较小的数构成新的数对。继续上面的除法&＃xff0c;直到大数被小数除尽&＃xff0c;则这时的较小数就是原来两个数的最大公约数.

&＃xff08;2&＃xff09;算法∶一般地&＃xff0c;用辗转相除法求两个正整数a&＃xff0c;b的最大公约数&＃xff0c;算法步骤∶第一步&＃xff0c;给定两个正整数 a&＃xff0c;b&＃xff08;a>b&＃xff09;第二步&＃xff0c;计算a除以b所得的余数r 第三步&＃xff0c;a&＃61;b&＃xff0c;b&＃61;T

第四步&＃xff0c;若 r&＃61;0&＃xff0c;则a&＃xff0c;b的最大公约数等于a;否则&＃xff0c;返回第二步例如∶求8251与6105这两个数最大公约数?

8251&＃61;6105×1&＃43;2146

6105&＃61;2146×2&＃43;1813

2146&＃61;1813×1&＃43;333

1813&＃61;333×5&＃43;148

333&＃61;148×2&＃43;37

148&＃61;37×4&＃43;0

2.更相减损术

&＃xff08;1&＃xff09;定义∶所谓更相减损术&＃xff0c;就是对于给定的两个数&＃xff0c;用较大的数减去较小的数&＃xff0c;然后将差和较小的数构成新的一对数&＃xff0c;再用较大的数减去较小的数&＃xff0c;反复执行此步骤直到差数和较小的数相等&＃xff0c;此时相等的两数便为原来两个数的最大公约数。

&＃xff08;2&＃xff09;算法∶一般地&＃xff0c;用更相减损术法求两个正整数a&＃xff0c;b的最大公约数&＃xff0c;算法步骤∶

第一步&＃xff0c;给定两个正整数 a&＃xff0c;b&＃xff08;&＃xff08;a→b&＃xff09;

第二步&＃xff0c;计算a-b所得的差r

第三步&＃xff0c;比较b与r的大小&＃xff0c;其中大者用a表示&＃xff0c;小者用b表示第四步&＃xff0c;若a&＃61;b&＃xff0c;则a&＃xff0c;b的最大公约数等于a;否则&＃xff0c;返回第二步例∶用更相减损术求98与63的最大公约数. 98-63&＃61;35 63-35&＃61;28 35-28&＃61;7 28-7&＃61;21 21-7&＃61;14 14-7&＃61;7

所以&＃xff0c;98和63的最大公约数等于7。