计算机程序设计基础课程教学PPTF.ppt

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;