山东理工大学：《计算机算法设计与分析》课程教学课件（PPT讲稿）第一章 算法概述概述（主讲：王红霞）

白本程子太军 归东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 会会空的3会的是 计算机算法设计与分析 Design and Analysis of ComputerAlgorithms 第一章算信撬述 王红霞

计算机算法设计与分析 Design and Analysis of Computer Algorithms 第一章 算法概述 王红霞

学习要点： 归本程子末军 SHANDONG UNIVERSITY OF TECHNOLOGY 华红众是空安会器会举完品条 ●理解算法的概念。 ●理解什么是程序，程序与算法的区别和内在联系。 ●掌握算法的计算复杂性概念。 ·掌握算法渐近复杂性的数学表述。 ●掌握用C++语言描述算法的方法 2

2 •理解算法的概念。 •理解什么是程序，程序与算法的区别和内在联系。 •掌握算法的计算复杂性概念。 •掌握算法渐近复杂性的数学表述。 •掌握用C++语言描述算法的方法 学习要点:

山东程子太军 提纲 SHANDONG UNIVERSITY OF TECINOLOGY 华是会实微特A空品会品☆ 一、 算法与程序 二、算法复杂性分析 三、用C++语言描述算法的方法 3

3 提纲 一、算法与程序 二、算法复杂性分析 三、用C++语言描述算法的方法

G 归东露子太军 提纲 SHANDONG UNIVERSITY OF TECHNOLOGY 一、算法与程序 二、算法复杂性分析 三、用C++语言描述算法的方法 4

4 提纲 一、算法与程序 二、算法复杂性分析 三、用C++语言描述算法的方法

在中央电视台节目中，有一个猜商品价格的 环节，竟猜者如在规定的时间内大体猜出某种商 品的价格就可获得该件商品现有一商品，价格往 0-8000元之间，采取怎样的策略才能在短的时间 内说出正确（大体上）的答案呢？ 第一步报“4000”； 第二步：若主持人说高了（说明答案 在0~4000之间)，就报“2000”，否则 (答数在4000-8000之间)报“6000”：， 第三步：重复第二步的报数方法取中间 数，直至得到正确结果

5 在中央电视台节目中,有一个猜商品价格的 环节,竟猜者如在规定的时间内大体猜出某种商 品的价格,就可获得该件商品.现有一商品,价格在 0-8000元之间,采取怎样的策略才能在短的时间 内说出正确(大体上)的答案呢? 第一步:报“4000”； 第二步:若主持人说高了(说明答案 在0~4000之间),就报“2000”,否则 (答数在4000~8000之间)报“6000”； 第三步:重复第二步的报数方法取中间 数,直至得到正确结果

两个大人和两名儿童一 起渡河渡只尽有条 什么是算法呢入 小船，一次只能渡过一 个大人或两名儿童，他 们四人都会划船，但都第一步：两个小孩同船渡过河去； 不会游泳。请你帮他们 第二步：一个小孩划船回来； 设计一个渡河方案。 第三步：一个大人独自划船渡过河去； 第四步：对岸的小孩划船回来： 第五步：两个小孩再同船渡过河去； 第六步：一个小孩划船回来： 第七步：余下的一个大人独自划船渡过河去； 第八步：对岸的小孩划船回来： 第九步：两个小孩再同船渡过河去。 6

6 两个大人和两名儿童一 起渡河，渡口只有一条 小船，一次只能渡过一 个大人或两名儿童，他 们四人都会划船，但都 不会游泳。请你帮他们 设计一个渡河方案。 什么是算法呢？ 第一步：两个小孩同船渡过河去； 第二步：一个小孩划船回来； 第三步：一个大人独自划船渡过河去； 第四步：对岸的小孩划船回来； 第五步：两个小孩再同船渡过河去； 第六步：一个小孩划船回来； 第七步：余下的一个大人独自划船渡过河去； 第八步：对岸的小孩划船回来； 第九步：两个小孩再同船渡过河去

归本理子末程 SHANDONG UNIVERSITY OF TECHNOLOOY 什么是算法呢？ 简单地说，算法就是解决 问题的方法或步骤

7 什么是算法呢？ 简单地说，算法就是解决 问题的方法或步骤

归东程子太军 问题3 你对以下的“算法”如何理解？ 问：要把大象装冰箱，分几步？ 答：分三步： 第一步：打开冰箱门 第二步：把大象装冰箱 第三步：关上冰箱门 8

8 你对以下的“算法”如何理解？ 要把大象装冰箱，分几步？ 答：分三步： 第一步：打开冰箱门 第二步：把大象装冰箱 第三步：关上冰箱门 问： 问题3

问题4 画莅商入有9被金币，其中宥一枝 略轻的假币，你能用天平（无砝码) 将假币找出来吗？写出解决这一问题 的算法。 第一步：把9枚金币平均分成三组，每组三枚。 第二步·李的要很擎锈锦：智果乔 重。 右平衡，则假金韦就程集称量的那一 第三步：驱出含假币的那一组，丛由任娶两格余币 适太半势空进行称鼻 如电 0 假在轻邦一透 岩季裔，动耒镙的 二就是假吊

9 一位商人有9枚金币，其中有一枚 略轻的假币，你能用天平（无砝码） 将假币找出来吗？写出解决这一问题 的算法。 第一步：把9枚金币平均分成三组，每组三枚。 先将其中的两组放在天平的两边，如果天平 不平衡，那么假金币就在轻的那一组；如果 天平左右平衡，则假金币就在未称量的那一 组里。 取出含假币的那一组，从中任取两枚金币放 在天平两边进行称量，如果天平不平衡，则 假金币在轻的那一边；若平衡，则未称的那 一枚就是假币。 第二步： 第三步： 问题4

归本程子末军 1.1算法的概念 SHANDONG UNIVERSITY OF TECHNOLOGY 华红资众是空安会器华哈品条 ●算法是指解决问题的方法和过程。 ●算法是对特定问题求解步骤的一种描述， 包含操作的有限规则和操作的有限序列。 通俗一点讲，算法就是一个解决问题 的公式（数学手册上的公式都是经典算 法)、规则、思路、方法和步骤。算法可 以用自然语言描述，也可以用流程图描述， 但最终要用计算机语言编程，上机实现。 10

10 1.1 算法的概念 ⚫算法是指解决问题的方法和过程。 ⚫算法是对特定问题求解步骤的一种描述， 包含操作的有限规则和操作的有限序列。 ⚫ 通俗一点讲，算法就是一个解决问题 的公式（数学手册上的公式都是经典算 法）、规则、思路、方法和步骤。算法可 以用自然语言描述，也可以用流程图描述， 但最终要用计算机语言编程，上机实现