当前位置：文档之家 › 北京大学《计算概论》课件：第七讲-算法.ppt

北京大学《计算概论》课件：第七讲-算法.ppt

  • 格式：ppt
  • 大小：2.05 MB
  • 文档页数：25

下载文档原格式

  / 25

合集下载

算法PPT课件

算法PPT课件

③
④ 直到p
图 1.20
29
第四节
怎样表示一个算法
三、用结构化流程图表示算法
3.用N-S流程图表示算法 用N-S流程图表示算法举例： 【例1.7】将例1.1的求5！算法用N-S图表示(图1.21)。 ① 1=>T 2=>I ② TXI=>T I+1=>I I> 5 打印T
2003/2/9
a b ③
2003/1/17 7
第二节
简单算法举例
1 _ 1 _ 1 _ 【例1.4】求 1- 2 + 3 - 4
1 1 — — + 99 - 100 [分析]先设四个变量：sum表示累加和，sign表示数值 符号，deno(denominator)表示分母，term表示某一项。 算法如下： S1：sum=1 S2：deno=2 S3：sign=1 S4：sign=(-1)X sign S5：term=signX(1/deno) S6：sum=sum + term S7：deno=deno+1 S8：若deno≤100返回S4，否则算法结束。
2003/1/19 8
第二节
简单算法举例
【例1.5】对一个大于或等于3的正整数，判断它是不是一 个素数。
[分析]判断一个数 N(N≥3)是否素数的方法是将N作被 除数，将2到√ — N 间的各个整数轮流作除数，如果都不能被 整除，则N为素数。算法如下： S1：输入 N 的值 S2：I=2 S3：N 被 I 除，得余数 R。 S4：若 R=0 (表示 N 能被 I整除),打印N “不是素数”, 算法结束；否则执行S5。 S5：I+1=>I N ，返回S3，否则算法结束。 S6：若I≤√ —

计算机算法ppt

计算机算法ppt

特权说明
VIP用户有效期内可使用VIP专享文档下载特权下载或阅读完成VIP专享文档（部分VIP专享文档由于上传者设置不可下载只能阅读全文），每下载/读完一篇VIP专享文 档消耗一个VIP专享文档下载特权。
年VIP
月VIP
连续包月VIP
享受60次VIP专享文档下载特权，一次发放，全 年内有效。
VIP专享文档下载特权自VIP生效起每月发放一次，每次发放的特权有 效期为1个月，发放数量由您购买的VIP类型决定。
0下载券文档一键搜索
VIP用户可在搜索时使用专有高级功能：一键搜索0下载券文档，下载券不够用不再有压力！
无限次复制特权 内容特权 文档格式转换
VIP有效期内可以无限次复制文档内容，不用下载即可获取文档内容 VIP有效期内可以将PDF文档转换成word或ppt格式，一键转换，轻松编辑！
阅读页去广告
VIP有效期内享有搜索结果页以及文档阅读页免广告特权，清爽阅读没有阻碍。
3、算法解决问题的类型
计算机科学领域的问题大致可分为以下三种类型：
一、判定性问题：这类问题给出的是与否的判别。 例如连通性问题，回路问题，查找与排序问题，字 符匹配问题等。
二、最优化问题：这类问题是在所有可能的解中求 出最优解。例如求函数的极值，最短路径问题，最 小生成数问题等。
三、函数计算问题：这类问题是在一定约束条件下 求数值解，例如方程求根，矩阵运算，函数求值等。
VIP专享文档下载特权自VIP生效起每月发放一次，每次发放的特权有 效期为1个月，发放数量由您购买的VIP类型决定。
每月专享9次VIP专享文档下载特权，自VIP生效 起每月发放一次，持续有效不清零。自动续费， 前往我的账号-我的设置随时取消。
服务特权 共享文档下载特权 VIP累积特权 100W优质文档免费下载

北京大学计算概论lesson7sk2007

北京大学计算概论lesson7sk2007

14
Interactive Input/Output
Interactive Input/Output
Input/Output data while a program is executing Input: char stream data Output: data char stream Use standard library <stdio.h>
19
Interactive Input (continued)
This statement produces a prompt This statement waiting for the input Address operator (&)
20
Interactive Input

The control string of scanf() typically consists of conversion control sequences only
Each time rebounds ¾ of original height Impact speed = sqrt (2 * g * height) Impact speed first three times?
1 3/4
a = b = c = 25; All = operators have the same precedence Operator has right-to-left associativity

