论文部分内容阅读
算法的初步知识，主要包括算法的基本思想，基本结构，基本语句等.学习中应从以前学过的典型实例中，分析其中蕴含的算法思想，体会算法通用化，机械化，程序化的特点以及对算法步骤“明确”“有效”“有限”的要求。
一．算法的基本思想.
（一）． 用自然语言描述算法的三个过程
1明确问题的性质，分析题意
2建立问题的描述模型
3设计确定算法
（二）．相关概念及特征.
1算法的定义：
广义的算法是指完成某项工作的方法和步骤，那么我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等.
在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成.
2算法的特征：
① 确定性：
算法的每一步都应当做到准确无误、“不重不漏”.“不重”是指不是可有可无的、甚至无用的步骤，“不漏” 是指缺少哪一步都无法完成任务。
② 逻辑性：
算法从开始的“第一步”直到“最后一步”之间做到环环相扣。分工明确，“前一步”是“后一步”的前提， “后一步”是“前一步”的继续.
③ 有穷性：
算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制的持续进行.
3算法的描述：
自然语言、程序框图、程序语言.
（三）．算法中的插入排序问题
1插入排序的基本思想：
经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
2 插入排序的常见方法：
(1) 有序列问题
ⅰ.直接插入法
定义：在有序列中通过逐一比较法
步骤：通过有限次的操作，将某一数据插入原有序列的一种算法。
① 将数据A与原有序列中的数据从右至左依次比较，直到发现某一数据，使得，把A插到的右边.
② 如果数据A小于原有序列中所有的数据，则将A插入到原序列的最左边.
ⅱ.有序列折半插入排序法
（1）概念：折半插入法的基本思想与二分法的思想一致，即逐渐缩小要比较的数据的范围，直到确定出所要插入数据的位置为止。
（2）步骤：
① 先将新数据与有序列中“中间位置”的数据进行比较。
② 若有序列有2n+1个数据，则”中间位置”的数据指得的第n+1个数;若有序列有2n个数据，则”中间位置”的数据指得的第n个数，
③ 如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则新数据插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应该在靠右边这一半。
④ 也就是说，一次数据的比较就排除了数据列中一半的位置，反复进行这种比较直到确定新的数据位置，像这样的插入排序法就称折半插入排序法。
(2)．无序列问题
a利用有序列插入排序法来解决.
b利用选择排序的方法来解决.例如,给定一个无序列｛23，12，56，40，98，33，56，67｝，首先从这个数据中，选出最小的数据放在第1个位置上，然后从余下的数据列中选出最小的数据放在第2个位置，反复进行上述步骤，直到数据列成为有序列，通常这种排序方法叫选择排序.
二 流程图
1 程序框图的概念
程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形；
2构成程序框的图形符号及其作用
程序框 名称 功能
起止框 表示一个算法的起始和结束，是任何算法程序框图不可缺少的。
输入、输出框 表示一个算法输入和输出的信息，可用在算法中任何需要输入、输出的位置。
处理框 赋值、计算。算法中处理数据需要的算式、公式等，它们分别写在不同的用以处理数据的处理框内。
判断框 判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时在出口处标明则标明“否”或“N”。
流程线 算法进行的前进方向以及先后顺序
循环框 用来表达算法中重复操作以及运算
连结点 连接另一页或另一部分的框图
注释框 帮助编者或阅读者理解框图
3程序框图的构成
一个程序框图包括以下几部分：实现不同算法功能的相对应的程序框；带箭头的流程线；程序框内必要的说明文字。
三 几种重要的结构
1顺序结构
顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.它是由若干个依次执行的步骤组成的，它是任何一个算法都离不开的一种基本算法结构.
见示意图和实例：
顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行算法步骤.如在示意图中，A框和B框是依次执行的，只有在执行完A框指定的操作后，才能接着执行B框所指定的操作.
2条件结构
如下面图示中虚线框内是一个条件结构，此结构中含有一个判断框，算法执行到此判断给定的条件P是否成立，选择不同的执行框（A框、B框）。无论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框，也不可能A框、B框都不执行.A框或B框中可以有一个是空的，即不执行任何操作.见示意图
3循环结构
在一些算法中要求重复执行同一操作的结构称为循环结构.即从算法某处开始，按照一定条件重复执行某一处理过程。重复执行的处理步骤称为循环体.
循环结构有两种形式：当型循环结构和直到型循环结构.
① 当型循环结构，如左下图所示，它的功能是当给定的条件P成立时，执行A框，A框执行完毕后，返回来再判断条件P是否成立，如果仍然成立，返回来再执行A框，如此反复执行A框，直到某一次返回来判断条件P不成立时为止，此时不再执行A框，离开循环结构.继续执行下面的框图。.
（陕西汉中市一厂学校）
一．算法的基本思想.
（一）． 用自然语言描述算法的三个过程
1明确问题的性质，分析题意
2建立问题的描述模型
3设计确定算法
（二）．相关概念及特征.
1算法的定义：
广义的算法是指完成某项工作的方法和步骤，那么我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等.
在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成.
2算法的特征：
① 确定性：
算法的每一步都应当做到准确无误、“不重不漏”.“不重”是指不是可有可无的、甚至无用的步骤，“不漏” 是指缺少哪一步都无法完成任务。
② 逻辑性：
算法从开始的“第一步”直到“最后一步”之间做到环环相扣。分工明确，“前一步”是“后一步”的前提， “后一步”是“前一步”的继续.
③ 有穷性：
算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制的持续进行.
3算法的描述：
自然语言、程序框图、程序语言.
（三）．算法中的插入排序问题
1插入排序的基本思想：
经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
2 插入排序的常见方法：
(1) 有序列问题
ⅰ.直接插入法
定义：在有序列中通过逐一比较法
步骤：通过有限次的操作，将某一数据插入原有序列的一种算法。
① 将数据A与原有序列中的数据从右至左依次比较，直到发现某一数据，使得，把A插到的右边.
② 如果数据A小于原有序列中所有的数据，则将A插入到原序列的最左边.
ⅱ.有序列折半插入排序法
（1）概念：折半插入法的基本思想与二分法的思想一致，即逐渐缩小要比较的数据的范围，直到确定出所要插入数据的位置为止。
（2）步骤：
① 先将新数据与有序列中“中间位置”的数据进行比较。
② 若有序列有2n+1个数据，则”中间位置”的数据指得的第n+1个数;若有序列有2n个数据，则”中间位置”的数据指得的第n个数，
③ 如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则新数据插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应该在靠右边这一半。
④ 也就是说，一次数据的比较就排除了数据列中一半的位置，反复进行这种比较直到确定新的数据位置，像这样的插入排序法就称折半插入排序法。
(2)．无序列问题
a利用有序列插入排序法来解决.
b利用选择排序的方法来解决.例如,给定一个无序列｛23，12，56，40，98，33，56，67｝，首先从这个数据中，选出最小的数据放在第1个位置上，然后从余下的数据列中选出最小的数据放在第2个位置，反复进行上述步骤，直到数据列成为有序列，通常这种排序方法叫选择排序.
二 流程图
1 程序框图的概念
程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形；
2构成程序框的图形符号及其作用
程序框 名称 功能
起止框 表示一个算法的起始和结束，是任何算法程序框图不可缺少的。
输入、输出框 表示一个算法输入和输出的信息，可用在算法中任何需要输入、输出的位置。
处理框 赋值、计算。算法中处理数据需要的算式、公式等，它们分别写在不同的用以处理数据的处理框内。
判断框 判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时在出口处标明则标明“否”或“N”。
流程线 算法进行的前进方向以及先后顺序
循环框 用来表达算法中重复操作以及运算
连结点 连接另一页或另一部分的框图
注释框 帮助编者或阅读者理解框图
3程序框图的构成
一个程序框图包括以下几部分：实现不同算法功能的相对应的程序框；带箭头的流程线；程序框内必要的说明文字。
三 几种重要的结构
1顺序结构
顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.它是由若干个依次执行的步骤组成的，它是任何一个算法都离不开的一种基本算法结构.
见示意图和实例：
顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行算法步骤.如在示意图中，A框和B框是依次执行的，只有在执行完A框指定的操作后，才能接着执行B框所指定的操作.
2条件结构
如下面图示中虚线框内是一个条件结构，此结构中含有一个判断框，算法执行到此判断给定的条件P是否成立，选择不同的执行框（A框、B框）。无论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框，也不可能A框、B框都不执行.A框或B框中可以有一个是空的，即不执行任何操作.见示意图
3循环结构
在一些算法中要求重复执行同一操作的结构称为循环结构.即从算法某处开始，按照一定条件重复执行某一处理过程。重复执行的处理步骤称为循环体.
循环结构有两种形式：当型循环结构和直到型循环结构.
① 当型循环结构，如左下图所示，它的功能是当给定的条件P成立时，执行A框，A框执行完毕后，返回来再判断条件P是否成立，如果仍然成立，返回来再执行A框，如此反复执行A框，直到某一次返回来判断条件P不成立时为止，此时不再执行A框，离开循环结构.继续执行下面的框图。.
（陕西汉中市一厂学校）