《(9)--第4章计算机中的问题求解1.ppt》由会员分享，可在线阅读，更多相关《(9)--第4章计算机中的问题求解1.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 4.1 程序设计的基本概念4.2 程序设计的构成要素4.3 结构化程序设计4.5 常用算法2023/11/21 程序设计的基本概念程序设计(Programing)：指利用计算机解决问题的全过程，它包含多方面的内容，而编写程序只是其中的一部分。程序设计的一般步骤：分分析析问问题题确定确定处理处理方案方案确定确定操作操作步骤步骤编编写写程程序序上机上机运行运行程序程序整整理理结结果果4.1 程序设计的基本概念程序设计的基本概念程序设计语言 用于书写计算机程序的语言2023/11/214.1 程序设计的基本概念程序设计的基本概念程序设计语言分为 5 代 机器语言：二进制语言汇编语言：用助记符表示二
2、进制高级语言：接近人们熟悉的自然语言和数学语言非过程语言：只说明做什么，不用说明怎么做智能化语言：具有智能性算法是对具体问题求解步骤的一种描述4.1 程序设计的基本概念程序设计的基本概念数据结构算法计算机解决问题的灵魂算法的特性 有穷性确定性有零个或多个输入有一个或多个输出可行性4.1 程序设计的基本概念程序设计的基本概念算法的描述 用自然语言表示：就是用人们所熟悉的自然语言把算法的各个步骤依次表示出来用流程图表示：就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算法用程序设计语言表示2023/11/214.1 程序设计的基本概念程序设计的基本概念例：求1+1/2+1/3+1/100
3、的和算法描述：第1步：将i的初始值设为1，累加和s的初始值设为0第2步：将s+1/i的值赋给s第3步：将i的值+1第4步：如果i的值=100重复第二步，否则执行下一步第5步：输出结果s的值4.1 程序设计的基本概念程序设计的基本概念4.1 程序设计的基本概念程序设计的基本概念开始S=0i=1i=100s=s+1/ii=i+1输出s结束YN流程图示例#include“stdio.h”#include“stdio.h”main()main()int s=0,i=1;int s=0,i=1;while(i=100)while(i、=、=、=、=、逻辑运算符完成与、或、非的运算，运算结果为逻辑值&、|
4、、！AND OR NOT赋值运算符给一个变量赋以一个常量、变量或表达式的值=运算符说明运算符说明 4.2 程序设计的构成要素程序设计的构成要素例：算术表达式：3+5*a 赋值表达式：a=5在这里需要特别说明的是赋值表达式，其形式为：变量名=表达式“=”符号称为赋值运算符赋值号左边是变量名，右边是合法的表达式赋值时自右向左读。赋值的含义是将右边表达式的值赋给左边的变量。4.2 程序设计的构成要素程序设计的构成要素执行下列赋值语句后，写出a,b,c,d的结果。a a=3 3a a=5 5d d=a ac c=a ab b=a ab b=3 34.2 程序设计的构成要素程序设计的构成要素答案是：a=
5、5b=3c=5d=5语句 表达式语句输入输出语句控制语句顺序语句选择语句 循环语句4.2 程序设计的构成要素程序设计的构成要素语句AB假真PAB真假AP真假AP控制语句对应的三种结构4.2 程序设计的构成要素程序设计的构成要素2023/11/21 结构化程序设计为使程序具有一个合理的结构以保证程序正确性而规定的一套如何进行程序设计的原则：4.3 结构化程序设计结构化程序设计自顶向下、逐步求精的方法程序结构模块化，模块化中的每个模块只有一个入口和一个出口3种基本控制结构描述程序流程。模块化就是把一个大型的程序按照功能分解为若干模块化就是把一个大型的程序按照功能分解为若干相对独立的、较小的子程序相
6、对独立的、较小的子程序(即模块即模块)，并把这些模，并把这些模块按层次关系进行组织块按层次关系进行组织。2023/11/21 常用算法极值问题-打擂台算法先从所有参加“打擂”的人中选第一个人站在台上；第二个人与之比较，胜者留在台上，败者下台；再上去第3个人，与台上的现任擂主比较，胜者留在台上，败者下台；循环往复，后面的每个人都与台上的人比较，直到所有人都比过为止，最后留在台上的就是冠军2023/11/214.5 常用算法常用算法所有的事物，信息在程序设计中都以变量来表示【例4.2】使用流程图描述从10个数中找出其最大数。分别输入10个数，设置n为计数器，每输入一个数，n加1；假设第一个数为大数
7、，放在变量max中，之后每输入一个数，都与max进行比较，大数存放到max变量中。只要n小于10，就一直比较下去。n=n+1开始n=1n10max=a输出max结束输入max输入amaxaYYNN2、求和在解决实际问题时经常遇到求和问题，如：求s=2+22+23+2n的值，其中n为自然数，由键盘输入。求和算法的一般步骤是：设置一个放置和的变量s，其初值设为0；设置或输入初始加数；利用循环操作，将每个加数依次加入放置和的变量中，每次循环后设置或输入新的加数；循环结束后，和的变量里的值即为最终结果。2023/11/214.5 常用算法常用算法开始输入nS=0i=1，k=1i=nk=k*2,s=s+
8、ki=i+1输出s求s=2+4+8+2n的值，其中n为自然数的流程图YN4.5 常用算法常用算法迭代算法利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出一个新值 2023/11/214.5 常用算法常用算法迭代算法解决问题，需要做好以下三个方面的工作：1确定迭代变量2建立迭代关系式3对迭代过程进行控制4.5 常用算法常用算法【例4.4】验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象对于任意一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其乘以3，然后再加1。如此经过有限次
9、运算后，总可以得到自然数1。人们把谷角静夫的这一发现叫做“谷角猜想”2023/11/214.5 常用算法常用算法谷角猜想：由键盘输入一个自然数n，把n经过有限次运算后，最终变成自然数1的全过程打印出来。算法分析：定义迭代变量为n，按照谷角猜想的内容，可以得到两种情况下的迭代关系式：当n为偶数时，n=n/2；当n为奇数时，n=n*3+1。开始n=1?结束输入nn是否整除2Nn=n*3+1n=n/2输出nYNY4.5 常用算法常用算法枚举算法也称为穷举法是编程中常用算法之一，就是按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，采纳这个解
10、，否则抛弃它。在列举的过程中，既不能遗漏也不能重复 2023/11/214.5 常用算法常用算法开始i=1i/3=int（i/3）i=i+1输出ii=1000结束【例4.6】求1-1000中，能被3整除的数 算法分析：1用变量i表示要列举的自然数。（1）列举范围：利用循环结构，i的值从1-1000一一列举；（2）检验条件：利用选择结构，判断i能否被3整除，如果可以输出i，否则继续循环，判断下一个。2分析出以上二个核心问题后，再将其合成，具体确定循环控制方式和列举方式4.5 常用算法常用算法YYNN在枚举算法中往往把问题分解成二部分：4.5 常用算法常用算法确定列举范围，通常需要用循环来完成。要
11、考虑的问题是如何设置循环变量及循环变量的初值、终值和递增值。同时考虑循环变量是否参与检验。一一列举检验通常用分支结构完成。要考虑的问题是检验的对象是谁？逻辑判后的二个结果该如何处理？检验2023/11/21求100以内的所有质数（素数）：除了1和它本身外没有约数的数 算法分析：一一列举：n，n的值从2到100，逐一检验：用n除以i，i的取值从2到n-1作答正常使用主观题需2.0以上版本雨课堂主观题10分2023/11/21开始n=2i=n-1输出nn=100结束YNNi=i+1Yi=2n mod i!=0Yn=n+1N顺序查找顺序查找5.3、查找与排序算法查找在内存中连续的存储单元作为在内存中
12、连续的存储单元作为存储结构存储结构查找过程：查找过程：从表中最后一个（或第一个）记录开始，逐从表中最后一个（或第一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，键字和给定值比较相等，则查找成功则查找成功；反之，若直至第；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，没有所查记录，查找失败查找失败。85786395544599二分查找二分查找(折半查找折半查找)存储的数据如果是有序的。二分查找法的基本思想是：每次将处于查找区间中间位
13、置上的数据元素的键值x与给定值K比较，若不等则缩小查找区间(若K比中间值大则舍弃下半部分，若K比中间值小则舍弃上半部分)并在新的区间内重复上述过程，直到查找成功或查找区间长度为0(即查找不成功)为止。5.3、查找与排序算法查找45546378859599lowhighmidhighlowmidlowhighmid10 16 20 36 46 68 80 98第一次查找第二次查找第三次查找例：在下列数列中查找数据25：1 2 3 4 5 6 7 8mid=low+（high-low）/2high=mid-15.3、查找与排序算法直接插入排序直接插入排序直接插入排序直接插入排序依次将每个记录插入到
14、一个有序的子序列中去。初始状态：946582第一趟：496582第二趟：46 9582第三趟：456982第四趟：456892第五趟：2456895.3、查找与排序算法排序冒泡排序冒泡排序冒泡排序冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。完成第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟冒泡排序，直至排序结束。5.3、查找与排序算法排序初始状态：946582第一趟：496582 4 69582 4 659
15、82 465892 4 65829第二趟:45628第三趟：4526第四趟：425第五趟：245.3、查找与排序算法直接选择排序直接选择排序直接选择排序直接选择排序首先在所有的记录中选出键值最小的记录，把它与第一个记录交换；然后在其余的记录中再选出键值最小的记录与第二个记录交换；依次类推，直至所有记录排序完成。在第i趟中，通过n-i次键值比较选出所需记录。初始状态：946582第一趟：246589第二趟：246589第三趟：245689 第四趟：245689第五趟：2456895.3、查找与排序算法排序1.下列语句中:m=m/x 3*5=1532=Aa=a+2*b其中是赋值语句的个数为()1A
16、2B3C4D提交单选题10分2.下面关于算法的认识错误的是()。算法是解决问题的方法和步骤A算法有一个或多个的输出B算法就是计算机程序C算法的步骤必须是有限的D提交单选题10分3.如果x=4，那么以下运算结果为True的表达式是（）。(x=6)(x4)Or(x=6)(x6)not(x4)ABCD提交单选题10分4.将两个数 a=8,b=7交换，使 a,b=8,使用赋值语句正确的一组 ()a=b，b=ac=b,b=a,a=cb=a,a=bc=a,b=a,b=cABCD提交单选题10分需掌握的知识点算法的5个特性程序设计的三种基本结构极值算法、求和算法、迭代算法和枚举算法会画流程图查找和排序算法2023/11/21