第一章算法初步

1.1.1算法的概念

1、算法概念：

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

2. 算法的特点:

(1)有限性：一个算法的步骤序列是有限的，必须在有限操作之后停止，不能是无限的.

(2)确定性：算法中的每一步应该是确定的并且能有效地执行且得到确定的结果，而不应当是模棱两可.

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

(4)不唯一性：求解某一个问题的解法不一定是唯一的，对于一个问题可以有不同的算法.

(5)普遍性：很多具体的问题，都可以设计合理的算法去解决，如心算、计算器计算都要经过有限、事先设计好的步骤加以解决.

1.1.2 程序框图

1、程序框图基本概念：

（一）程序构图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形。

一个程序框图包括以下几部分：表示相应操作的程序框；带箭头的流程线；程序框外必要文字说明。学习这部分知识的时候，要掌握各个图形的形状、作用及使用规则，画程序框图的规则如下：

1、使用标准的图形符号。2、框图一般按从上到下、从左到右的方向画。3、除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号。4、判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果。5、在图形符号内描述的语言要非常简练清楚。

（二）构成程序框的图形符号及其作用

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

顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，

按顺序执行算法步骤。如在示意图中，A框和B框是依次执行的，只有在

执行完A框指定的操作后，才能接着执行B框所指定的操作。

2、条件结构：

条件结构是指在算法中通过对条件的判断

根据条件是否成立而选择不同流向的算法结构。

条件P是否成立而选择执行A框或B框。无论P条件是否成立，只能执行A框或B框之一，不可能同时执行A框和B框，也不可能A框、B框都不执行。一个判断结构可以有多个判断框。

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

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

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

p

当型循环结构                            直到型循环结构

注意：1循环结构要在某个条件下终止循环，这就需要条件结构来判断。因此，循环结构中一定包含条件结构，但不允许“死循环”。2在循环结构中都有一个计数变量和累加变量。计数变量用于记录循环次数，累加变量用于输出结果。计数变量和累加变量一般是同步执行的，累加一次，计数一次。

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

1、输入语句

（1）输入语句的一般格式

（2）输入语句的作用是实现算法的输入信息功能；（3）“提示内容”提示用户输入什么样的信息，变量是指程序在运行时其值是可以变化的量；（4）输入语句要求输入的值只能是具体的常数，不能是函数、变量或表达式；（5）提示内容与变量之间用分号“；”隔开，若输入多个变量，变量与变量之间用逗号“，”隔开。

2、输出语句

（1）输出语句的一般格式

（2）输出语句的作用是实现算法的输出结果功能；（3）“提示内容”提示用户输入什么样的信息，表达式是指程序要输出的数据；（4）输出语句可以输出常量、变量或表达式的值以及字符。

3、赋值语句

（1）赋值语句的一般格式

（2）赋值语句的作用是将表达式所代表的值赋给变量；（3）赋值语句中的“＝”称作赋值号，与数学中的等号的意义是不同的。赋值号的左右两边不能对换，它将赋值号右边的表达式的值赋给赋值号左边的变量；（4）赋值语句左边只能是变量名字，而不是表达式，右边表达式可以是一个数据、常量或算式；（5）对于一个变量可以多次赋值。

注意：①赋值号左边只能是变量名字，而不能是表达式。如：2=X是错误的。②赋值号左右不能对换。如“A=B”“B=A”的含义运行结果是不同的。③不能利用赋值语句进行代数式的演算。（如化简、因式分解、解方程等）④赋值号“=”与数学中的等号意义不同。

1．2．2条件语句

1、条件语句的一般格式有两种：（1）IF—THEN—ELSE语句；（2）IF—THEN语句。2、IF—THEN—ELSE语句

IF—THEN—ELSE语句的一般格式为图1，对应的程序框图为图2。

IF  条件  THEN

语句1

ELSE

语句2

END IF

图1                                          图2

分析：在IF—THEN—ELSE语句中，“条件”表示判断的条件，“语句1”表示满足条件时执行的操作内容；“语句2”表示不满足条件时执行的操作内容；END  IF表示条件语句的结束。计算机在执行时，首先对IF后的条件进行判断，如果条件符合，则执行THEN后面的语句1；若条件不符合，则执行ELSE后面的语句2。

3、IF—THEN语句

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

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

1．2．3循环语句

循环结构是由循环语句来实现的。对应于程序框图中的两种循环结构，一般程序设计语言中也有当型（WHILE型）和直到型（UNTIL型）两种语句结构。即WHILE语句和UNTIL语句。

1、WHILE语句

（1）WHILE语句的一般格式是            对应的程序框图是

WHILE  条件

循环体

WEND

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

2、UNTIL语句

（1）UNTIL语句的一般格式是                对应的程序框图是

DO

循环体

LOOP  UNTIL  条件

（2）直到型循环又称为“后测试型”循环，从UNTIL型循环结构分析，计算机执行该语句时，先执行一次循环体，然后进行条件的判断，如果条件不满足，继续返回执行循环体，然后再进行条件的判断，这个过程反复进行，直到某一次条件满足时，不再执行循环体，跳到LOOP UNTIL语句后执行其他语句，是先执行循环体后进行条件判断的循环语句。

分析：当型循环与直到型循环的区别：

（1）当型循环先判断后执行，直到型循环先执行后判断；

在WHILE语句中，是当条件满足时执行循环体，在UNTIL语句中，是当条件不满足时执行循环

1.3.1辗转相除法与更相减损术

1、辗转相除法。

2、更相减损术

