第三章算法基础课件粤教版高中信息技术必修12

（1）把羊带到右岸；（2）空船返回左岸，

把狼带到右岸；（3）把羊带回左岸；（4）把卷心菜带到右岸；（5）空船返回左岸，

把羊带到右岸。第三章

算法基础一、算

法1.算法的概念算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。1.算法的概念通俗地说，算法就是计算机求解某一问题的方法，是能被执行的动作或指令的有穷集合。2.人工解决问题

VS计算机解决问题例1：圆周率的计算历史人物研究方法/时间圆周率位数（范围）阿基米德（古希腊）内外接多边形（96边形）3.141851祖冲之（中国）割圆术（公元480年）3.1415926~3.1415927鲁道夫（德国）1596年1610年20位小数值35位小数值梅钦（英国）无穷级数（1706年）突破100位JurijVega梅钦类公式（1789年）140位（137位正确）弗格森、伦奇1948年808位2.人工解决问题

VS计算机解决问题例1：圆周率的计算时间节点花费时间圆周率位数1950年70小时2037位1955年13分钟3089位1973年100万位1989年10.1亿位2010年5万亿位2011年一年（自组装计算机）10万亿位2.人工解决问题

VS计算机解决问题例2：韩信点兵西汉大将韩信，善于带兵，神机妙算，能征善战。一次阅兵时，韩信要求士兵排成3路纵队，此时末尾多出2人，改排成5路纵队，末尾多出3人，再排成7路纵队，末尾余下2人。这时，领兵的部下报告说，这队士兵一共有2395人，韩信立刻摇头说：不对，实际实际只有（

）人，部下迟疑地回去，又重新清点人数，果真是那么多人，部下们因此对韩信十分佩服。人数范围x：2300~2400从2300开始，逐个数去试试，如果这个数能同时被3、5、7整除后的余数分别为2、3、2，则这个数就是正确的人数。分析问题（抽象与建模）例2：韩信点兵例2：韩信点兵设计算法①总人数x=2300；②判断x是否在2300~2400之间，满足则执行下一步，否则结束；③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步；④x在原来的基础上加1，回到第②步；⑤输出x。思考1：计算机解决问题的过程是怎样的？分析问题设计算法编写程序调试运行程序抽象与建模例2：韩信点兵①总人数x=2300；②判断x是否在2300~2400之间，满足则执行下一步，否则结束；③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步；④x在原来的基础上加1，回到第②步；⑤输出x。3.算法的特征（1）有穷性；（2）确定性：每个步骤必须有确切的定义，不能出现模棱两可的情况；（3）数据输入：算法可以有零个或多个输入；（4）数据输出：算法必须有一个或多个输出；（5）可行性：任何步骤都可执行，能在有限时间内完成。4.算法的描述（1）用自然语言描述算法易掌控当算法较复杂时，用自然语言很难清晰表示自然语言具有歧义性，容易导致算法执行的不确定性4.算法的描述（2）用流程图描述算法使算法的流程描述得清晰、简洁

流程图的基本图形及其功能起始框：表示算法的开始和结束处理框：表示完成某种操作判断框：表示根据一个条件成立与否，决定执行两种不同操作的其中一个输入、输出框：表示数据的输入输出流程线：用箭头表示程序执行的流向朋友的意思程序猿的理解例2：韩信点兵①总人数x=2300；②判断x是否在2300~2400之间，满足则执行下一步，否则结束；③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步；④x在原来的基础上加1，回到第②步；⑤输出x。4.算法的描述（3）用伪代码描述算法伪代码是介于自然语言和计算机语言之间的文字和符号。是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。它没有任何编程语言的语法，因此无法由计算机编译或解释。4.算法的描述（3）用伪代码描述算法“韩信点兵”问题：if(x>=2300andx<=2400): if(x%3==2andx%5==3andx%7==2): {输出对应的x的值}4.算法的描述（3）用伪代码描述算法不用图形符号，每条指令占一行书写方便，格式紧凑易于理解便于向计算机程序设计语言过渡5.常用算法枚举法：也称“穷举法”。将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。解析法：用解析的方法，找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式计算实现问题求解。一般使用公式进行计算的计算机程序都是用的解析法。递归法：通过重复将问题分解为同类的子问题。分治法：将一个规模较大的问题分解为若干个规模较小的子问题，通过解决子问题就可得到原问题的解。《张邱建算经》中有一个“百鸡问题”：“今有鸡翁一,值钱伍;鸡母一,值钱三;鸡雏三,值钱一。凡百钱买鸡百只,问鸡翁、母、雏各几何？”