5
Assignment (cont.)
6
Assignment (cont.)
Not a l-value

21
Interactive Input/Output

2019北京大学《计算概论》课件：01-01 课程介绍.ppt

2019北京大学《计算概论》课件：01-01 课程介绍.ppt






为什么要学习计算机相关的知识？
计算机 模拟人 进行工作，它的构造和运行都吸取 （利用）了人类思想的精华
学习人类智慧的机会
大学生计算机基础教育课程
枪杆里出政权VS标准之争。经济增长速度、效益、
和谐 VS 计算机发展：运行速度、成本、可靠性。
计算机是一个基础工具，要学会使用---初级阶段
课程目标
在 理论 方面
初步掌握 计算思维 了解 个人计算机的基本组成及各部件的功能 了解 操作系统及其主要功能 了解 信息的表示、处理、存储的基本原理 了解 互联网的基本功能和原理 了解 计算机程序的工作原理及开发过程
在 实践 方面
熟练使用 Windows 操作系统 熟练使用 一些常用软件
John von Neumann
Hamming
McCarthy
Dijstra
Knuth
Codd
Litchie
Brooks
姚期智
计算机科学历史上一些伟大的时刻

1930年，一位英国的天才开创了计算机科学这个领域，并证明有 些问题是任何计算机都不可能解的。 1948年，一位在电话公司工作的科学家发表的成果，使得计算机 即使在受干扰的信道中也能正确传输数据。 1956年，一群学者开创了人工智能的研究工作，迄今为止，尽管 取得了显著成就，我们仍然在期待“真正”的智能系统出现。 1959年，在IBM工作的一群科学家提出一种方法将数据组成特殊 的结构，成为我们今天事务处理的基础。 1974年，为英国政府通信实验室工作的一群科学家发明了一种非 常聪明的方法，成为我们今天保密通信的基础。 1996年，斯坦福大学的两个博士生设计了一个网络搜索引擎。几 年后在此基础上成立了Google公司，今天它是互联网领域的巨人 。

算法的概念课件PPT

算法的概念课件PPT

动态规划
背包问题
给定一组物品和一个背包容量，如何选择物品放入背包以使得背 包内物品的总价值最大。
最长公共子序列（LCS）
给定两个序列，找出它们的最长公共子序列。
最优二叉搜索树
给定一组按概率排序的键和对应的搜索成本，构建一棵二叉搜索树 使得总的搜索成本最低。
04 算法性能分析
时间复杂度
时间复杂度的定义
空间复杂度
1 2
空间复杂度的定义
描述算法执行所需内存空间与问题规模之间的关 系，也用大O表示法表示。
常见空间复杂度类型
包括常数空间复杂度O(1)、线性空间复杂度O(n) 等。
3
空间复杂度的优化
通过减少不必要的内存占用、使用数据结构等方 式来降低空间复杂度。
稳定性与正确性评估
01
算法稳定性评估
稳定性指算法在输入数据发生微小变化时，输出结果不会发生较大变化
问题分类
根据问题的性质和求解方 法，将问题分为不同类型， 如排序问题、图论问题等。
问题建模方法
运用数学、逻辑等工具， 对问题进行形式化描述， 建立问题的数学模型。
数据结构选择
基本数据结构
掌握数组、链表、栈、队 列等基本数据结构的特点 和使用方法。
高级数据结构
了解并学会使用树、图、 堆等高级数据结构，以便 更有效地解决问题。
算法在各个领域的应用
随着算法技术的不断成熟和普及，其将在各个领域得到更广泛的应用，如医疗、金融、交 通等，为社会发展带来更多的便利和进步。
THANKS FOR WATCHING
感谢您的观看
描述算法执行时间与问题规模之间的关系，通常用大O表 示法表示。
常见时间复杂度类型
包括常数时间复杂度O(1)、线性时间复杂度O(n)、对数时 间复杂度O(logn)、线性对数时间复杂度O(nlogn)、平方 时间复杂度O(n^2)、立方时间复杂度O(n^3)等。

算法 ppt课件

