算法和程序设计

《算法和程序设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.3算法和程序设计3.3.1算法3.3.2程序设计语言3.3.3程序设计语言处理器3.3.1算法计算机求解问题的步骤(1)确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成算法(Algorithm)；(3)使用某种程序设计语言描述该算法(编程),并编译成目标程序和进行调试；(4)运行程序，获得问题的解答；(5)进行评估，改进算法和程序1.什么是算法？算法是解决问题的方法与步骤例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？分析：方法明确而有序按提供的条件进行操作任何人均可仿照进行(共享智能)开始C是伪币B是伪币A是

2、伪币A＝B？A＝C？是否否是ABC关于算法的三方面问题如何确定算法（算法设计）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？2.算法设计举例典型问题：如何对数据进行排序问题：任给一组(n个)整数，将它们从小到大进行排序“选择排序”算法的思路：①从所有整数中选一个最小数，作为已排序的第一个数②从剩下未排序整数中选最小的数，添加到已排序整数的后面③反复执行步骤②，直到所有整数都处理完毕“选择排序”算法举例2345789第6次循环后，排序结束2937845与首元素交换，第1次循环结束4937825数组的初态，全部是未排序元素4937825在未排序元素中确定最小数位置239784

3、5与首元素交换，第2次循环结束2937845在未排序元素中确定最小数位置2347895与首元素交换，第3次循环结束2397845在未排序元素中确定最小数位置3.算法的表示文字叙述流程图表示伪代码描述文字(自然语言)描述“比较Ａ与Ｂ的重量，若Ａ＝Ｂ，则Ｃ是伪造的；否则再比较Ａ与Ｃ的重量，若Ａ＝Ｃ，则Ｂ是伪造的；否则Ａ是伪造的。”缺点：容易产生歧义，很难“精确”地进行表达叙述冗长，很难清楚地表达算法的逻辑流程算法的流程图表示流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件流程图符号：比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误端点符处理判断预定义功能原

4、始数据放在数组A中；令i=1确定A[i]到A[n]中最小整数的位置,设为jA[i]和A[j]交换位置i=i+1i=n?结束开始用流程图表示选择排序算法将原始数据放在数组A中；设置i的初值为1，循环执行下列操作，直到i=n：{确定A[i]到A[n]中最小整数的位置，设为j；交换A[i]和[j]；i=i+1}使用伪代码描述“选择排序”算法使用伪代码描述算法伪代码(Pseudocode)是用来描述算法的一种语言，它既类似于自然语言，又使用与程序设计语言相似的方法描述算法优点：结构清晰，代码简单，可读性好，可以容易地以任何一种编程语言(Pascal,C,Java等)实现每个整数是A的一个元素

5、：A[1],A[2],···,A[n]4.算法的分析算法分析的基本内容正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果简单性算法是否容易理解，是否容易验证其正确性，程序是否容易调试简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单时间复杂性(TimeComplexity)：当问题的规模n充分大时，运行该算法所需要的时间的数量级表示空间复杂性(SpaceComplexity)：除原始数据之外，额外占用的存储空间的大小选讲：选择排序算法的时间复杂性假设参加排序的整数有n个（1）比较操作的次数：在第i趟排序中选出最小整数时，需做n-i次比较操作，因此，总的比较操作次

6、数为：n(n-1)/2=(n2-n)/2（2）移动操作的次数：最好情况(原始数据已经排序)时，移动次数为0最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1)所以，直接选择排序的时间复杂性为O(n2)设置i的初值为1，循环执行下列操作，直到I=n：{确定A[i]到A[n]中最小的整数元素的位置，设为j；交换A[i]和[j]；i=i+1}关于算法的小结计算机中处处是算法！例1：Word程序如何在文档中查找用户指定的词语？例2：在Word文档的表格中如何将表格内容排序？例3：如何把一幅彩色图片转换为灰度(黑白)图片？例4：Windows如

7、何在硬盘中找到用户指定的文件？例5：媒体播放器如何把MP3文件转换成动听的音乐？例6：搜索引擎如何在WWW网中找到用户需要的网页？算法是计算机软件的灵魂计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法算法所解决的是一类问题而不是一个特定的问题，例如排序(sort)可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等查找(search)，可以在文档中查找某个单词或在硬盘中