第2章程序的灵魂算法精选文档.ppt

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

1、第2章程序的灵魂算法2023/4/101本讲稿第一页，共六十页第第2章章 程序的灵魂程序的灵魂算法算法本章主要介绍算法的概念、算法的特征、本章主要介绍算法的概念、算法的特征、算法的表示法以及结构化程序设计。算法的表示法以及结构化程序设计。2.1 算法的概念与举例算法的概念与举例2.2 算法的特征算法的特征2.3 算法的表示方式算法的表示方式2.4 结构化程序设计方法结构化程序设计方法2023/4/102本讲稿第二页，共六十页算法的概念与举例算法的概念与举例计算机科学家沃思（计算机科学家沃思（Nikiklaus Wirth）提出一个公式）提出一个公式：数据结构数据结构+算法算法=程序程序 目前，

2、认为程序设计包括四个方面，目前，认为程序设计包括四个方面，表示如下：表示如下：程序程序=算法算法+数据结构数据结构+程序设计方法程序设计方法+语言工具和环境语言工具和环境 算法算法是灵魂，解决是灵魂，解决“做什么做什么”和和“怎么做怎么做”的问题；的问题；数据结构数据结构是加工对象；是加工对象；编程需要采用合适的方法，不了解算法则谈不上编程需要采用合适的方法，不了解算法则谈不上程序设计程序设计；语言语言是工具。是工具。厨师炒菜：厨师炒菜：炒法炒法+原料原料+操作和炒菜工具。操作和炒菜工具。2023/4/103本讲稿第三页，共六十页算法的概念和特性算法的概念和特性 算算法法的的概概念念：广广义义

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

4、法可能不科学门；后一种方法可能费时费力，该方法可能不科学！2023/4/104本讲稿第四页，共六十页算法的概念和特性算法的概念和特性 说说明明3：可可以以将将一一些些常常用用的的算算法法集集合合在在一一起起，形形成成“算算法法程程序序库库”，方方便便应应用用。如如数数学学程程序序库库（求求正正旋旋、余余旋旋、求求开开方方等等），和和其其他他非非数数值值算算法法，如如排排序等。序等。如：如：stdio.h是输入输出库，是输入输出库，math.h 数学库。数学库。说说明明4：计计算算机机的的算算法法与与常常规规的的数数值值算算法法有有所所区区别别，计计算算机机的的算算法法包包括括数值算法和非数值算

5、法数值算法和非数值算法：（1）数数值值运运算算方方法法：目目的的是是数数值值求求解解。如如求求方方程程的的根根。应应用用非非常常深深入入，如如“Fortran 程序库程序库”；（2）非非数数值值运运算算方方法法：最最常常见见的的是是用用于于事事务务管管理理领领域域，例例如如图图书书管管理理、人人事事管管理理、行行车车调调度度等等。目目前前，计计算算机机在在非非数数值值运运算算方方面面的的应应用用远远超超过过数数值值运算方面应用。运算方面应用。2023/4/105本讲稿第五页，共六十页算法的特性算法的特性（1）有穷性，往往指是在合理的范围内有穷）有穷性，往往指是在合理的范围内有穷;（2）确定性，

6、算法的步骤应当是确定的，不应是含糊不清的）确定性，算法的步骤应当是确定的，不应是含糊不清的;（3）有零个或多个输入）有零个或多个输入;（4）有有一一个个或或多多个个输输出出。无无输输出出的的算算法法通通常常是是无无意意义义的的;（I/O）（5）有效性。）有效性。2023/4/106本讲稿第六页，共六十页算法的表示算法的表示自然语言自然语言流程图流程图传统流程图传统流程图N-S流程图流程图伪代码伪代码2023/4/107本讲稿第七页，共六十页 用传统流程框图表示算法用传统流程框图表示算法 起止框起止框 判断框判断框 流程线流程线 注释框注释框 输入输出框输入输出框 处理框处理框 连接点连接点 流