算法 ppt课件
iii) 循环结构
三种基本算法结构
A
N
A
p
Y
p
N
Y
（直到型）
（当型）
第2节 流程图
引例
开始
投票
循环结构示例
淘汰得票最 少的城市
有一城市 得票超过总 票数一半
Y 输出该城市 结束
N
第2节 流程图
循环结构
开始 T←1 I←2
例4 （P12）求1×2×3×4×5。
算法2 S1 T←1； S2 I←2； S3 T←T × I； S4 I←I + 1． S5 如果I不大于5，重新执行 S3、S4、S5；否则算法结束．
If b > x Then x ← b If c > x Then x ← c Print x
算法的实现——条理化、逻辑化、精微化
的过程
a InputBox("输入a"): b InputBox("输入b")
c InputBox("输入c")
xa
If b > x Then x b: If c > x Then x c
基本算法语句
例6（P21）计算1 3 5 7 „ 99。
伪代码
S←1 For I From 3 To 99 Step 2 S←SI End For Print S
Excel VBA
S1 For I 3 To 99 Step 2 S S*I Next I MsgBox S
MsgBox "最大数为" & x
分别输入a 12，b 9，c 5时，为什么 输出最大数为9？

《算法的概念》PPT课件


(1) (2)
a1b2 a2b1 0
第一步, (1) b2 (2) b1 得：
a1b2 a2b1 x c1b2 c2b1. （3）
第二步,解（3）得 x
c1b2 a1b2
c2b1 a2b1
.
第三步, (1) a2 (2) a1 得：
a2b1 a1b2 y a2c1 a1c2. （4）
|a-b| 1
0.5 0.25 0.125 0.062 5 0.031 25 0.015 625 0.007 812 5 0.003 906 25
y=x2-2
1 1.25 1.5
1.375
2
于是，开区间〔1.4140625,1.41796875〕 中的实数都是当准确度为0.005时的原方程的 近似解.
➢信息输出:一个算法至少要有一个有效的信息 输出,这就是问题求解的结果.
➢不唯一性:求解某一个题的解法不一定是唯 一的, 对于一个问题可以有不同的算法.
例1.(1)设计一个算法判断7是否为质数.
第一步, 用2除7,得到余数1.因为余数不为0， 所以2不能整除7.
第二步, 用3除7,得到余数1.因为余数不为0， 所以3不能整除7.
x 2 y 1 ① 2x y 1 ②
解：第一步, ① +②×2得 5x=1; ③
第二步, 解③得 x 1 ; 5
第三步, ② -① ×2得 5y=3;
④
第四步, 第五步,
解④得 y 3 ; 5
得到方程组的解为
x
y
1, 5 3.
5
你能写出解一般的二元一次方程组的步骤吗？
aa12xxbb12yycc12
第二步, 用3除35,得到余数2.因为余数不为0， 所以3不能整除35.

算法PPT课件


2.2简单的算法举例
➢ S1：使p=1，或写成1p
➢ S2：使i=2，或写成2i
➢ S3：使p与i相乘，乘积仍放在变量p中，可表
示为：p*ip
若是1000，求什么？
➢ S4：使i的值加1，即i+1 i
➢ S5：如果i不大于5，返回重新执行S3；否则 ，算法结束
➢ 最后得到p的值就是 5!的值
若2求.21简×3单×的5×算7×法9×举11例
➢ S4：sign=(-1)*sign -1/2
➢ S5：term=sign*(1/deno) 1-1/2
➢ S6：sum=sum+term 3 ➢ S7：deno=deno+1
满足，返回S4
➢ S8：若deno≤100返回S4；否则算法结束
例2.4 求 1 1 1 1 1 1
234
➢ 用ni代表第i个学生学号，gi表示第i个学生成绩 S1：1i S2：如果gi≥80， 则输出ni和gi，否则不输出 S3：i+1i S4：如果i≤50，返回到步骤S2，继续执行， 否则，算法结束
例2.3 判定2000—2500年中的每一年是 否闰年，并将结果输出。
➢闰年的条件：
(1)能被4整除，但不能被100整除的年份都是 闰年，如2008、2012、2048年 (2)能被400整除的年份是闰年，如2000年 不符合这两个条件的年份不是闰年 例如2009、2100年
➢算法是解决“做什么”和“怎么做”的 问题
➢程序中的操作语句，是算法的体现 ➢不了解算法就谈不上程序设计
2.1 什么是算法 2.2 简单的算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法
2.1 什么是算法

北京大学算法分析的课件


•
简介[2]
• • • • • • • •
U 0 (n 0) k Un aiu n / bi g (n) i 1
(n 1)
其中 k 1. ai 1 i 1 2. bi>=2,k>=1; 3. g(x)当x>0时渐进有界，大于0，单调递增； 4. c 1, x1, k 1 0使得g ( x / c) k 1 g ( x), x x1 意思是说当x足够大时，g(x)的渐进界限不会突然增大
k
由于m / bi n
(n 2而b i 2)所以
i 1
c c 取k 2 min{k , k1}则
i 1

