第9知识点
- 格式：doc
- 大小：876.00 KB
- 文档页数：8
程序设计基础知识 编辑：熊韬
- 1 - 第一章 程序设计基础知识
1.1 程序与程序语言
1.1.1 语言
1、计算机语言
是人与计算机进行交流的方式，有其符合数学规范的单词、句子和含义的定义。
2、 语言的发展
第一代：机器语言 ——二进制代码，计算机母语
第二代：汇编语言——用符号表示的计算机指令（面向计算机的语言）
第三代： 高级语言——采用完全符号化的描述，用类似自然语言的形式来描述对问题的处理过程，用数学表达式的形式来描述对数据的处理过程，Pascal, C等，要求人告诉计算机怎样做。（面向过程的语言）
第四代： 非结构化语言（面向对象的语言）
第五代： 智能化语言（面向过程的语言是程序设计的基础）
1.1.2 程序设计
1 程序
计算机是一种具有内部存储能力的自动、高效的电子设备，其本质的使命就是执行指令所规定的操作。
程序＝{ 指令 }，是用计算机语言对来所要解决问题中数据以及处理问题的方法和步骤所做的完整而准确的描述。 ——这个描述过程称为程序设计
程序 = 算法 + 语言 + 数据结构
2 程序设计步骤
⑴ 分析问题，建立数学模型
将解题过程归纳为一系列的数学表达式
⑵ 确定数据结构和算法
确定存放数据的内部结构，解决问题的方法和步骤
⑶ 编制程序
用某种计算机语言把问题的解决方案严格的书写出来。
⑷ 调试程序
在计算机上用实际的输入数据对编好的程序进行测试。
3 程序涉及方面
数据结构、算法、编程语言和程序设计方法
1.2 算法和算法的表示
1.2.1 算法的概念
1 算法
是为解决一个特定的问题所采取的确定的有限的步骤。
例1：解数学题——解题的计算步骤和过程。
例2：演唱歌曲——歌谱，它规定了歌唱家如何唱歌，先唱什么，后唱什么，唱什么音阶，什么音符……。
例3：制作写字台——加工顺序：从桌腿→桌面→抽屉→组装的过程。
2 计算机算法
告诉计算机如何一步步进行操作，直至解决问题的具体步骤。包含：数值计算和非数值计算 程序设计基础知识 编辑：熊韬
- 2 - 3 设计算法的思维方法
例1—1 有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在了黑墨水瓶子里，要求将其互换。
算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以一问题的关键是需要引入第三个墨水瓶。设第三个墨水瓶为白色，其交换步骤如下：
①将黑瓶中的蓝墨水装人白瓶中；
②将蓝版中的黑墨水装入黑瓶中；
③将白瓶中的蓝墨水装入蓝瓶中；
④交换结束。
[例] 猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办理，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？
假设每天有an(n=1…10)只桃子，而我们可以看出，a1, a2, . .，a10之间存在一个简单的关系：
a9= 2 * ( a10+ 1 )
a8= 2 * ( a9+ 1 )
┇
a1= 2 * ( a2+ 1 )
也就是：ai= 2 * ( ai + 1+1) (i=9,8,7,6,...,1)
这就是此题的数学模型。
再考察上面从a9，a8直至a1的计算过程，这其实是一个递推过程，这种递推的方法在计算机解题中经常用到。另一方面，这九步运算从形式上完全一样，不同的只是ai的下标而已。
由此，我们引入循环的处理方法，并统一用a0表示前一天的桃子数，a1表示后一天的桃子数，将算法改写如下：
1) a 1=1; ｛第1 0天的桃子数，a1的初值｝
i = 9。｛计数器初值为9｝
2) a 0= 2 * ( a1+ 1 )。｛计算当天的桃子数｝
3) a 1= a0。｛将当天的桃子数作为下一次计算的初值｝
4) i=i-1。
5) 若i > = 1，转2 )。
6) 输出a0的值。
其中2 )～5 )步循环执行9次。
这就是一个从具体到抽象的过程，具体方法是：
1) 弄清如果由人来做，应该采取哪些步骤。
2) 对这些步骤进行归纳整理，抽象出数学模型。
3) 对其中的重复步骤，通过使用相同变量等方式求得形式的统一，然后简练地用循环解决
4．算法的两要素
4.1 两要素：基本功能操作 + 控制结构
4.2 计算机的基本功能操作包括以下四个方面：
(1)逻辑运算：与、或、非；
(2)算术运算：加、减、乘、除；
(3)数据比较：大于、小于、等于、不等于、大于等于
(4)数据传送：输入、输出、赋值。 程序设计基础知识 编辑：熊韬
- 3 - 4.3 算法的控制结构决定了算法的执行顺序，包括：
顺序结构、分支结构、循环结构。
1.2.2 算法的基本特征
(1)有穷性：一个算法必须在执行有限个操作步骤后终止；
(2)确定性：算法中每一步的含义必须是确切的，不可出现任何二义性；
(3)有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的，如一个数被0除的操作就是无效的，应避免。
(4)有零个或多个输入：这里的输入是指在算法开始之前所需要的初始数据。例如，例l—1的算法中有2个输入，即需要输人a和b两个初始数据，而例1—2的算法中则需要输入四个初始数据。有些特殊算法也可以没有输入。
(5)有一个或多个输出：所谓输出是指与输入有某种特定关系的量，在一个完整的算法中至少会有一个输出。如上述三个例子中都有输出。试想若例1—3中没有“输出n的当前值”这一步，则该算法将毫无意义。
1.2.3 算法的表示
原则上说，算法可以用任何形式的语言和符号来描述．通常有自然语言、程序语百、流程图、NS图、PAD团、伪代码等。第一节中的三个例子就是用自然语言来表示算法，
流程图是最早提出的用图形表示算法的工具，具有直观性强、便于阅读等特点；NS图和PAD图符合结构化程序设计要求，是软件工程中强调使用的图形工具。
1．流程图符号
由美国国家标准化协会ANSI规定了一些常用的符号．
或
或 (a) 流程线：表示算法的执行方向
(b) 注释框：表示对算法中的某操作或某部分操作所作的必要的备注说明。
(c) 连接点：表示不同地方的流程图的连接。
(d) 起止框：用以表示算法的开始或结束。
(e) 输入／输出框：表示算法的输入和输出操作。 程序设计基础知识 编辑：熊韬
- 4 -
2．用流程图表示算法
1.2.4 几种常用算法介绍
1．枚举法（穷举法）
首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况进行逐一验证，直到全部情况均通过了验证为比。若某个情况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部情况验证结果均不符合题目的全部条件，则说明该题无答案
例题1．鸡翁—，值钱五；母鸡一，值钱三；雏鸡三，值钱一；百钱买百鸡，翁、母、雏各几何？
这就是列方程：x十Y十z＝100
5x十3Y十z＝100
据题意可知，x , y , z的范围一定是0到100的正整数，则最简单的解题方法是假设一组 x ,
y , z 值，直接带入方程组求解，即在各个变量的取值范围内不断变化 x , y , z 全部可能的组(f) 处理框：算法中各种计算和赋值的操作均以处理框加以表示。
(g) 判断框：表示算法中的条件判断操作。 程序设计基础知识 编辑：熊韬
- 5 - 合，若满足方程组则是一组解。
利用枚举法解题需要以下步骤：
(1) 分析题目，确定答案的大致范围。
(2) 确定列举方法。常用的列举方法有：顺序列举，排列列举和组合列举。
(3) 作试验，直到遍历所有情况。
(4) 试验完后可能找到与题目要求完全一致的一组或多组答案，也可能没找到答案，即证明题目无答案。
枚举法的特点是算法简单，容易理解，但运算量较大。对于可确定取值范围但又找不到其它更好的算法时，就可以用枚举法。通常枚举法用来解决“有几种组合”、“是否存在”、求解不定方程等类型的问题。
利用枚举法没计算法大多以循环控制结构实现。
2．迭代法
是一种数值近似求解的方法，特点是：把一个复杂问题的求解过程转化为相对简单的迭代算式，然后重复执行这个简单的算式，直到得到最终解。
迭代法有精确迭代法和近似迭代法。所谓精确选代是指算法本身提供了问题的精确解；如对N个数求和、求均值、求方差等，这些问题都适合使用精确迭代法解决。
例l—5 计算 s=1十2+3+4十……+100
其迭代方法如下：
首先确定迭代变量 s 的初始值为0；
其次确定迭代公式 s+i→s；
当i分别取值1,2,3,4,…,100时，重复计算迭代公式 s+i→s，迭代100次后，即可求出 s 的精确值。
迭代法通常用于数值运算的求解问题
3．递推和递归法
这是程序设计中常用的两种算法，都是利用某些公式的递推性。最常见的例子是计算级数，—般给出数列后项与前项的递推公式，要求计算数列通项。
例如：
(1) f1(n)=2+fl(n—1)，f1(1)＝1 f1(n)＝{1．3，5，7，…}
——这是首项为l公差为2的等差数列(等差级数)。
(2) f2(n)＝2 × f2(n一1)，f2(1)＝1
——这是首项为1公比为2的等比数列。
(3) f3(n)＝n×f3(n一1)，f3(1)=1
——这个数列的通项f3(n)＝n！。
(4) f4(n)=f4(n—1)+f4(n一2)，f4(1)=1，f4(2)=1;
——这就是有名的斐波那契数列。
特点：在数列的未知项与已知项之间存在着一定关系，借助于已知项和这一关系，就可逐项求出未知项。
计算数列通常用递推和递归两种算法。
①递推法：是指利用递推公式，由简到繁逐次迭代求解。
例1—7 求n! 设n=15。
∵ n! ＝1 ×2 × …… × n，其算法存在如下递推过程：
f(0)＝0!＝l
f(1)＝1!=1×0!=1
f(2)＝2!＝2×1! ＝2