7、程图符号流程图符号流程图符号流程图符号2023/4/108本讲稿第八页，共六十页输入三个数，输出其中最大的数输入三个数，输出其中最大的数算法：算法：首首先先，找找个个地地方方放放这这三三个个数数，定定义义三三个个变变量量A、B、C，将将三三个个数数依依次次输输入入到到、B、C中中，另外，再准备一个另外，再准备一个MAX放最大数；放最大数；由由于于计计算算机机一一次次只只能能比比较较两两个个数数，于于是是先先把把A与与B比比，大大的的数数放放入入MAX中中，再再把把MAX与与C比，又把大的数放入比，又把大的数放入MAX中；中；最最后后，把把MAX输输出出，此此时时MAX中中放放的的就就是是、C三

8、数中最大的数。三数中最大的数。2023/4/109本讲稿第九页，共六十页求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值值2023/4/1010本讲稿第十页，共六十页算法的三种基本结构算法的三种基本结构顺序结构顺序结构选择结构（分支结构）选择结构（分支结构）循环结构（重复结构）循环结构（重复结构）当型（当型（While）循环结构）循环结构直到型（直到型（Until）循环结构）循环结构2023/4/10

9、11本讲稿第十一页，共六十页顺序结构顺序结构顺序结构顺序结构：坐：坐：坐：坐345345从中国政法大学到德胜门买衣服；从中国政法大学到德胜门买衣服；从中国政法大学到德胜门买衣服；从中国政法大学到德胜门买衣服；选选选选择择择择结结结结构构构构：坐坐坐坐345345从从从从中中中中国国国国政政政政法法法法大大大大学学学学到到到到德德德德胜胜胜胜门门门门买买买买衣衣衣衣服服服服，若若若若车车车车在在在在沙沙沙沙河河河河坏坏坏坏了了了了，就就就就转转转转919919到到到到德德德德胜胜胜胜门门门门；否否否否则则则则，坐坐坐坐345345直直直直接接接接到到到到德胜门；德胜门；德胜门；德胜门；循循循循环

10、环环环结结结结构构构构：坐坐坐坐345345从从从从中中中中国国国国政政政政法法法法大大大大学学学学到到到到德德德德胜胜胜胜门门门门买买买买衣衣衣衣服服服服，如如如如果果果果你你你你带带带带的的的的钱不够，需要回来取钱再去，直到钱够！钱不够，需要回来取钱再去，直到钱够！钱不够，需要回来取钱再去，直到钱够！钱不够，需要回来取钱再去，直到钱够！三种基本结构的类比举例三种基本结构的类比举例2023/4/1012本讲稿第十二页，共六十页三种基本结构的共同点三种基本结构的共同点（1）只有一个入口）只有一个入口（2）只有一个出口）只有一个出口（3）结构内的每一部分都有机会被执行到）结构内的每一部分都有机会

11、被执行到（4）结构内不存在）结构内不存在“死循环死循环”2023/4/1013本讲稿第十三页，共六十页用用N-S流程图表示算法流程图表示算法 1973年美国学者年美国学者I.Nassi和和B.Shneiderman提出了所谓的提出了所谓的N-S流程图。流程图。顺序结构顺序结构选择结构选择结构循环结构循环结构 2023/4/1014本讲稿第十四页，共六十页N-S图特点说明图特点说明（1）比文字描述直观、形象、易于理解；）比文字描述直观、形象、易于理解；（2）比比传传统统流流程程图图紧紧凑凑易易画画，尤尤其其是是其其废废除除流流程程线线，整整个个算算法结构是由各个基本结构按顺序组成；法结构是由各个

