第2章程序的灵魂算法PPT讲稿.ppt

《第2章程序的灵魂算法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第2章程序的灵魂算法PPT讲稿.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章程序的灵魂算法2022/9/171第1页，共60页，编辑于2022年，星期一第第2章章 程序的灵魂程序的灵魂算法算法本章主要介绍算法的概念、算法的特征、本章主要介绍算法的概念、算法的特征、算法的表示法以及结构化程序设计。算法的表示法以及结构化程序设计。2.1 算法的概念与举例算法的概念与举例2.2 算法的特征算法的特征2.3 算法的表示方式算法的表示方式2.4 结构化程序设计方法结构化程序设计方法2022/9/172第2页，共60页，编辑于2022年，星期一算法的概念与举例算法的概念与举例计算机科学家沃思（计算机科学家沃思（Nikiklaus Wirth）提出一个公式）提出一个公式：数据

2、结构数据结构+算法算法=程序程序 目前，认为程序设计包括四个方面，目前，认为程序设计包括四个方面，表示如下：表示如下：程序程序=算法算法+数据结构数据结构+程序设计方法程序设计方法+语言工具和环境语言工具和环境 算法算法是灵魂，解决是灵魂，解决“做什么做什么”和和“怎么做怎么做”的问题；的问题；数据结构数据结构是加工对象；是加工对象；编程需要采用合适的方法，不了解算法则谈不上编程需要采用合适的方法，不了解算法则谈不上程序设计程序设计；语言语言是工具。是工具。厨师炒菜：厨师炒菜：炒法炒法+原料原料+操作和炒菜工具。操作和炒菜工具。2022/9/173第3页，共60页，编辑于2022年，星期一算法

3、的概念和特性算法的概念和特性 算算法法的的概概念念：广广义义地地讲讲，为为解解决决一一个个问问题题而而采采取取的的方方法法和和步步骤，就称为骤，就称为“算法算法”。说说明明1：计计算算机机是是低低能能儿儿、是是没没有有思思维维的的，需需要要程程序序设设计计者者设计算法；设计算法；说说明明2：解解决决同同一一问问题题可可以以有有不不同同的的方方法法和和步步骤骤，好好的的算算法法不不仅保证解决问题，还要有高的效率；仅保证解决问题，还要有高的效率；举举例例：从从我我们们学学校校到到德德胜胜门门可可以以直直接接乘乘坐坐345到到达达，也也可可以以做做345到到沙沙河河再再转转919到到达达；两两种种方

4、方法法都都能能到到达达德德胜胜门；后一种方法可能费时费力，该方法可能不科学门；后一种方法可能费时费力，该方法可能不科学！2022/9/174第4页，共60页，编辑于2022年，星期一算法的概念和特性算法的概念和特性 说说明明3：可可以以将将一一些些常常用用的的算算法法集集合合在在一一起起，形形成成“算算法法程程序序库库”，方方便便应应用用。如如数数学学程程序序库库（求求正正旋旋、余余旋旋、求求开开方方等等），和和其其他他非非数值算法，如排序等。数值算法，如排序等。如：如：stdio.h是输入输出库，是输入输出库，math.h 数学库。数学库。说说明明4：计计算算机机的的算算法法与与常常规规的的

5、数数值值算算法法有有所所区区别别，计计算算机机的的算算法法包包括括数数值值算算法法和和非数值算法非数值算法：（1）数数值值运运算算方方法法：目目的的是是数数值值求求解解。如如求求方方程程的的根根。应应用用非非常常深深入入，如如“Fortran 程序库程序库”；（2）非非数数值值运运算算方方法法：最最常常见见的的是是用用于于事事务务管管理理领领域域，例例如如图图书书管管理理、人人事事管管理理、行行车车调调度度等等。目目前前，计计算算机机在在非非数数值值运运算算方方面面的的应应用用远远超超过过数数值值运运算算方方面面应应用。用。2022/9/175第5页，共60页，编辑于2022年，星期一算法的特

6、性算法的特性（1）有穷性，往往指是在合理的范围内有穷）有穷性，往往指是在合理的范围内有穷;（2）确确定定性性，算算法法的的步步骤骤应应当当是是确确定定的的，不不应应是是含含糊糊不不清的清的;（3）有零个或多个输入）有零个或多个输入;（4）有有一一个个或或多多个个输输出出。无无输输出出的的算算法法通通常常是是无无意意义义的的;（I/O）（5）有效性。）有效性。2022/9/176第6页，共60页，编辑于2022年，星期一算法的表示算法的表示自然语言自然语言流程图流程图传统流程图传统流程图N-S流程图流程图伪代码伪代码2022/9/177第7页，共60页，编辑于2022年，星期一 用传统流程框图表

