算法与程序设计：第1章 算法基础.ppt

算法与程序设计算法与程序设计算算 法法 初初 步步你愿意不厌其烦地去作枯燥的、重复的、你愿意不厌其烦地去作枯燥的、重复的、繁琐的工作吗？繁琐的工作吗？用计算机代替人来完成这些工作，这恰恰用计算机代替人来完成这些工作，这恰恰是计算机的特长是计算机的特长电脑发展到今天，能有如此广泛而神奇的应用，电脑发展到今天，能有如此广泛而神奇的应用，除了半导体集成电路芯片的制造工艺提高以外，除了半导体集成电路芯片的制造工艺提高以外，主要靠软件，而软件的核心是主要靠软件，而软件的核心是算法算法算法，计算的方法，可以理解为解决问题的方法算法，计算的方法，可以理解为解决问题的方法算算 法法 学习学习 的的 重重 要要 性性 算法是计算机科学的基石；算法是计算机科学的基石；算法：计算的灵魂算法：计算的灵魂 程序算法数据结构程序算法数据结构；学习算法可以开发人们的分析能力；学习算法可以开发人们的分析能力；算算 法法 学习学习 的的 必必 要要 性性知道计算机领域中解决不同问题的一系列知道计算机领域中解决不同问题的一系列标准算法标准算法具备设计新算法和分析其效率的能力具备设计新算法和分析其效率的能力 算法能解决的问题种类是有限的算法能解决的问题种类是有限的不能找到使人生活愉快的算法，也不能找到一个不能找到使人生活愉快的算法，也不能找到一个使人富有和出名的算法。

