




已阅读5页,还剩66页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1清华大学计算机科学与技术系 计算机程序设计基础 乔乔 林林 计算机程序设计基础计算机程序设计基础 Email: Email: Tel: 62780973Tel: 62780973 清华大学计算机科学与技术系清华大学计算机科学与技术系 2清华大学计算机科学与技术系 计算机程序设计基础 第十一章 算法设计与分析 学习目标 了解大多数问题都可以用几种不同的算法解决 掌握什么样的算法是正确的 了解解决同一问题的不同算法其性能各不相同 了解算法复杂度的概念,用它可对随着问题规模 成比例增长的运行时间的变化作定性分析 学会用大“O”符号表示算法复杂度;掌握最常见 的复杂度类型,并且理解每个复杂度类型的性能 特点 3清华大学计算机科学与技术系 计算机程序设计基础 11.1 算法的概念与特征 算法的由来 解决问题的方法与步骤 演算过程的抽象表述 算法的基本特征 有穷性:算法必须能够在有限步内终止 确定性:每一步骤的顺序和内容不能有二义性 有效性:所有操作都有明确含义并能够实现 有零个或多个输入:算法应该接受处理数据 有一个或多个输出:算法必须能够输出结果 正确性不是算法的特征,算正确性不是算法的特征,算 法的正确性由设计者保证!法的正确性由设计者保证! 4清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 33 幻方 用数字19组成33方阵,各行各列各对角线的数 字之和为15 算法步骤 S1:把1放在第一行中间的一格 S2:在右上方斜对角线方向给出下一个自然数 在此过程中,若该数已出方框,则将其写在该行或该 列另一端 S3:写完三个数后,将第四个数写在第三个数下 S4:重复上述操作, 直到格子填满为止 5清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 1 6清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 1 7清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 1 2 8清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 1 3 2 9清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 1 33 2 10清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 1 33 42 11清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 1 353 42 12清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 16 353 42 13清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 16 3573 42 14清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 168 3573 42 15清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 2 8168 3573 42 16清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 92 8168 3573 42 17清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 92 8168 3573 492 18清华大学计算机科学与技术系 计算机程序设计基础 算法举例一 816 357 492 19清华大学计算机科学与技术系 计算机程序设计基础 算法举例二 查英文词典的算法步骤 S1:翻开词典任意一页 S2:若所查词汇在本页第一个单词前,则往前翻 页重复S2;若所查词汇在本页最后一个单词后, 则往后翻页重复S2 S3:若非S2的情况,则依次比较本页单词,或者 查出该单词,或者得出结论,查不到该单词 20清华大学计算机科学与技术系 计算机程序设计基础 算法举例三 素数判定的算法步骤 S1:输入 n 的值 S2:i = 2 S3:r = n / i S4:若 r = 0,则 n 不是素数,结束;若 r 0 , 执行S5 S5:i = i + 1 S6:若 i n 1,返回S3;否则判定 n 为素数, 结束 21清华大学计算机科学与技术系 计算机程序设计基础 11.2 算法的类型与结构 数值算法与非数值算法 算法的基本结构 顺序结构 分支结构 循环结构 程序的结构化 22清华大学计算机科学与技术系 计算机程序设计基础 11.3 算法的描述方法 流程图 使用流线表示程序控制流 程序逻辑清晰,绘制复杂 N-S图 去除流线与箭头的流程图 绘制复杂,逻辑不清晰 伪代码 程序逻辑较不清晰,书写简单 23清华大学计算机科学与技术系 计算机程序设计基础 11.4 算法的设计与实现 算法实现过程 问题分析 按某种策略实现算法 验证上述实现确实为算法 证明算法的正确性 选择合适的策略,提高算法效率 24清华大学计算机科学与技术系 计算机程序设计基础 素数判定问题 函数原型 int IsPrime( int n ); 素数判定问题的第二种算法 检查 1 到 n 的数中,是否存在可被 n 整除的数 每找到一个因子,计数器自加 1 在所有数判断完毕后,查看计数器是否为 2 若为2则为素数,否则不是 25清华大学计算机科学与技术系 计算机程序设计基础 素数判定问题 int int IsPrimeIsPrime( ( intint n n ) ) intint divisorsdivisors, , i i; ; divisorsdivisors = 0; = 0; for( for( i i = 1; = 1; i i .h void void SortIntergeArraySortIntergeArray( ( intint a a, , intint n n ) ) int int lhlh, , rhrh, , i i, , temptemp; ; for( for( lhlh = 0; = 0; lhlh low low + 1 ) + 1 ) / more than two numbers/ more than two numbers midmid = ( = ( highhigh + + lowlow ) / 2; ) / 2; / divide into two / divide into two subarrayssubarrays SortIntegerArraySortIntegerArray( ( a a, , lowlow, , mid mid ); ); / sort them respectively/ sort them respectively SortIntegerArraySortIntegerArray( ( a a, , midmid+1, +1, high high ); ); MergeMerge( ( a a, , lowlow, , midmid, , high high ); ); / merge them/ merge them 56清华大学计算机科学与技术系 计算机程序设计基础 归并排序 void void MergeMerge( ( intint a a, , intint lowlow, , intint midmid, , intint high high ) ) intint i i, , mm, , n n; ; intint * *p p, *, *q q; ; p p = ( = ( intint* )* )mallocmalloc( ( sizeofsizeof( ( intint ) * ( ) * ( high high low low + 1 ) );+ 1 ) ); m m = = lowlow; ; n n = = mid mid + 1; + 1; q q = = p p; ; while( while( mm = = pivot pivot ) ) rhrh;
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 展览展示活动组织与参与协议
- 项目合同管理与合同存档规范模板
- 消防门安装合同6篇
- 新化肥采购合同5篇
- 占股不分红合同格式6篇
- 股权转让协议书对内转让7篇
- 公司融资业务咨询服务协议书5篇
- 2026届天津市滨海新区第四共同体数学九上期末达标检测试题含解析
- 江苏省苏州市梁丰初级中学2026届数学九年级第一学期期末综合测试模拟试题含解析
- 浙江嘉兴北师大南湖附学校2026届数学九年级第一学期期末监测试题含解析
- 福建省全国名校联盟2026届高三上学期联合开学摸底考试语文试题及参考答案
- 2025年广工建筑电气试卷及答案
- 2024年广西桂林理工大学南宁分校招聘真题
- 排污许可证管理条例课件
- 乡镇人大主席“干在实处、走在前列”学习讨论发言材料
- 2025年食品安全管理员考试题库及参考答案
- 用户反馈收集及问题分析表
- 无人机飞行操作规范手册
- 【里斯】年轻一代新能源汽车消费洞察与预测 -新物种 新理念 新趋势(2024-2025)
- 医院收费室培训课件
- 信仰思政课件
评论
0/150
提交评论