算法与程序设计算法与程序设计 信息技术（选修信息技术（选修1 1）1.2 算法和算法的描述算法和算法的描述导入新课导入新课 我们上节课通过“韩信点兵”的例子探讨了计算机解决问题的步骤，你们还记得计算机解决问题的步骤吗？计算机解决问题的步骤分析问题设计算法编写程序调试程序得出答案具体问题导入新课导入新课欧几里德在几何原本中阐述了求两个整数的最大公约数的过程，这就是所谓的欧几里德算法辗转相除法。 例如：设给定的两个正整数为m和n，求它们的最大公约数的步骤为：（1）以m除以n,令所得的余数为r。（2）若r=0，则输出结果n,算法结束；否则，继续步骤（3）。（3）令m=n，n=r ,并返回步骤（1）继续进行。 在公元前3000多年就有了“算法”这个名词，那么什么是算法？怎样对算法进行描述呢？这就是我们今天学习的内容。一、算法一、算法1 1、算法的概念、算法的概念 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，算法就是求解某一问题的方法，求解某一问题的方法，是能被机械地执行的动作或指令的是能被机械地执行的动作或指令的有穷集合有穷集合。算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。一、算法一、算法2 2、算法的特征、算法的特征（1）输入。一个算法有零个或多个输入。零个输入的例子：Private sub command1_click()a=3，b=4Print a*bEnd sub（2）确定性。算法的每一个步骤必须要确切地定义。例1：这个人好说话。例2：三角形的内角和是180。一、算法一、算法2 2、算法的特征、算法的特征（3）有穷性。一个算法在执行有穷步之后必须结束。反例：S1: sum=0S2: i=1S3: sum=sum+iS4: i=i+1S5: 若sum=0 ，返回S3;否则，算法结束。（4）输出。算法有一个或多个输出。（5）可行性。二、算法的描述二、算法的描述表示算法的语言有哪几种？表示算法的语言有自然语言、流程图、伪代码。1 1、用自然语言描述算法、用自然语言描述算法例:求200-500能被5整除的所有正整数。（1）分析问题。 设能被5整除的数为I,令I=200,201,202，500，如果I是能被5整除的数，则输出I；否则，检查下一个I，直到I=500为止。（2）设计算法令I=200;如果I能被5整除，则输出I;I=I+1;如果I=500，则返回第；结束。二、算法的描述二、算法的描述1 1、用自然语言描述算法、用自然语言描述算法用自然语言描述算法优点：描述的算法通俗易懂。缺点：自然语言容易产生歧义，可能导致算法执行的不确定性。自然语言描述的算法太长。当算法中循环和分支较多时，很难清晰地表示出来。自然语言表示的算法不便翻译成计算机程序设计语言。二、算法的描述二、算法的描述2 2、用流程图描述算法、用流程图描述算法图形名称功能起始/结束 表示算法的开始或结束输入/输出表示算法中变量的输入或输出处理表示算法中变量的计算或赋值判定表示算法中的判断流程线表示算法中的流向二、算法的描述二、算法的描述2 2、用流程图描述算法、用流程图描述算法例:求200-500能被5整除的所有正整数。开始I=200I能被5整除输出I的值I=I+1I=500结束是否否是二、算法的描述二、算法的描述2 2、用流程图描述算法、用流程图描述算法用流程图描述算法优点：形象直观，不依赖计算机和计算机程序设计语言。缺点：画起来费事，难以修改，不易编辑。二、算法的描述二、算法的描述3 3、用伪代码描述算法、用伪代码描述算法Input m, n r= m mod nDo while r0 m=n n=r r=m mod nLoopPrint n 例：用辗转相除法求两个数的最大公约数的伪代码。 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。二、算法的描述二、算法的描述3 3、用伪代码描述算法、用伪代码描述算法用伪代码描述算法优点：书写方便，格式紧凑，易于理解，便于向计算机 程序设计语言过渡。缺点：由于语言的种类繁多，伪代码的语句不容易规范。三、算法在实际问题中的应用三、算法在实际问题中的应用课堂练习：课堂练习：分别用自然语言和流程图描述求解1、所有水仙花数的问题。水仙花数是指一个三位数，它的各位数的立方和正好等于该数本身。如153=13+53+33。2、设计算法：找出乘积为840的两个相邻偶数 四、算法在解决问题中的地位和作用四、算法在解决问题中的地位和作用探究：运行这两个程序，比较它们的效率，把你观察到的现象填在表1-6中。同学甲的算法：同学乙的算法：Private Sub Command1_Click()m = 9147485n = 5147480r = m Mod nDo While r 0m = nn = rr = m Mod nLoopPrint 最大公约数=; nEnd SubPrivate Sub Command1_Click()m = 9147485n = 5147480i = mDo While m Mod i 0 Or n Mod i 0i = i - 1LoopPrint 最大公约数=; iEnd Sub四、算法在解决问题中的地位和作用四、算法在解决问题中的地位和作用表1-6中 两个程序的效率比较指标用辗转相除法设计的程序用穷举法设计的程序运行结果最大公约数=最大公约数=运行时间 较长 较短较长 较短通用性较好 较差较好 较差 由此看来，算法是程序设计的核心，是程序设计的灵魂。算法的好坏，直接影响着程序的通用性和有效性，影响着问题解决的效率。