第31课时 算法初步

景简单了解算法的历史背代数学之父”。《代数学》，被誉为“著作有《算法》、花拉子米的名字，主要阿尔家一词起源于阿拉伯数学算法)lg(.1orithma组成的那种形式。被设想为由模式最有趣的方式之一，是方式中，对世界各式各样的观察个很高的评价的一句名言给了算法一论的创始人维纳美国著名数学家、控制:.2那么，什么是算法呢？加以说明。下面我们通过两个例子？子邮件，你能教会他吗假如你的朋友不会发电.1之一是：发电子邮件的操作步骤第一步打开电子信箱；第二步单击“写邮件”按钮；第三步输入发送地址；第四步输入主题；第五步输入信件内容；第六步；单击“发送邮件”按钮该件商品。商品的价格，就可获得内猜出某种竞猜者如在规定的时间戏：中，有一个“猜数”游幸运52.2猜出正确的答案？较短的时间内采取怎样的策略才能在元之间，～现有一商品的价格在80000较好的方法是：第一步”；报“4000第二步”；报“之间）～”，否则（答案在就报“之间），～说明答案在若主持人说“高了”（600080004000200040000第三步。，直到得到正确的结果重复第二步的报数方法么共同特点？上面的两个例子，有什的统一方法和步骤。，完成某一类事情上面两个例子都给出了执行的一系列操作。某种顺序都是在一定的条件下按件事情，事实上，我们做任意一步骤、程序进行操作。常可以按统一的方法、此，对于某一问题，解决数学问题也常常如问题的速度。提高了解决行操作，这样就极大地就可以借助与计算机进的语言后，序转换成计算机能识别将这些方法、步骤、程要。一程序，就显得十分重因此探求解决问题的统算法统一的求解方法。对一类问题的机械的、：实际上，算法就是研究理的思考一个问题；如何有根有据，有条有.1理的处理问题；如何有根有据，有条有.2言表达出来；的过程、步骤用数学语理的把思考和处理问题如何有根有据，有条有.3临和解决两个问题：所以研究算法主要要面题的方法和步骤？如何思考、设计解决问.1的方法和步骤？考、设计解决问题如何用数学语言描述思.2法的例子吗？你能举出日常生活中算自然语言一.的一个算法给出求543211例题逐一相加法算法1第一步第二步第三步第四步；，得到计算321；相加，得到与将第一步中的运算结果633；相加，得到与将第二步中的运算结果1046。相加，得到与将第三步中的运算结果15510注意：)1(S第一步步）(step公式法算法21S2S3S；取5n；计算2)1(nn输出计算结果。1S2S3S；5n；2)1(nnS。输出S那么如何将其互换。和醋，两个瓶子，分别盛放酒和设有BA2例题1SAC2SBA3SCB注意：.pxxp的值赋给变量表示将算法的特点.1有限性).1(确定性).2(有序性).3(不唯一性).4(普遍性).5(即不是算法。法没有意义，因此没有输出结果的算题，算法是为了解决某类问.2注意：引例输出结果是多少？样的算法？如能它表示了一个什么？下列操作能表示算法吗开始1S2I5IYISS1IINS输出结束起止框.常用圆角矩形表示，表示算法的开始或结束处理框.常用矩形表示表示赋值或计算，流程线.常用箭头表示表示执行步骤的路径，判断框.常用菱形表示路径中的某一条，根据条件决定执行两条输入、输出框.常用平行四边形表示表示输入或输出操作，★流程图二)(.chartflow次序。流程线表示操作的先后示操作的内容，图框中的文字和符号表的类型，其中图框表示各种操作成，由一些图框和流程线组。法清晰直观的表示出来流程图能将设计好的算有的需循环执行。有的需选择执行，有的按顺序执行，出，该算法的步骤中，从上面的流程图可以看本结构。来。流程图有这三种基通过组合和嵌套表达出环结构序结构、选择结构和循事实上，算法可以由顺)(.1structuresequence顺序结构引例的外接圆的一个算法写出作ABC1S；的垂直平分线作1lAB2S；的垂直平分线作2lBC3S的外接圆。即为圆为半径作圆，为圆心，以的交点与以ABCOOAOll21顺序结构)1(构称为顺序结构。依次进行多个处理的结顺序结构的流程图表示)2(AB1例并画出流程图。的值的一个算法，设设计交换这两个变量的值，和了变量已知两个单元分别存放yx1Sxp2Syx3Spy开始xpyxpy结束自然语言流程图1S10r2S2rS3SS输出开始10r2rSS输出结束自然语言流程图2例图。一个算法，并画出流程时，写出计算圆面积的当半径的圆的面积计算公式为半径为10,2rrSr)(.2structureselection选择结构引例并画出流程图。用设计一个算法，请为计算托运行李的费）之间的关系：（单位：与行李的重量（单位：元）旅客托运行李的费用、乙两地之间某铁路客运部门规定甲.50,85.0)50(53.050,50,53.0输入行李的重量2S,53.050c，那么如果3S.c和托运费输出行李的重量自然语言;85.0)50(53.050c否则，流程图开始输入50YN53.0c85.0)50(53.050cc,输出结束）选择结构（1的结构称为选择结构。再决定执行哪一种操作先根据条件作出判断，示）选择结构的流程图表（2YABpN例题程图。的一个算法，并画出流设计求解一元二次方程)0(02acbxax1S;,,cba输入2S;,0根”那么输出“方程无实数如果3S自然语言.,,2,22121xxabxabx输出否则，acb42流程图开始cba,,输入acb420YN“方程无实数根”输出abxabx2,22121,xx输出结束变题程图。如何修改上述算法和流还是不等的实数根）实数根息（区别是两个相等的如果要输出根的详细信,1S;,,cba输入2S;,0根”那么输出“方程无实数如果3S自然语言否则，acb42.20xabx输出，如果.,,2,22121xxabxabx输出否则，流程图开始cba,,输入acb420YN“方程无实数根”输出0Yabx2x输出Nabxabx2,22121,xx输出结束★循环结构)(.3structurecycle引例并画出流程图。算法来描述上述过程，多远。请设计一个那么又会想离终点还有如果没有跑完全程，会想是否跑完了全程。圈，长跑测试中，你每跑在学校的110000m1S，，转如果未跑到310000Sm;起跑2S3S圈，跑1;2S转；否转4S4S;结束自然语言开始流程图0S10000SY400SSN结束循环结构)1(的结构称为～。需要重复执行同一操作当型循环)2(不成立为止。条件如此反复，直到某一次仍成立，则又执行若是否成立，再判断，成立，则执行若是否成立，先判断所给的条件pAppApp,当型循环的流程图表示)3(注意：，后执行”；①当型循环是“先判断退出”；循环，②当型循环是“NYpYAN1S，，转如果跑到410000Sm;起跑2S3S;1圈跑；否则转2S4S.结束自然语言开始流程图0S10000SY400SSN结束直到型循环)4(成立为止。条件如此反复，直到某一次，不成立，则再执行若是否成立，再判断所给的条件先执行pAppA示直到型循环的流程图表)5(注意：行，后判断”；①直到型循环是“先执循环”；退出，②直到型循环是“NY可以相互转化。直到型循环和当型循环)6(pYAN1例并画出流程图。的一个算法写出求,54321.,:所以使用循环设计因为需要重复进行乘法分析当型循环设计1S;1T2S;2I3S，转如果4,5SI4S;ITT5S;3,1SII转6S否则转6ST输出开始流程图1T5IYITTN结束2I1IIT输出改成直到型循环。请把上面算法和流程图直到型循环设计1S;1T2S;2I3S，转如果6,5SI4S;ITT5S;1II3S否则转6ST输出开始流程图1T5IYITTN结束2I1IIT输出并画出流程图。个数的平均数的算法，设计一个计算102例当型循环设计1S0S2S1I3S,4,10SI那么转如果4SG输入5SGSS6S3,1SII转7S否则转7S10Sx8Sx输出开始流程图0S10IYGSSN结束1I1IIx输出G输入10Sx改成直到型循环。请把上面算法和流程图）★基本算法语句（伪代码三.赋值语句.1”表示赋值语句用“xyyx的值赋给”表示将“输入、输出语句.2.,,Rebabaad给表示输入的数据依次送”输入语句用“.intPrxx表示输出运算结果”输出语句用“条件语句（选择结构）.3条件语句的一般形式：BElseIfEndIfThenAC注意：;.1”分支条件语句也可以没有“Else.称为单行条件语句”束标志“单行条件语句不需要结IfEnd.21例收取的卫生费？根据输入的人数计算应如何设计算法元。人加收人的住户，每超出超过元；取人以下的住户，每户收人和生费：每月按以下方法收取卫某居民小区的物管部门,.2113533，则表示某户人家的人口数用，（元）表示应收取的费设xy3),3(2.1530,5xxxy自然语言1S;x输入2S;5,3yx那么如果)3(2.15xy否则3Sy输出流程图开始x输入3xYN5y)3(2.15xyy输出结束伪代码5yElseIfEndIfThen3x)3(2.15xyadReintPrxy2例出伪代码。并画出流程图值的一个算法计算的值，写出根据输入已知函数,,,0,20,00,log2yxxxxxyx1S;x输入2S;log,02xyx那么如果自然语言否则，;00yx，那么如果;2xy否则，3S.y输出流程图开始x输入0xYNxy2log0xY0yx输出Nxy2结束xy2logElsexadReIfEndIfThen0xintPryxy2IfThen0x0yElseIfEnd伪代码★循环语句（循环结构）.4形式）当型循环语句的一般（1循环体pWhileWhileEnd般形式）直到型循环语句的一（2DoEnd循环体DoUntilp:3”语句的一般形式）“（ForForEnd循环体ForFrom“初值”ToStep“步长”“终值”I注意：数已知；”语句，必须是循环次①用“For循环是当型循环；②用For“步长”。，则可省略：③若步长为Step1例写出伪代码。并画出流程图的一个算法写出求,,997531.,:所以使用循环设计因为需要重复进行乘法分析当型循环设计1S;1T2S;3I3S，转如果4,99SI4S;ITT5S;3,2SII转6S否则转6ST输出自然语言开始流程图1T99IYITTN结束3I2IIT输出1T3IITT2II99IWhileWhileEndintPrT伪代码当型循环语句”语句“For1TForFrom3ToStep299IITTForEnd直到型循环设计1S;1T2S;3I3S，转如果6,99SI4S;ITT5S;2II3S否则转6ST输出自然语言开始流程图1T99IYITTN结束3I2IIT输出伪代码1T3IintPrDoEndITT2IIDoUntil99IT,0S,2n1i开始nSS12nn1iiS输出结束YN内应填入的条件是流程图，其中判断框的值的一个算法以下给出的是计算201614121.110i开始,0S1i10i是偶数iiSS1iiiSSS输出结束YNYN的运行结果是的流程图表示如下图所示.25开始n输入,0S1iiimmSS2iiniS输出结束YN时输出的结果是当，算法流程图如下图所示6