我国早期也有求最大公约数问题的算法，就是更相减损术。在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之。

翻译为：（1）：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。（2）：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。

例2 用更相减损术求98与63的最大公约数

3、辗转相除法与更相减损术的区别：

（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到

1.3.2秦九韶算法与排序

1、秦九韶算法概念：

f(x)=anxn+an-1xn-1+….+a1x+a0求值问题

f(x)=anxn+an-1xn-1+….+a1x+a0=( anxn-1+an-1xn-2+….+a1)x+a0 =(( anxn-2+an-1xn-3+….+a2)x+a1)x+a0

    =......=(...( anx+an-1)x+an-2)x+...+a1)x+a0

求多项式的值时，首先计算最内层括号内依次多项式的值，即v1=anx+an-1

然后由内向外逐层计算一次多项式的值，即

v2=v1x+an-2     v3=v2x+an-3   ......      vn=vn-1x+a0

这样，把n次多项式的求值问题转化成求n个一次多项式的值的问题。

1.3.3进位制

1、概念：进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数。对于任何一个数，我们可以用不同的进位制来表示。比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的。

一般地，若k是一个大于一的整数，那么以k为基数的k进制可以表示为：

，

而表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数

数学必修3第一章《算法初步》微型试卷

一、选择题：本大题共10小题，每小题4分，共40分．在每小题给出的四处备选项中，只有一项是符合题目要求的．

1．算法的三种基本结构是(    )

   （A）顺序结构、条件结构、循环结构      （B）顺序结构、循环结构、模块结构

   （C）顺序结构、模块结构、条件结构      （D）模块结构、条件结构、循环结构

2．将两个数a=25，b=9交换，使a=9，b=25，下面语句正确一组是 (    )

（A）           （B）           （C）             （D）

a=b

b=a

a = c

c = b

b = a

t = b

b = a

a = t

b=a

a=b

3．下列各数中，最小的数是（     ）。

   （A）111 111（2）      （B）105（8）      （C）200（6）      （D）75

4．下列给变量赋值的语句正确的是（  ）

（A）5＝a        （B）a＋2＝a      （C）a＝b＝4     （D）a＝2*a

5．下面程序运行后，a，b，c的值各等于    （   ）

a = 3

b = - 5

c = 8

a = b

b = c

c = a

PRINT  a, b, c

END

(A) –5,8,-5          (B) –5,8,3         (C) 8,–5,3      (D) 8,–5,8

6．为了在运行下面的程序之后得到输出y＝16，键盘输入x应该是（    ）。

        Input x

If x<0 then

y=(x+1)(x+1) 

Else 

y=(x-1)(x-1) 

        End if

Print y

End

(A) 3或-3            (B) -5           (C) -5或5         (D) 5或-3

7．读两段程序：

甲：i=1                乙：i=1000

S=0                       S=0

WHILE i<=1000           DO

S=S+i                     S=S+i

i=i+1                     i=i-1

WEND                   LOOP UNTIL i<1

PRINT S                   PRINT S

END                       END

对甲、乙程序和输出结果判断正确的是（     ）

（A）程序不同，结果不同              （B）程序不同，结果相同

（C）程序相同，结果不同              （D）程序相同，结果相同

8．用二分法求方程的近似根，精确度为δ，用直到型循环结构的终止条件是（    ）。

（A）|x1－x2|＞δ   （B）|x1－x2|＜δ   （C）x1＜δ＜x2   （D）x1=x2=δ

9．给出下面的程序框图，那么其循环体执行的次数是   （   ） 

(A) 500            (B) 499             (C) 1000             (D) 998

i=12

s=1

DO

   s = s * i

   i = i－1

LOOP UNTIL   条 件 

PRINT  s

END

（第10题）程序

否

是

（第9题）

10．已知有上面程序，如果程序执行后输出的结果是11880，那么在程序UNTIL后面的“条件”应为 (     )

(A) i > 9 (B) i >= 9 (C) i <= 8 (D) i < 8

二、填空题：本大题共5小题，每小题4分，共20分．把答案填在题中相应的横线上．

11．下列四个有关算法的说法中，正确的是                . ( 要求只填写序号 )

    (1) 算法的某些步骤可以不明确或有歧义，以便使算法能解决更多问题；

    (2) 正确的算法执行后一定得到确定的结果；

    (3) 解决某类问题的算法不一定是唯一的；

    (4) 正确的算法一定能在有限步之内结束。

12．右边的程序框图（如图所示），

能判断任意输入的整数x是奇数

或是偶数。其中判断框内的条件

是________________。

程序2如下：

i = 51

sum = 0

do  

     sum=sum＋i 

       i = i＋1

loop until i > 50

print  sum

end

程序1如下：

i = 51

sum = 0

while i <= 50

     sum=sum＋i 

       i = i＋1

wend

print  sum

end

13．已知有如下两段QBasic程序：

问：程序1运行的结果为_______________。   程序2运行的结果为_______________。

14．把下面求n！（ n!= n×(n-1)×……×3×2×1 ）的程序补充完整

________________“n＝”；n

i＝1

s＝1

WHILE _______________

_________________

i = i+1

WEND

PRINT  s

END

15.给出50个数，1，2，4，7，11，…，其规律是：第1个数是1，第2个数比第1个数大1，第3个数比第2个数大2，第4个数比第3个数大3，…，以此类推. 要求计算这50个数的和. 先将下面给出的程序框图补充完整，再根据程序框图写出程序.

         1. 把程序框图补充完整：

           （1）________________________ 

           （2）________________________ 

         2. 程序：下载本文