i 1 k
k
k m / bi m ai f ( ) g ( ) ai kf ( m / bi ) k1 g (m)
k m / bi m ai f ( ) g ( ) ai k 2 f ( m / bi ) k 2 g ( m) k 2 f ( m)
s/a s s p 1
dv
s
s/a
f (v)(v)
p 1
dv f ( s ) (v) p 1 dv
s/a
s
对p 0和p 0讨论积分 f ( s) 得f ( s ) (v) dv （ p ） s/a s s u p 1 f ( s) p 这样，我们证明了 f ( )u d (u ) a F ( s, p ) ( p ) (1) 1 a s
c
c
i 1
证毕
现在来探讨f(x)的积分问题
• 由于f(x)可以趋近无穷，直接积分可能有困难， 因此在f(x)旁边加一个因子求

算法的概念(ppt课件)


写出一般二元一次方程组的解法步骤. (1) a1 x b1 y c1 a1b2 a2b1 0 (2) a2 x b2 y c2
第一步, (1) b2 (2) b 1 得：
a1b2 a2b1 x c1b2 c2b1
c1b2 c2b1 第二步,解（3）得 x a1b2 a2b1
8．写出求1＋2＋3＋…＋100的一个算法.
n( n 1) 可以运用公式1＋2＋3＋…＋n＝ 2
直接计算. 第一步 第二步
① ②
； ①取n＝100 ； ②计算 n(n 1)
2
第三步 输出运算结果.
9．已知一个学生的语文成绩为89，数学 成绩为96，外语成绩为99，求他的总分和 平均成绩的一个算法为： 第一步 取A＝89，B＝96，C＝99; 第二步 ① ； 第三步 ② ； 第四步 输出D，E.
巩固概念
×
写出交换两个大小相同的杯子中 的液体 (A 水、 B 酒) 的一个算法． 第一步,找一个大小与A相同的空杯子C. 第二步,将A 中的水倒入C中. 第三步,将B中的酒精倒入A中. 第四步,将C中的水倒入B中,结束.
例1：读下列算法，回答问题： 第一步，令s=0 第二步，令i=1。 第三步，求出s+i，仍用s表示。 第四步，判断i＞100是否成立？若是，输出s；若不是 ，将i的值增加1，仍用i表示返回第三步。 （1）该算法是解决什么问题的？ （2）最终输出的结果是什么？
D. 加减乘除运算法则
7．下列语句表达中是算法的有（ C ）. ① 从济南到巴黎可以先乘火车到北京再坐 飞机抵达； ②利用公式 S = ah÷2 计算底为1高为2的 1 三角形的面积； ③ x>2x +4； 2 ④求M(1，2)与N(3，5)两点连线的方程可 先求MN的斜率再利用点斜式方程求得． A. 1 个 B. 2 个 C. 3 个 D. 4 个
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
程序：刻画现实世界，解决现实世界中的问题 程序设计语言：实现的工具 算法：问题的解的描述 数据结构：现实世界的数据模型
程序就是在数据的某些特定的表示方式和结构的基 础上对抽象算法的具体表述。一行行代码、语言
1 算法的基本概念
2020/10/11
北京大学
4
算法的定义
设计程序的目的是为了求解问题，为解决一个问题 所采取的方法和步骤，就称为“算法”
2020/10/11
1 算法的基本概念
北京大学
9
算法范化
从N个正整数中找出最大数的通用算法
循环结构
S0: 设Largest为0，当前位置p为0 S1: 若当前数比Largest大，则设Largest为当前数 S2: 若p比N小，则p增加1，并返回S1；否则返回Largest
2020/10/11
2020/10/11
1 算法的基本概念
北京大学
8
算法动作精化
S0: 设Largest为0 S1: 若当前数比Largest大，则设Largest为当前数 S2: 若当前数比Largest大，则设Largest为当前数 S3: 若当前数比Largest大，则设Largest为当前数 S4: 若当前数比Largest大，则设Largest为当前数 S5: 若当前数比Largest大，则设Largest为当前数
17
现实生活中的示例
选择 二选一 条条道路通罗马
如果明天天晴
小明就去郊游
否则
就在家里看书
如果分数达到一本线
录取到一本大学
如果分数达到二本线
录取到二本大学
如果分数达到三本线
录取到三本大学
如果分数达到专科线
录取到专科学校
否则
落榜
2.2 分支结构
2020/10/11
北京大学
顺序执行，每个动作只执行一次， 各动作对执行结果产生的影响是 独立的
动作1 动作2 动作3 … 动作n
动作1 动作2 动作3
… 动作n
2.1 顺序结构
2020/10/11
北京大学
15
现实生活中的示例
按部就班 先来后到 循序渐进 接连不断
起床 刷牙 吃早饭 上课 吃中饭 午休 上课 吃晚饭 晚自习 洗漱 睡觉
算法是一个由一组严格定义的动作组成的过程，给 定一个出始状态，这个过程能够结束在一个确定终 止状态。
大多数算法都可以用程序实现。 常用算法一般都被实现为算法库，供程序员调用。
2020/10/11
1 算法的基本概念
北京大学
5
算法的基本思想
如何把大象关在冰箱里?
分3步：
第一步：打开冰箱门; 第二步：把大象推进冰箱; 第三步：关上冰箱门;
1 算法的基本概念
2020/10/11
北京大学
12
不了解施加于数据上的算法就无法决定如 何构造数据；反之，算法的结构和选择却 常常在很大程度上依赖于作为基础的数据 结构。简而言之，程序的构成（算法） 与数据结构是两个不可分割地联系在一 起的问题。
2020/10/11
1 算法的基本概念
北京大学
13
程序设计就是要告诉计算机如何进行计算 的。这与我们中学时代的数学解题过程是 一样的，只不过描述的手段有所变化而已。
2020/10/11
1 算法的基本概念
北京大学
3
1984年图灵奖获得者瑞士科学家尼克劳斯·沃斯（Niklaus Wirth，Pascal语言的发明者和结构化程序设计创始者）1976 年出版了《算法+数据结构 = 程序设计》一书，提出了著名 的公式：“程序 ＝ 数据结构 ＋ 算法” 。
一个实例：找出一组正整数中的最大的数
2020/10/11
1 算法的基本概念
北京大学
7
逐步求解，定义算法的动作
S1: 设Largest为第一个数 S2: 若第二个数比Largest大，则设Largest为第二个数 S3: 若第三个数比Largest大，则设Largest为第三个数 S4: 若第四个数比Largest大，则设Largest为第四个数 S5: 若第五个数比Largest大，则设Largest为第五个数
内结束，并给出明确的计算结果。 离散性：算法的输入数据及输出数据都应是离散的符号。
1 算法的基本概念
2020/10/11
北京大学
11
算法的基本要求
正确 易维护（可读，易修改） 方便使用空间复杂度低 算法的效率可以测试，用大量输入数据测量运行的时间和 占用的内存，通过比较判别和选择效率高的算法。 更重要的是可以在编程前进行分析和估计（算法分析）， 即理论的计算，给出事前的判断。高斯，查字典
2.1 顺序结构
2020/10/11
北京大学
16
分支结构：根据条件判
断执行什么动作（序列），
最多只有一个动作（序列）
被执行
是 条件成立？ 否
如果 条件成立 则
动作（或动作序列）1
否则
动作（或动作序列） 2
分支结束
动作（序列）1 动作（序列）2
2.2 分支结构
2020/10/11
北京大学
1 算法的基本概念
北京大学
10
算法的基本性质
通用性：即适用于某一类问题中的所有个体，而不只是用 来解决一个具体的问题。
有效性：即应有明确的步骤一步一步地引导计算的进行。 确定性：即每个步骤都是机械的、有明确定义的动作，不
需要计算者临时动脑筋。 有限性：对满足算法要求的输入数据，算法应在有限多步
18
循环结构：重复执行
一系列动作
当 条件成立 做
动作1 动作2 … 动作n
循环结束处
第七讲 算法
北京大学信息学院 2013年10月
了解算法的基本概念 掌握描述算法的三种基本结构 学会算法的流程图描述 介绍几种基本算法
难、有意思、数学、编程的基础
主要内容
2020/10/11
北京大学
2
计算机是一个计算工具，它本身不能主动 帮助我们做任何事情，需要我们告诉它如 何进行计算。
计算机科学家已经证明，只使用如下三种 结构，就可以描述任何算法，且算法结构 优良
顺序结构（Sequence） 分支结构（Decision） 循环结构（Repetition）
每一种基本结构分别只有一个入口和一个 出口
2 描述算法的三种基本结构
2020/10/11
北京大学
14
顺序结构：动作（语句）序列，