7、示算法用传统流程框图表示算法 起止框起止框 判断框判断框 流程线流程线 注释框注释框 输入输出框输入输出框 处理框处理框 连接点连接点 流程图符号流程图符号2022/9/178第8页，共60页，编辑于2022年，星期一输入三个数，输出其中最大的数输入三个数，输出其中最大的数算法：算法：首首先先，找找个个地地方方放放这这三三个个数数，定定义义三三个个变变量量A、B、C，将将三三个个数数依依次次输输入入到到、B、C中中，另外，再准备一个另外，再准备一个MAX放最大数；放最大数；由由于于计计算算机机一一次次只只能能比比较较两两个个数数，于于是是先先把把A与与B比比，大大的的数数放放入入MAX中中，再

8、再把把MAX与与C比，又把大的数放入比，又把大的数放入MAX中；中；最最后后，把把MAX输输出出，此此时时MAX中中放放的的就就是是、C三数中最大的数。三数中最大的数。2022/9/179第9页，共60页，编辑于2022年，星期一求1-1/2+1/3-1/4+1/99-1/100开开 始始1 sum2 deno1 sign(-1)*sign signsign*(1/deno)termsum+term sumdeno+1 denodeno100NY结束结束输出输出sum值值2022/9/1710第10页，共60页，编辑于2022年，星期一算法的三种基本结构算法的三种基本结构顺序结构顺序结构选择结

9、构（分支结构）选择结构（分支结构）循环结构（重复结构）循环结构（重复结构）当型（当型（While）循环结构）循环结构直到型（直到型（Until）循环结构）循环结构2022/9/1711第11页，共60页，编辑于2022年，星期一顺序结构顺序结构顺序结构顺序结构：坐：坐：坐：坐345345从中国政法大学到德胜门买衣服；从中国政法大学到德胜门买衣服；从中国政法大学到德胜门买衣服；从中国政法大学到德胜门买衣服；选选选选择择择择结结结结构构构构：坐坐坐坐345345从从从从中中中中国国国国政政政政法法法法大大大大学学学学到到到到德德德德胜胜胜胜门门门门买买买买衣衣衣衣服服服服，若若若若车车车车在在在在

10、沙沙沙沙河河河河坏坏坏坏了，就转了，就转了，就转了，就转919919到德胜门；否则，坐到德胜门；否则，坐到德胜门；否则，坐到德胜门；否则，坐345345直接到德胜门；直接到德胜门；直接到德胜门；直接到德胜门；循循循循环环环环结结结结构构构构：坐坐坐坐345345从从从从中中中中国国国国政政政政法法法法大大大大学学学学到到到到德德德德胜胜胜胜门门门门买买买买衣衣衣衣服服服服，如如如如果果果果你你你你带带带带的的的的钱钱钱钱不够，需要回来取钱再去，直到钱够！不够，需要回来取钱再去，直到钱够！不够，需要回来取钱再去，直到钱够！不够，需要回来取钱再去，直到钱够！三种基本结构的类比举例三种基本结构的类比

11、举例2022/9/1712第12页，共60页，编辑于2022年，星期一三种基本结构的共同点三种基本结构的共同点（1）只有一个入口）只有一个入口（2）只有一个出口）只有一个出口（3）结构内的每一部分都有机会被执行到）结构内的每一部分都有机会被执行到（4）结构内不存在）结构内不存在“死循环死循环”2022/9/1713第13页，共60页，编辑于2022年，星期一用用N-S流程图表示算法流程图表示算法 1973年美国学者年美国学者I.Nassi和和B.Shneiderman提出了所谓的提出了所谓的N-S流程图。流程图。顺序结构顺序结构选择结构选择结构循环结构循环结构 2022/9/1714第14页，

12、共60页，编辑于2022年，星期一N-S图特点说明图特点说明（1）比文字描述直观、形象、易于理解；）比文字描述直观、形象、易于理解；（2）比比传传统统流流程程图图紧紧凑凑易易画画，尤尤其其是是其其废废除除流流程程线线，整整个个算算法法结构是由各个基本结构按顺序组成；结构是由各个基本结构按顺序组成；（3）N-S图图的的上上下下顺顺序序就就是是执执行行顺顺序序，用用N-S图图表表示示的的算算法法是是结结构构化化算算法法：由由一一些些基基本本单单元元组组成成，在在基基本本单单元元之之间间不不存存在在向向前前或向后的跳转，流程的转移只存在于一个基本结构范围内。或向后的跳转，流程的转移只存在于一个基本结

