9512.net
甜梦文库
当前位置:首页 >> 理学 >>

第2章 算法---程序的灵魂(包含闰年版本)



第2章 算法---程序的灵魂

? 一个程序主要包括以下两方面的信息:
(1) 对数据的描述。在程序中要指定用到哪些 数据以及这些数据的类型和数据的组织形式 ?这就是数据结构(data structure)

(2) 对操作的描述。即要求计算机进行操作的 步骤
?也就是算法(algorithm)

? 数据是操作的对象 ? 操作的目的是对数据进行加工处理,以 得到期望的结果

程序=数据结构 +算法

? 算法是解决“做什么”和“怎么做”的 问题

? 程序中的操作语句,是算法的体现
? 不了解算法就谈不上程序设计

2.1 什么是算法

2.2 简单的算法举例
2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法

2.1 什么是算法
? 广义地说,为解决一个问题而采取的方 法和步骤,就称为“算法” ? 对同一个问题,可以有不同的解题方法 和步骤 ? 为了有效地进行解题,不仅需要保证算 法正确,还要考虑算法的质量,选择合 适的算法

2.2简单的算法举例
例2.1 求1×2×3×4×5× …×1000
? 最原始的方法进行:
?结果=(((1*2)*3)*4)*5 #include <stdio.h> void main(){ int p=1; p = p*2; p = p*3; p = p*4; p = p*5; printf(“积=%d”, p) }

? 改进方法

999行? ?s1:结果=1*2; 太繁琐 ?s2:结果=上次结果*3;
?s3:结果=上次结果*4; ?s4:结果=上次结果*5。

2.2简单的算法举例
? 改进的算法:
?设变量p为被乘数 ?变量i为乘数 ?用循环算法求结果
#include <stdio.h> void main(){ int p=1; p = p*2; p = p*3; p = p*4; p = p*5; printf(“积=%d”, p) }

2.2简单的算法举例
? S1:使p=1,或写成1?p
? S2:使i=2,或写成2?i

#include <stdio.h> void main(){ int p=1; p = p*2; p = p*3; p = p*4; p = p*5; printf(“积=%d”, p) }

? S3:使p与i相乘,乘积仍放在变量p中,可表 若是1000,求什么? 示为:p*i?p ? S4:使i的值加1,即i+1 ?i

? S5:如果i不大于5,返回重新执行S3;否则 ,算法结束 ? 最后得到p的值就是 5!的值

若求 1 ×3×5×7×9×11 2.2 简单的算法举例
? S1:使p=1,或写成1?p
? S2:使i=2 3 ,或写成2 3?i ? S3:使p与i相乘,乘积仍放在变量p中,可表 相当于i ≦11 示为:p*i?p ? S4:使i的值加1 2 ?i 2,即i+1

? S5:如果i不大于5 ,返回重新执行S3;否则 11 ,算法结束 ? 最后得到p的值就是11 5!的值

例2.2 有50个学生,要求将成绩在80分 以上的学生的学号和成绩输出。
? 用ni代表第i个学生学号,gi表示第i个学生成绩 S1:1?i S2:如果gi≥80, 则输出ni和gi,否则不输出

S3:i+1?i
S4:如果i≤50,返回到步骤S2,继续执行, 否则,算法结束

例2.3 判定2000—2500年中的每一年是 否闰年,并将结果输出。 ? 闰年的条件:
(1)能被4整除,但不能被100整除的年份都是 闰年,如2008、2012、2048年

(2)能被400整除的年份是闰年,如2000年
?不符合这两个条件的年份不是闰年

?例如2009、2100年

? 设year为被检测的年份。算法表示如下: ?S1:2000?year ?S2:若year不能被4整除,则输出year 的 值和“不是闰年”。然后转到S6 ?S3:若year能被4整除,不能被100整除, 则输出year的值和“是闰年”。然后转到S6 ?S4:若year能被400整除,则输出year的 值和“是闰年” ,然后转到S6 ?S5: 其他情况输出year的值和“不是闰年” ?S6:year+1?year ?S7:当year≤2500时,转S2,否则停止

year不能 被4整除 非闰年 闰年

year被100 整除,又能 被400整除

year被4整 除,但不能 被100整除 闰年 逐渐缩小判 断的范围

其他 非闰年

1 1 1 1 1 例2.4 求 1 ? ? ? ? ... ? ? 2 3 4 99 100
100项

? 规律: 1 ? (? 1 ) ? ( 1 ) ? (? 1 ) ? ... ? ( 1 ) ? (? 1 )
2 3 4 99 100

①第1项的分子分母都是1