12、基本结构按顺序组成；（3）N-S图图的的上上下下顺顺序序就就是是执执行行顺顺序序，用用N-S图图表表示示的的算算法法是是结结构构化化算算法法：由由一一些些基基本本单单元元组组成成，在在基基本本单单元元之之间间不不存存在在向向前前或或向向后的跳转，流程的转移只存在于一个基本结构范围内。后的跳转，流程的转移只存在于一个基本结构范围内。2023/4/1015本讲稿第十五页，共六十页判断闰年的算法闰闰年年的的条条件件：（1）能能被被4整整除除，但但不不能能被被100整整除除的的年年份份都都是是闰闰年年；（2）能能被被100整整除除，又又能能被被400整整除除的的年年份份是是闰闰年年。不不符合这两个条件

13、的年份不是闰年。符合这两个条件的年份不是闰年。2023/4/1016本讲稿第十六页，共六十页用传统流程图表示y+1 y开开 始始2000 yy不能被不能被4整除整除y不能被不能被100整除整除打印打印y“是闰年是闰年”打印打印y“不是闰年不是闰年”y不能被不能被400整除整除打印打印y“是闰年是闰年”打印打印y“不是闰年不是闰年”结结 束束Y2500YNYYNNNY2023/4/1017本讲稿第十七页，共六十页用N-S流程图表示y+1 y2000 y y/4的余数为的余数为0是是否否 y/100的余数不为的余数不为0是是否否打印打印y“是闰年是闰年”y/400的余数的余数为为0打印打印y“是闰

14、年是闰年”打印打印y“非闰年非闰年”是是否否直到直到y 2500打印打印y“非闰年非闰年”2023/4/1018本讲稿第十八页，共六十页1 1 结构化程序结构化程序 用高级语言表示的结构化算法就是结构化程序，用高级语言表示的结构化算法就是结构化程序，用三种基用三种基本结构组成的程序必然是结构化的程序。本结构组成的程序必然是结构化的程序。结构化程序设计方法结构化程序设计方法2023/4/1019本讲稿第十九页，共六十页2 结构化程序设计的思路结构化程序设计的思路 把一个问题求解过程分阶段进行，每个阶段处理的问把一个问题求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理范围：题都控制

15、在人们容易理解和处理范围：（1）自顶向下；）自顶向下；（2）逐步细化；）逐步细化；（3）模块化设计；）模块化设计；（4）结构化编码：）结构化编码：用高级语言正确实现三种基本结构用高级语言正确实现三种基本结构结构化程序设计方法结构化程序设计方法2023/4/1020本讲稿第二十页，共六十页工作报告工作报告前期工作前期工作将来打算将来打算成成功功之之处处失失败败之之处处短短期期打打算算长长期期打打算算用结构化思路编写工作报告用结构化思路编写工作报告结构化程序设计方法结构化程序设计方法2023/4/1021本讲稿第二十一页，共六十页 1.结结构构化化程程序序设设计计结结构构清清晰晰、层层次次分分明明

16、、作作者者容容易易编编写写，读读者者易易懂；懂；2.自自顶顶向向下下、逐逐步步细细化化的的设设计计方方法法是是将将问问题题从从抽抽象象到到具具体体化的过程；化的过程；3.层层层层设设计计、层层层层分分析析，容容易易保保证证能能够够算算法法的的正正确确性性、保保证证思思路路清晰；清晰；4.复杂程序采用模块化设计，对整体的任务分模块完成。复杂程序采用模块化设计，对整体的任务分模块完成。盖房子盖房子图纸设计图纸设计工程施工工程施工质量检查质量检查子模块子模块1子模块子模块2子模块子模块3结构化程序设计方法结构化程序设计方法2023/4/1022本讲稿第二十二页，共六十页注注 意意 学学习习程程序序设

