第8章-算法基础.pptxVIP

大学计算机基础第8章计算思维西华师范大学教育信息技术中心

8.1计算思维概述

8.1.1国王的婚姻核心问题：求解大数48770428433377171的真因子。按数学逻辑，其真因子不会超过9位，最多10亿大小，但计算量仍然惊人解决方案：发动5亿老百姓，每个老百姓两个数，分摊计算量。思考：这个方案真能实施吗?

8.1.2三大科学研究的方法理论：始于假说，经历从假说到科学理论的转化过程，最后形成科学命题系统。实验：根据研究问题设计科学实验，完成并可重复实验，从中发现规律的研究方法计算：利用计算机再现，预测和发现客观世界运动规律和演化特征的全过程。

8.1.3计算思维概念及内涵概念：计算思维是在表述问题及其解决方案时所涉及的思维过程，其解决问题的表示形式应该能有效地被信息处理代理执行。内涵：像计算机科学家一样思考，成为一种超越计算机科学范畴的概念体系计算思维是概念化思维，不是程序化思维计算思维是基础的技能，不是机械的技能计算思维是人的思维，不是计算机的思维计算思维是思想，不是人造品计算思维是数学和工程互补融合的思维，不只是数学性的思维计算机思维面向所有人，所有领域

8.2计算思维下问题求解的策略

8.2.1实例分析：谁是凶手？案例：某地区发生了一桩命案，警官圈定了四名嫌疑人甲、乙、丙、丁，在讯问时，警方确定四人中有一人在说谎，而说谎的这个人就是凶手。这四人口供如下：甲说：“不是我干的”，乙说：“丙是凶手”，丙说：“丁是凶手”，丁说：“不是我”。知识背景和数理表达：逻辑值：True，False逻辑运算：and，or，not关系运算：，，=，=，==，!=

8.2.1实例分析：谁是凶手？数理表达：只有一个人说谎，设其编号为x，则有：编号姓名供述逻辑式表达1甲不是我X12乙是丙X==33丙是丁X==44丁不是我X4将四人表达式组合起来，最终找到满足下式的x(x!=1)+(x==3)+(x==4)+(x!=4)==3

8.2.1实例分析：谁是凶手？算法的流程（流程图参考本书8.3.4节）：TrueTrueFalseX增加1结束x4吗输出x并结束开始让x值为1计算(x!=1)+(x==3)+(x==4)+(x!=4)并存入c中C==3吗False

8.2.2计算思维求解问题基本步骤分解问题找寻求解方法进行模式匹配（抽象）最终抽象成模型--算法设计和实施

8.2.3像程序员一样思考准确地理解和描述问题一定要有计划大事化小，小事讲规矩遇到难题，感觉无法逾越怎么办?要多练习和观察总结

8.3算法

8.3.1算法的概念算法(algorithm)这一名词最早来源于公元85年左右,波斯著名的数学家穆罕默德?本?穆萨?阿尔?花剌子模(muhammadibnmsaalkhwarizmi)在其所著《代数学》一书中首次提出了四则算术运算的基本法则以及四则算术代数学中的一些基本概念。13世纪，意大利数学家斐波那契(fibonacci)将这套十进制计数法和算术方法传播到欧洲，并将他在这本著作中讲解到的基于十进制计数法的算术方法称之为Algorismus，经过不断地历史沿革，逐渐成为今天的算法（Algorithm）。算法中的指令通常是在计算机中通过编程语言来实现的，它是一句句的机器语言或操作代码组成的程序，一条指令代表一个或几个操作。指令的运行是指从最开始的输入开始，经过一条条明确、清晰的指令的加工、运行后，最终产生输出结果并结束算法

8.3.1算法的概念算法是针对解决方案的确切且完整的表述，是通过一连串的指令的细致的描述。同一个问题会有不同的解决办法，也就是说不同算法运用不同指令可能达到相同的目的。算法中的指令通常是在计算机中通过编程语言来实现的，它是一句句的机器语言或操作代码组成的程序，一条指令代表一个或几个操作。指令的运行是指从最开始的输入开始，经过一条条明确、清晰的指令的加工、运行后，最终产生输出结果并结束算法。

8.3.2算法的特性一个算法还应具有下列几个重要特性1有穷性：计算时间的确定性，问题解决所花费的时间不能过长甚至没有结果2确定性：算法中的每一条指令必须有明确的含义，在阅读时不会产生歧义。即对于相同的输入只能得出相同的输出。3可行性：通过对问题进行算法指令执行后能得到一个结果。4有输入和输出：算法要有0个或多个输入和一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

8.3.2算法的特性除了上述种特性外，通常一个“好”的算法还应考虑达到以下目标：可读性：算法应当具有良好的可读性，以便于人们理解。健壮性：当输入数据无效时，算法同样也能进行反馈与说明，而不会产生一个误以为正确的输出结果。效率与低存储量需求：效率即算法执行的时间长短，存储量需求是指算法执行过程中所需要的最