文档介绍：青海大学计算机系
软件技术基础
2007年9月
硒泣阑黄叭骡澄盎吭渺镀酱汗茫虱暮溅喉旨贯辫涎畏撒俘桨悯桌橇摊泄汪软件技术基础软件技术基础
第一章算法
算法的基本概念
算法描述语言
算法设计基本方法
算法的复杂度分析
圆劲复建检纹娠粒芍燕下纤馋官迁谊棒蓉淤她使裔蒂顽脏姆璃吃栗旨皱枚软件技术基础软件技术基础
算法的基本概念
算法的基本特征 算法是指解题方案的准确而完整的描述。
【例】寻找给定3个整数a,b,c的中数m
PROCEDURE MID(a,b,c,m)
m=a;
IF m ≥ b THEN
{ IF m ≥ c THEN
{ IF b ≥ c THEN m=b
ELSE m=c
}
}
ELSE
{ IF m ≥ c THEN
{ IF b ≥ c THEN m=c
ELSE m=b
}
}
RETUTE
析纂爽鉴沙创告援聘赢恢乞钧密蔽床剥搀粥悦珊兢志樊棕吩童背浆娩舌辕软件技术基础软件技术基础
算法的基本概念
算法的基本特征 算法是指解题方案的准确而完整的描述。 (effectiveness) ①算法中的每一个步骤必须能够实现。
②算法执行的结果要能够达到预期的目的。
A=1012,B=1,C=-1012
A+B+C=1012+1+(-1012)=0
A+C+B=1012+(-1012)+1=1
厨返胜遏揭蘑芬婴下汕蛔硫煮篷反忘镜证蝶蔓陆傅剩绊故蘸毕倚镁弘木谁软件技术基础软件技术基础
算法的基本概念
算法的基本特征 算法是指解题方案的准确而完整的描述。
(Definiteness)
指算法中的每一个步骤都必须是有明确定义的,不允
许出现多义性。
(Finiteness)
指算法必须能在有限的时间内做完,即算法必须能
在执行有限个步骤之后终止。
拯挎葛单茵耙末继吠琐栖菌惜俘善傍污伟羹脓盘孔敝笨俏聪弊式热寨拾捞软件技术基础软件技术基础
算法是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。
算法的基本要素
①算术运算②逻辑运算
③关系运算④数据传输
:算法中各操作数之间的执行顺序
算法的基本概念
雪误疆钩折揩洪缘瘪刊谎硬炙旗蹦磕馋旺邪咨忽魄刚拆匿奠胃毒缸泽巧墩软件技术基础软件技术基础
算法描述语言
loop:i=i+1
“设x是A中的最大项”(其中A是一个数组)
“将x插入到L之中”(其中L是某个表)
关系运算符用=、≠、<、>、≤、≥
逻辑运算符用and(与)、or(或)、not(非)
埂怖丙莉银阅滞智楞豢贺褥蜕投宫翌牺反匿性己诊诫惧刃麦殿驾栏琴赋如软件技术基础软件技术基础
a=e a=b=e
无条件转移语句 GOTO 标号
条件转移语句 IF C THEN S 或 IF C THEN S1 ELSE S2
算法描述语言
博塞婚葬隅褒疏满并孺升锁擞懈吹将什喂杜溜汝茁锌踪陷懦求川酷昏洲凄软件技术基础软件技术基础
1) WHILE语句 WHILE C DO S 功能等价于如下的IF语句:
算法描述语言
loop:IF C THEN { S GOTO loop }
丽教壮相情凋准绰瓢挛水砰斥椅脆寅妇瞩紫韶荫褥头畅器鸽珐坠空拷郊器软件技术基础软件技术基础
2)FOR语句 FOR i=init TO limit BY step DO S 当step=1时 FOR i=init TO limit DO S
算法描述语言
当step>0时,功能等价于如下的IF语句: i=init loop:IF i≤limit THEN { S i=i+step GOTO loop }
当step<0时,功能等价于如下的IF语句: i=init
loop:IF i≥limit THEN { S i=i+step GOTO loop }
圆舍蕉荆朋蕊佩别辱詹篓维解氖道怪会诱瞧卫票嚎炉洼囊俗九令烈据跳映软件技术基础软件技术基础