1、第一章 算法初步一、算法与程序框图1算法的概念：按照一定规则解决某一类问题的明确和有限的步骤2算法的三个基本特征：明确性，有限性，有序性3程序框图：也称流程图，是一种用程序框、流程线及文字说明来表示算法的图形图形符号名称功能终端框表示一个算法的起始和结束输入（输出框）表示一个算法输入和输出的信息处理框赋值、计算判断框判断某一个条件是否成立，成立时在出口处标明“是”或“Y”，不成立时标明“否”或“N”流程线连接程序框连接点连接程序框图的两部分4三种程序框图（1）顺序结构： （2）条件结构：2种IF-THEN-ELSE格式 IF-THEN格式： （3）循环结构：直到型循环结构（先执行，后判断），当
2、型循环结构（先判断，后执行）注意：一个完整的循环结构，应该包括三个内容：1）循环体；2）循环判断语句；3）与循环判断语句相关的变量 当型（WHILE型）循环结构示意图 直到型（UNTIL型）循环结构示意图： 例1如图x1，x2，x3为某次考试三个评阅人对同一道题的独立评分，p为该题的最终得分当x16，x29，p8.5时，x3等于()A10B7C8D11答案：C解析：x16，x29，|x2x1|32，输入x3，假设|x3x1|x3x2|成立，即|x36|x39|，解得x37.5，把x3赋值给x2，p8.5，解得x311，与x37.5矛盾，舍去；假设|x3x1|x3x2|成立，即|x36|x39|
3、，解得x37.5，把x3赋值给x1，p8.5，解得x38，符合要求例2右图给出的是计算的值的一个程序框图，其中判断框内应填入的条件是()Ai20？Bi10？Ci10？Di10?答案：D解析：i1，S；i2，S；i3，S；依次下去：i10，S，故选D例3 根据右边的图，当输入x为2006时，输出的y()A28B10 C4 D2答案：B解析：初始条件：x2006；第1次运行：x2004；第2次运行：x2002；第3次运行：x2000；第1003次运行：x0；第1004次运行：x2，不满足条件x0，停止运行，所以输出的y32110，故选B二、基本算法语句（一定要注意各种算法语句的正确格式）1输入语句
4、 注意：提示内容用双引号标明，并与变量用分号隔开INPUT “提示内容”； 表达式2输出语句 PRINT “提示内容”； 表达式3赋值语句 注意：“=”的含义是赋值，将右边的值赋予左边的变量变量 = 表达式 4条件语句 IF 条件 THEN语句体END IFIF 条件 THEN语句体1ELSE 语句体2END IF5循环语句：直到型 当型WHILE条件循环体WEND DO循环体LOOPUNTIL条件6常用的数学符号与程序符号的对照表数学符号程序符号举例运算符号乘号：*ab表示为a*b除号：/表示为5/3乘方：abab32表示32取m除以n的余数m MOD n7除以2的余数表示为7 MOD 2取
5、m除以n的商mn7除以2的商表示为72函数符号绝对值函数：|x|ABS(x)|3|表示为ABS(3)平方根函数：SQR(x)表示为SQR(8)取整函数：取不大于x的最大整数INT(x)INT(15/4)3例1如图程序中，输出的是4，则输入的x可以是()A8B4C8D16答案：D解析：本题考查条件语句的基本结构和功能程序实现了函数y的功能；当输出4时，则4，故输入的x16，故选D例2下列程序的功能是()S1i1WHILES100END(1)试将上面的程序补充完整(2)改写为WHILE型循环语句解析：(1)m0ii1(2)改写为WHILE型循环程序如下：i1WHILEi100mi MOD 2IFm
6、0THENPRINTiENDIFii1WENDEND三、算法案例1辗转相除法利用辗转相除法求最大公约数的步骤如下：）用较大的数m除以较小的数n得到一个商和一个余数；）若0，则n为m，n的最大公约数；若0，则用除数n除以余数得到一个商和一个余数；）若0，则为m，n的最大公约数；若0，则用除数除以余数得到一个商和一个余数；依次计算直至0，此时所得到的即为所求的最大公约数例1求2146与1813的最大公约数214618131333 18133335148 3331482371483740 余数为0时计算终止，所以37为最大公约数2更相减损术利用更相减损术求最大公约数的步骤如下：）任意给出两个正数；判
7、断它们是否都是偶数，若是，用2约分；若不是，执行第二步）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数3秦九韶算法：将改写成再由内及外逐层计算注意：包含的加法、乘法、乘方次数分别为n，n，0例1用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x的值，当x3时，v3的值为()A27B86C262D789答案：C解析：多项式变形为：f(x)(7x6)x5)x4)x3)x2)x1)x，v07，v173627，v2273586，v386342624进位制：一般地，若k是一个大于1的整数，那么以k为基数的k进制可以表示为：例1将三进制数化为十进制数解：例2将十进制数104化为三进制数（除k取余法）解：1043342 最先出现的余数是三进制数的最右一位 3431111133233101301商数为0时计算终止，最后出现的余数是三进制数的最左一位 所以十进制数104化为三进制数为本章整合