② 第2项的分母是2,以后每一项的分母都是前 一项的分母加1
③ 笫2项前的运算符为“-”,后一项前面的运 算符都与前一项前的运算符相反

1 1 1 1 1 例2.4 求 1 ? ? ? ? ... ? ? 2 3 4 99 100
? S1:sign=1 ? S2:sum=0 1/1 ? S3:deno=1 ? S4:term=sign*(1/deno) ? S5:sum=sum+term 2 ? S6 -1 :deno=deno+1 满足,返回S4 ? S7:sign=(-1)*sign ? S8:若deno≤100返回S4;否则算法结束 sign—当前项符号 sum—当前各项的和 term—当前项的值 0+1 deno—当前项分母

1 1 1 1 1 例2.4 求 1 ? ? ? ? ... ? ? 2 3 4 99 100
? S1:sign=1 ? S2:sum=0 -1/2 1-1/2 ? S3:deno=1 ? S4:term=sign*(1/deno) 3:sum=sum+term ? S5 ? S6:deno=deno+1 满足,返回S4 ?1 S7:sign=(-1)*sign ? S8:若deno≤100返回S4;否则算法结束 sign—当前项符号 sum—当前各项的和 term—当前项的值 deno—当前项分母

1 1 1 1 1 例2.4 求 1 ? ? ? ? ... ? ? 2 3 4 99 100
? S1:sign=1 99次循环后sum的值 就是所要求的结果 ? S2:sum=1 ? S3:deno=2 ? S4:term=sign*(1/deno) ? S5:sum=sum+term ? S6:deno=deno+1 ? S7:sign=(-1)*sign ? S8:若deno≤100返回S4;否则算法结束

例2.5 给出一个正整数,判断它是不是一 个素数。 ? 素数:指除了1和该数本身之外,不能被 其他任何整数整除的数

例如给定正整数13:
?S1:判断是否能被2整除? No
?S2:判断是否能被3整除? No

?...
?S11:判断是否能被12整除? No

13是素数!

例如给定正整数15:
?S1:判断是否能被2整除? No
?S2:判断是否能被3整除? Yes

15不是素数!
无需判断是否能被4、5、...、14整除!

? 判断一个数n是否素数:将n作为被除数, 将2到(n-1)各个整数先后作为除数,如果 都不能被整除,则n为素数
S1:输入n的值 S2:i=2 (i作为除数) S3:n被i除,得余数r S4:如果r=0,表示 n能被 n 可改为 n/2 i整除,则输出“ n 不是素数”,算法结束;否则执行S5 S5:i+1?i S6:如果i≤n-1,返回S3;否则输出“n是素 数”,然后结束。

2.3算法的特性
? 一个有效算法应该具有以下特点:
(1) 有穷性。一个算法应包含有限的操 作步骤,而不能是无限的。 (2) 确定性。算法中的每一个步骤都应 当是确定的,而不应当是含糊的、模棱 两可的。

2.3算法的特性
? 一个有效算法应该具有以下特点:
(3) 有零个或多个输入。所谓输入是指在执 行算法时需要从外界取得必要的信息。 (4) 有一个或多个输出。算法的目的是为了 求解,“解” 就是输出。

?没有输出的算法是没有意义的。
(5) 有效性。算法中的每一个步骤都应当能 有效地执行,并得到确定的结果。

2.3算法的特性
? 对于一般最终用户来说:
?他们并不需要在处理每一个问题时都要自 己设计算法和编写程序 ?可以使用别人已设计好的现成算法和程序 ?只需根据已知算法的要求给予必要的输入 ,就能得到输出的结果

输入3个数

求3个数的 黑箱子 最大数

3个数中最大数

2.4怎样表示一个算法
? 常用的方法有:
?自然语言 ?传统流程图 ?结构化流程图 ?伪代码 ?……

2.4怎样表示一个算法
2.4.1 用自然语言表示算法
2.4.2 用流程图表示算法

2.4.3 三种基本结构和改进的流程图
2.4.4 用N-S流程图表示算法 2.4.5 用伪代码表示算法 2.4.6 用计算机语言表示算法

2.4.1 用自然语言表示算法
? 2.2节介绍的算法是用自然语言表示的
? 用自然语言表示通俗易懂,但文字冗长,容 易出现歧义性 ? 用自然语言描述包含分支和循环的算法,不 很方便 ? 除了很简单的问题外,一般不用自然语言

一个入口

x≧0 两个出口 …… ? 流程图是用一些图框来表示各种操作 …… ? 用图形表示算法,直观形象,易于理解

Y 2.4.2用流程图表示算法 N

起止框

输入输出框

判断框

处理框

流程线

连接点

注释框



2.4.2用流程图表示算法




② ? 流程图是用一些图框来表示各种操作