13、构范围内。2022/9/1715第15页，共60页，编辑于2022年，星期一判断闰年的算法闰闰年年的的条条件件：（1）能能被被4整整除除，但但不不能能被被100整整除除的的年年份份都都是是闰闰年年；（2）能能被被100整整除除，又又能能被被400整整除除的的年年份份是是闰闰年年。不不符合这两个条件的年份不是闰年。符合这两个条件的年份不是闰年。2022/9/1716第16页，共60页，编辑于2022年，星期一用传统流程图表示y+1 y开开 始始2000 yy不能被不能被4整除整除y不能被不能被100整除整除打印打印y“是闰年是闰年”打印打印y“不是闰年不是闰年”y不能被不能被400整除整除打印打

14、印y“是闰年是闰年”打印打印y“不是闰年不是闰年”结结 束束Y2500YNYYNNNY2022/9/1717第17页，共60页，编辑于2022年，星期一用N-S流程图表示y+1 y2000 y y/4的余数为的余数为0是是否否 y/100的余数不为的余数不为0是是否否打印打印y“是闰年是闰年”y/400的余数的余数为为0打印打印y“是闰年是闰年”打印打印y“非闰年非闰年”是是否否直到直到y 2500打印打印y“非闰年非闰年”2022/9/1718第18页，共60页，编辑于2022年，星期一1 1 结构化程序结构化程序 用高级语言表示的结构化算法就是结构化程序，用高级语言表示的结构化算法就是结构

15、化程序，用三种用三种基本结构组成的程序必然是结构化的程序。基本结构组成的程序必然是结构化的程序。结构化程序设计方法结构化程序设计方法2022/9/1719第19页，共60页，编辑于2022年，星期一2 结构化程序设计的思路结构化程序设计的思路 把一个问题求解过程分阶段进行，每个阶段处理的问题都把一个问题求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理范围：控制在人们容易理解和处理范围：（1）自顶向下；）自顶向下；（2）逐步细化；）逐步细化；（3）模块化设计；）模块化设计；（4）结构化编码：）结构化编码：用高级语言正确实现三种基本结构用高级语言正确实现三种基本结构结构化程序设计方

16、法结构化程序设计方法2022/9/1720第20页，共60页，编辑于2022年，星期一工作报告工作报告前期工作前期工作将来打算将来打算成成功功之之处处失失败败之之处处短短期期打打算算长长期期打打算算用结构化思路编写工作报告用结构化思路编写工作报告结构化程序设计方法结构化程序设计方法2022/9/1721第21页，共60页，编辑于2022年，星期一 1.结结构构化化程程序序设设计计结结构构清清晰晰、层层次次分分明明、作作者者容容易易编编写写，读读者易懂；者易懂；2.自自顶顶向向下下、逐逐步步细细化化的的设设计计方方法法是是将将问问题题从从抽抽象象到到具具体体化化的的过程；过程；3.层层层层设设计

17、计、层层层层分分析析，容容易易保保证证能能够够算算法法的的正正确确性性、保保证证思思路路清清晰；晰；4.复杂程序采用模块化设计，对整体的任务分模块完成。复杂程序采用模块化设计，对整体的任务分模块完成。盖房子盖房子图纸设计图纸设计工程施工工程施工质量检查质量检查子模块子模块1子模块子模块2子模块子模块3结构化程序设计方法结构化程序设计方法2022/9/1722第22页，共60页，编辑于2022年，星期一注注 意意 学学习习程程序序设设计计的的目目的的不不仅仅学学习习一一种种语语言言，而而是是学学习习进进行行程程序序设设计计的的一一般般方方法法，掌掌握握了了算算法法，则则掌掌握握了了程程序序设设计

18、计的的灵灵魂魂，总总体体上上讲讲，不不能能拘拘泥泥于于一一种种具具体体的的语语言言，但但是是，目前，通过本课程我们应该学会目前，通过本课程我们应该学会C语言！语言！2022/9/1723第23页，共60页，编辑于2022年，星期一C语言上机地点和时间语言上机地点和时间地点：地点：润杰公寓六层机房润杰公寓六层机房时间：时间：2,3,5,7,9,11,13,15周周 星期三星期三 15:3017:152022/9/1724第24页，共60页，编辑于2022年，星期一九月九月 22上机流程与注意问题上机流程与注意问题（1）1建立个人目录和进入建立个人目录和进入VC+环境环境（1）利用资源管理器在）利

