计算机软件基础第1章.ppt

第1章 算法 1.1 算法的基本概念 1.1.1 算法的基本特征 1.1.2 算法的基本要素 1.1 算法的基本概念 1.1.1 算法的基本特征 算法是指解题方案的准确而完整的描述。1.能行性(effectiveness) A＝1012，B＝1，C＝－1012 A＋B＋C＝1012＋1＋(－1012)＝0 A＋C＋B＝1012＋(－1012)＋1＝12.确定性(definiteness)3.有穷性(finiteness)4.拥有足够的情报 算法是一组严谨地定义运算顺序的规则， 并且每一个规则都是有效的，且是明确的， 此顺序将在有限的次数下终止。 1.1.2 算法的基本要素 (1) 算法中对数据的运算和操作 ①算术运算 ②逻辑运算 ③关系运算 ④数据传输 (2) 算法的控制结构 1.2 算法描述语言 1.符号与表达式 loop：i＝i＋1 “设x是A中的最大项”（其中A是一个数组） “将x插入到L之中”（其中L是某个表） 关系运算符用＝、≠、＜、＞、≤、≥ 逻辑运算符用and(与)、or(或)、not(非) 2.赋值语句 a＝e a～b a＝b＝e 3.控制转移语句无条件转移语句 GOTO 标号 条件转移语句 IF C THEN S 或 IF C THEN S1 ELSE S2 4.循环语句 WHILE语句 WHILE C DO S 功能等价于如下的IF语句： loop：IF C THEN { S GOTO loop } FOR语句 FOR i＝init TO limit BY step DO S 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 } 5.其他语句 EXIT, RETURN READ（或INPUT） WRITE（或PRINT，或OUTPUT） 1.3 算法设计基本方法 1. 列举法 根据提出的问题，列举所有可能的情况，并用问题 中给定的条件检验哪些是需要的，哪些是不需要的。 因此，列举法常用于解决“是否存在”或“有多少种可 能”等类型的问题，例如求解不定方程的问题。 例 设每只母鸡值3元，每只公鸡值2元，两只小鸡值1 元。现要用100元钱买100只鸡，设计买鸡方案。 假设买母鸡I只，公鸡J只，小鸡K只。 FOR I＝0 TO 100 DO FOR J＝0 TO 100 DO FOR K＝0 TO 100 DO { M＝I＋J＋K N＝3I＋2J＋0.5K IF ((M＝100)and(N＝100)) THEN OUTPUT I，J，K } RETURN 总循环次数为1013 FOR I＝0 TO 33 DO FOR J＝0 TO 50－1.5I DO { K＝100－I－J IF (3I＋2J＋0.5K＝100) THEN OUTPUT I，J，K } RETURN 总循环次数为 #include stdio.h main() { int i，j，k；