? 用图形表示算法,直观形象,易于理解


位置不够
① 起止框 输入输出框 ②

判断框 防止交叉 处理框

流程线

连接点

注释框

开始

例2.6 将1×2×3×4 ×5用流程图表示。
? S1:使p=1,或写成1?p

1? p
2? i p*i?p i+1?i N

? S2:使i=2,或写成2?i
? S3:使p与i相乘,乘积仍放在变量 p中,可表示为:p*i?p ? S4:使i的值加1,即i+1 ?i

? S5:如果i不大于5,返回重新执行 S3;否则,算法结束
? 最后得到p的值就是 5!的值

i>5
Y
结束

#include <stdio.h> int main( ) { int i,p; 例2.6 将1×2×3×4 p=1; × 5用流程图表示。 i=2; do { ? 如果需要将最后结果 p=p*i; 输出 : i=i+1; }while(i<=5); printf(“积=%d\n",p); return 0; } 结束

开始

1? p
2? i p*i?p i+1?i N

i>5
Y 输出t

例2.8 例2.3判定闰年的算法用流程图表 示。判定2000—2500年中的每一年是否 闰年,将结果输出。

开始
2000?year

year不能 被4整除 N year不能 被100整除
Y year是闰年 year+1?year

Y year 不是闰年
N

N

Y

year不能 被400整除

year不是闰年

year是闰年

year>2500
N

结束 Y

例2.9 将例2.4的算法用流程图表示。求

1 1 1 1 1 1 ? ? ? ? ... ? ? 2 3 4 99 100

#include <stdio.h> 0?sum int main( ) 1?deno { int sum, deno, sign; 1?sign sign=1; sum=0; sum+ sign*(1/deno) ?sum deno=1; deno+1?deno do (-1)*sign?sign { sum=sum+sign*(1/deno); deno = deno + 1; sign=sign*(-1); deno<=100 Y }while(deno<=100); N printf(“和=%f\n",sum); 输出sum return 0; 结束 }

开始

例2.10 例2.5判断素数的算法用流程图表 示。对一个大于或等于3的正整数,判断 它是不是一个素数。

开始
#include <stdio.h> int main( ) { int n, i, r; scanf(“输入n: %d”, &n); i=2; do { r=n%i; if(r==0){ printf(“%d不是素数!\n”, n); break; } i = i + 1; } while(i <=n/2); if(i>n/2) printf (“%d是素数!\n”, n); return 0; }

输入n 2? i n%i?r r=0 N i+1?i N Y 输出n不 是素数

i>n/2 Y 输出n是素数 结束

? 通过以上几个例子可以看出流程图是表示 算法的较好的工具 ? 一个流程图包括以下几部分:
(1) 表示相应操作的框 (2) 带箭头的流程线 (3) 框内外必要的文字说明

? 流程线不要忘记画箭头,否则难以判定各 框的执行次序

2.4.3 三种基本结构和改进的流程图
1.传统流程图的弊端
? 传统的流程图用流程线指出各框的执行顺 序,对流程线的使用没有严格限制 ? 使用者可以毫不受限制地使流程随意地转 来转去,使人难以理解算法的逻辑

2.4.3 三种基本结构和改进的流程图
2.三种基本结构
(1) 顺序结构
A B

2.4.3 三种基本结构和改进的流程图
2.三种基本结构
(2) 选择结构
Y A
p N

Y B A

p

N

2.4.3 三种基本结构和改进的流程图 输出1,2,3,4,5
2.三种基本结构
(3) 循环结构
① 当型循环结构 p1 Y A N
0? x x<5 Y 输出x的值

N

x+1?x

2.4.3 三种基本结构和改进的流程图 输出1,2,3,4,5
2.三种基本结构
(3) 循环结构
② 直到型循环结构
A N p2 Y

0? x x+1?x
输出x的值

N

x≧ 5
Y

? 以上三种基本结构,有以下共同特点:
(1) 只有一个入口 (2) 只有一个出口 ?一个判断框有两个出口 ?一个选择结构只有一个出口 (3) 结构内的每一部分都有机会被执行到。也 就是说,对每一个框来说,都应当有一条从入 口到出口的路径通过它 (4) 结构内不存在“死循环”

? 由三种基本结构派生出来的结构:
根据表达式p 的值进行选择

B Y

A
p2 N A

B



M

N

2.4.4 用N-S流程图表示算法
? N-S流程图用以下的流程图符号:
p Y A N B 当p1成立 A 循环结构 (当型)

A
B 顺序结构

A
直到p2成立 循环结构 (直到型)

选择结构

例2.11将例2.1的求5!算法用N-S图表示。
1? t

