算法及算法的描述方法VIP

SchoolofComputerScience Engineering XidianUniversity China C程序设计 ProgramminginC 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China2 上次课程的内容提要 C语言是一种得到广泛应用的高级程序设计语言用高级程序语言编写的程序需要进行翻译才能被计算机执行 对于C语言程序 该翻译过程由C编译器完成明确本课程的学习目标 初步掌握程序设计基本知识和良好的程序设计风格用计算机解决问题的首要步骤是分析问题并设计算法算法描述了给定问题的解题步骤流程图是一种算法描述方法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China3 素性判别 素性判别就是给定一个正整数 判定其是否为素数 素数的定义 一个大于1的整数 如果它的正因数只有1和它本身 就叫做素数 否则就叫合数 如何判定给定正整数n是否为素数呢 根据定义 从2开始找n的因子 若能找到一个介于2和n 1之间的n的因子 说明n不是素数 否则 n是素数 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China4 素性判别 Y N K 2 K不能整除n K K 1 输出n是素数 输入n的值 开始 结束 Y N K等于n 输出n不是素数 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China5 求最大公约数 设有两个正整数m和n 如何求其最大公约数 有多种方法 例如求解速度最快的方法是辗转相除法 辗转相除法 欧几里得算法 给定两个正整数m和n 求它们的最大公约数 公因子 步骤1 求余数 以n除m并令r为所得余数 0 r n 步骤2 余数为0 若r 0 算法结束 n即为答案步骤3 互换 置m n n r 转向步骤1 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China6 求最大公约数流程图 Y N r m被n除的余数 r不等于0 n r 输出n的值 输入正整数m和n 开始 结束 m n 结构不好 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China7 这次课的主要内容 结构化方法的基本结构 顺序结构 选择结构 循环结构其他算法描述方法N S盒图方法伪代码方法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China8 三种基本结构 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China9 三种基本结构 1966年 Bohra和Jacopini提出了以下三种基本结构 作为构造算法的基本单元顺序结构选择结构循环结构顺序结构和选择结构的流程图如下图所示 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China10 三种基本结构 循环结构当型循环结构 while型循环 如图循环结构1所示直到型循环结构 Until型循环 如图循环结构2所示 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China11 基本结构小结 只有一个入口只有一个出口结构中的每一部分都存在一条从入口到出口的路径结构内不存在 死循环 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China12 计算1 2 100的流程图 A B C 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China13 判断闰年的流程图 k能被4整除 输入一个年份值k 开始 结束 输出k不是闰年 输出k是闰年 Y N k能被100整除 Y k能被400整除 Y N N 输出k是闰年 输出k不是闰年 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China14 判断闰年的流程图 k能被4整除 输入一个年份值k 开始 结束 输出k不是闰年 Y N k能被100整除 Y k能被400整除 Y N N 输出k是闰年 输出k是闰年 输出k不是闰年 A B C 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China15 判断闰年的流程图 k能被4整除 输入一个年份值k 开始 结束 输出k不是闰年 输出k是闰年 Y N k能被100整除 Y k能被400整除 Y N N 结构不好 A B 无法划分基本单元 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China16 求最大公约数流程图 结构不好 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China17 求最大公约数流程图 A B C D 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China18 求最大公约数流程图 Y N r不等于0 输出m的值 输入正整数m和n 开始 结束 r m被n除的余数m n n r A B C 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China19 流程图的优缺点 优点直观形象 比较清楚地表现了各个框图的逻辑关系缺点占用篇幅较多对流程线的使用没有限制 允许随意转向可能造成流程混乱 理解困难 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China20 其他算法描述方法 用N S盒图表示算法用伪代码描述算法用PAD图描述算法 略 用计算机语言描述算法 程序 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China21 用N S盒图描述算法 N S盒图的基本符号 流程图符号 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China22 用N S盒图描述算法 N S盒图的基本符号 流程图符号 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China23 求最大公约数流程图 输入正整数m和n r m被n除的余数 输出n的值 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China24 N S盒图表示法小结 与流程图相比 N S盒图保留了流程图方式直观 形象和易于理解的优点去掉了流程线 形式上更紧凑避免了流程的随意跳转 确保了结构化技术 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China25 用伪代码表示算法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China26 规定一些基本符号 运算符号简单算术运算符号 mod 整除取余 关系运算符号 逻辑运算符号 and or not括号 用于表示某种对象名字的符号以英文字母开头的字母 数字符号串例如 sum price i m k n a1 a2其他 处理 语句 赋值 例如i 1如果p成立则A否则B ifpthenAelseB当p成立时 则A whilepdoAdoAwhilep输入和输出 打印 input print基本块起 止符号 算法开始和结束 BEGIN END 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China27 伪代码算法中基本符号的使用 运算符号 a 5 b 3 简单算术运算符号 mod 整除取余 例如 a b a b a b a b amodb关系运算符号 成立 true Yes Y 不成立 false No N 括号 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China28 伪代码算法中基本符号的使用 逻辑运算逻辑运算符号 and or not并且 and或者 or非 不是 not 因此 给定一个年号k 判断是否为闰年的条件是 kmod4 0 and kmod100 0 or kmod100 0 and kmod400 0 例如 判断闰年的条件 给定一个年号k 能被4整除 但是不能被100整除的年份是闰年 kmod4 0 and kmod100 0 能同时被100和400整除的年份是闰年 kmod100 0 and kmod400 0 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China29 伪代码算法中基本符号的使用 选择结构如果p成立则A否则B ifpthenAelseB 例如 ifa bthenmax aelsemax b 例如 if kmod4 0 and kmod100 0 or kmod100 0 and kmod400 0 thenprint kisaleapyear elseprint kisnotaleapyear 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China30 伪代码算法中基本符号的使用 循环结构当p成立时 则A whilepdoA 例如 whilea bdoa a b whileI 100do S S I I I 1 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China31 伪代码描述计算1 2 100的算法 算法1 计算1 2 100BEGINS 0 I 1 while I 100 do S S I I I 1 printS END 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China32 伪代码算法 求最大公约数 算法2 辗转相除法求最大公约数BEGINinputm n 输入正整数m和n r mmodn 求m被n除的余数 while r 0 do m n n r r mmodn printn 输出最大公约数 END 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China33 伪代码算法 求最大公约数 算法3 辗转相除法求最大公约数BEGINinputm n 输入正整数m和n do r mmodn m n n r whiler 0 printm 输出最大公约数 END Y N r不等于0 输出m的值 输入正整数m和n 开始 结束 r m被n除的余数m n n r 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China34 伪代码算法 素性判别 Y N K 2 K不能整除n K K 1 输出n是素数 输入n的值 开始 结束 Y N K等于n 算法2 素性判别BEGINinputn 输入正整数n k 2 while nmodk 0 do k k 1 if k n thenprint n是素数 elseprint n不是素数 END