算法—程序的灵魂课件.ppt

2024/8/9课件1第第2 2章章 程序的灵魂程序的灵魂------算法算法2第第2章章 程序的灵魂程序的灵魂---算法算法2-1 算法的概念算法的概念（理解）（理解）2-2 简单算法举例简单算法举例（理解）（理解）2-3 算法的特性算法的特性（理解）（理解）2-4 怎样表示一个算法怎样表示一个算法(熟练掌握熟练掌握)2-5 结构化程序设计方法结构化程序设计方法（了解）（了解）3第第2章章 程序的灵魂程序的灵魂---算法算法l 本章要点本章要点n n算法的概念 n n算法的表示n n结构化程序设计方法 4一个程序应包括两个方面的内容:§对数据的描述：数据结构(data structure)§对操作的描述：算法(algorithm)著名计算机科学家沃思提出一个公式著名计算机科学家沃思提出一个公式: 数据结构数据结构 + 算法算法 = 程序程序 数据结构＋算法＋结构化程序设计方法＋语言工具数据结构＋算法＋结构化程序设计方法＋语言工具完整的程序设计应该是:2-1 算法算法52-1 算法算法§定义定义：算法是指为解决一个问题而采取的方法和步骤算法是指为解决一个问题而采取的方法和步骤。

§分类：数值运算算法和非数值运算算法分类：数值运算算法和非数值运算算法§算法有优劣算法有优劣 为为了了有有效效地地进进行行解解题题，，不不仅仅需需要要保保证证算算法法正正确确，，还还要要考考虑虑算算法法的的质质量量，，选选择择合合适适的的算算法法希希望望方方法法简简单，运算步骤少单，运算步骤少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 =len×wid；；Ø输出面积输出面积area的值；的值；8求求1×2×3×4×5=？？步骤步骤1 1：先求：先求1 1××2 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 1××2 2××…××10001000，则要写，则要写999999个步骤个步骤9 S1：使：使p=1 S2：使：使i=2 S3：使：使p×i，乘积仍放在变量，乘积仍放在变量p中，可表示为：中，可表示为：p×i=>p S4：使：使i的值加的值加1，即，即i+1 => i。

 S5：如果：如果i≤5，返回步骤，返回步骤S3；否则，算法结束否则，算法结束最后得到最后得到p的值就是的值就是5!的值可以设两个变量：一个变量代表被乘数，一个变量代表乘一个变量代表被乘数，一个变量代表乘数不另设变量存放乘积结果，而直接将每一步骤的乘数不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中设积放在被乘数变量中设p p为被乘数，为被乘数，i i为乘数用循环为乘数用循环算法来求结果算法来求结果, , 算法可改写：算法可改写： 10S1：：1 => pS2：：3 => iS3：：p×i => pS4：：i+2 => iS5：若：若i≤1001，返回，返回S3否则，结束否则，结束 如果题目改为：求如果题目改为：求1 1××3 3××5 5××……××10011001算法只需作算法只需作很少的改动：很少的改动：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判断一个数是否素数判断一个数是否素数分析：分析：本题要点是先搞清楚什么是素数。

本题要点是先搞清楚什么是素数思路：思路：Ø输入一个大于输入一个大于3的正整数的正整数NØ定义一个变量定义一个变量 I 从从 2~N-1 ，，I 每取一个值做：每取一个值做：§如果如果N能被能被I整除则中断循环，整除则中断循环，N不是素数；否则不是素数；否则 I继续取下一个值；继续取下一个值；Ø若当若当I取完所有值都不能整除取完所有值都不能整除N，，则则N是素数是素数一个正整数，若不能被除一个正整数，若不能被除1和它本身以外的任何和它本身以外的任何整数整除，则是素数整数整除，则是素数132.3 算法的特性算法的特性§有穷性有穷性有穷性有穷性 指一个算法经过有限步骤后停止（或在合理范围内）指一个算法经过有限步骤后停止（或在合理范围内）指一个算法经过有限步骤后停止（或在合理范围内）指一个算法经过有限步骤后停止（或在合理范围内）§确定性确定性确定性确定性 算法的每一步都应当是确定的，无歧义的算法的每一步都应当是确定的，无歧义的算法的每一步都应当是确定的，无歧义的算法的每一步都应当是确定的，无歧义的§有效性有效性有效性有效性 算法的每一步计算机都能有效执行算法的每一步计算机都能有效执行算法的每一步计算机都能有效执行算法的每一步计算机都能有效执行§有有有有0 0 0 0个或多个输入个或多个输入个或多个输入个或多个输入 一个算法可以没有输入，即执行时无需输入信息一个算法可以没有输入，即执行时无需输入信息一个算法可以没有输入，即执行时无需输入信息一个算法可以没有输入，即执行时无需输入信息§有有有有1 1 1 1个或多个输出个或多个输出个或多个输出个或多个输出 一个算法必须有输出，运算过程或运算结果一个算法必须有输出，运算过程或运算结果一个算法必须有输出，运算过程或运算结果一个算法必须有输出，运算过程或运算结果142.4 怎样表示一个算法怎样表示一个算法常用的算法描述方法：常用的算法描述方法：常用的算法描述方法：常用的算法描述方法：①①①①带序号的自然语言描述，易懂却不直观，不严格。