19、用资源管理器在D盘上建立个人目录（字母或数字）；盘上建立个人目录（字母或数字）；（2）双双击击桌桌面面“Microsoft Visual C+6.0”的的快快捷捷方方式式，或或者者单单击击“开开始始程程序序Microsoft Visual Studio 6.0Microsoft Visual C+6.0”，进进入入Visual C+6.0环境的主界面；环境的主界面；2创创建建工工程程：单单击击“FileNew”选选项项，选选择择“NewProjects”选选项项，选选择择“Win32 Console Application”工工程程类类型型，分分别别在在“Project name”栏栏和和“L

20、ocation”栏栏中中填填写写工工程程名名、选选择择路路径径，然然后后单单“OK”按按钮钮，在在弹弹出出的的对对话话框框中单击中单击“Finish”按钮，再单击按钮，再单击“OK”按钮按钮，完成，完成工程的创建；工程的创建；2022/9/1725第25页，共60页，编辑于2022年，星期一九月九月 22上机流程与注意问题上机流程与注意问题（2）3创创建建源源文文件件和和输输入入编编辑辑源源程程序序：单单击击“FileNew”选选项项，选选择择“NewFiles”选选项项，选选择择“C+Source File”文文件件类类型型，并并在在“File”栏栏中中填填写写文文件件名名（examp3），

21、单击单击“OK”按钮，进入代码编辑窗口进行程序的输入；按钮，进入代码编辑窗口进行程序的输入；4源源程程序序的的编编译译：单单击击“Build Compile examp3.CPP”选选项项，进进行行源源程程序序的的编编译译，若若输入的源程序没有错误，则在工作目录中形成后缀为输入的源程序没有错误，则在工作目录中形成后缀为.OBJ的目标程序；的目标程序；5目目标标程程序序的的连连接接：单单击击“Build Build sum1.EXE”选选项项，进进行行目目标标程程序序的的连连接接。若无错误，在工作目录中形成后缀为若无错误，在工作目录中形成后缀为.EXE的可执行文件；的可执行文件；6可可执执行行程

22、程序序的的运运行行：单单击击“Build Execute sum1.EXE”选选项项，产产生生结结果果；在在结结果显示窗口查看结果。果显示窗口查看结果。2022/9/1726第26页，共60页，编辑于2022年，星期一九月九月 22上机流程与注意问题（上机流程与注意问题（3）7其他其他（1）目录名、文件名符合个人习惯和系统要求）目录名、文件名符合个人习惯和系统要求（2）输入程序一定要细心：）输入程序一定要细心：“inclnde”，“toois”，“intx”等等（3）打开已经存在的文件：）打开已经存在的文件：File（Open）（4）文件改变后）文件改变后注意保存注意保存，以当前文件名保存程序

23、：点击，以当前文件名保存程序：点击File（Save）（5）把当前文件存为新文件：点击）把当前文件存为新文件：点击File（Save as），然后输入新文件名），然后输入新文件名（6）下课后下课后，退出，退出“Microsoft Visual C+6.0”集成环境集成环境8只只能能调调试试以以.CPP为为后后缀缀的的源源文文件件；不不可可以以打打开开或或调调试试后后缀缀为为.OBJ和和.EXE的的文文件！件！9 务必把需要上机调试的程序在上机前编写完成！务必把需要上机调试的程序在上机前编写完成！10上机严肃认真！目前，以上课讲授的内容、要求和操作为主！上机严肃认真！目前，以上课讲授的内容、要求

24、和操作为主！2022/9/1727第27页，共60页，编辑于2022年，星期一举例操作说明举例操作说明（1）建立的目录：）建立的目录：D:wangwuD:wangwu（2）工程名：）工程名：Sum1 路路 径：径：D:wangwuD:wangwu（3 3）C C语言源程序名：语言源程序名：语言源程序名：语言源程序名：examp3.cppexamp3.cpp2022/9/1728第28页，共60页，编辑于2022年，星期一创建文件夹2022/9/1729第29页，共60页，编辑于2022年，星期一2022/9/1730第30页，共60页，编辑于2022年，星期一2022/9/1731第31页，共

