第2章 算法的概念

算法的概念——知能阐释一、知识精讲1．算法的含义算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或看成按要求设计好的有限的确切的计算序列，并且这样的步骤或序列能够解决一类问题。

说明：（1）算法一般是机械的，有时要进行大量的重复计算，只要按部就班地去做，总能算出结果。

通常把算法过程称为“数学机械化”，数学机械化的最大优点，是它可以让计算机来完成。

（2）实际上，处理任何问题都需要算法，中国象棋有中国象棋的棋谱，国际象棋有国际象棋的棋谱。

再比如，邮寄物品有其相应的手续，购买飞机票也有一系列的手续等等。

（3）求解某个问题的算法不唯一。

2．算法的特征（1）确定性：算法的每一步必须是确切定义的，且无二意性，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。

（2）有容性：一个算法必须在执行有穷次运算后结束，在所规定的时间和空间内，若不能获得正确结果，其算法也是不能被采用的。

（3）可行性：算法中的每一个步骤都必须能用实现算法的工具——可执行指令精确表达，并在有限步骤内完成，否则这种算法也是不会被采纳的。

（4）算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤。

（5）有输出，算法一定能得到问题的解，有一个或多个结果输出，达到求解问题的目的，没有输出结果的算法是没有意义的。

3．算法的描述（1）自然语言：自然语言就是人们日常使用的语言，可以是汉语、英语或数学语言等。

用自然语言描述算法的优点是通俗易懂，当算法中的操作步骤都是顺序执行时比较容易理解。

缺点是如果算法中包含判断或转向，并且操作步骤较多时，就不那么直观清晰了。

（2）框图（流程图）：所谓框图，就是指用规定的图形符号来描述算法，用框图描述算法，具有直观、结构清晰、条理分明、通俗易懂、便于检查修改及交流等优点。

（3）程序设计语言：算法最终可通过程序的形式编写出来，并在计算机上执行。

程序设计语言可分为低级语言和高级语言，低级语言包括机器语言和汇编语言。

2.1算法的概念及描述教案一、教材分析本节教学内容选自高中信息技术必修一浙教版（2019）的第二章第一节，本章主要要使学生掌握算法的特征及概念，本章必须为学生打好基础，让学生必须理解算法的概念及描述方式，打好基础后，才能为后面学习Python语言做好铺垫。

二、学情分析学生在第一章学习数据与大数据中已经基本的对数据有了一些了解，本章主要涉及到的是算法，学生在初中时简单学过Python语言，对于算法可能有了简单的理解，但并不清楚它是什么，本节的重点就是要让学生明确算法的概念及特征，为后面学习的Python语言做好铺垫，本节内容多运用案例，加深学生对算法的认识与理解。

三、教学目标（1）掌握并理解算法的定义（2）掌握算法的特征（3）了解算法的要素（4）掌握并能分辨算法的描述方式四、教学重难点重点：掌握并理解算法的定义。

难点：掌握并能分辨算法的描述方式。

五、教学过程（一）新课导入以高一新生报到流程进行导入，引导学生根据流程图能说出具体的流程，让学生知道，这种，某个任务的一系列步骤集合就是算法。

由此引出算法。

（二）讲授新课让学生带着问题去阅读书上38、39页的内容，从阅读中找出算法的定义，阅读后请同学上来分享算法的定义，“算法是指解决问题或完成任务的一系列步骤集合”，并请学生举出例子。

根据一个例子，带领学生学习算法的特征，引出算法的有穷性。

之后再引出算法的其他特征，即可行性、确定性、0个或多个输入、一个或多个输出，这里老师需向学生重点区分输入和输出数量的不同，算法可以没有输入，但是必须要有输出。

之后用洗衣机的例子，为学生讲述算法的三要素，即数据、运算、控制转移。

在讲述算法的描述方式时，可以先让学生阅读算法描述方式的定义，其中，重点在于算法的描述方式是被算法执行者理解并执行的，这里可以重点讲下算法执行者是人或机器，也就是说，算法的描述方式是让人或机器去理解的，由此引出四种描述方式。

第一种——自然语言，也就是人们在日常生活中所运用的语言。

算法分析(第二章)：递归与分治法一、递归的概念知识再现：等比数列求和公式：1、定义：直接或间接地调用自身的算法称为递归算法。

用函数自身给出定义的函数称为递归函数。

2、与分治法的关系：由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

这自然导致递归过程的产生。

分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。

3、递推方程：(1)定义：设序列01,....na a a简记为{na}，把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。

