高中信息技术算法与程序设计.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.1 计算机解决问题的一般过程,人工解题的步骤,正确理解题意,寻找或设计正确的解题方法,使用计算工具进行计算并得到结果,验证计算结果,计算机解题的步骤,正确理解题意,寻找或设计正确的解题方法,设计正确的算法,使用合适的程序设计语言将算法表达为计算机程序,由计算机按照设计好的程序高速、自动地计算结果,无论使用人工解题还是使用计算机解题，都必须在正确理解题意地基础上寻找或设计正确的解题方法。,使用人工解题最后需验算，而使用计算机解题则不需要。,1.1.1 从问题到算法,问题,：在一次班级联欢会上，同学们玩了一个猜商品价格的游戏。,A,同学出示一件商品，价格在,11000,元之间，价格为整数，要求,B,同学猜价格。,B,同学每猜一个价格，,A,同学需要回答猜对了，或猜大了，还是猜小了。要求,B,同学尽可能快地猜出商品的价格。,【,方法,1】,：,B,同学从,1,、,2,、,3,、,依次猜测商品的价格，直到猜对为止。,【,方法,2】,：,B,同学先从,11000,的,中间数,500,开始猜，根据,A,同学的回答决定下一个要猜测的价格，如果,A,回答“猜大了”，则在,1499,之间取,中间数,进行猜测；,否则,，取,5011000,的,中间数,进行猜测，如此反复，直到猜对为止。,1.1.2 计算机与程序,看似无所不能的计算机，迄今为止也,只能按照设计好的程序,，一步步地进行运算处理。事实上，要使用计算机来解决问题，人们必须事先设计好解决问题的计算机程序。,没有计算机程序，就不可能用计算机来解决问题,。,计算机程序,就是指示计算机如何去解决问题或完成任务的,一组可执行的指令,。,程序设计,就是寻求解决问题的方法，并将其实现步骤编写成计算机可以执行的程序的过程。,计算机是一种按照设计好的程序，快速、自动地进行计算的电子设备。计算机开始计算之前，必须把解决某个问题地程序存储在计算机内存中。,程序由,指令部分,和,数据部分,组成。,指令部分,由一系列指令构成，每条指令都是要求计算机执行地一个动作。由适当的指令构成一个序列，描述了解决这个问题的计算过程。,数据部分,用来存储计算过程中所需的原始数据、计算的中间结果和最终结果。,指令,就是用来规定计算机操作的命令。计算机的所有指令组成了计算机的,指令集,。一般而言，计算机的指令越丰富，功能也就越强大。,计算机指令的种类,输入,通过输入设备，程序接收外界输入的数据，将数据存储到指定的,变量,中；,输出,把文字、变量中存储的数据或计算产生的结果，通过输出设备显示或打印出来；,数学运算,进行、,、,、平方、开平方、求余数等数学运算。通常，计算所需的的数据从变量中获得，计算的结果可以存储到指定的,变量,中。,逻辑判断,可以对指定的两个数据进行大小或相等性（、）比较，比较的结果为逻辑值（真或假），也使用逻辑运算（如与、或、非），把若干个较简单的判断连接起来，成为一个复杂的判断。,控制转移指令,用来改变程序中指令的执行顺序。,现在由计算机来扮演,A,同学的角色，计算机应该按照下述过程进行工作：,计算机得到,B,同学所猜的价格,计算机对得到价格与实际价格进行比较，告诉,B,同学比较的结果（,猜小了,、,猜大了,、,猜对了,）,计算机根据比较的结果决定是否继续猜测。,使用计算机解决问题一般要经历以下三个阶段：,分析问题并确定要计算机做什么,寻找解决问题的途径和方法,开始,用计算机进行处理,分析问题,设计算法,编写程序,运行程序,问题解决,猜大了或是猜小了，则继续猜测,猜对了则停止猜测，游戏结束,设计程序时需考虑的问题,数据的存储：,计算所需的原始数据、计算产生的中间结果、计算的最终结果需要存储在,变量,中。,计算的过程：,首先确定解决问题的方法；,然后必须将该方法,步骤化,，即用计算机可以执行的,步骤,（,指令,），来描述问题的计算过程，这意味着程序的计算过程不仅必须指出动作，而且必须指出动作的次序。,地址,指令内容,1,显示“输入价格：”,2,输入价格到变量,T,3,比较输入价格,T,和商品价格,S,，如果,TS,，转到,9,5,显示“猜对了！”,6,结束,7,显示“猜小了！”,8,转到,1,9,显示“猜大了！”,10,转到,1,11,商品价格变量,S,12,输入价格变量,T,输出指令,输入指令,逻辑判断指令,控制转移指令,变量的概念与用途,程序中的变量是计算过程中要用到的数据的存储单元；,通过输入指令的执行，程序将外界输入的数据存储到指定的变量中，程序计算的结果也可以存储到指定的变量中；,一旦将数据存储到某个变量中，只要我们不再把新的数据存储到其中，那么在程序运行过程中，该变量将永久保存着原来的数据；,在计算过程中如果要使用到该变量中的数据，我们可以从该变量中读取出其中的数据，,这种读取是不会改变变量中存储的内容的,。,指令区,数据区,地址,指令内容,1,显示“输入价格：”,2,输入价格到变量,T,3,比较输入价格,T,和商品价格,S,，如果,TS,，转到,9,5,显示“猜对了！”,6,结束,7,显示“猜小了！”,8,转到,1,9,显示“猜大了！”,10,转到,1,11,商品价格变量,S,12,输入价格变量,T,图中的每行代表了内存中的一个存储单元，,每个存储单元可以存放一条指令或一个数据,。每个存储单元都有唯一的,编号,，称为,地址,。,指令是,依次逐条执行,的，如果遇到转移指令，会按指令要求选择下一条要执行的指令。,遇到,结束指令,，整个程序,终止运行,。,输入价格：,500,地址,指令内容,1,显示“输入价格：”,2,输入价格到变量,T,3,比较输入价格,T,和商品价格,S,，如果,TS,，转到,9,5,显示“猜对了！”,6,结束,7,显示“猜小了！”,8,转到,1,9,显示“猜大了！”,10,转到,1,11,商品价格变量,S,12,输入价格变量,T,375,250,500,250,375,猜大了！,输入价格：,猜小了！,输入价格：,猜对了！,375,输入价格：,地址,指令内容,1,显示“输入价格：”,2,输入价格到变量,T,3,比较输入价格,T,和商品价格,S,，如果,TS,，转到,9,5,显示“猜对了！”,6,结束,7,显示“猜小了！”,8,转到,1,9,显示“猜大了！”,10,转到,1,11,商品价格变量,S,12,输入价格变量,T,375,375,猜小了！,输入价格：,猜小了！,输入价格：,猜对了！,375,.,1.3 算法的概念,算法,是在,有限步骤,内求解某一个问题所使用的,具有精确定义的,一系列,操作规则,。每条规则都必须是,确定的,、,能行的,、,不能有二义性,的。,算法要有一个清晰的,起始步骤,，且每一个步骤都,只能有一个确定的后继步骤,，从而组成一个有限步骤序列。步骤终止时也给出了问题的解答。,解决问题的过程,就是,实现算法的过程,。,算法,是程序设计的“,灵魂,”，,算法,+,数据结构,=,程序,。算法,独立于任何具体程序设计语言,，一个算法可以用多种程序设计语言实现。,1、算法的概念,2、算法的特点,（,1,）有穷性,一个算法必须保证它的执行步骤是有限的，即它是能够终止的，操作步骤不能无限。算法可以有重复执行的步骤，只要这些步骤的执行能够终止。,广义地说，“有穷性”是指操作步骤的数目或完成操作的时间在合理的范围内，如果一个算法虽然在操作步骤的数目是有限的，但它所花费的时间超过了合理的限度，这种算法并不是有效的算法。,（,3,）可行性,算法中的每一个步骤都要是实际能做的，而且必须在有限的时间内可以完成。例如：,步骤“输出：,L,d”,在,d,0,的情况下就不可以做。,（,4,）有,0,个或多个输入,所谓输入就是指算法在执行时要从外界获得数据，其目的是为算法建立某些初始状态；如果建立初始状态所需的信息已经包含算法中，那就不需要输入了。,（,5,）有一个或多个输出,算法的目的是用来求解问题，问题的结果应以一定的方式输出，以便用户知道。在数学中的”无解“对于算法来说也是一个输出，没有输出的算法是毫无意义的。,（,2,）确定性,算法的每个步骤必须有确切的含义，而不应当是含糊的、模棱两可的。,例如：步骤“输出：,L,正整数”是无法执行的，因为没有指定,L,除以哪一个正整数，这个步骤是不确定的。,问题：步骤“输入一个正整数”是否是确定的？,1.3 算法的表示,我们可以采用多种方法来描述一个算法，,流程图,是一种比较直观易用的、用图形来描述算法的方法。,用流程图来描述算法要遵循一定的标准，这套标准中最常用的符号有：,处理框,输入、输出框,判断框,流程线,开始、结束符,在一般情况下，输入、输出框可以用处理框代替。,开始,结束,开始,结束,开始,T S,结束,显示：“输入价格：”,输入价格到变量,T,T S,显示：“猜小了！”,显示：“猜大了！”,显示：“猜对了！”,地址,指令内容,1,显示“输入价格：”,2,输入价格到变量,T,3,比较输入价格,T,和商品价格,S,，如果,TS,，转到,9,5,显示“猜对了！”,6,结束,7,显示“猜小了！”,8,转到,1,9,显示“猜大了！”,10,转到,1,11,商品价格变量,S,12,输入价格变量,T,判断框,表示条件判断,：,取出变量,T,、,S,中的数据，若,TS,是否成立,),。,想一想,问题,1,：键盘输入两个数，输出两个数的和与积,?,（,1,）需要输入哪些数据？,（,2,）需要计算机输出什么信息？,（,3,）如何根据输入数据得到要输出的信息,？,需要输入两个不同的数,需要计算机输出两数的,和,与,积,分别存入变量,a,、,b,中,两数之和存入变量,sum,中,计算,a+b,，,将结果存放在变量,sum,中；,计算,ab,，,将结果存放在变量,s,中,。,最后输出,sum,、,s,。,两数之积存入变量,s,中,键盘输入两个不同的数，分别存入变量,a,、,b,中,。,计算,a+b,，将结果存放在变量,sum,中；,计算,ab,，将结果存放在变量,s,中。,输出,sum,、,s,算法分析,流程图描述,开始,输入,a,、,b,输出,sum,、,s,sum,a+b,s,a,b,结束,顺序模式的特点：,按照顺序一步一步执行。,表示,先,计算,a+b,的值，,然后,将计算的结果存入变量,sum,中。,“,”称为,赋值符,，它的计算过程是：,先计算符号右侧的代数式的结果，然后将计算结果存储到符号左侧的变量中。,想一想,问题,2,：键盘输入两个不同的数，存入不同的变量中，交换两变量中的数值并输出,?,（,1,）需要输入哪些数据？,（,2,）需要计算机输出什么信息？,（,3,）如何根据输入数据得到要输出的信息,？,需要输入两个不同的数,需要计算机输出交换位置后的两个变量,分别存入变量,a,、,b,中,将变量,a,的值存入变量,b,中；,将变量,b,的值存入变量,a,中,。,最后输出变量,a,、,b,。,将变量,a,的值存入变量,T,中；,将变量,b,的值存入变量,a,中,。,将变量,T,的值存入变量,b,中,最后输出变量,a,、,b,。,键盘输入两个不同的数，分别存入变量,a,、,b,中,。,输出变量,a,、,b,算法分析,流程图描述,开始,输入变量,a,、,b,输出变量,a,、,b,Ta,ab,bT,结束,ba,ab,将变量,a,的值存入变量,T,中；,将变量,b,的值存入变量,a,中,。,将变量,T,的值存入变量,b,中,【,例,1】,已知矩形的长和宽，求矩形的面积。,求矩形面积的方法是：矩形面积,=,长,宽。如果设计的程序只能计算固定的长和宽，那么，这个程序就没有什么实用性了。,用变量,a,、,b,、,s,分别代表矩形的,长、宽、面积,，则,s,的值应该是,ab,的计算结果。,程序的执行流程应该是：,输入两个数值给,a,、,b,通过计算,ab,，将结果给变量,s,输出变量,s,的值,开始,输入长到变量,a,输入宽到变量,b,计算：,s,ab,输出面积：,s,结束,表示,先,计算,ab,的值，,然后,将计算的结果存入变量,s,中。,“,”称为,赋值符,，它的计算过程是：,先计算符号右侧的代数式的结果，然后将计算结果存储到符号左侧的变量中,。,1.3.3 算法的执行流程,算法的执行流程,，是指算法中各个处理步骤的执行次序和模式。通常需要如下三种不同的执行流程：,1.,顺序模式,：执行完一个处理步骤,step1,后，接着执行下一个处理步骤,step2,。,开始,输入变量,a,、,b,输出变量,a,、,b,Ta,ab,bT,结束,ba,ab,想一想,【,问题,1】,：该怎样过马路？,应观察交通信号灯并判断,:,红灯停,;,绿灯行,。,信号灯是否为,红灯,？,等待信号灯变为,绿灯,过马路,情况,e,为,真,？,step1,step2,情况,e,为,真,？,就是,对某个条件进行判断,，具体在判断框中用,关系表达式,或,逻辑表达式,来表达。,xy?,x0,且,y0?,选择模式,是先,对某个情况,e,进行判断,，,当结果为,真,时，执行处理步骤,step1,，,否则,执行处理步骤,step2,。,例如：,选择模式,可以使算法根据情况的不同，在,两个预定,的处理步骤中，,选择,执行,其中一个,处理步骤。,“,预定的处理步骤,”可以是,一系列操作,，亦可以是,无操作,。,当两个“,预定的处理步骤,”中有一个是,无操作,时，我们称其为,单分支结构，,如果,均有操作，,我们称其为,双分支结构,。,判断条件“,x,大于,y,”,判断条件“,x,、,y,均为正数,”,想一想,问题,2,：比较两个不同数的大小关系，输出其中较大的那个数,?,（,1,）需要输入哪些数据？,（,2,）需要计算机输出什么信息？,（,3,）如何根据输入数据得到要输出的信息,？,需要输入两个不同的数,需要计算机输出两数中较大的数,分别存入变量,a,、,b,中,存入变量,max,中,判断条件“,ab,”,，,若,条件成立,(,情况为,真,）,则,maxa,；,否则,（情况为,假,）,maxb,。,最后输出,max,。,键盘输入两个不同的数，分别存入变量,a,、,b,中,。,判断条件“,ab,”,，若,条件成立,（情况为,真,）,则,max,a,；,否则,（情况为,假,）,maxb,。,输出,max,算法分析,流程图描述,开始,输入,a,、,b,输出,max,maxa,maxb,结束,ab?,想一想,问题,3,：比较,三个,不同数的大小关系，输出其中,最大,的那个数,?,（,1,）需要输入哪些数据？,（,2,）需要计算机输出什么信息？,（,3,）如何根据输入数据得到要输出的信息,？,需要输入三个不同的数,需要计算机输出三个数中最大的数,分别存入变量,a,、,b,、,c,中,存入变量,max,中,判断条件“,ab,”,，若条件成立,则,maxa,；否则,maxb,。,判断条件“,maxc,”,，若条件成立,则,保持,max,不变,；,否则,maxc,。,最后输出,max,。,键盘输入三个不同的数，分别存入变量,a,、,b,、,c,中,。,判断条件“,ab,”,，若条件成立,则,maxa,；否则,maxb,。,判断条件“,maxc,”,，若条件成立,则,保持,max,不变,；否则,maxc,。,输出,max,算法分析,流程图描述,开始,输入,a,、,b,、,c,输出,max,maxa,maxb,结束,ab?,maxc,maxc?,开始,输入,a,、,b,、,c,结束,ab,且,ac?,bc?,maxa,maxb,maxc,输出,max,选择模式的嵌套,选择模式小结,选择模式的特点,选择模式是,由判断条件的成立与否,来,选择,执行,相应的,操作步骤,使用选择模式解决问题的要点,判断框中的判断条件表达方式,判断框中的判断条件可以是,关系表达式（如,:ab,），,也可以是,逻辑表达式（如,:ab,且,ac,）,。,1,、当算法执行到某一步,如果其结果存在多种可能性时，就应使用选择模式来解决；,2,、全面考虑问题的所有可能性，合理设置判断条件；,3,、使用流程图描述算法时应注意各执行步骤的汇合点。,3.,重复模式（循环结构）,问题：如果条件始终成立，会出现什么情况？,当型循环结构,的特点是：先判断条件，条件成立方能执行相应语句,继续判断条件，直到条件不成立退出循环。,当型循环结构,中，,语句块,可能,一次都不执行。,当型循环结构,直到型循环结构,直到型循环结构,的特点是：先执行语句块，条件不成立继续重复执行语句块，直到条件成立退出循环。,直到型循环结构,中的,语句块至少执行,1,次,。,是女生,？,游戏,N,聊天,Y,Y,终于可以休息了，上网,结束,吃晚饭、睡觉,(Day,加一天,),Day=,星期天，完成作业,Day=,星期一,开始,Day,星期六？,N,上学去,上完,8,节课,放学、回家、吃晚饭、做作业,睡觉，又过了一天,(Day,加一天,),设输入n的值是4,k的值是5，条件不成立，输出s,开始,sum,0,i,1,sum,sum i,i,i 1,i 100？,Y,输出,sum,结束,N,.,开始,sum,1,i,1,sum,sum i,i,i 2,i 5？,Y,输出总和：,sum,结束,N,sum=_ i=_,i,sum,条件,i=5,是否成立,成立,1+1,成立,1+1+3,成立,1+1+3+5,不成立,10,开始,sum,1,i,1,sum,sum i,i,i 1,sum5？,Y,输出总和：,sum,结束,N,sum=_ i=_,i,sum,条件,sum=5,是否成立,成立,1+1,成立,1+1+2,成立,1+1+2+3,不成立,开始,a,1,b,1,a,a b,b,a b,a10？,Y,输出：,a,，,b,结束,N,a=_ b=_,a,b,条件,a S,结束,显示：“输入价格：”,输入价格到变量,T,T 0,是否成立，若条件成立，则,d,是正数,，使正数计数器,c,1,计数,(,c1,c1,+1,),，转回步骤,2,；,否则，说明,d,是负数,，使负数计数器,c,2,计数,(,c,2,c2,+1,),，转回步骤,2,；,开始,结束,正数计数器,c1,置初值：,c10,负数计数器,c2,置初值：,c20,显示：“请输入：”,接收输入数据送到变量,d,d=0,？,计数器,c1,计数：,c1c1+1,d0,？,输出正数个数：,c1,计数器,c2,计数：,c2c2+1,输出负数个数：,c2,4,、输出正数的个数（,正数计数器,c1,）,，负数的个数（,负数计数器,c2,）,。,2.1 解析算法,问题,1,：已知一个三角形一条边的长度,a,和该边上的高,h,，则该三角形的面积是多少？,问题,2,：在理想情况下，从,h,米高的楼顶让一个铁球自由落下，铁球落地时的速度是多少,？,解析算法,是指用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。,利用数学公式中所反映的客观事务间的数量关系，以此为基础，设计出合适的算法，从而编制出正确的程序，利用计算机的高速计算能力，便能快速地获得问题的解。,注意,：并不是所有问题都可以找到与之相对应的数学公式。,第2章 算法实例,【,例题,1】,计算并联电阻的总阻值（一）,把,2,个电阻的两端分别连在一起，称为“,2,个电阻的并联”。,R,1,R,2,此算法应分为如下三个步骤：,1.,输入两个电阻的阻值；,2.,计算总阻值；,3.,输出计算结果。,开始,结束,输入,R,1,、,R,2,输出,R,计算：,T,（）,计算：,R,（）,计算：,R,（）,【,例题,2】,一元二次方程求解,一元二次方程,ax,2,+bx+c=0,（,a0,）,，输入,方程系数,a,、,b,、,c,，求方程的解。,根据一元二次方程的求解方法，首先需要判别,b,2,-4ac,的结果是大于,0,、小于,0,还是等于,0,，然后才能用求根公式进行计算。,所以我们需要使用选择模式，根据条件判别的不同结果，输出两个解、一个解、“无解”。,此算法应分为如下步骤：,1.,输入方程系数,a,、,b,、,c,；,2.,计算,b,2,-4ac,的值到变量,d,中；,3.,判断条件,d0,是否成立，,条件成立,，继续判断条件,d,0,是否成立，,条件成立,，计算并输出两个解；,否则，计算并输出一个解。,4.,若条件,d0,不成立,，则输出“无解”。,开始,输入,a,、,b,、,c,db,*b-4*a*c,d0,？,d0,？,计算并输出两个解,计算并输出一个解,输出“无解”,结束,输出 、,输出,开始,输入,a,、,b,、,c,db,*b-4*a*c,d0,？,d0,？,输出“无解”,结束,题目改为：,方程,ax,2,+bx+c=0,，输入,方程系数,a,、,b,、,c,，求方程的解。,输出 、,输出,a=0,？,输出“非二次方程”,【,例题,3】,计算并联电阻的总阻值（二）,把,n,个电阻的一端都连在一起，把这,n,个电阻的另一端也都连在一起，这样的连接成的电阻称为“,n,个电阻的并联”。此时我们从并联的,n,个电阻的两端,A,、,B,测得的电阻，是这,n,个并联电阻的“总阻值”。,R,1,R,2,R,1,R,2,R,3,n,个并联电阻的总阻值,R,，其倒数是各个电阻阻值的倒数的和，即：,1,、在算法的开始阶段，我们应设置变量,rs,的初值为,0,；,2,、通过输入指令，把使用者输入的电阻阻值,(,也可能是表示结束的,0),送到变量,r,中,;,3,、判断条件,r=0,是否成立，如果,不成立,，则,r,的倒数,应该被累加到变量,rs,中，转到步骤,2,；,如果条件,r=0,成立，执行步骤,4,；,开始,结束,累加器置初值：,rs0,输入电阻阻值送到变量,r,r=0,？,把,r,的倒数累加到,rs,中：,rs,=0,？,输出总电阻：,1/rs,输出“无电阻连接”,4,、输出总电阻值,1,/rs,。,4,、判断条件,rs,=0,是否成立，如果条件,不成立,，说明有效电阻的个数不为,0,，,输出,1/rs,；,否则说明没有连接电阻，,输出“无电阻连接”,。,问题：步骤,4,是否正确？为什么？,.,计数器,c,1,cn,?,cc,+1,累乘器,y1,yya,【,例题,4】,设计算法计算,y,a,n,，,a,、,n,由使用者输入，,a0,，,n,为正整数。,.,n个1相加,n个a相乘,负整数,c,InI,?,开始,输入,a,、,n,输出,y,结束,输出,1/y,c,-n?,(n+1)个1相加,|n|（-n）个a相乘,n个a相乘,【,习题,1】,设计算法完成下述功能：键盘输入三个正数，分别存储在变量,a,、,b,、,c,中，判断长度为,a,、,b,、,c,的三条线段是否能构成一个三角形，若能，计算并输出三角形的面积，否则，输出文字“不能构成三角形”。,提示：,（,1,）判断三条线段能否构成三角形的条件是什么？应如何使用判断框进行描述？,（,2,）利用三角形的三条边长计算三角形面积的公式如下：,【,习题,2】,：假定某银行储蓄的年利率为,2.15%,，按复利计算。设计一个算法，计算,y,元在该银行储蓄,m,年后所得的本金和利息之和是多少？,提示,：按复利计算是指每年产生的利息与本金合计作为下一年产生利息的本金，即每年产生利息的本金是上一年的本金与利息之和。,按照复利计算，一笔数量为,y,元的存款，,m,年后的本息和为,x,：,1,年后到期的本息为：,x=y,y0.0215=y1.0215,；,2,年后到期的本息为：,x=y,y0.0215,(y,y0.0215),0.0215,y1.0215,2,；,以此类推，,m,年后到期的本息为：,x=y1.0215,m,1.0215,m,为高阶指数运算，计算机不能一次算出结果，应采用重复模式进行计算，让,1.0215,这个数做,m,次连乘,即可。,【,习题,1】,：设计算法完成下述功能：键盘输入三个正数，分别存储在变量,a,、,b,、,c,中，判断长度为,a,、,b,、,c,的三条线段是否能构成一个三角形，若能，计算并输出三角形的面积，否则，输出文字“不能构成三角形”。,线段,a,、,b,、,c,能构成一个三角形的条件是：,任何两条线段长度的和应该大于第三条线段的长度，即：,a+b,c,、,b+c,a,、,a+c,b,三个不等式同时成立,。,使用变量,a,、,b,、,c,：用来分别存储构成三角形的三条线段的长度。,p,用来存储周长的一半，,s,用来存储三角形的面积。,计算的过程：,1,、在算法的开始阶段，首先输入变量,a,、,b,、,c,的值；,2,、判断变量,a,、,b,、,c,的值是否能够满足,a+b,c,、,b+c,a,、,a+c,b,三个不等式,同时,成立；,3,、如果三个不等式能够同时成立，则计算并输出三角形面积,s,；,否则，输出“不能构成三角形,”,。,输入：,a,、,b,、,c,开始,a+b,c,且,b+c,a,且,c+a,b,？,a+b,c,？,b+c,a,？,a+c,b,？,输入：,a,、,b,、,c,开始,输出,s,结束,输出“不能,构成三角形”,输出,s,结束,输出“不能,构成三角形”,输入：,“,a,、,b,、,c,”,开始,a+b,c,且,b+c,a,且,c+a,b,？,输出,“,N,”,结束,输出,“,s,”,在输入、输出,变量的值,时，该变量名,不能加引号,；,在输出,文字内容,时，该文字内容两端,要加引号,。,利用数学公式进行解析算法设计时，不应习惯性的将公式中的等号带入使用，在算法流程图中，“,”,代表判断等号左右两边的表达式的值是否相等,，而我们实际的操作是,将公式左侧的表达式经计算机计算后将其结果（即表达式的值）送入右侧的变量中,，所以,必须使用,“,”。,【,习题,2】,：假定某银行储蓄的年利率为,2.15%,，按复利计算。设计一个算法，计算,y,元在该银行储蓄,m,年后所得的本金和利息之和是多少？,提示,：按复利计算是指每年产生的利息与本金合计作为下一年产生利息的本金，即每年产生利息的本金是上一年的本金与利息之和。,按照复利计算，一笔数量为,y,元的存款，,m,年后的本息和为,x,：,1,年后到期的本息为：,x=y,y0.0215=y1.0215,；,2,年后到期的本息为：,x=y,y0.0215,(y,y0.0215),0.0215,y1.0215,2,；,以此类推，,m,年后到期的本息为：,x=y1.0215,m,1.0215,m,为高阶指数运算，计算机不能一次算出结果，应采用重复模式进行计算，让,1.0215,这个数做,m,次连乘,即可。,.,m个1相加,m个1.0215相乘,计数器,c,1,cm,?,cc,+1,累乘器,t1,tt1.0215,开始,输入本金,y,、存期,m,输出,x,结束,xyt,（m+1)个1相加,.,m个1相加,m个1.0215相乘,计数器,c,1,c,m?,cc,+1,yy1.0215,开始,输入本金,y,、存期,m,输出,y,结束,（m+1)个1相加,典型错误,计数器,c,1,c=m?,cc,+1,累乘器,t1,xy1.0215,开始,输入本金,y,、存期,m,输出,x,结束,2.5 递推算法,问题,1,：观察一串数,1,、,2,、,6,、,24,、,120,、,找出相邻两个数的关系？,问题,2,：观察一串数,2,、,5,、,7,、,12,、,19,、,31,、,找出,31,后的数应该是多少,？,递推法,是从头开始一步步地推出问题的最终结果的方法。,递推是序列计算中的一种常用方法。它是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得到序列中指定项的结果。,例题,1,计算斐波那奇数列的第,n,项,月份,序号,兔子对数,12,结论,:,从第,3,个月起,每个月的兔子对数总是等于上个月的兔子对数加上前个月的兔子对数,因此我们可以得到下面的这个数列,:,1,1,2,3,5,8,13,21,34,55,89,144,233,当前项号,k,a,b,c(c,a+b,),3,F,1,F,2,F,3,4,F,2,F,3,F,4,5,F,3,F,4,F,5,输出,c,初始化：,a,1,b,1,ca+b,k3,k=n?,项号变化,kk+1,初始化：,a,1,b,1,ca+b,k3,sum,a+b+c,计算下一项：,a,b,b,c,ca+b,计算下一项并累加求和：,a,b,b,c,ca+b,sum,sum+c,输出,c,，,sum,开始,结束,输出,1,n3?,输入项号,n,项号,k,a,b,c,(,c,a+b,),sum,1+1+2,1+1+2+3,1+1+2+3+5,1+1+2+3+5+8,计算出斐波那契数列的第,n,项（,n3,），并求出前,n,项的和。,例题,3,：讲义习题,1,计数器,c,1,c,n,?,c,c,+1,temp,x,0,temp,.,开始,输入,x,0,，,a,，,n,输出,temp,结束,.,例题,4,：讲义习题,2,.,temp,1,计数器,c,1,s,0,c,n,?,c,c,+1,s,s,+,temp,e,s+,1,开始,输出,e,结束,输入,n,.,2.2 枚举算法,问题,1,：有,1,把锁和一串钥匙,(100,把,),，只知道在这串钥匙中至少有,1,把钥匙可以打开锁，如何将所有可以开锁的钥匙都找出来？,问题,2,：在一副已经混乱的扑克牌中，如何找出所有花色是“,”的扑克牌？,有一类问题可以采用一种盲目搜索的方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不合要求的结果，保留那些合乎要求的结果，这种方法称为,枚举法,。,枚举法就是按照问题本身的性质，一一列举出该问题所有,可能的解,，并在逐一列举的过程中，检验每个可能的解是否是问题,真正的解,，若是，我们采纳它，否则，抛弃它。,并不是所有问题都可以采用枚举法来寻找答案的，,仅当问题的所有可能的解的个数不太多时，在可以接收的时间内获得问题所有的解,。,【,例题,1】,在,12008,这些自然数中，找出所有是,37,倍数的自然数。,求余数运算,mod,，,A mod B,就是,求,A/B,的余数,例如：,5 mod 3=2,，,10 mod 3=1,此算法应分为如下步骤：,1,、设置,n,的初值为,1,；,2,、判断条件,n2008,是否成立，,条件成立,，继续判断条件,n mod 37=0,是否成立，,条件成立,，输出,n,；,条件,n2008,不成立,，跳到步骤,4,；,3,、,n,的值增加,1,（,nn+1,），转回步骤,2,；,4,、此时,n,当前的值,大于,2008,，表示所有的数据均检查过了，算法结束。,开始,n,1,n2008,？,n mod 37=0,？,输出,n,nn+1,结束,开始,n,37,n2008,？,输出,n,nn+,37,结束,通过观察，我们发现,12008,中,37,的倍数是,从,37,开始，每次增加,37,，最大不超过,2008,的这些数,，所以，我们可以采用,n,初值设置为,37,，,每次增加,37,的方法枚举出这些数。相对前面的方法，效率提高。,【,例题,2】,单据中被涂抹的数字的推算,一张单据上有一个,5,位数的编码，其千位数和百位数处已经变得模糊不清，如右图所示。但知道这个,5,位数是,57,或,67,的,倍数,。现在请设计一个算法，输出所有满足这些条件的数，并统计这样的数的个数。,No.1 47,No.1 47,ij,我们可以从上述数学推导中得知：,n,的取值由,i,和,j,的取值共同决定，当我们确定当前,i,和,j,的值之后，,n,的取值自然也就确定了。,.,.,共100种组合,n为真正解的数学判断方法,开始,结束,j9,n mod 57=0,或,n mod 67=0,i,9,j,0,i,0,，计数器,c,0,j,j+1,i,i+1,输出真正解,n,计数器,c,计数，,c,c+1,n,10047+i1000,j100,输出,:,计数器,c,的值,对于,每个符合条件的,i,的取值,，我们让变量,j,从,0,开始,逐次枚举,到,9,，对于由,i,和,j,确定的,n,，判断其是否符合条件。具体步骤如下：,1,、变量,j,置初值,0,；,2,、判断条件,j 9,是否成立,若成立，计算出,n,的值；,继续判断,n,是否符合条件,条件成立，输出,n,，,计数器,c,计数,3,、,j,增加,1,，转回步骤,2,；,当条件,j 9,不成立，说明当前,i,的所有可能解均完成验证。此时，应验证,i,的下一个取值对应的所有可能解,。具体步骤如下：,1,、,i,增加,1,；,2,、判断条件,i,9,是否成立,若成立，开始验证对应的可能解,否则，说明所有可能解都完成验证，输出计数器,c,，算法结束。,i的取值0、1、2、.、9,j的取值0、1、2、.、9,问题,1,：如果原题中的,5,位数如下,图,1,所示，课本上的算法是否还适用？,问题,2,：如果原题中的,5,位数如下,图,2,所示，课本上的算法是否还适用？,No.15 7,图1,No.1 1 7,图2,【,例题,3】P23,，“实践体验”，,用,10,元与,50,元的两种纸币组成,240,元，共有几种组合方式，试用枚举算法列出所有不同的取法和种数。,设,240,元由,x,张,10,元、,y,张,50,元纸币组成，则必有以下方程成立：,10,x,+50,y,=240,.,.,.,开始,结束,y,4,10 x+50y=240,x 24,y,0,x,0,计数器,c,0,y,y+1,x,x+1,输出,x,、,y,计数器计数,:cc+1,输出：计数器,c,对于,每个符合条件的,x,的取值,，我们让变量,y,从,0,开始,逐次枚举,到,4,，对于由,x,和,y,确定的,方程,，判断其是否成立。具体步骤如下：,1,、变量,y,置初值,0,；,2,、判断条件,y 4,是否成立,若成立，继续判断,方程是否,成立,条件成立，输出,x,、,y,计数器,c,计数,3,、,y,增加,1,，转回步骤,2,；,当条件,y 4,不成立，说明当前,x,的所有可能解均完成验证。此时，应验证,x,的下一个取值对应的所有可能解,。具体步骤如下：,1,、,x,增加,1,；,2,、判断条件,x,24,是否成立,若成立，开始验证对应的可能解,否则，说明所有可能解都完成验证，输出计数器,c,，算法结束。,x的取值0、1、2、.、24,y的取值0、1、2、3、4,【,例题,4】,包装问题,包装,600,个变形金刚，要求是：,(1),包装的规格分别是：小盒,(,每盒,12,个,),、大盒,(,每盒,15,个,),；,(2),每种规格的盒数都不能为,0,。,请设计一个算法，输出所有可能的包装方案。,设,600,个变形金刚分别装入,x,个小盒、,y,个大盒中，则必有以下方程成立：,12x+15y=600,.,.,.,开始,结束,y 39,12x+15y=600,x 48,y,1,x,1,y,y+1,x,x+1,输出,x,、,y,对于,每个符合条件的,x,的取值,，我们让变量,y,从,1,开始,逐次枚举,到,39,，对于由,x,和,y,确定的,方程,，判断其是否成立。具体步骤如下：,1,、变量,y,置初值,1,；,2,、判断条件,y 39,是否成立,若成立，继续判断,方程是否,成立,条件成立，输出,x,、,y,3,、,y,增加,1,，转回步骤,2,；,当条件,y 39,不成立，说明当前,x,的所有可能解均完成验证。此时，应验证,x,的下一个取值对应的所有可能解,。具体步骤如下：,1,、,x,增加,1,；,2,、判断条件,x,48,是否成立,若成立，开始验证对应的可能解,否则，说明所有可能解都完成验证，算法结束。,x的取值1、2、3、.、48,y的取值1、2、3、.、39,【,例题,5,】,求直角三角形边长整数解的算法,在一直角三角形中，三条边,a,、,b,、,c,的长度都是正整数，本问题中,一条直角边,a,的长度已经给定，,斜边,c,的长度不能超过某个给定的正整数值,maxc