张邱建：北魏时期数学家，“百鸡问题”是中古时期关于不定方程正整数解的典型问题，张邱建对此有精湛和独到的见解。著有《张邱建算经》3卷。6.算法的优化分析：设可以买公鸡x只，母鸡y只，小鸡z只，根据题意可得出：x+y+z=100

5x+3y+z/3=10010000次x+y+z==100

and

5*x+3*y+z/3==100?分析：设可以买公鸡x只，母鸡y只，小鸡z只，根据题意可得出：x+y+z=100

5x+3y+z/3=100X的范围：0<X<=20Y的范围：0<Y<=33660次x+y+z==100

and

5*x+3*y+z/3==100?分析：设可以买公鸡x只，母鸡y只，小鸡z只，根据题意可得出：x+y+z=100

5x+3y+z/3=100x+y=100-z5x+3y=100-z/3x=4*z/3－100y=200－7*z/333次forzinrange(3,100,3):x=4/3*z-100y=200-7/3*zifx>0andy>0:print(int(x),int(y),int(z))分析：设可以买公鸡x只，母鸡y只，小鸡z只，根据题意可得出：x+y+z=100

5x+3y+z/3=100x+y=100-z5x+3y=100-z/30<x=4*z/3－100<=200<y=200－7*z/3<=333次forzinrange(78,85,3):x=4/3*z-100y=200-7/3*zifx>0andy>0:print(int(x),int(y),int(z))75<z<85二、计算机程序与程序设计语言1.计算机程序

计算机程序是指计算机可以识别运行的指令集合。二、计算机程序与程序设计语言2.算法与计算机程序的关系程序算法灵魂代码实现算法与程序相互依附，算法要在计算机上执行，必须将算法的步骤用编程语言的语法描述出来，编译通过后，方可在计算机上执行。二、计算机程序与程序设计语言3.计算机程序设计语言2023年顶级编程语言交互排行榜Dimx,y,zasintegerForx=1to100Step1Fory=1to100Step1

Z=100-x-yIf5*x+3*y+z/3=100ThenPrintx,y,zEndifNextyNextxVB

forxinrange(1,101):

foryinrange(1,101):

z=100-x-y

ifx+y+z==100and5*x+3*y+z/3==100:print(x,y,z)python3.计算机程序设计语言（1）机器语言是由“0”和“1”这样的二进制代码指令组来表示。每一条机器指令包含两个主要部分：操作（指出计算机应做什么）和被操作的对象（指出处理的数据或它的地址），计算机能直接识别和执行。3.计算机程序设计语言（1）机器语言3.计算机程序设计语言（2）汇编语言使用了一种类似英文缩略词且带有助记性符号的语言，来替代一个特定的指令的二进制串，每条指令都和一条机器指令相对应。需要一个专门的语言翻译器，负责将程序中的每条语句都翻译成用二进制数表示的机器语言。3.计算机程序设计语言（2）汇编语言3.计算机程序设计语言（3）高级语言接近于数学语言或人的自然语言，并且不再过度地倚赖某种特定的机器或环境，必须经过翻译器将其翻译成机器语言。3.计算机程序设计语言（2）高级语言3.计算机程序设