C语言算法讲课课件

程序的灵魂：算法
单 位：信息工程系 授 课 人：焦峰亮 授课时间： 2015.11
【复习引入】
●什么叫做程序？ ●C语言程序的主要特点有哪些？
●简述运行C程序的步骤和方法。
●我们使用的程序是如何编写出来
算 法
的？写程序的第一步是什么？
引例——
高斯的故事 德国著名数学家高斯幼年时代聪明过人， 上学时，有一天老师出了一道题让同学 们计算： 1＋2＋3＋4＋„＋99＋100＝？ 老师出完题后，全班同学都在埋头计算。
开始
a1＝1，a100=S， n=100
S100=(1+100)*100/2
输出S=5050
结束
例1.N-S流程图 (计算机累加算法)
S=0,i=1 S=S+i
i=i+1
直到i>100
输出S=5050
C程序设计 (4) 伪代码表示算法
程序的灵魂：算法
E1. 求累加和1+2+3+…+100
AlgorithmSTEP1：input let S=0；i=1； STEP2：S=S+i;i=i+1; STEP3：if i≤100 then do STEP2; STEP4：output S. （5）计算机语言表示的算法。 main() {int i,p; p=1; i=2; while(i<=5) {p=p*i; i=i+1; } printf(“%d”,p); } < >
自然语言、传统流程图、N-S图、伪代码、PAD图等。
E1. 求累加和1+2+3+…+100 (1)用自然语言描述
自然语言就是人们日常使用的语言，可以是中文、英文等 。用自然语言表示的算法通俗易懂，但一般篇幅较冗长，表达 上不易准确，易引起理解上的“歧义性”。 (2)用传统流程图描述
传统流程图是用一组规定的图形符号、流程线和文字说明 来表示各种操作算法。直观形象，易于理解。 ANSI C 规定了一 些常用的流程图符号，如下表所示。 < >
计算机算法分为两大类别：数值算法：1+2+…+100 非数值算法：图书检索、人事管理
<
>
C程序设计
程序的灵魂：算法
2 简单算法举例：
E1、求累加和1+2+3+…+100 100+（1+99）+（2+98）+…+（49+51）+50<高斯> E2、交换两个变量a,b的值。 ⑴引进中间变量t ⑵t=a,a=b,b=t E3、判断一个正整数m是否是质数(素数)。 任取一个整数p（2≤p≤m-1），如果m能被p整 除，则m为非质数，否则为质数。
C程序设计
程序的灵魂：算法
符 号
符号名称 起止框 输入输出框 处理框 判断框
含 表示算法的开始和结束 表示输入输出操作
义
表示对框内的内容进行处理 表示对框内的条件进行判断
流程线
连接点
表示流程的方向 表示两个具有同一标记的“连接点”应连接成一个 点
<
>
C程序设计
程序的灵魂：算法
例1：求累加和 1+2+3+…+100 ，用流程表示。(我们的算法) 开始 a1＝1，a100=S，n=100 S100=(1+100)*100/2
1+2=3,3+3=6， 6+4=10,10+5=15，„„,s99+100=s100
99次加法
累加
【内容导航】
程序的灵魂：算法
1.算法的概念 2.简单算法举例
3.算法的特性 4.算法的表示 5. 结构化程序算法
C程序设计
程序的灵魂：算法
1 算法的概念
所谓算法即解决一个问题而采取的方法和步骤 的精确描述，可以理解为有基本运算及规定的运算 顺序所构成的完整的解决步骤。 程序设计的灵魂是算法。 ——计算机算法即计算机能执行的算法。 ——同一问题可以有不同的算法实现。（举例） 算法 + 数据结构 = 程序(worth公式)
②直到型循环：
a
A
A P1
不满足
直到P1满 足
满足
b
< >
C程序设计
程序的灵魂：算法
例题分析：求1+2+3+4…直到其和大于或等于100。
开始 0 =>t 1=>i
t＋ i=>t i＋1=>i 否
0 =>t ，1=>i
t＋i=>t i＋1=>i
直到 t≥100
输出t
t≥100 是 输出t
结束
<
>
C程序设计
2
P*i i+1 i>5 结束
i
p i
2
P*i i+1
i
p i
S5:若i<=5, 返回s3; 否则，结束 用自然语言表示
直到i>5 结束
用N-S流程表示
用流程图表示
<
>
C程序设计
程序的灵魂：算法
5.结构化程序算法
为了避免出现BS算法(a Bowl of Spaghetti的缩写，意为“一碗面条”似 的) ，Bohra和Jacopini提出了三种基本程序结构。 已经证明，由这三种基本结构组成的算法，可以解决任何复杂问题。称之 为结构化程序算法。 （1）顺序结构 （2）选择结构 （3）循环结构： 当型循环 直到型循环 三种基本程序结构具有以下特点： 1) 只有一个入口。（a点） 2) 只有一个出口。（b点） 3) 每一个基本结构中的每一部分都有机会被执行。 4) 结构内不存在死循环
高斯的计算
1＋2＋3＋„+49+50+51+„＋97+98+99＋100＝？
50*100=5000
(1+99)+(2+98)+(3+97)+…+（49+51）+100+50
=5050
我们的计算法 1＋2＋3＋„+49+50+51+„＋97+98+99＋100 ＝？ S100=（a1+a100）*100/2=(1+100)/2=5050 小学生的计算法
输出和S100=5050 结束 < >
C程序设计
程序的灵魂：算法
例2：求累加和 1+2+3+…+100 ，用流程表示。(计算机累加算法) 开始 S＝1 S+2=S S+3=S S+i=S S+100=S 否 开始 S＝0 i=1 S+i=S i＋1=i i>100? 是 输出S 结束
输出S 结束
< >
C程序设计
第二章 程序的灵魂：算法
例3：几种算法表示法的比较
●求5！
开始 p i p i 1 p 1 p main() {int i,p; p=1; i=2; while(i<=5) {p=p*i; i=i+1; } printf(“%d”,p); } 用代码Ｃ语言表 示
S1: 1 S2: 2 S3: p*i S4: i+1
<
>
C程序设计
程序的灵魂：算法
N-S流程图表示
a
（1）顺序结构
A
A B
B
b < >
C程序设计
程序的灵魂：算法
a
（2）选择结构
满足
P
不 满足 B
不满足
P 满足 A
A
B
b < >
C程序设计
程序的灵魂：算法
（3）循环结构 ① 当型循环：
a
当P1满 足 不满足
P1
满足 A
A
b < >
C程序设计
程序的灵魂：算法
<
>
C程序设计
程序的灵魂：算法
【作业布置】
教材Page15：T1，T3，T5 同时预习《结构化程序设计方法》内容
<
>
<
>
C程序设计
程序的灵魂：算法3 算法的源自性一个算法应具有以下5个特性： （1）有穷性：有限的操作步骤；
（2）确定性：每一个步骤都是确定的；
（3）有效性：每一个步骤能有效执行并
能得到确定的结果；
（4）输 （5）输
< >
入：有0个或多个输入； 出：有1个或多个输出。
C程序设计
程序的灵魂：算法
4 算法的表示
程序的灵魂：算法
【课堂小结】
本节课主要讲了算法的概念，算法的特性，算法的表示和
结构化算法，同学们要掌握算法的基本概念，掌握算法的表示 及三种结构化算法，要注意总结课堂练习中出现的各种问题和 解决方法，以做到熟练使用算法。本节的内容是十分重要的， 是学习后面各章的基础。学习程序设计的目的不只是学习一门 特定的语言，而是学习进行程序设计的方法。掌握了算法就是 掌握了程序设计的灵魂，再学习有关的计算机语言知识，就能 够顺利编写任何一种语言的程序。关键是算法。有了正确的算 法，用任何语言进行编码都不应该有什么困难。
C程序设计
程序的灵魂：算法
(3)N-S流程图表示算法
由于用基本结构的顺序组合就可以表示任何复杂的算法结构，－－基本 结构之间的流程线就多余。 1973年Nassi和Shneiderman提出了新的流程图形式－－N-S流程图, 又叫盒图。