使人富有和出名的算法算算 法法 学习学习 的的 必必 要要 性性【问题问题】求求26个英文字母全排列个英文字母全排列它的排列数为：它的排列数为：26！41026以每年以每年365天计算，共有天计算，共有 3652436003.1536107秒秒以每秒能完成以每秒能完成107个排列的超高速电子计算机来做这个排列的超高速电子计算机来做这项工作，需要项工作，需要 41026/(3.15361014)1.21012年年即使计算机运行速度随着技术的提高，恐怕也还是不即使计算机运行速度随着技术的提高，恐怕也还是不可能实现的可能实现的1课程学时课程学时 总学时总学时:48学时学时;讲课讲课:36学时学时;上机上机:12学时学时 上机时间：第上机时间：第6、8、10、12、14、16周周2本课程主要参考书本课程主要参考书1 王晓东王晓东.计算机算法设计与分析计算机算法设计与分析.电子工业出电子工业出版社版社2 软件设计师教程软件设计师教程课课 前前 简简 介介课课 前前 简简 介介3 3学习成绩考核方法学习成绩考核方法期末考试占期末考试占60%60%平时平时(课堂作业课堂作业+实验实验+大作业）占大作业）占40%40%逢周一课交作业逢周一课交作业课课 前前 简简 介介5.学习方法学习方法多思考，多专研，多实践多思考，多专研，多实践课课 程程 内内 容容第一章：算法基础第一章：算法基础第二章：第二章：(补充补充)穷举搜索和迭代算法穷举搜索和迭代算法第三章：递归和分治算法第三章：递归和分治算法第四章：动态规划算法第四章：动态规划算法第五章：贪心算法第五章：贪心算法第六章：回溯算法第六章：回溯算法第七章第七章*：分枝限界算法：分枝限界算法第八章：图算法第八章：图算法第第1章章 算法基础算法基础学习要点学习要点:理解算法的概念。

理解算法的概念理解什么是程序，程序与算法的区别和内在联系理解什么是程序，程序与算法的区别和内在联系掌握算法的计算复杂性概念掌握算法的计算复杂性概念掌握算法渐近复杂性的数学表述掌握算法渐近复杂性的数学表述掌握用伪代码描述算法的方法掌握用伪代码描述算法的方法第第1章章 算法基础算法基础1.1 算法（算法（Algorithm）1.2 算法分析算法分析1.3 算法的运行时间算法的运行时间1.1 算法算法(Algorithm)1.算法的定义算法的定义2.算法的性质算法的性质3.算法的表示算法的表示4.算法举例算法举例5.程序程序6.冒泡排序算法冒泡排序算法7.算法正确性证明算法正确性证明算法通常指算法通常指可以用来解决的某一类问题的步可以用来解决的某一类问题的步骤骤，这些步骤必须是明确的和有效的，而，这些步骤必须是明确的和有效的，而且能够在有限步之内完成的且能够在有限步之内完成的1.1.算法的定义算法的定义 一般来说，一般来说，“用算法解决问题用算法解决问题”可以利用可以利用计算机帮助完成计算机帮助完成1.1 算法算法(Algorithm)“算法算法”的大陆中文名称出自的大陆中文名称出自公元前1世纪成书的周髀算经周髀算经；英文名称英文名称Algorithm 来自于来自于9世纪波斯数学家世纪波斯数学家al-Khwarizmi；欧几里得算法欧几里得算法被人们认为是史上第一个算法。

被人们认为是史上第一个算法1.1.算法的定义算法的定义 1.1 算法算法(Algorithm)2.2.算法的性质算法的性质 1）可行性）可行性 2）确定性）确定性 3）有穷性）有穷性 4）有输入信息的说明）有输入信息的说明 5）有输出结果的说明）有输出结果的说明3.3.算法的表示算法的表示 描描述述算算法法可可以以有有不不同同的的方方式式,常常用用的的有有自自然语言、程序框图、程序设计语言、然语言、程序框图、程序设计语言、伪代码伪代码等等.1.1 算法算法(Algorithm)可行性：算法中描述的操作都可通过有限可行性：算法中描述的操作都可通过有限次的基本运算来次的基本运算来实现确定性：算法中每个步骤含义明确，无二确定性：算法中每个步骤含义明确，无二义性有穷性：一个算法必须保证在有穷性：一个算法必须保证在有限有限个操作个操作步骤执行后步骤执行后终止终止输入：一个算法应具有输入：一个算法应具有零个或多个零个或多个输入输出：一个算法应具有输出：一个算法应具有一个或多个一个或多个输出2.2.算法的性质算法的性质 1.1 算法算法(Algorithm)自然自然语言就是人言就是人们日常使用的日常使用的语言，可以言，可以是是汉语或英或英语或其它或其它语言。

言除了那些很除了那些很简单的的问题外，一般不用自然外，一般不用自然语言描述算法言描述算法1 1）自然语言）自然语言3.3.算法的表示算法的表示1.1 算法算法(Algorithm)1.1 算法算法(Algorithm)概念：概念：伪代代码是用介于自然是用介于自然语言和言和计算机算机语言之言之间的文字和符号来描述算法的文字和符号来描述算法特点特点：它如同一篇文章一它如同一篇文章一样，自上而下地，自上而下地写下来每一行写下来每一行(或几行或几行)表示一个基本操表示一个基本操作用用处：适用于适用于设计过程中需要反复修改程中需要反复修改时的流程描述的流程描述2 2）伪代码）伪代码3.3.算法的表示算法的表示1.1 算法算法(Algorithm)伪代码规则说明：见教材伪代码规则说明：见教材P3a）缩进形式表示块结构，主要体现在循环和条件控）缩进形式表示块结构，主要体现在循环和条件控制结构上制结构上b）while,do-while,for循环结构，以及循环结构，以及if-then-else条件结构采用类似高级语言中相应表示条件结构采用类似高级语言中相应表示c）符号）符号“/”后是注释部分后是注释部分。

d）多重赋值表达为）多重赋值表达为ijee）所有变量不经显式说明均为局部变量所有变量不经显式说明均为局部变量f）通过数组名后跟下标访问数组元素；符号）通过数组名后跟下标访问数组元素；符号“.”表示数组中元素的范围表示数组中元素的范围Ai Ai.j3.3.算法的表示算法的表示1.1 算法算法(Algorithm)g）复合数据可以组织成由属性或域组成的对）复合数据可以组织成由属性或域组成的对象，通过域名后跟方括号括住的对象名访问象，通过域名后跟方括号括住的对象名访问某个特定域某个特定域LengthAh）通过传值将参数传给一个过程；当传递一）通过传值将参数传给一个过程；当传递一个对象时，只拷贝指向表示对象的数据的指个对象时，只拷贝指向表示对象的数据的指针，不拷贝它的各个域针，不拷贝它的各个域i）“and”和和“or”是布尔运算符是布尔运算符j）break语句表示将控制转移到含有语句表示将控制转移到含有break的的最内层循环语句后面的第一条语句最内层循环语句后面的第一条语句3.3.算法的表示算法的表示令士兵从令士兵从1 13 3报数，结果最后一个士兵报报数，结果最后一个士兵报2 2；令士兵从令士兵从1 15 5报数，结果最后一个士兵报报数，结果最后一个士兵报3 3；令士兵从令士兵从1 17 7报数，结果最后一个士兵报报数，结果最后一个士兵报2 2；【例例1 1】韩信点兵韩信点兵你能算出韩信你能算出韩信至少至少有多少兵吗？有多少兵吗？1.1 算法算法(Algorithm)4.4.算法举例算法举例【例例1 1】韩信点兵韩信点兵1.列出除以列出除以3余余2的数：的数：2，5，8，11，14，17，20，23，26 2.列出除以列出除以5余余3的数：的数：3，8，13，18，23，28 3.这两列数中，首先出现的公共数是这两列数中，首先出现的公共数是8，3与与5的最小公的最小公倍数是倍数是15。

两个条件合并成一个就是两个条件合并成一个就是815整数，列整数，列出这一串数是出这一串数是8，23，38，4.列出除以列出除以7余余2的数的数：9，16，23，30 5.得出符合题目条件的最小数是得出符合题目条件的最小数是236.我们已把题目中三个条件合并成一个：被我们已把题目中三个条件合并成一个：被105除余除余23的数1.1 算法算法(Algorithm)4.4.算法举例算法举例【例例1 1】韩信点兵韩信点兵算法描述算法描述三人同行七十稀，三人同行七十稀，五树梅花廿一枝，五树梅花廿一枝，七子团圆正半月，七子团圆正半月，除百零五便得知除百零五便得知这首诗的意思是：用这首诗的意思是：用3除除所得的余数乘上所得的余数乘上70，加上，加上用用5除所得余数乘以除所得余数乘以21，再加上用再加上用7除所得的余数除所得的余数乘上乘上15，结果大于，结果大于105就就减去减去105的倍数，这样就的倍数，这样就知道所求的数了知道所求的数了1.1 算法算法(Algorithm)4.4.算法举例算法举例最初记述这类算法的是一本名叫最初记述这类算法的是一本名叫孙子算经孙子算经的书这类算法的名称也很多，宋朝周密叫它这类算法的名称也很多，宋朝周密叫它“鬼鬼谷算谷算”，又名，又名“隔墙算隔墙算”；杨辉叫它；杨辉叫它“剪管剪管术术”；而比较通行的名称是；而比较通行的名称是“韩信点兵韩信点兵”。

这在数学史上是极有名的问题，外国人一般这在数学史上是极有名的问题，外国人一般把它称为把它称为“中国剩余定理中国剩余定理”例例1 1】韩信点兵韩信点兵1.1 算法算法(Algorithm)4.4.算法举例算法举例【点点评】了解一些了解一些经典算法是我典算法是我们的学的学习目目标例例2】求求1+2+3+4+5+6累加和累加和算法算法1.1.按照逐一相加的算法进行按照逐一相加的算法进行.第一步第一步:计算计算1+2,得得3;第二步第二步:将第一步中的运算结果将第一步中的运算结果3与与3相加得相加得6;第三步第三步:将第二步中的运算结果将第二步中的运算结果6与与4相加得相加得10;第四步第四步:将第三步中的运算结果将第三步中的运算结果10与与5相加得相加得15;第五步第五步:将第四步中的运算结果将第四步中的运算结果15与与6相加得相加得21.4.4.算法举例算法举例1.1 算法算法(Algorithm)算法算法2.2.可以运用下面公式直接计算可以运用下面公式直接计算.第一步第一步:取取 n=6;第二步第二步:计算计算 ;第三步第三步:输出计算结果输出计算结果.【点点评】算算法法1 1繁繁琐,步步骤较多多;算算法法2 2简单，步步骤较少。

少找出好的算法是我找出好的算法是我们的学的学习目目标。