下载文档原格式
信息奥赛基础知识——常用算法与策略第一章算法1.1 什么是算法算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言。
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。
通俗点说，就是计算机解题的过程。
在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。
前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下五个重要的特征：1.有穷性：一个算法必须保证执行有限步之后结束；2.确切性：算法的每一步骤必须有确切的定义；3.输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；4.输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；5.可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
1.2 算法的表示方法算法通常有三种表示方法：自然语言法、程序流程图法、程序法。
结构化程序设计三种程序结构的流程图（N-S图）如下：1.顺序结构2.选择结构3.循环结构当型循环直到型循环例题1:百钱买百鸡问题:1.3 算法分析算法的复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。
一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。
因而，算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。
因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。
1.时间复杂性：例1：设一程序段如下（为讨论方便，每行前加一行号）(1) for i:=1 to n do(2) for j:=1 to n do(3) x:=x+1......试问在程序运行中各步执行的次数各为多少？解答：行号次数(频度)(1) n+1(2) n*(n+1)(3) n*n可见，这段程序总的执行次数是：f(n)=2n2+2n+1。
第三部常用算法与策略第一章算法1.1 什么是算法1.2 算法的表示方法1.3 算法分析1.1 什么是算法算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言。
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。
通俗点说，就是计算机解题的过程。
在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。
前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下五个重要的特征：1.有穷性：一个算法必须保证执行有限步之后结束；2.确切性：算法的每一步骤必须有确切的定义；3.输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；4.输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；5.可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
1.2 算法的表示方法算法通常有三种表示方法：自然语言法、程序流程图法、程序法。
结构化程序设计三种程序结构的流程图（N-S图）如下：1.顺序结构2.选择结构3.循环结构当型循环直到型循环例题1:百钱买百鸡问题:1.3 算法分析算法的复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。
一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。
因而，算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。
因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。
教科版2019信息技术必修1数据与计算第4单元计算与问题解决4.1 算法及其特征教学设计【教材分析】程序设计是给出解决特定问题程序的过程。
程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。
算法是程序设计中的核心，算法依赖程序设计语言来实现。
程序设计语言有较大的局限性，不能用来解决所有类型的问题，人们要根据所需解决的问题不同而选择不同的语言，而语言本身也在不断变化和更新。
因此，语言具有不稳定和变化更新快的特征；算法则比较稳定，它与描述算法的语言无关，可以在更长的时间内发挥作用。
程序设计语言只要多实践多使用就能熟能生巧，算法则需要比较深入的理论基础知识，必须经过严格的科学训练。
基于以上认识，程序设计语言知识可以作为一种技能来培养，程序设计方法可以作为一个规则来遵循，算法可以作为科学方法来传授，这样才能适应时代的需要，跟上技术的飞速发展。
通过前面单元的学习，我们可以认为学生具备初步编写程序的简单技能，如基本的输入输出语句、选择结构和循环结构的语句实现、列表及文件的初步操作等。
本项目既要唤醒学生已有的技能，又要让学生初识算法，因此在项目及活动设计时，抛开晦涩难懂的概念和语法，不做内容上的堆积和罗列，采用了生动有趣的活动形式，每个活动中会涉及到一个或几个知识点。
代码不是最终目的，而是作为载体，让学生初步了解程序设计的基本方法，在面对实际问题的时候，可以换一种思维，找到有效的算法。
本节的项目“软件开发社招新”主要包含“探讨面试题的解决方案”和“求解‘谁是冠军’”两个任务，包含4个活动。
任务一的重点在已有知识和技能的唤醒，任务二的重点是最基本算法思想的介绍。
【教学建议】通过本项目的教学应让学生了解程序设计的基本方法和基本流程，利用学生感兴趣的实例，让学生感觉程序设计并不是遥不可及的，而是人机对话的一种方式，让学生带着轻松的心情，在游戏中学习，在学习中游戏。
以活动为中心，增加拓展类知识，兼顾到不同层次学生的需求。
【算法复习一】常见的算法策略汇总一，概述算法策略和算法是有区别的,它们是算法设计中的两个方面，算法策略是面向问题的,算法是面向实现的；但二者又是不可分的,首先是通过算法策略才找出解决问题的算法，其次对于用不同算法求解的问题算法策略是自然不同的。
二，算法策略1）递推策略：“递推法”和贪心算法一样也是由当前问题的逐步解决从而得到整个问题的解，只是依赖的是信息间本身的递推关系，每一步不需要策略参与到算法中，它们更多地用于计算。
2）递归策略：递归法是利用大问题与其子问题间的递归关系来解决问题的。
每次找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。
例如：汉诺塔问题3）穷举策略：对所有可能的解逐一尝试。
4）递归回溯策略：类似于穷举法的思想,递归回朔法通过递归尝试遍问题各个可能解的通路，发现此路不通时回朔到上一步继续尝试别的通路。
5）分治策略：求解的则是较复杂的问题，这类问题是可以被分解成独立的子问题来解决的，将两个或两个以上的独立子问题的解“合成”，就得到较大的子问题的解，最后合成为总问题的解。
（注意一定是可以分解成独立子问题，否则会重复计算公共子问题）6）动态规划策略：动态规划法与贪心法类似，要求问题具有最优子结构（即最优解包含子问题的最优解），是一种自底向上的求解思路，与递归正好相反，每次求解到一个阶段时，该阶段求解所依赖的子问题已经完全求解完毕，因此每一步的求解都是在直到全部所需信息的情况下进行的，因此可以得到全局最优解。
7）贪心策略：如果想要得到最优解，需要对问题性质有更严格的要求，除了要有最优子结构外，还要求问题具有贪婪选择性质。
具体来说就是：贪心是一种策略，即每一步都要选择当前看来最好的，做完此选择后便将问题化为一个（仅仅一个）子问题，这是一个顺序的求解过程，每一步都是单独考虑，只考虑局部最优，因为并没有完成对之后子问题的求解，所以贪心算法不能完成对整个解空间的搜索，因此通常不能得到最优解。
第四章1算法策略迭代算法迭代算法是一种通过重复应用一些过程或步骤来逐步逼近解的策略。
在计算机科学中，迭代算法是解决问题的一种常见方法，尤其在计算复杂度比较高的情况下，迭代算法可以提供一种有效的解决方案。
迭代算法的核心思想是将问题分解成一系列小的子问题，并通过重复执行一些步骤来逐渐逼近解。
每次迭代时，算法会根据上一次迭代的结果来更新当前的状态，然后继续下一次迭代。
这样的迭代过程会持续进行，直到达到一些停止条件为止。
迭代算法可以应用在各个领域的问题中，比如数值计算、优化问题、问题等。
下面将介绍一些常见的迭代算法。
1.迭代加深：这是一种在问题中应用的常见迭代算法。
它通过逐渐增加的深度来逼近解。
首先进行深度为1的，如果没有找到解，则增加深度，再次进行。
通过不断增加深度，直到找到解为止。
2.迭代法解线性方程组：线性方程组的解可以通过迭代算法逐步求得。
一种常见的迭代算法是雅可比迭代法，它通过不断迭代解方程组的近似解，直到满足特定的收敛准则为止。
3.迭代法求函数零点：对于给定的函数，通过迭代算法可以逐步逼近函数的零点。
其中，牛顿迭代法是一种常见的迭代算法，它通过使用函数的导数和当前函数值来逐步逼近零点。
除了上述几种常见的迭代算法，还有其他很多迭代算法方法，如迭代法解非线性方程组、最小二乘法、迭代法求特征值等。
迭代算法的优点是它可以解决很多复杂的问题，并且可以提供一种近似解。
此外，迭代算法通常比较灵活，可以根据实际情况进行调整。
迭代算法的缺点是它可能需要进行大量的迭代次数才能得到满意的结果，并且在一些情况下可能无法收敛到解。
总之，迭代算法是一种常见的算法策略，可以应用于很多领域的问题。
通过不断迭代，算法可以逐步逼近最优解或者满足特定的目标。
虽然迭代算法可能需要较长时间才能得到完美的解，但它是解决复杂问题的一种有效方法。
