算法初步
- 格式：doc
- 大小：81.00 KB
- 文档页数：6
1 算法初步
一、知识概述
主要学习了算法初步，首先引出了算法的描述性的定义及算法的主要特征，然后借助例题进一步展现这些特征．程序框图能够更加直观、清楚地描述算法步骤．用算法语句描述算法是用计算机解决问题的前提条件，而一般的操作顺序是先设计算法，接着用程序框图表示算法，然后将程序框图转化为算法语句．本节按照三种基本的逻辑结构的顺序，分别介绍了相关的基本的算法语句，其中包含了与相应程序框图比较、把程序框图转化为算法语句的过程．最后学习了算法案例，了解经典的算法案例有助于学生深入理解算法的特征和进一步体会算法的思想．
二、重难点知识归纳
（一）算法的基本概念
1、算法定义描述：在数学中，现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成．
2、算法的特性：
①有穷性：一个算法的步骤序列是有限的，它应在有限步操作之后停止，而不能是无限的．
②确定性：算法中的每一步应该是确定的并且能有效地执行且得到确定的结果，而不应当是模棱两可．
③可行性：算法中的每一步操作都必须是可执行的，也就是说算法中的每一步都能通过手工和机器在有限时间内完成．
④输入：一个算法中有零个或多个输入．
⑤输出：一个算法中有一个或多个输出．
（二）三种基本逻辑结构
1、顺序结构：顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的，它是由若干个依次执行的处理步骤组成的，它是任何一个算法都离不开的一种基本算法结构．
2、条件结构：条件结构是指在算法中通过对条件的判断，根据条件是否成立而选择不同流向的算法结构．
3、循环结构：在一些算法中，经常会出现从某处开始，按照一定条件，反复执行某一处理步骤的情况，这就是循环结构，反复执行的处理步骤为循环体，显然，循环结构中一定包含条件结构．循环结构又称重复结构，循环结构可细分为两类：
（1）当型循环结构：每次执行循环体前对循环条件进行判断，当条件满足时执行循环体，不满足时停止．
（2）直到型循环结构：执行了一次循环体之后，对控制循环条件进行判断，当条件不满足时执行循环体，满足则停止．
（三）基本算法语句
1、输入语句
2、输出语句
2 3、赋值语句
注意：赋值语句中的“＝”叫做赋值号，它和数学中的等号不同，计算机执行赋值语句时，先计算“＝”右边表达式的值，然后把这个值赋给“＝”左边的变量．
4、条件语句
当计算机执行上述语句时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句1，否则执行ELSE后的语句2．其对应的程序框图为：（如上右图）
计算机执行这种形式的条件语句时，也是首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句，如果条件不符合，则直接结束该条件语句，转而执行其他语句．其对应的程序框图为：（如上右图）
5、循环语句
（1）WHILE语句
其中循环体是由计算机反复执行的一组语句构成的．WHLIE后面的“条件”是用于控制计算机执行循环体或跳出循环体的． 3 当计算机遇到WHILE语句时，先判断条件的真假，如果条件符合，就执行WHILE与WEND之间的循环体；然后再检查上述条件，如果条件仍符合，再次执行循环体，这个过程反复进行，直到某一次条件不符合为止．这时，计算机将不执行循环体，直接跳到WEND语句后，接着执行WEND之后的语句．因此，当型循环有时也称为“前测试型”循环．其对应的程序结构框图为：（如上右图）
（2）UNTIL语句
当计算机遇到UNTIL语句时，先判断条件的真假，如果条件不符合，就执行DO与LOOP UNTIL之间的循环体；然后再检查上述条件，如果条件仍不符合，再次执行循环体，直到某一次符合条件时停止．其对应的程序结构框图为：（如上右图）
（四）算法案例
1、辗转相除法与更相减损术
辗转相除法与更相减损术的区别：
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显．
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到．
2、秦九韶算法
3、进位制
进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值．可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制．现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数．
三、典型例题剖析
例1、设计求|x－2|的算法，并画出流程图．
解：算法如下：
⑴ 若x<2，则|x－2|等于2－x，
⑵ 若x≥2，则|x－2|等于x－2．
其流程图如图： 4
例2、（I）用辗转相除法求840与1764的最大公约数．
（II）用更相减损术求440 与556的最大公约数．
解：（I）用辗转相除法求840与1764 的最大公约数．
1764 = 840×2＋84；
840 = 84×10＋0．
所以840与1764 的最大公约数是84.
（II）用更相减损术求440 与556的最大公约数．
556－440 = 116；440－116 = 324；324－116 = 208；208－116 = 92；
116－92 = 24；92－24 = 68；68－24 = 44；44－24 = 20；24－20 = 4；
20－4 = 16；16－4 = 12；12－4 = 8；8－4 = 4．
所以440 与556的最大公约数4．
例3、设计算法求的值．要求画出程序框图，写出用基本语句编写的程序．
解：这是一个累加求和问题，共99项相加，可设计一个计数变量，一个累加变量，用循环结构实现这一算法．程序框图如下图所示： 5
例4、已知函数, 编写一程序求函数值．
解:
例5、有10个互不相等的数，写出找出其中一个最大数的算法和程序．
解：(一)算法
S1：输入一个数，放在MAX中
S2：i=1
S3：输入第1个数，放入x中
S4：若x>MAX，则MAX=x
S5: i=i＋1
S6：若i≤9，返回S3继续执行，否则停．
(二)程序框图 6
