计算机基础案例解析指导教程案例计算机问题求解算法.pptx
Copyright 2013计算机基础案例解析指导教程计算机基础案例解析指导教程 Copyright 2013计算机基础案例解析指导教程计算机基础案例解析指导教程2案例实践8 计算机问题求解算法l概述概述l算法算法的的发现发现l问题求解的问题求解的艺术艺术l算法的算法的概念概念l算法算法的的表示表示l算法的有效性和算法的有效性和正确性正确性l程序设计程序设计l案例分析与案例分析与求解求解 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程3计算机问题求解算法概述 我们我们生存在一个信息爆炸的计算机时代，在工作、生活甚至娱生存在一个信息爆炸的计算机时代，在工作、生活甚至娱乐中，我们会遇到很多与信息处理相关的问题，并需要解决各种乐中，我们会遇到很多与信息处理相关的问题，并需要解决各种各样的问题。当我们必须求解一个特定的问题时，首先会问：各样的问题。当我们必须求解一个特定的问题时，首先会问：l这个问题确定是可解的吗？这个问题确定是可解的吗？l解决这个问题有多么困难？解决这个问题有多么困难？l怎样才是最佳的解决方法？怎样才是最佳的解决方法？这时这时就不仅仅是考虑传统的手工处理方式，而应该将计算机就不仅仅是考虑传统的手工处理方式，而应该将计算机的因素考虑其中，因为我们要借助计算机来帮助我们解决问题。的因素考虑其中，因为我们要借助计算机来帮助我们解决问题。于是于是，我们又会好奇地问：计算机是怎样求解问题的？，我们又会好奇地问：计算机是怎样求解问题的？下面下面就让我们在不同类型的案例求解过程中，了解和学习计就让我们在不同类型的案例求解过程中，了解和学习计算机求解问题的思想和方法。算机求解问题的思想和方法。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程4计算机问题求解算法概述 针对具体的问题求解要求，我们需要考虑的问题针对具体的问题求解要求，我们需要考虑的问题很多，诸如：很多，诸如：l常规我们怎么处理这个问题？常规我们怎么处理这个问题？l利用计算机来实现是可行的吗？利用计算机来实现是可行的吗？l需要做哪些规律性的归纳和一致性的整合？需要做哪些规律性的归纳和一致性的整合？l如何发现算法并直观地表示算法？如何发现算法并直观地表示算法？l实现的效率是我们可以接受的吗？实现的效率是我们可以接受的吗？l怎样在人与计算机之间找到一个最佳的契合点？怎样在人与计算机之间找到一个最佳的契合点？l计算机提供的软件工具平台如何使用？计算机提供的软件工具平台如何使用？l语法规则与数据描述有哪些？语法规则与数据描述有哪些？l如何将算法转换为可实现的高级语言程序代码？如何将算法转换为可实现的高级语言程序代码？Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程5计算机问题求解算法概述 要要想有效地利用计算机来实现问题的求解和想有效地利用计算机来实现问题的求解和处理，就必须具备计算思维能力和程序设计开发处理，就必须具备计算思维能力和程序设计开发技能。技能。问题问题的分析、归纳、建模和整理算法（粗框的分析、归纳、建模和整理算法（粗框架）的过程属于计算思维范畴；而具体的实现算架）的过程属于计算思维范畴；而具体的实现算法（细化）、数据描述、控制结构、特定计算机法（细化）、数据描述、控制结构、特定计算机高级语言软件环境的工具运用、编码、调试和实高级语言软件环境的工具运用、编码、调试和实现的过程就属于程序设计范畴。现的过程就属于程序设计范畴。Copyright 2013计算机基础案例解析指导教程计算机基础案例解析指导教程6案例实践8 计算机问题求解算法l概述概述l算法算法的的发现发现l问题求解的问题求解的艺术艺术l算法的算法的概念概念l算法的算法的表示表示l算法的有效性和算法的有效性和正确性正确性l程序设计程序设计l案例分析与案例分析与求解求解 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程7计算机问题求解算法算法的发现l问题求解的技术与学习不仅仅是在计算机科学领域，问题求解的技术与学习不仅仅是在计算机科学领域，而是在任何领域，都是要求永久需要和具备的技能。而是在任何领域，都是要求永久需要和具备的技能。算法发现的过程和一般问题的求解过程之间存在着算法发现的过程和一般问题的求解过程之间存在着紧密的联系，因此在计算机科学领域人们把问题的紧密的联系，因此在计算机科学领域人们把问题的求解简化为一种算法，但并不是所有的问题都一定求解简化为一种算法，但并不是所有的问题都一定都能找到解决问题的算法。都能找到解决问题的算法。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程8计算机问题求解算法算法的发现l程序开发由两个活动组成：发现潜在的算法和以程序的方程序开发由两个活动组成：发现潜在的算法和以程序的方法表示算法。要理解算法是如何发现的就是要理解问题的法表示算法。要理解算法是如何发现的就是要理解问题的求解过程。求解过程。l算法的发现起源于公元前算法的发现起源于公元前30003000年年 公元前公元前15001500年的巴比伦，年的巴比伦，当时巴比伦人求解当时巴比伦人求解“算法算法”的过程：先用解代数方法，再的过程：先用解代数方法，再计算实际数目，最后写上一句短句计算实际数目，最后写上一句短句“这就是一个过程这就是一个过程”。Copyright 2013计算机基础案例解析指导教程计算机基础案例解析指导教程9案例实践10 计算机问题求解算法l概述概述l算法算法的的发现发现l问题求解的问题求解的艺术艺术l算法的算法的概念概念l算法的算法的表示表示l算法的有效性和算法的有效性和正确性正确性l程序设计程序设计l案例分析与案例分析与求解求解 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程10计算机问题求解算法问题求解的艺术l问题求解的艺术包括四个阶段：问题求解的艺术包括四个阶段：l第一阶段：理解问题；第一阶段：理解问题；l第二阶段：寻找一个可能解决问题的算法过程的思路；第二阶段：寻找一个可能解决问题的算法过程的思路；l第三阶段：阐明算法并且用程序将其表达出来；第三阶段：阐明算法并且用程序将其表达出来；l第四阶段：从准确度及其是否有潜力作为一个解决其他问题第四阶段：从准确度及其是否有潜力作为一个解决其他问题的工具这两方面来评估这个程序。的工具这两方面来评估这个程序。l但这些阶段不是一定要遵循的步骤，也不必一定按顺但这些阶段不是一定要遵循的步骤，也不必一定按顺序完成。序完成。l算法发现是一种富有挑战性的艺术，必须花费时间去算法发现是一种富有挑战性的艺术，必须花费时间去学习学习。Copyright 2013计算机基础案例解析指导教程计算机基础案例解析指导教程11案例实践10 计算机问题求解算法l概述概述l算法算法的的发现发现l问题求解的问题求解的艺术艺术l算法的算法的概念概念l算法的算法的表示表示l算法的有效性和算法的有效性和正确性正确性l程序设计程序设计l案例分析与案例分析与求解求解 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程12计算机问题求解算法概念l算法的概念算法的概念l算法（算法（AlgorithmAlgorithm）是指解题方案的准确而完整的描述，是一）是指解题方案的准确而完整的描述，是一系列解决问题的方法步骤或清晰指令的陈述。算法存在于人系列解决问题的方法步骤或清晰指令的陈述。算法存在于人们的生活中，如：上街购物、顾客付款、营业员找银等等。们的生活中，如：上街购物、顾客付款、营业员找银等等。l算法代表着用系统的方法描述解决问题的策略机制。也就是算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。算法将不会解决这个问题。l一个算法的优劣可以用一个算法的优劣可以用空间复杂度空间复杂度（是指算法需要消耗的内（是指算法需要消耗的内存空间）与存空间）与时间复杂度时间复杂度（是指执行算法所需要的时间）来衡（是指执行算法所需要的时间）来衡量。不同的算法可能用不同的时间、空间或效率来完成同样量。不同的算法可能用不同的时间、空间或效率来完成同样的任务。的任务。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程13计算机问题求解算法概念l算法要素算法要素l一个算法是由操作与控制结构两个要素组成。一个算法是由操作与控制结构两个要素组成。l操作：计算机最基本的操作有：算术运算、关系操作：计算机最基本的操作有：算术运算、关系运算、逻辑运算和数据传送等。运算、逻辑运算和数据传送等。l控制结构：各操作之间的执行顺序为算法的控制控制结构：各操作之间的执行顺序为算法的控制结构，有：顺序结构、选择结构和循环结构。结构，有：顺序结构、选择结构和循环结构。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程14计算机问题求解算法概念l算法性质一般归纳为下列五点：算法性质一般归纳为下列五点：l输入：要求若干个信息的输入；输入：要求若干个信息的输入；l有穷性：任意一个算法在执行有限个计算步骤后必有穷性：任意一个算法在执行有限个计算步骤后必须终止；须终止；l可行性：有限个步骤应该可以在一个合理的范围内可行性：有限个步骤应该可以在一个合理的范围内进行；进行；l确定性：每一个计算步骤，必须是精确地定义、无确定性：每一个计算步骤，必须是精确地定义、无二义性；二义性；l输出：有若干个输出信息即处理结果。输出：有若干个输出信息即处理结果。Copyright 2013计算机基础案例解析指导教程计算机基础案例解析指导教程15案例实践10 计算机问题求解算法l概述概述l算法算法的的发现发现l问题求解的问题求解的艺术艺术l算法的算法的概念概念l算法的算法的表示表示l算法的有效性和算法的有效性和正确性正确性l程序设计程序设计l案例分析与案例分析与求解求解 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程16计算机问题求解算法 算法描述l算法描述算法描述l可以使用多种方法描述算法：自然语言、流程图、可以使用多种方法描述算法：自然语言、流程图、伪代码和计算机语言。伪代码和计算机语言。l例如：分析一天中，根据时间归纳出一个人的日程例如：分析一天中，根据时间归纳出一个人的日程安排情况。下面用了四种方法描述算法。安排情况。下面用了四种方法描述算法。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程17计算机问题求解算法算法描述l自然语言自然语言l用自然语言表达算法，就是把算法的各个步骤，依用自然语言表达算法，就是把算法的各个步骤，依次用人们所熟悉的自然语言表示出来。次用人们所熟悉的自然语言表示出来。l自然语言描述算法的特点是通俗易懂，但缺乏直观自然语言描述算法的特点是通俗易懂，但缺乏直观性和简洁性，且易产生歧义。使用此种方式描述算性和简洁性，且易产生歧义。使用此种方式描述算法，需要注意的事项是：描述要求尽可能精确和详法，需要注意的事项是：描述要求尽可能精确和详尽。尽。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程18计算机问题求解算法算法描述l流程图流程图l流程图是用一些图框、线条以及文字说明来形象地、流程图是用一些图框、线条以及文字说明来形象地、直观地描述算法。直观地描述算法。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程19计算机问题求解算法算法描述l伪代码伪代码l伪代码（伪代码（PseudocodePseudocode）是一种在算法开发过程中非正式）是一种在算法开发过程中非正式地表达思想的符号系统，也是一种算法描述语言，它是地表达思想的符号系统，也是一种算法描述语言，它是通过使用一些介于自然语言与高级语言之间的符号语言通过使用一些介于自然语言与高级语言之间的符号语言表达算法。表达算法。l使用伪代码的目的是为了使被描述的算法可以容易地以使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（任何一种编程语言（Visual BasicVisual Basic、C C或或JavaJava）实现。）实现。l用伪代码描述算法的特点是它介于自然语言与编程语言用伪代码描述算法的特点是它介于自然语言与编程语言之间，结构清晰、代码简单、不拘于具体实现，可读性之间，结构清晰、代码简单、不拘于具体实现，可读性好。好。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程20计算机问题求解算法算法描述运算符号说明符号表示范例赋值符号或=A 5、B=6算术运算符号+、-、/、Mod（整除取余）A+B、A-B、AB、A/B、A Mod B关系运算符号、AB、AB逻辑运算符And（与）、Or（或）、Not（非）Not（AB And A+BA*B Or A0）输入和输出Input、PrintInput A 、Print B选择结构如果P成立则A否则B：If P Then A Else BIf A=B Then Print A Else B循环结构当型循环结构：While P Do A直到型循环结构：Repeat A Until P或Do A While PCount1；While（Count Y XY 同时同时XZXZ）l至此，在确定问题是可解的（有唯一结果）前提下，至此，在确定问题是可解的（有唯一结果）前提下，找处符合条件的年龄值找处符合条件的年龄值。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程44计算机问题求解算法案例分析与求解案例分析与求解l推算年龄推算年龄l对于对于这个问题，是在逐步推理的过程中，验证线索这个问题，是在逐步推理的过程中，验证线索的充分性，进而发现问题求解的可行性的充分性，进而发现问题求解的可行性。l在在这个方面，人与计算机的问题求解思路有些不同，这个方面，人与计算机的问题求解思路有些不同，比如在具体实现上，人是依靠逻辑推理，找出符合比如在具体实现上，人是依靠逻辑推理，找出符合条件的可能的数，并需要保证答案是唯一的。而计条件的可能的数，并需要保证答案是唯一的。而计算机是通过穷举法，在一个可能的范围，一个个代算机是通过穷举法，在一个可能的范围，一个个代入线索公式中进行逻辑条件判断，如果都满足，就入线索公式中进行逻辑条件判断，如果都满足，就得到最终的结果了，但是这样得到的结果可能有多得到最终的结果了，但是这样得到的结果可能有多种组合种组合。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程45计算机问题求解算法案例分析与求解案例分析与求解l推算年龄推算年龄l如果如果只有线索一，会有很多种可能情况，结果并不只有线索一，会有很多种可能情况，结果并不唯一；加上线索二，结果依然不唯一；再加上线索唯一；加上线索二，结果依然不唯一；再加上线索三之后，结果才明朗。三之后，结果才明朗。l穷举法，也叫枚举法或列举法。在研究对象是由有穷举法，也叫枚举法或列举法。在研究对象是由有限个元素构成的集合时，把所有对象一一列举出来，限个元素构成的集合时，把所有对象一一列举出来，再对其一一进行研究。有时穷举法用于破译密码，再对其一一进行研究。有时穷举法用于破译密码，又又称为称为暴力破解暴力破解法法，即将密码进行各种可能组合逐，即将密码进行各种可能组合逐个推算直到找出真正的密码为止。个推算直到找出真正的密码为止。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程46计算机问题求解算法案例分析与求解案例分析与求解l百钱买百鸡百钱买百鸡l古代算经中有一个经典的数学算题：要求用一百个铜古代算经中有一个经典的数学算题：要求用一百个铜钱，去买回一百只鸡来。其中：公鸡一只钱，去买回一百只鸡来。其中：公鸡一只5 5钱、母鸡钱、母鸡一只一只3 3钱，小鸡一钱钱，小鸡一钱3 3只。问一百只鸡中公鸡、母鸡、只。问一百只鸡中公鸡、母鸡、小鸡各多少？小鸡各多少？Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程47计算机问题求解算法案例分析与求解案例分析与求解l百钱买百百钱买百鸡鸡l设可能的鸡只数为：设可能的鸡只数为：l鸡翁：鸡翁：X X只，鸡母：只，鸡母：Y Y只，鸡雏：只，鸡雏：Z Z只只l线索一：线索一：X+Y+Z=100 X+Y+Z=100（只）（只）l线索二：线索二：5*X+3*Y+Z/3=100 5*X+3*Y+Z/3=100 （钱）（钱）l三个未知数，两个方程，无法求解三个未知数，两个方程，无法求解l但如果将但如果将X X和和Y Y可能的只数逐个枚举（穷举）出来，带可能的只数逐个枚举（穷举）出来，带入上面两个方程，就可以得解：入上面两个方程，就可以得解：lX X可能的只数是：可能的只数是：020020lY Y可能的只数是：可能的只数是：033033lZ Z可能的只数是：可能的只数是：Z=100-X-YZ=100-X-Y Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程48计算机问题求解算法案例分析与求解案例分析与求解l百钱买百百钱买百鸡鸡l对于对于这个问题，人与计算机的问题求解思路类似，只这个问题，人与计算机的问题求解思路类似，只是由于需要枚举的数据范围比较大，如果仅仅是通过是由于需要枚举的数据范围比较大，如果仅仅是通过手工计算，需要耗费大量的时间，而通过计算机来解手工计算，需要耗费大量的时间，而通过计算机来解决，就只需要一眨眼的瞬间就完成了。这个问题得到决，就只需要一眨眼的瞬间就完成了。这个问题得到的结果可能有多种组合的结果可能有多种组合。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程49计算机问题求解算法案例分析与求解案例分析与求解l剪正方形剪正方形l从一张长从一张长20022002毫米，宽毫米，宽847847毫米的长方形纸片上，剪下毫米的长方形纸片上，剪下一个边长尽可能大的正方形，如果剩下的部分不是正一个边长尽可能大的正方形，如果剩下的部分不是正方形，那么在剩下的纸片上再剪下一个边长尽可能大方形，那么在剩下的纸片上再剪下一个边长尽可能大的正方形，按照上面的过程不断地重复，最后剪得的的正方形，按照上面的过程不断地重复，最后剪得的正方形的边长是多少毫米呢？正方形的边长是多少毫米呢？Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程50计算机问题求解算法案例分析与求解案例分析与求解l剪正方形剪正方形l这个问题表面上看，似乎是个纯手工操作，但如果这个问题表面上看，似乎是个纯手工操作，但如果把思路稍稍往规律上靠，就会发现这是一个在指定把思路稍稍往规律上靠，就会发现这是一个在指定的两个数的两个数20022002和和847847之间求最大公约数的问题。之间求最大公约数的问题。l首先必须先了解数学上关于公倍数和公约数的概念。首先必须先了解数学上关于公倍数和公约数的概念。公倍数是两个正整数的公共倍数（有无限多个）。公倍数是两个正整数的公共倍数（有无限多个）。而公约数是两个正整型数的公共约数（通常也有多而公约数是两个正整型数的公共约数（通常也有多个）。个）。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程51计算机问题求解算法案例分析与求解案例分析与求解l剪正方形剪正方形l“辗转相除法辗转相除法”又叫做又叫做“欧几里得算法欧几里得算法”，是欧几，是欧几里得在他的著作几何原本第七卷中提出的。利里得在他的著作几何原本第七卷中提出的。利用这个方法，可以较快地求出两个自然数的最大公用这个方法，可以较快地求出两个自然数的最大公约数。约数。,l当当将问题求解的算法归纳出来了，直接用手工运算将问题求解的算法归纳出来了，直接用手工运算也不是不可，只是效率太低。如果可以配合计算机也不是不可，只是效率太低。如果可以配合计算机高级语言环境实现的语法规则和控制结构，就可以高级语言环境实现的语法规则和控制结构，就可以高效轻松地完成运算，得到所需的结果高效轻松地完成运算，得到所需的结果。l这里这里会用到迭代的算法，它的基本思想是：不断用会用到迭代的算法，它的基本思想是：不断用新值取代变量的旧值，或由旧值递推出变量的新值。新值取代变量的旧值，或由旧值递推出变量的新值。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程52计算机问题求解算法案例分析与求解案例分析与求解l比赛评分计算比赛评分计算l在在N N个评委给出的大小不同的无序评分中，去掉一个个评委给出的大小不同的无序评分中，去掉一个最高分和最低分，然后求平均分数。最高分和最低分，然后求平均分数。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程53计算机问题求解算法案例分析与求解案例分析与求解l比赛评分计算比赛评分计算l这类问题有两个关键点：一个是找出最大和最小；这类问题有两个关键点：一个是找出最大和最小；二个是求和再平均。二个是求和再平均。l在在N N个数中找最大最小的方法很简单，只要预设两个数中找最大最小的方法很简单，只要预设两个变量，用于存放最大和最小值，将个变量，用于存放最大和最小值，将N N个数中的第个数中的第一个数作为最大最小的初值，依次与其他一个数作为最大最小的初值，依次与其他N-1N-1个数个数逐个比较大小，大的放到存放最大的变量中，小的逐个比较大小，大的放到存放最大的变量中，小的放到存放最小的变量中。放到存放最小的变量中。l至于求和，只要逐个将至于求和，只要逐个将N N个数累加起来，再减去得个数累加起来，再减去得到的最大最小数，最后除以到的最大最小数，最后除以N-2N-2即得平均分。即得平均分。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程54计算机问题求解算法案例分析与求解案例分析与求解l分卡牌分卡牌l有有1111个人围成一圈，按固定规则发卡牌，依次按个人围成一圈，按固定规则发卡牌，依次按1 1、3 3、6 6、8 8、1111、2 2、5 5、7 7、1010、1 1、4 4、6 6、的序号发，问至的序号发，问至少发到多少张时每人手上至少都有卡牌？最后拿到卡牌少发到多少张时每人手上至少都有卡牌？最后拿到卡牌的是几号？每个人手上的牌数分别是多少？的是几号？每个人手上的牌数分别是多少？Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程55计算机问题求解算法案例分析与求解案例分析与求解l分卡牌分卡牌l这个问题需要考虑的线索比较多：这个问题需要考虑的线索比较多：l当前该给几号发牌；当前该给几号发牌；l发出卡牌的计数；发出卡牌的计数；l每个人手中卡牌的计数；每个人手中卡牌的计数；l分发顺序号的规律；分发顺序号的规律；l判断是否有人手中无牌；判断是否有人手中无牌；l什么时候结束发牌。什么时候结束发牌。l在这个问题的具体处理中，整体发牌过程是一个需要在这个问题的具体处理中，整体发牌过程是一个需要重复处理的过程，只是在每发出一张牌，就需要处理重复处理的过程，只是在每发出一张牌，就需要处理上面罗列的多条线索，为下一次发牌做准备。上面罗列的多条线索，为下一次发牌做准备。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程561234567891011规则：有11个人围成1圈，发卡牌，依次给1、3、6、8、11、2、5、7、10、1、4、6、号发，问至少发到多少张时每人都有卡牌？最后拿到卡牌的是几号。发卡牌 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程571234567891011 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程5812345678910111 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程5912345678910112 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程6012345678910113 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程6112345678910114 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程6212345678910115 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程6312345678910116 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程6412345678910117 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程6512345678910118 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程6612345678910119 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程67123456789101110 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程68123456789101111 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程69123456789101112 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程70123456789101113 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程71计算机问题求解算法案例分析与求解案例分析与求解l兔子繁殖问题兔子繁殖问题l一般而言，兔子在出生两个月后，就具备了繁殖能力，一般而言，兔子在出生两个月后，就具备了繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？不死，那么一年以后可以繁殖多少对兔子？Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程72计算机问题求解算法案例分析与求解案例分析与求解l兔子繁殖问题兔子繁殖问题l兔子繁殖问题，是著名的兔子繁殖问题，是著名的FibonacciFibonacci（斐波拉契）序列（斐波拉契）序列数的趣味版。数的趣味版。FibonacciFibonacci（斐波拉契）序列数的计算，（斐波拉契）序列数的计算，是通过递推算法实现的。是通过递推算法实现的。l递推算法是数学上常用的一种算法，即通过已知条件，递推算法是数学上常用的一种算法，即通过已知条件，利用数据之间的特定关系得出中间推论，直至得到最利用数据之间的特定关系得出中间推论，直至得到最终结果的算法。终结果的算法。l1 1、1 1、2 2、3 3、5 5、8 8、1313、2121，从这个数列不难发，从这个数列不难发现其中的规律：从第现其中的规律：从第3 3项开始，当前项等于其前两项项开始，当前项等于其前两项之和：之和：F F（N N）=F=F（N-1N-1）+F+F（N-2N-2）。）。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程73计算机问题求解算法案例分析与求解案例分析与求解l杨辉三角形杨辉三角形l杨辉三角形的阵列中，值与值之间存在着一定的推算关杨辉三角形的阵列中，值与值之间存在着一定的推算关系，如图所示是系，如图所示是5 5行和行和6 6行的杨辉三角形阵列，那么如何行的杨辉三角形阵列，那么如何推算更多行的数值？推算更多行的数值？Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程741111211331146411234512345杨辉三角形杨辉三角形X(1)=1,x(2)=0,x(3)=0,x(4)=0,x(5)=0X(1)=1,x(2)=1,x(3)=0,x(4)=0,x(5)=0X(1)=1,x(2)=2,x(3)=1,x(4)=0,x(5)=0X(1)=1,x(2)=3,x(3)=3,x(4)=1,x(5)=0X(1)=1,x(2)=4,x(3)=6,x(4)=3,x(5)=1归纳整理输出N行N列的杨辉三角形的算法（要求用一维数组实现）i=1n，j=(i-1)2(递减),x(j)=x(j-1)+x(j)Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程751111211331146411234512345杨辉三角形杨辉三角形X(1,1)=1,x(1,2)=0,x(1,3)=0,x(1,4)=0,x(1,5)=0X(2,1)=1,x(2,2)=1,x(2,3)=0,x(2,4)=0,x(2,5)=0X(3,1)=1,x(3,2)=2,x(3,3)=1,x(3,4)=0,x(3,5)=0X(4,1)=1,x(4,2)=3,x(4,3)=3,x(4,4)=1,x(4,5)=0X(5,1)=1,x(5,2)=4,x(5,3)=6,x(5,4)=3,x(5,5)=1归纳整理输出N行N列的杨辉三角形的算法（要求用二维数组实现）x(i,j)=x(i-1,j-1)+x(i-1,j)i=3n,j=2i Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程76计算机问题求解算法案例分析与求解案例分析与求解l排序问题排序问题l对给定的对给定的N N个大小不同的无序数进行从小到大整理排序。个大小不同的无序数进行从小到大整理排序。Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程77三杯水颜色深浅排序l对三杯不同颜色的水进行颜色深浅排序处理，你对三杯不同颜色的水进行颜色深浅排序处理，你会怎么做？计算机又会怎么做？计算机为什么那会怎么做？计算机又会怎么做？计算机为什么那样做？样做？A B C输入：输入：输出：输出：Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程A B C输入：输出：分析过程A B CA B CA B CA B CA B CA B C可能的输入排列情况 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程 分析过程分析过程A B C T 第一步：交换：Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程A B C T 第二步：交换：分析过程 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程A B C T 第三步：交换：分析过程 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程A B C 第三步：交换：最终结果 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程 算法表示开始分别从键盘输入数值A，B，C交换A,B的值，T=A,A=B,B=T输出结果A,B,C结束AB?交换A,C的值，T=A,A=C,C=TAC?AABC?NNNYYY交换B,C的值，T=B,B=C,C=T Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程 程序代码实现 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程85原始排列顺序排序后的顺序比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程86原始排列顺序排序后的顺序N个数的从小到大排序问题 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程87第一轮比较比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程88第一轮比较比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程89第一轮比较第一轮比较后的顺序比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程90第二轮比较比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程91第二轮比较第二轮比较后的顺序比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程92第三轮比较第三轮比较后的顺序比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程93第四轮比较第四轮比较后的顺序比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程94比较交换排序法第四轮比较后的顺序第四轮比较 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程95最终排好的顺序比较交换排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程96原始排列顺序排序后的顺序选择排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程97第一轮比较排序后的顺序选择排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程98第一轮比较排序后的顺序选择排序法 Copyright Copyright 20201313计算机基础案例解析指计算机基础案例解析指导教程导教程99第一轮比较排序后的顺序选择排序法 Copyright Copy