17、设计计的的目目的的不不仅仅学学习习一一种种语语言言，而而是是学学习习进进行行程程序序设设计计的的一一般般方方法法，掌掌握握了了算算法法，则则掌掌握握了了程程序序设设计计的的灵灵魂魂，总总体体上上讲讲，不不能能拘拘泥泥于于一一种种具具体体的的语语言言，但但是是，目前，通过本课程我们应该学会目前，通过本课程我们应该学会C语言！语言！2023/4/1023本讲稿第二十三页，共六十页C语言上机地点和时间语言上机地点和时间地点：地点：润杰公寓六层机房润杰公寓六层机房时间：时间：2,3,5,7,9,11,13,15周周 星期三星期三 15:3017:152023/4/1024本讲稿第二十四页，共六十页四月

18、四月 23上机流程与注意问题上机流程与注意问题（1）1建立个人目录和进入建立个人目录和进入VC+环境环境（1）利用资源管理器在）利用资源管理器在D盘上建立个人目录（字母或数字）；盘上建立个人目录（字母或数字）；（2）双双击击桌桌面面“Microsoft Visual C+6.0”的的快快捷捷方方式式，或或者者单单击击“开开始始程程序序Microsoft Visual Studio 6.0Microsoft Visual C+6.0”，进进入入Visual C+6.0环境的主界面；环境的主界面；2创创建建工工程程：单单击击“FileNew”选选项项，选选择择“NewProjects”选选项项，选

19、选择择“Win32 Console Application”工工程程类类型型，分分别别在在“Project name”栏栏和和“Location”栏栏中中填填写写工工程程名名、选选择择路路径径，然然后后单单“OK”按按钮钮，在在弹弹出出的的对对话话框框中中单单击击“Finish”按钮，再单击按钮，再单击“OK”按钮按钮，完成，完成工程的创建；工程的创建；2023/4/1025本讲稿第二十五页，共六十页四月四月 23上机流程与注意问题上机流程与注意问题（2）3创创建建源源文文件件和和输输入入编编辑辑源源程程序序：单单击击“FileNew”选选项项，选选择择“NewFiles”选选项项，选选择择“

20、C+Source File”文文件件类类型型，并并在在“File”栏栏中中填填写写文文件件名名（examp3），单单击击“OK”按钮，进入代码编辑窗口进行程序的输入；按钮，进入代码编辑窗口进行程序的输入；4源源程程序序的的编编译译：单单击击“Build Compile examp3.CPP”选选项项，进进行行源源程程序序的的编编译译，若若输输入入的的源源程程序序没没有有错错误误，则则在在工工作作目目录录中中形形成成后后缀缀为为.OBJ的的目目标标程程序；序；5目目标标程程序序的的连连接接：单单击击“Build Build sum1.EXE”选选项项，进进行行目目标标程程序序的的连连接接。若无错

21、误，在工作目录中形成后缀为若无错误，在工作目录中形成后缀为.EXE的可执行文件；的可执行文件；6可可执执行行程程序序的的运运行行：单单击击“Build Execute sum1.EXE”选选项项，产产生生结结果果；在结果显示窗口查看结果。在结果显示窗口查看结果。2023/4/1026本讲稿第二十六页，共六十页四月四月 23上机流程与注意问题（上机流程与注意问题（3）7其他其他（1）目录名、文件名符合个人习惯和系统要求）目录名、文件名符合个人习惯和系统要求（2）输入程序一定要细心：）输入程序一定要细心：“inclnde”，“toois”，“intx”等等（3）打开已经存在的文件：）打开已经存在的

22、文件：File（Open）（4）文件改变后）文件改变后注意保存注意保存，以当前文件名保存程序：点击，以当前文件名保存程序：点击File（Save）（5）把当前文件存为新文件：点击）把当前文件存为新文件：点击File（Save as），然后输入新文件名），然后输入新文件名（6）下课后下课后，退出，退出“Microsoft Visual C+6.0”集成环境集成环境8只只能能调调试试以以.CPP为为后后缀缀的的源源文文件件；不不可可以以打打开开或或调调试试后后缀缀为为.OBJ和和.EXE的文件！的文件！9 务必把需要上机调试的程序在上机前编写完成！务必把需要上机调试的程序在上机前编写完成！10上机