(2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。

4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

二、递归算法改进：1、迭代法：(1)不断用递推方程的右部替代左部(2)每一次替换，随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例：-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−（1）=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−（1）2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代：(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解（关于k 的函数）转换成关于n 的函数4、举例：---------------二分归并排序---------------()2(/2)1W n W n n W =+−（1）=0（1）换元：假设2kn =，递推方程如下()2(/2)1W n W n n W =+−（1）=0 → 1(2)2(2)21k k k W W W−=+−（0）=0（2）迭代求解：12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+（3）解的正确性—归纳验证： 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−（1）=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法：数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程，则（）---------------快速排序--------------------->>>平均工作量：假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简，然后迭代(1)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。

算法的概念1、算法的概念：算法一词出现于12世纪，指的是阿拉伯数字进行运算的过程，在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。

现在，算法通常可以编成计算机程序，让计算机执行并解决问题。

2、算法的特点（1）有穷性：一个算法的步骤是有限的，它应在有限步骤操作后停止；（2）确定性：算法中的每一步操作应是确定的，并能有效执行，且得到确定的结果；（3）普遍性：一个好的算法可以用来解决一类问题，而不是解决一两个具体的问题；（4）不唯一性：求解某一类问题的算法不一定是唯一的；（5）可执行性：算法是从初始步骤开始，分为若干个明确的步骤，前一步是后一步的前提，只有执行完前一步，才能执行下一步，并且在保证每一步都准确无误的前提下，才能够完成问题；（6）有输入和输出：输入：算法的出发点所给出的原始数据；输出：算法的终点所得出的结果数据3、设计算法的要求和目的要求：（1）写出的算法必须能够解决某一类问题；（2）要使算法尽量简单，步骤尽量少；（3）要保证算法正确，且计算能够执行。

目的：设计具体的数学问题的算法，实际上就是寻求一类问题的算法，它可以通过计算机来完成，设计算法的关键是把过程分解成若干个明确的步骤，然后用计算机能够接受的“语言”准确描述出来，从而达到让计算机执行的目的。

4、设计具体问题的算法应注意以下问题：a)认真分析问题，提出解决问题的一般数学方法；b)借助有关的原理、参数对计算机加以表述；c)将解决问题的过程划分成若干个步骤；d)用简练的各个步骤表示出来。

e)5、算法的描述：自然语言、框图、程序设计语言、防伪代码等。

例1、写出求1+2+3+4+5+6的一个算法，用自然语言描述。

拓展：1+2+3+4+5+6+…+1000呢？例2、有蓝黑两个墨水瓶，但现在却把蓝墨水装在了黑墨水瓶中，黑墨水装在了蓝墨水瓶中，要求将其互换，请你设计一个算法解决这一问题。

简述算法的概念
算法是一系列有序步骤的集合，用于解决特定问题或执行特定任务。

它是一种清晰、明确且逐步定义的计算过程，以产生所需的输出结果。

算法是计算机科学的基本概念之一，它不仅限于计算机领域，也涉及到数学、工程、物理学等多个学科。

以下是关于算法的一些关键概念：
1. 有序步骤：算法是一个由明确定义和有序排列的步骤序列。

每个步骤执行特定的操作，直到最终目标达到。

2. 输入和输出：算法通常接受一些输入，经过计算处理后，生成输出。

输入是算法的起点，输出是算法的终点。

3. 确定性：算法应该是确定性的，即在相同的输入条件下，它总是产生相同的输出。

这使得算法的行为可预测。

4. 有限性：算法必须在有限的步骤内结束。

这不仅有助于确保算法的有效性，也与计算机资源的有限性相一致。

5. 可行性：算法的每个步骤都必须是可行的，即可以在有限时间内执行。

6. 优势：一个好的算法应该在解决问题或执行任务的过程中具有良好的效率。

效率通常通过时间复杂度和空间复杂度来衡量。

算法是计算机科学中设计和分析的核心主题，它们用于解决各种问题，例如搜索、排序、图算法、机器学习等。

研究和选择合适的算法对于解决问题、提高性能和有效利用计算机资源至关重要。

第2章算法的概念和特性介绍第二章主要介绍算法的概念和特性。

算法是指解决问题的一系列步骤或方法的描述，它是对问题求解过程的精确而完整的描述。

在计算机科学中，算法是计算过程的抽象描述，用于解决确定性的或可计算的问题。

1.算法的定义算法是一种确定性的、有穷的、针对特定问题的解决方案的描述。

它是一个序列的指令，描述了如何将输入转换为输出。

算法必须具备以下三个特点：-确定性：算法的每一步都必须明确且唯一，不会产生二义性。

-有穷性：算法必须在执行有限次后终止。

-输入输出：算法必须具有输入和输出。

2.算法的特性-可行性：算法必须能够在有限的时间内解决问题。

-确定性：算法的每一步必须明确且唯一-可终止性：算法必须在有限的步骤后终止。

-输入输出：算法必须具有明确的输入和输出。

-可读性：算法必须易于理解，可读性好。

-高效性：算法的执行时间和空间复杂度应尽可能优化。

-鲁棒性：算法对于异常输入或错误输入具有一定的容错性和稳定性。

3.算法的设计方法-穷举法：穷举法即列举出问题的所有可能解，通过遍历所有解空间找到问题的最优解。

但穷举法的时间复杂度往往非常高。

-递归法：递归法通过将大问题分解为小问题来解决问题。

递归法通常使用递归函数来实现，但需要注意递归深度和递归边界条件。

-分治法：分治法将大规模问题分成若干个小规模问题，然后分别解决小规模问题，并将结果合并起来得到大问题的解。

-动态规划法：动态规划法通过将问题分解为独立子问题，并将子问题的解存储起来，从而避免重复计算子问题，提高算法效率。

-贪心法：贪心法是一种在每一步选择中都采取当前最优解的策略，但不一定能得到全局最优解。

贪心法适用于一些具有贪心选择性质的问题。

-回溯法：回溯法是一种通过试探和回溯的方式来寻找问题解的方法。

回溯法通常用于解决求解空间非常大、需要枚举所有可能解的问题。

本章介绍了算法的概念和特性，以及常用的算法设计方法。

算法是计算机科学的重要基础，对于解决各种实际问题具有重要的意义。