2023年4月19日发(作者：50岁生日)第一章 算法初步
一．算法的概念
1.算法的概念
1、算法定义：在数学上，现代意义上的“算法”通常是指可以用计算机来解决的某一类问题是程序或步骤，这些程
序或步骤必须是明确和有效的，而且能够在有限步之内完成.
2. 算法的特点:
(1)有穷性：一个算法在执行有限个步骤之后，必须结束.
(2)确定性：算法的每一个步骤和次序应该是确定的.
(3)可行性：原则上算法能够精确地元算，而且人们用笔和纸做有限次即可完成.
(4)不唯一性：求解某一个问题的解法不一定是唯一的，对于一个问题可以有不同的算法.
(5)输出：一个算法有0个或多个输入，以刻画运算对象的初始条件.所谓0个输入是指算法本身已经给出了初始
条件.
(6)输出：一个算法有1个或多个输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的.
3．算法的描述：自然语言、程序框图、程序语言。
例1、写出123456的一个算法.
解:按照逐一相乘的程序进行
第一步:计算12,得到2；
第二步:将第一步的运算结果2与3相乘,得到6；
第三步: 将第二步的运算结果6与4相乘,得到24；
第四步小猫的图片
: 将第三步的运算结果24与5相乘,得到120；
第五步: 将第四的运算结果120与6相乘,得到720；
第六步:输出结果.
例2、写出按从小到大的顺序重新排列三个数值的算法.
x,y,z
解:（1）.输入三个数值；
x,y,z
（2）.从三个数值中挑出最小者并换到中；
x
（3）.从中挑出最小者并换到中；
y,z
y
（4）.输出排序的结果.
二．程序框图
1、程序框图基本概念：
（一）程序构图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示
算法的图形。
一个程序框图包括以下几部分：表示相应操作的程序框；带箭头的流程线；程序框外必要文字说明。
（二）构成程序框的图形符号及其作用
程序框 名称 功能
表示一个算法的起始和结束，是任何流程图
起止框
不可少的。
表示一个算法输入和输出的信息，可用在算
输入、输出框
法中任何需要输入、输出的位置。
赋值、计算，算法中处理数据需要的算式、
处理框 公式等分别写在不同的用以处理数据的处
理框内。
判断某一条件是否成立，成立时在出口处标
判断框
明“是”或“Y”；不成立时标明“否”或“N”。
学习这部分知识的时候，要掌握各个图形的形状、作用及使用规则，画程序框图的规则如下：
1、使用标准的图形符号。
2、框图一般按从上到下、从左到右的方向画。
3、除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号。
4、判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几
种不同的结果。
5、在图形符号内描述的语言要非常简练清楚。
开始
输出
y
输入
x
x
≥0?
Y
N
yx1
2
y2x1
结束
（三）、算法的三种基本逻辑结构：顺序结构、条件结构、循环结构。
1、顺序结构：
2、条件结构：
步骤n
步骤n+1
我的姥姥
3、循山楂荷叶茶的功效
环结构：
注意：1循环结构要在某个条件下终止循环，这就需要条件结构来判断。因此，循环结构中一定包含条件
结构，但不允许“死循环”。
2在循环结构中都有一个计数变量和累加变量。计数变量用于记录循环次数，累加变量用于输出结果 。计数
变量和累加变量一般是同步执行的，累加一次，计数一次。
例、设计一个计算1+2+3+……+100的值得算法，并画出程序框图。
三．输入、输出语句和赋值语句
1、输入语句
图形计算器
INPUT“提示内容”；变量 INPUT “提示内容”，变量
格式
2、输出语句
图形计算器
PRINT“提示内容”；表达式
格式
Disp “提示内容”，变量
3、赋值语句
图形计算器
变量＝表达式
格式
表达式变量
四．条件语句
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
图1 图2
3、IF—THEN语句 IF—THEN语句的一般格式为图3，对应的程序框图为图4。
IF 条件 THEN
语句
END IF
（图3）
（图4）
否
满足条件？
是
语句
五．循环语句
循环结构是由循环语句来实现的。对应于程序框图中的两种循环结构，一般程序设计语言中也有当型（WHILE型）
和直到型（UNTIL型）两种语句结构。即WHILE语句和UNTIL语句。
1、WHILE语句
WHILE 条件
循环体
WHILE语句的一般格式是 对应的程序框图是
WEND
满足条件？
否
是
循环
2、UNTIL语句
DO
循环
否
满足条件？
是
UNTIL语句的一般格式是 对寄情山水
应的程序框图是
循环体
LOOP UNTIL 条件
六．算法案例
1、辗转相除法与更相减损术
（1）、辗转相除法。也叫欧几里德算法，用辗转相除法求最大公约数的步骤如下：
（1）：给定两个正整数m，n；
（2）：计算m除以n所得的余数r；
（3）：m=n，n=r；
（4）若r=0，则m，n的最大公约数等于m；否则，返回第二步。
（2）、更相减损术
我国早期也有求最大公约数问题的算法，就是更相减损术。在《九章算术》中有更相减损术求最大公约数的步骤：
可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之。
翻译为：（1）：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
（2）：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直
到所得的数相等为止，则这个数（等数）就是所求的最大公约数。
2、秦九韶算法与排序
nn-1
1、秦九韶算法概念：求值问题
f(x)=ax+ax+….+ax+a
nn-110
把一个n次多项式改写成如下形式：
f(x)=ax+ax+….李清照画像
+ax+a
nn-110
nn-1
nn-1
f(x)=ax+ax+….+ax+a
nn-110
=( ax+ax+….+a)x+a
nn-110
=(( ax+ax+….+a)x+a)x+a
nn-1210
n-2n-3
n-1n-2
=......
=(...( ax+a)x+a)x+...+a)x+a
nn-1n-210
求多项式的值时，首先计算最内层括号内依次多项式的值，即然后由内向外逐层计算一次多项式
v=ax+a
1nn-1
的值，即
v=vx+a v=vx+a ...... v=vx+a
21n-2 32n-3 nn-10
这样，把n次多项式的求值普通话分数等级划分
问题转化成求n个一次多项式的值的问题。
例1、已知一个5次多项式为f(x)5x2x3.5x2.6x1.7x0.8.
5432
用秦九韶算法求这个多项式当x5时的值.
f(x)=((((5x2)x3.5)x2.6)x1.7)x0.8.
v5;
0
v55227;
1
v2753.5138.5;
2
v138.552.6689.9;
3
v689.951.73451.2;
4
v3451.250.817255.2.
5
所以，当x=5时，多项式的值等于17255.2.
例2、
例3、
3、进位制
概念：进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基
数为n，即可称n进位制，简称n进制。现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数。
对于任何一个数，我们可以用不同的进位制来表示。比如：十进数57，可以用二进制表示为111001，也可以
用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的。
一般地，若k是一个大于一的整数，那么以k为基数的k进制可以表示为： ，
aa...aa(0ak,0a,...,a,ak)
nn110(k)nn110
而表示各种进位制数一般在数字右下脚加注来表示,如111001表示二进制数,34表示5进制数
(2)(5)
⑴把十进制转化为别的进制
例、把89化为二进制.
把上式中个步所得的余数从下到上排列，得到89=1011001.
2
⑵把别的进制转化为十进制
例、把二进110011制化为十进制.
(2)
110011121202021212
(2)
543210
321621
德国皇帝
51
⑶把别的进制转化为别的进制
别的进制十进制别的进制