23、严肃认真！目前，以上课讲授的内容、要求和操作为主！上机严肃认真！目前，以上课讲授的内容、要求和操作为主！2023/4/1027本讲稿第二十七页，共六十页举例操作说明举例操作说明（1）建立的目录：）建立的目录：D:wangwuD:wangwu（2）工程名：）工程名：Sum1 路路 径：径：D:wangwuD:wangwu（3 3）C C语言源程序名：语言源程序名：语言源程序名：语言源程序名：examp3.cppexamp3.cpp2023/4/1028本讲稿第二十八页，共六十页创建文件夹2023/4/1029本讲稿第二十九页，共六十页2023/4/1030本讲稿第三十页，共六十页2023/4/1

24、031本讲稿第三十一页，共六十页2023/4/1032本讲稿第三十二页，共六十页(1)Open VC+平台窗口四月四月 23II-33CDEA AB BF F2023/4/1033本讲稿第三十三页，共六十页(2)New Project2023/4/1034本讲稿第三十四页，共六十页(3)确定Project 性质2023/4/1035本讲稿第三十五页，共六十页确定工作目录2023/4/1036本讲稿第三十六页，共六十页(3)2023/4/1037本讲稿第三十七页，共六十页(4)确定project名字2023/4/1038本讲稿第三十八页，共六十页(5)2023/4/1039本讲稿第三十九页，共六

25、十页(6)2023/4/1040本讲稿第四十页，共六十页(7)完成Project创建2023/4/1041本讲稿第四十一页，共六十页浏览Project内容2023/4/1042本讲稿第四十二页，共六十页(8)New file2023/4/1043本讲稿第四十三页，共六十页(9)确定Files 性质2023/4/1044本讲稿第四十四页，共六十页(10)确定file 名字:examp32023/4/1045本讲稿第四十五页，共六十页2023/4/1046本讲稿第四十六页，共六十页(11)完成filet创建:examp3.cpp2023/4/1047本讲稿第四十七页，共六十页(12)编辑examp

26、3.cpp文件2023/4/1048本讲稿第四十八页，共六十页(13)Save examp3.cpp2023/4/1049本讲稿第四十九页，共六十页(14)完成examp3.cpp保存2023/4/1050本讲稿第五十页，共六十页(15)编译examp3.cpp2023/4/1051本讲稿第五十一页，共六十页(16)examp3.cpp编译完成,无错2023/4/1052本讲稿第五十二页，共六十页(17)试图形成sum1.exe2023/4/1053本讲稿第五十三页，共六十页(18)sum1.exe形成(完成)2023/4/1054本讲稿第五十四页，共六十页(19)运行sum1.exe2023

27、/4/1055本讲稿第五十五页，共六十页(20)运行结果窗口2023/4/1056本讲稿第五十六页，共六十页(21)返回VC+平台窗口2023/4/1057本讲稿第五十七页，共六十页上机作业（上机作业（1）（1）编写一个）编写一个C程序，输入程序，输入a,b,c三个整数，输出其中三个整数，输出其中的最大数。的最大数。（2）编写一个）编写一个C程序，输入程序，输入a,b,c三个浮点数，输出其三个浮点数，输出其中的最小数。中的最小数。（3）例）例3.1、例、例3.2、例、例3.3和例和例3.42023/4/1058本讲稿第五十八页，共六十页上机作业上机作业第二次第二次第二次第二次（1）4.5（2）

28、4.8（3）4.9（4）5.4（5）5.5（5）三角形求面积）三角形求面积（6）例）例5.5、例、例5.6第三次第三次第三次第三次（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列列

29、的的数数组组，求求和和；求求平平均均值值；求每行的最大值；求每列的最大值；求每行的最大值；求每列的最大值；（3）习题）习题8.2（4）例）例8.6 2023/4/1059本讲稿第五十九页，共六十页上机作业上机作业(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.32023/4/1060本讲稿第六十页，共六十页