算法—程序的灵魂

1、11/14/2021课件1第第2 2章章 程序的灵魂程序的灵魂-算法算法2第第2章章 程序的灵魂程序的灵魂-算法算法2-1 算法的概念算法的概念（理解）（理解）2-2 简单算法举例简单算法举例（理解）（理解）2-3 算法的特性算法的特性（理解）（理解）2-4 怎样表示一个算法怎样表示一个算法(熟练掌握熟练掌握)2-5 结构化程序设计方法结构化程序设计方法（了解）（了解）3第第2章章 程序的灵魂程序的灵魂-算法算法l 本章要点本章要点4一个程序应包括两个方面的内容: 对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm)著名计算机科学家沃思提出一个公式著

2、名计算机科学家沃思提出一个公式: 数据结构数据结构 + 算法算法 = 程序程序数据结构算法结构化程序设计方法语言工具数据结构算法结构化程序设计方法语言工具完整的程序设计应该是:2-1 算法算法52-1 算法算法 定义定义：算法是指为解决一个问题而采取的方法和步骤。：算法是指为解决一个问题而采取的方法和步骤。 分类：数值运算算法和非数值运算算法分类：数值运算算法和非数值运算算法 算法有优劣算法有优劣 为了有效地进行解题，不仅需要保证算法正确，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。单，运

3、算步骤少。62-2 简单算法举例简单算法举例 例例1-1 计算任意长方形的面积计算任意长方形的面积 例例1-2 计算计算 1x2x3x4x5=？ 例例1-3 计算计算1-1/2+1/3-.+1/99-1/100=？ 例例1-4 判断一个数是否素数判断一个数是否素数算法描述算法描述7计算任意长方形的面积计算任意长方形的面积 问题分析：问题分析：输入长和宽输入长和宽计算面积计算面积=长长x宽宽输出面积输出面积 数据存放：数据存放：长长-len，宽，宽-wid，面积，面积-area 设计算法：设计算法：输入输入len和和wid的值；的值；计算计算area =lenwid；输出面积输出面积area的值

4、；的值；8求求12345=？步骤步骤1 1：先求：先求1 12 2，得到结果，得到结果2 2步骤步骤2 2：将步骤：将步骤1 1得到的乘积得到的乘积2 2再乘以再乘以3 3，得到结果，得到结果6 6步骤步骤3 3：将：将6 6再乘以再乘以4 4，得，得2424步骤步骤4 4：将：将2424再乘以再乘以5 5，得，得120120如果要求如果要求1 12 210001000，则要写，则要写999999个步骤个步骤9 s1：使：使p=1 s2：使：使i=2 s3：使：使pi，乘积仍放在变量，乘积仍放在变量p中，可表示为：中，可表示为：pi=p s4：使：使i的值加的值加1，即，即i+1 = i。 s

5、5：如果：如果i5，返回步骤，返回步骤s3；否则，算法结束。；否则，算法结束。最后得到最后得到p的值就是的值就是5!的值。的值。可以设两个变量：一个变量代表被乘数，一个变量代表乘一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设积放在被乘数变量中。设p p为被乘数，为被乘数，i i为乘数。用循环为乘数。用循环算法来求结果算法来求结果, , 算法可改写：算法可改写： 10s1：1 = ps2：3 = is3：pi = ps4：i+2 = is5：若：若i1001，返回，返回s3。否则，结束。否则

6、，结束。 如果题目改为：求如果题目改为：求1 13 35 510011001算法只需作算法只需作很少的改动：很少的改动：111-1/2+1/3-.+1/99-1/100=？ 提示：提示：首先考虑实现首先考虑实现1+2+3+4+100其次考虑实现其次考虑实现1/1+1/2+1/3+1/4+.+1/100最后考虑实现最后考虑实现1/1-1/2+1/3-1/4+.+1/100 思路：思路：s1：sum=0,i=1s2：sum=sum+ is3： i=i+1s4：如果：如果i=100则转则转 s2 ，否则转，否则转 s5s5：打印：打印sum的值的值1/ i,p=1p*1/i,p=-p;12判断一个数

7、是否素数判断一个数是否素数分析：分析：本题要点是先搞清楚什么是素数。本题要点是先搞清楚什么是素数。思路：思路：输入一个大于输入一个大于3的正整数的正整数n定义一个变量定义一个变量 i 从从 2n-1 ，i 每取一个值做：每取一个值做：如果如果n能被能被i整除则中断循环，整除则中断循环，n不是素数；否则不是素数；否则 i继续取下一个值；继续取下一个值；若当若当i取完所有值都不能整除取完所有值都不能整除n，则，则n是素数是素数一个正整数，若不能被除一个正整数，若不能被除1和它本身以外的任何和它本身以外的任何整数整除，则是素数。整数整除，则是素数。132.3 算法的特性算法的特性142.4 怎样表示

8、一个算法怎样表示一个算法。15 结构化程序设计方法结构化程序设计方法16 ：使用语言给计算机的一组指令序列。：使用语言给计算机的一组指令序列。 结构化程序结构化程序：用三种基本结构组成的程序就是结构化程序。：用三种基本结构组成的程序就是结构化程序。 ：为求解特定问题而编写的正确有效的程序。：为求解特定问题而编写的正确有效的程序。 ：编写程序所用的语言。：编写程序所用的语言。结构化程序设计方法结构化程序设计方法171 1、顺序结构、顺序结构 例如：例如：a=3; b=4; c=a+b;操作的步骤按照书写的顺序执行操作的步骤按照书写的顺序执行ab结构化程序设计方法结构化程序设计方法三、三种基本结构

9、三、三种基本结构182 2、选择结构、选择结构 例如：例如：if(x!=0) y=sin(x)/x; else y=1;pabyn结构化程序设计方法结构化程序设计方法三、三种基本结构三、三种基本结构193、循环结构循环结构: :根据条件根据条件p p决定是否重复执行循环体中的操作决定是否重复执行循环体中的操作 例如：例如：sum=0； i=1; while (i=100) sum+=i; i+; 先判断后执行先判断后执行napy结构化程序设计方法结构化程序设计方法三、三种基本结构三、三种基本结构20例如：例如：sum=0； i=1; do sum+=i; i+; while (i=100)pn

10、ay结构化程序设计方法结构化程序设计方法三、三种基本结构三、三种基本结构21结构化程序设计方法结构化程序设计方法22at p f a b当p1成立 a a直到直到p2成立成立 处理处理 判断判断 循环循环23n-s图：图：ababpabyny p n a b24n-s图：图：当p1成立 aap1y apyann252627例题：计算例题：计算s=n，写出其算法写出其算法 s=0,n=1n=100输出输出sn开始开始结束结束s=s+nn=n+1y100n=1流程图描述：流程图描述：自然语言描述：自然语言描述：1、0 s单元单元 2、1 n单元单元3、s+n s4、n+1 n5、判断、判断n100？是，转是，转3；否则转；否则转66、 输出输出 s的值的值 28例题：计算例题：计算s=n，写出其算法写出其算法 100n=1伪代码描述：伪代码描述：ns图描述：图描述：n100？s+n sn+1 n输出s的值0 s1 nbegin 1 s2 nwhile n 100s+n s n+1 nprint send292.5 结构化程序设计方法结构化程序设计方法核心思想：自顶向下，逐步细化，模块化设计，结核心思想：自顶向下，逐步细化，模块化设计，结 构化编码。构