2? i
t*i?t

i+1?i
直到i>5 输出t

2.4.5用伪代码表示算法
? 伪代码是用介于自然语言和计算机语言之 间的文字和符号来描述算法
? 用伪代码写算法并无固定的、严格的语法 规则,可以用英文,也可以中英文混用

例2.16 求5!。
begin 1?t 2?i while i≤5 { t*i ? t i+1 ? i } print t end (算法开始)

(算法结束)

1 1 1 1 1 例2.17 求 1 ? ? ? ? ... ? ? 2 3 4 99 100 begin
0 ? sum 1 ? deno 1 ? sign while deno ≤ 100 { sign*1/deno ? term sum+term ? sum (-1)*sign ? sign deno+1 ? deno } print sum end

2.4.6用计算机语言表示算法
? 要完成一项工作,包括设计算法和实现算 法两个部分。
? 设计算法的目的是为了实现算法。 ? 不仅要考虑如何设计一个算法,也要考虑 如何实现一个算法。

例2.18 将例2.16表示的算法(求5!)用 C语言表示。

#include <stdio.h> int main( ) { int i,t; t=1; i=2; while(i<=5) { t=t*i; i=i+1; } printf("%d\n",t); return 0; }

例2.19 将例2.17表示的算法(求多项式

1 1 1 1 1 1 ? ? ? ? ... ? ? 2 3 4 99 100
的值)用C语言表示。

#include <stdio.h> int main( ) { int sign=1; double deno = 2.0,sum = 1.0, term; while (deno <= 100) { sign = -sign; term = sign/deno; sum = sum+term; deno = deno+1; } printf ("%f\n",sum); return 0; }

2.5结构化程序设计方法
? 结构化程序设计强调程序设计风格和程序 结构的规范化,提倡清晰的结构。
? 结构化程序设计方法的基本思路是:把一 个复杂问题的求解过程分阶段进行,每个 阶段处理的问题都控制在人们容易理解和 处理的范围内。

2.5结构化程序设计方法
? 采取以下方法保证得到结构化的程序:
(1) 自顶向下;

(2) 逐步细化;
(3) 模块化设计;

(4) 结构化编码。



更多相关文章:
C程序设计(第4版)教案第2章算法
教授课日期 年级、专业 案 首 页 课 题: 第二章 算法——程序的灵魂 课 ...如不能被 100 整除,则肯定是闰年(例如 1996 年)。如能被 100 整除,还 不...
算法程序设计的灵魂
算法程序设计的灵魂_计算机软件及应用_IT/计算机_...随机化算法在内的一些算法,包含了一些随机输入。 ...cormen 等 算法导论(第二版) 机械工业出版社 【3...
第2章 算法
第2 章 程序的灵魂---算法教学时数:4 教学目的:掌握结构化程序设计的基本概念...闰年的条件: (1)能被 4 整除,但不能被 100 整除的年份都是闰年,如 2008...
第二章 程序的灵魂——算法
课题: 第二章 程序的灵魂——算法 教学目的及要求: 了解算法的概念; 掌握用流程...例 2.3 判定 2000-2500 年中的每一年是否是闰年。 五、用 N-S 流程图...
C程序设计(第四版)(谭浩强)第二章课后习题答案
第 2 章课 后习题答案 算法——程序的灵魂 P017...P019 2.3 判断2000-2500年中的闰年,并输出. 年...//下面用到sqrt,所以需要包含数据函数.sqrt是求根,...
谭浩强c语言word版第2章
11 2 程序的灵魂算法一个程序应包括: ? 对数据的描述。在程序中要指定数据...【例 2.3】判定 2000 — 2500 年中的每一年是否闰年,将结果输出。 润年的...
ch2_C语言程序讲义
第二章 算法――程序的灵魂一个程序主要包括以下两个方面的信息: (1)对数据...【例 2.3】判定 2000-2500 年中的每一年是否为闰年,并将结果输出。 闰年的...
C语言学习--程序的灵魂算法
2 程序的灵魂算法 一个程序应包括: ? 对数据的描述。在程序中要指定数 据...【例 2.3】 判定 2000 — 2500 年中的 每一年是否闰年,将结果输出。 润年...
程序的灵魂-算法
程序的灵魂程序的灵魂算法 一个程序应包括: l 对数据的描述。 在程序中...【例 2.3】判定 2000 — 2500 年中的每一年是否闰年,将结果输出。 润年的...
第二章 程序设计的灵魂
第二章程序设计的灵魂---算法学号 姓名 班级 成绩 A B C 学习目的与要求: 1、理解什么是算法; 2、掌握算法的特点; 3、重点掌握算法的表示---N-S 流程图...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图