带序号的自然语言描述，易懂却不直观，不严格带序号的自然语言描述，易懂却不直观，不严格带序号的自然语言描述，易懂却不直观，不严格②②②②流程图：灵活、自由、形象、直观，可表示任何算法流程图：灵活、自由、形象、直观，可表示任何算法流程图：灵活、自由、形象、直观，可表示任何算法流程图：灵活、自由、形象、直观，可表示任何算法15一、结构化程序设计的三种基本结构一、结构化程序设计的三种基本结构 三种基本结构：三种基本结构：顺序、选择、循环顺序、选择、循环，用这三种，用这三种基本结构作为表示一种良好算法的基本单元基本结构作为表示一种良好算法的基本单元结构化程序设计方法结构化程序设计方法16二、相关术语二、相关术语 程序程序程序程序：使用语言给计算机的一组指令序列使用语言给计算机的一组指令序列 结构化程序结构化程序：用三种基本结构组成的程序就是结构化程序用三种基本结构组成的程序就是结构化程序 程序设计程序设计程序设计程序设计：为求解特定问题而编写的正确有效的程序为求解特定问题而编写的正确有效的程序 程序设计语言程序设计语言程序设计语言程序设计语言：编写程序所用的语言编写程序所用的语言。

结构化程序设计方法结构化程序设计方法171 1、顺序结构、顺序结构 例如：例如：a=3; b=4; c=a+b;操作的步骤按照书写的顺序执行操作的步骤按照书写的顺序执行AB结构化程序设计方法结构化程序设计方法三、三种基本结构三、三种基本结构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)先执行后判断先执行后判断PNAY结构化程序设计方法结构化程序设计方法三、三种基本结构三、三种基本结构21结构化程序设计方法结构化程序设计方法二、三种基本结构特点：二、三种基本结构特点：1.只有一个入口和一个出口；只有一个入口和一个出口；2.结构内每一部分都有机会执行到；结构内每一部分都有机会执行到；3.结构内不存在结构内不存在“死循环死循环”。

注：以上三种基本结构顺序组成的算法结构可以解决注：以上三种基本结构顺序组成的算法结构可以解决注：以上三种基本结构顺序组成的算法结构可以解决注：以上三种基本结构顺序组成的算法结构可以解决任何复杂的问题任何复杂的问题任何复杂的问题任何复杂的问题22常用的算法描述方法：常用的算法描述方法：常用的算法描述方法：常用的算法描述方法：③③③③N-SN-SN-SN-S图（盒图）：特点是完全去掉了带箭头的流程线，算图（盒图）：特点是完全去掉了带箭头的流程线，算图（盒图）：特点是完全去掉了带箭头的流程线，算图（盒图）：特点是完全去掉了带箭头的流程线，算法的所有处理步骤都写在一个大矩形框，表示简单，符合法的所有处理步骤都写在一个大矩形框，表示简单，符合法的所有处理步骤都写在一个大矩形框，表示简单，符合法的所有处理步骤都写在一个大矩形框，表示简单，符合结构化思想结构化思想结构化思想结构化思想AT P F A B当P1成立 A A直到直到P2成立成立 处理处理 判断判断 循环循环23N-S图：图：ABAB顺序结构顺序结构顺序结构顺序结构PABYNY P N A B选择结构选择结构选择结构选择结构24N-S图：图：当型循环当型循环当型循环当型循环直到型循环直到型循环直到型循环直到型循环当P1成立 AAP1Y A直到直到直到直到P2P2成立成立成立成立PYANN25常用的算法描述方法：常用的算法描述方法：常用的算法描述方法：常用的算法描述方法：④④④④伪代码：用介于自然语言与计算机语言之间的文字及伪代码：用介于自然语言与计算机语言之间的文字及伪代码：用介于自然语言与计算机语言之间的文字及伪代码：用介于自然语言与计算机语言之间的文字及符号来描述算法，特点是方便、易懂、便于向计算机语符号来描述算法，特点是方便、易懂、便于向计算机语符号来描述算法，特点是方便、易懂、便于向计算机语符号来描述算法，特点是方便、易懂、便于向计算机语言过渡。

言过渡26学习建议学习建议：：：：流程图和流程图和N-SN-S图一定要熟练掌握，伪代码表示法图一定要熟练掌握，伪代码表示法在学习完基本的流程控制语句后也经常使用在学习完基本的流程控制语句后也经常使用27例题：计算例题：计算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、判断、判断n≤100？？是，转是，转3；否则转；否则转66、、 输出输出 S的值的值 28例题：计算例题：计算s=∑n，，写出其算法写出其算法 100n=1伪代码描述：伪代码描述：N—S图描述：图描述：n≤100？s+n sn+1 n输出S的值0 s1 nBegin 1 s2 nwhile n ≤100{s+n s n+1 n}print send292.5 结构化程序设计方法结构化程序设计方法核心思想：自顶向下，逐步细化，模块化设计，结核心思想：自顶向下，逐步细化，模块化设计，结 构化编码。

构化编码强调强调程序设计的风格程序设计的风格和和程序结构的规范化程序结构的规范化优点：易编、易读、易懂、易维护优点：易编、易读、易懂、易维护 30本章小结本章小结§本章介绍算法及算法表示的基本知识本章介绍算法及算法表示的基本知识§重点：重点：分析问题，设计算法分析问题，设计算法§作业：作业：P36P36习题第习题第4 4、、8 8题题。