25、60页，编辑于2022年，星期一2022/9/1732第32页，共60页，编辑于2022年，星期一(1)Open VC+平台窗口九月九月 22II-33CDEA AB BF F2022/9/1733第33页，共60页，编辑于2022年，星期一(2)New Project2022/9/1734第34页，共60页，编辑于2022年，星期一(3)确定Project 性质2022/9/1735第35页，共60页，编辑于2022年，星期一确定工作目录2022/9/1736第36页，共60页，编辑于2022年，星期一(3)2022/9/1737第37页，共60页，编辑于2022年，星期一(4)确定proj

26、ect名字2022/9/1738第38页，共60页，编辑于2022年，星期一(5)2022/9/1739第39页，共60页，编辑于2022年，星期一(6)2022/9/1740第40页，共60页，编辑于2022年，星期一(7)完成Project创建2022/9/1741第41页，共60页，编辑于2022年，星期一浏览Project内容2022/9/1742第42页，共60页，编辑于2022年，星期一(8)New file2022/9/1743第43页，共60页，编辑于2022年，星期一(9)确定Files 性质2022/9/1744第44页，共60页，编辑于2022年，星期一(10)确定fil

27、e 名字:examp32022/9/1745第45页，共60页，编辑于2022年，星期一2022/9/1746第46页，共60页，编辑于2022年，星期一(11)完成filet创建:examp3.cpp2022/9/1747第47页，共60页，编辑于2022年，星期一(12)编辑examp3.cpp文件2022/9/1748第48页，共60页，编辑于2022年，星期一(13)Save examp3.cpp2022/9/1749第49页，共60页，编辑于2022年，星期一(14)完成examp3.cpp保存2022/9/1750第50页，共60页，编辑于2022年，星期一(15)编译examp3

28、.cpp2022/9/1751第51页，共60页，编辑于2022年，星期一(16)examp3.cpp编译完成,无错2022/9/1752第52页，共60页，编辑于2022年，星期一(17)试图形成sum1.exe2022/9/1753第53页，共60页，编辑于2022年，星期一(18)sum1.exe形成(完成)2022/9/1754第54页，共60页，编辑于2022年，星期一(19)运行sum1.exe2022/9/1755第55页，共60页，编辑于2022年，星期一(20)运行结果窗口2022/9/1756第56页，共60页，编辑于2022年，星期一(21)返回VC+平台窗口2022/9

29、/1757第57页，共60页，编辑于2022年，星期一上机作业（上机作业（1）（1）编写一个）编写一个C程序，输入程序，输入a,b,c三个整数，输出其中三个整数，输出其中的最大数。的最大数。（2）编写一个）编写一个C程序，输入程序，输入a,b,c三个浮点数，输出三个浮点数，输出其中的最小数。其中的最小数。（3）例）例3.1、例、例3.2、例、例3.3和例和例3.42022/9/1758第58页，共60页，编辑于2022年，星期一上机作业上机作业第二次第二次第二次第二次（1）4.5（2）4.8（3）4.9（4）5.4（5）5.5（5）三角形求面积）三角形求面积（6）例）例5.5、例、例5.6第三

30、次第三次第三次第三次（1）6.4 、6.5（2）6.8、6.11（3）例）例6.6、例例6.7、例、例6.9第四次第四次第四次第四次（1）例）例7.4，例，例 7.5，例，例7.7（2）7.5，7.6（3）有有一一4行行、4列列的的矩矩阵阵，求求对对角角线线元元素素之之和和；求求对对角角线线元元素素之之积积；求求所所有有元元素素的的平平均均值值；求所有元素中的最大值；输出下三角矩阵。求所有元素中的最大值；输出下三角矩阵。第五次第五次第五次第五次（1）复习！）复习！（2）10行行、5列列的的数数组组，求求和和；求求平平均均值值；求求每每行行的的最最大大值值；求求每每列列的的最最大值；大值；（3）

31、习题）习题8.2（4）例）例8.6 2022/9/1759第59页，共60页，编辑于2022年，星期一上机作业上机作业(new)作业二作业二作业二作业二（1）例）例6.6（2）6.4（3）6.5（4）6.8（5）6.11（6）例）例7.2、7.4（7）7.5（8）7.6 作业三作业三作业三作业三（1）4行、行、4列的数组，求对角线列的数组，求对角线的和；求所有元素的平均值；的和；求所有元素的平均值；求所有元素中的最大值。求所有元素中的最大值。（2）5行、行、6列的数组，求和；列的数组，求和；求平均值；求每行的最大求平均值；求每行的最大值；求每列的最大值值；求每列的最大值（3）8.2（4）例）例8.6（5）例）例10.2和例和例10.32022/9/1760第60页，共60页，编辑于2022年，星期一