第一章算法 进行程序设计,需要具备两方面知识:(1)掌握 一门计算机语言;(2)掌握解题的方法和步骤。 §1算法的概念及特征 §2算法的表示 2021/2/24
1 2021/2/24 第一章 算法 进行程序设计，需要具备两方面知识：⑴掌握 一门计算机语言；⑵掌握解题的方法和步骤。 §1 算法的概念及特征 §2 算法的表示
§1算法的概念及特征(P15) 2 、算法的基本概念 不论是计算机还是人,要完成一项工作都是按 照一定的工作步骤进行的。 例如,去商业大厦买东西,可以按照下面步骤 进行: ①到西校门;②乘106路公交车;③到“商业大 厦”站点下车;④进大厦买东西。 又如,到食堂吃饭,要按照以下步骤进行 ①带上饭碗走进食堂排队;②买饭付钱;到 餐桌吃饭。 2021/2/24
2 2021/2/24 §1 算法的概念及特征(p1-5) 不论是计算机还是人，要完成一项工作都是按 照一定的工作步骤进行的。 例如，去商业大厦买东西，可以按照下面步骤 进行： ①到西校门；②乘106路公交车；③到“商业大 厦”站点下车；④进大厦买东西。 又如，到食堂吃饭，要按照以下步骤进行： ①带上饭碗走进食堂排队；②买饭付钱；③到 餐桌吃饭。 一、算法的基本概念
3 上述两个例子说明,无论完成什么任务,都有 一定的方法和具体步骤 算法( Algorithm)是为解决某个问题而采取的方 法和步骤。 对于同一个问题可以采用不同的方法和步骤即 可以有不同的算法),但应选择最佳的方案。 100 【例1】计算m=∑k k: 方法一:先进行1+2、再加3、再加4、∴、加 到100为止。(做99次加法) 2021/2/24 §1算法的概念及特征
3 2021/2/24 上述两个例子说明，无论完成什么任务，都有 一定的方法和具体步骤。 算法(Algorithm)是为解决某个问题而采取的方 法和步骤。 对于同一个问题可以采用不同的方法和步骤(即 可以有不同的算法)，但应选择最佳的方案。 = = 100 k 1 【例1】计算 sum k §1 算法的概念及特征 方法一：先进行1＋2、再加3、再加4、…、 加 到100为止。（做99次加法）
方法二:100+(1+99)+(2+98)+…+( 49+51 +50=100+49×100+50=5050。(1次乘法,2次 加法) 些例说明:解决问题的算法有优劣之分。算法 的优劣是程序设计中一个极为重要的问题,不仅要 保证算法正确,而且要考虑算法的质量(方法简单 运算步骤少)。 二、计算机算法的分类 2021/2/24 §1算法的概念及特征
4 2021/2/24 方法二：100＋(1＋99)＋(2＋98)＋…＋(49＋51) ＋50=100＋49×100＋50=5050。（1次乘法，2次 加法） …… 此例说明：解决问题的算法有优劣之分。算法 的优劣是程序设计中一个极为重要的问题，不仅要 保证算法正确，而且要考虑算法的质量（方法简单、 运算步骤少）。 §1 算法的概念及特征 二、计算机算法的分类
5 分为数值运算算法和非数值运算算法两大类。 数值运算算法:求问题数值解所用的算法。例 如求方程组的解、求函数的定积分等所用的算法都 是数值运算算法。 非数值运算算法:求问题非数值解所用的算法, 它涉及的面比数值运算算法更广。例如在网络搜索 引擎、图书检索、人事管理、行车调度等领中的 算法都是非数值运算算法 2021/2/24 §1算法的概念及特征
5 2021/2/24 分为数值运算算法和非数值运算算法两大类。 数值运算算法：求问题数值解所用的算法。例 如求方程组的解、求函数的定积分等所用的算法都 是数值运算算法。 非数值运算算法：求问题非数值解所用的算法， 它涉及的面比数值运算算法更广。例如在网络搜索 引擎、图书检索、人事管理、行车调度等领域中的 算法都是非数值运算算法。 §1 算法的概念及特征
三、简单算法举例 6 【例2】计算5=1×2×3×4×5 约定:用s1、s2、…、sn表示算法的第1、第2、… 第n步。 实现思想:设A、B两个变量,其中A代表被乘数,B代 表乘数。每一步的乘积结果存放在A中。另外,用循环表 示每一步的乘积运算。 具体算法如下: s1:使A=1(初值) s2:使B=2(初值) s3:AxB→A(A与B的积存放于A中) s4:B+1→B(B的值增1) s5:如果B≤5,返回重新执行s3、s4、s5;否则, 算法结束,A的值为5!。 2021/2/24 §1算法的概念及特征
6 2021/2/24 【例2】计算5!=1×2×3×4×5 约定：用s1、s2、…、sn表示算法的第1、第2、…、 第n步。 实现思想：设A、B两个变量，其中A代表被乘数，B代 表乘数。每一步的乘积结果存放在A中。另外，用循环表 示每一步的乘积运算。 具体算法如下： s1：使A = 1（初值） s2：使B = 2（初值） s3：A×BA（A与B的积存放于A中） s4：B＋1B（B的值增1） s5：如果B≤5，返回重新执行s3、s4、s5；否则， 算法结束，A的值为5！。 §1 算法的概念及特征 三、简单算法举例
7 A 22>B A×BxA B+1=B 否 B>5? 算法结束 计算5的算法示意图 2021/2/24 §1算法的概念及特征
7 2021/2/24 1 A 2 B A×B A B+1 B B﹥5? 算法结束 否 是 计算5!的算法示意图 §1 算法的概念及特征
8 【例3】计算N!(N为任意正整数)。 s1:输入N s2:使A=1(初值) s3:使B=2(初值) s4:A×B→A(A与B的积存放于A中) s5:B+1→B(B的值增1) s6:如果B≤N,返回重新执行s4、s5、s6;否 则,算法结束,A值为N!。 2021/2/24 §1算法的概念及特征
8 2021/2/24 【例3】计算N!（N为任意正整数）。 s1：输入N s2：使A = 1（初值） s3：使B = 2（初值） s4：A×BA（A与B的积存放于A中） s5：B＋1B（B的值增1） s6：如果B≤N，返回重新执行s4、s5、s6；否 则，算法结束，A值为N!。 §1 算法的概念及特征
【例4】将2000~2500年中的闺年打印出来 9 闰年的条件是:()能被4整除,但又不能被100整除的 年份是闰年;(2)能被100整除,又能被400整除的年份是 闰年。 设年份为Y 否 Y被4整除? 否 Y被100整除? 是 L非年 闫年 是 Y被400整除? 闰年 非闫年 2021/2/24 §1算法的概念及特征
9 2021/2/24 是 否 是 否 【例4】将2000～2500年中的闰年打印出来。 闰年的条件是：⑴能被4整除，但又不能被100整除的 年份是闰年；⑵能被100整除，又能被400整除的年份是 闰年。 设年份为Y： 否 Y被4整除？ 是 Y被100整除？ 闰年 非闰年 Y被400整除？ 闰年 非闰年 §1 算法的概念及特征
10 具体算法如下: s1:2000→Y s2:着Y不能被4整除,则打印Y不是闫年”,然后转 到S5。 s3:若Y能被4整除,但不能被100整除,则打印γ"是 闰年”,然后转到s5。 s4:若Y能被100整除,又能被400整除,则打印Y“是 闰年”;否则打印“不是闫年 s5:Y+1→Y s6:若Y≤2500时,转S2继续执行;否则算法结束。 2021/2/24 §1算法的概念及特征
10 2021/2/24 具体算法如下： S1：2000Y S2：若Y不能被4整除，则打印Y“不是闰年”，然后转 到S5。 S3：若Y能被4整除，但不能被100整除，则打印Y“是 闰年”，然后转到S5。 S4：若Y能被100整除，又能被400整除，则打印Y“是 闰年”；否则打印“不是闰年”。 S5：Y+1Y S6：若Y≤2500时，转S2继续执行；否则算法结束。 §1 算法的概念及特征