高中信息技术算法与程序设计.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同学比较的结果（猜小了、猜大了、猜对了）,计算机根据比较的结果决定是否继续猜测。,使用计算机解决问题一般要经历以下三个阶段：,分析问题并确定要计算机做什么,寻找解决问题的途径和方法,开始,用计算机进行处理,分析问题,设计算法,编写程序,运行程序,问题解决,猜大了或是猜小了，则继续猜测,猜对了则停止猜测，游戏结束,设计程序时需考虑的问题,数据的存储：计算所需的原始数据、计算产生的中间结果、计算的最终结果需要存储在变量中。,计算的过程：首先确定解决问题的方法；然后必须将该方法步骤化，即用计算机可以执行的步骤（指令），来描述问题的计算过程，这意味着程序的计算过程不仅必须指出动作，而且必须指出动作的次序。,输出指令,输入指令,逻辑判断指令,控制转移指令,变量的概念与用途,程序中的变量是计算过程中要用到的数据的存储单元；通过输入指令的执行，程序将外界输入的数据存储到指定的变量中，程序计算的结果也可以存储到指定的变量中；一旦将数据存储到某个变量中，只要我们不再把新的数据存储到其中，那么在程序运行过程中，该变量将永久保存着原来的数据；在计算过程中如果要使用到该变量中的数据，我们可以从该变量中读取出其中的数据，这种读取是不会改变变量中存储的内容的。,指令区,数据区,图中的每行代表了内存中的一个存储单元，每个存储单元可以存放一条指令或一个数据。每个存储单元都有唯一的编号，称为地址。指令是依次逐条执行的，如果遇到转移指令，会按指令要求选择下一条要执行的指令。遇到结束指令，整个程序终止运行。,输入价格：,500,375,250,500,250,375,猜大了！,输入价格：,猜小了！,输入价格：,猜对了！,375,输入价格：,1,375,2,1,2,375,猜小了！,输入价格：,猜小了！,输入价格：,猜对了！,375,.,1.3 算法的概念,算法是在有限步骤内求解某一个问题所使用的具有精确定义的一系列操作规则。每条规则都必须是确定的、能行的、不能有二义性的。算法要有一个清晰的起始步骤，且每一个步骤都只能有一个确定的后继步骤，从而组成一个有限步骤序列。步骤终止时也给出了问题的解答。解决问题的过程就是实现算法的过程。算法是程序设计的“灵魂”，算法+数据结构=程序。算法独立于任何具体程序设计语言，一个算法可以用多种程序设计语言实现。,1、算法的概念,2、算法的特点,（1）有穷性一个算法必须保证它的执行步骤是有限的，即它是能够终止的，操作步骤不能无限。算法可以有重复执行的步骤，只要这些步骤的执行能够终止。广义地说，“有穷性”是指操作步骤的数目或完成操作的时间在合理的范围内，如果一个算法虽然在操作步骤的数目是有限的，但它所花费的时间超过了合理的限度，这种算法并不是有效的算法。,（3）可行性算法中的每一个步骤都要是实际能做的，而且必须在有限的时间内可以完成。例如：步骤“输出：Ld”在d0的情况下就不可以做。,（4）有0个或多个输入所谓输入就是指算法在执行时要从外界获得数据，其目的是为算法建立某些初始状态；如果建立初始状态所需的信息已经包含算法中，那就不需要输入了。,（5）有一个或多个输出算法的目的是用来求解问题，问题的结果应以一定的方式输出，以便用户知道。在数学中的”无解“对于算法来说也是一个输出，没有输出的算法是毫无意义的。,（2）确定性算法的每个步骤必须有确切的含义，而不应当是含糊的、模棱两可的。例如：步骤“输出：L正整数”是无法执行的，因为没有指定L除以哪一个正整数，这个步骤是不确定的。问题：步骤“输入一个正整数”是否是确定的？,1.3 算法的表示,我们可以采用多种方法来描述一个算法，流程图是一种比较直观易用的、用图形来描述算法的方法。用流程图来描述算法要遵循一定的标准，这套标准中最常用的符号有：,处理框输入、输出框判断框流程线开始、结束符,在一般情况下，输入、输出框可以用处理框代替。,开始,结束,开始,结束,开始,T S,结束,显示：“输入价格：”,输入价格到变量T,T S,显示：“猜小了！”,显示：“猜大了！”,显示：“猜对了！”,Y,Y,N,N,判断框表示条件判断：取出变量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,suma+b,sab,结束,顺序模式的特点：按照顺序一步一步执行。,表示先计算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,计算：sab,输出面积：s,结束,表示先计算ab的值，然后将计算的结果存入变量s中。“”称为赋值符，它的计算过程是：先计算符号右侧的代数式的结果，然后将计算结果存储到符号左侧的变量中。,1.3.3 算法的执行流程,算法的执行流程，是指算法中各个处理步骤的执行次序和模式。通常需要如下三种不同的执行流程：,1.顺序模式：执行完一个处理步骤step1后，接着执行下一个处理步骤step2。,开始,输入变量a、b,输出变量a、b,Ta,ab,bT,结束,ba,ab,想一想,【问题1】：该怎样过马路？,应观察交通信号灯并判断:红灯停;绿灯行。,信号灯是否为红灯？,等待信号灯变为绿灯,Y,N,过马路,情况e为真？,step1,step2,Y,N,情况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”，若条件成立（情况为真）,则maxa；否则（情况为假）maxb。,输出max,算法分析,流程图描述,开始,输入a、b,输出max,maxa,maxb,结束,ab?,Y,N,想一想,问题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?,Y,N,maxc,maxc?,Y,N,开始,输入a、b、c,结束,ab且ac?,Y,N,bc?,Y,N,maxa,maxb,maxc,输出max,选择模式的嵌套,选择模式小结,选择模式的特点,选择模式是由判断条件的成立与否来选择执行相应的操作步骤,使用选择模式解决问题的要点,判断框中的判断条件表达方式,判断框中的判断条件可以是关系表达式（如:ab），也可以是逻辑表达式（如:ab且ac）。,1、当算法执行到某一步,如果其结果存在多种可能性时，就应使用选择模式来解决；,2、全面考虑问题的所有可能性，合理设置判断条件；,3、使用流程图描述算法时应注意各执行步骤的汇合点。,3.重复模式（循环结构）,问题：如果条件始终成立，会出现什么情况？,当型循环结构的特点是：先判断条件，条件成立方能执行相应语句,继续判断条件，直到条件不成立退出循环。当型循环结构中，语句块可能一次都不执行。,当型循环结构,直到型循环结构,直到型循环结构的特点是：先执行语句块，条件不成立继续重复执行语句块，直到条件成立退出循环。直到型循环结构中的语句块至少执行1次。,设输入n的值是4,k的值是5，条件不成立，输出s,.,sum=_ i=_,1,1,成立,1+1,3,成立,1+1+3,5,成立,1+1+3+5,7,不成立,7,10,sum=_ i=_,1,1,成立,1+1,2,成立,1+1+2,3,成立,1+1+2+3,4,不成立,4,7,a=_ b=_,1,1,成立,1+1,2+1,成立,2+3,5+3,成立,5+8,13+8,不成立,21,13,考虑该问题中涉及的数据，使用以下变量来保存数据：c:用来记录非0数的个数。d:用来存储当前输入的数据。sum:用来存放有效数的和。,这批数据由使用者从键盘输入，使用者预先不知道数据的个数。根据题意，计算的是非零数的平均值，所以我们以输入0表示本次计算所需的全部数据已输入完毕(即所有有效的数据，其值均不为0)。,【例2】设计算法，求输入的若干非零数的平均值。,对于输入的每一个数，如果不是0，则应进行两项处理:（1）将这个数加到总和里；（2）有效数的个数增加1。然后继续输入非零数据。重复上述两项处理，直到输入的数据为0时，结束这个累加和计数的过程。最后输出平均值（总和/个数）。,1、在算法的开始阶段，我们应设置变量sum的初值为0，变量c的初值为0；2、通过输入指令，把使用者输入的数据(也可能是表示结束的0)送到变量d中;3、判断条件d=0是否成立，如果不成立，则d应该被累加到变量sum中，然后变量c的值增加1，表示接收到一个有效数据，转到步骤2；如果条件d=0成立，执行步骤4；,开始,结束,累加器置初值：sum0,计数器置初值：c0,显示：“请输入：”,接收输入数据送到变量d,d=0？,把d累加到sum中：sumsum+d,计数器c计数：cc+1,c=0？,输出平均值：sum/c,输出平均值：0,4、输出平均值sum/c。,Y,N,4、判断条件c=0是否成立，如果条件不成立，说明有效数的个数不为0，输出sum/c；否则说明没有输入有效数据，输出0。,N,Y,问题：步骤4是否正确？为什么？,计数器(counter)，算法执行过程中，用来记录某种事件发生次数的变量。假定变量c作为计数器。计数器的典型用法：1.在算法执行的准备阶段中，应预置初值0。向计数器c预置初值0的动作为：c 0。2.算法执行过程中，每当指定的事件发生时，对计数器c计数，即，把事件已经发生的次数(在计数器c中)加1后，结果仍然送回到计数器c中。计数器c的计数动作为:c c+1。累加器(accumulator)，算法执行过程中，用来形成并存储数据之和的变量。假定变量sum作为累加器，变量d中存储了符合要求的一个数据。累加器的典型用法：1.在求和开始前的准备阶段中，应预置初值0。向累加器sum预置初值0的动作为：sum 0。2.算法执行过程中，每遇到一个符合要求的数据时，把这个数据累加到累加器中，即，计算累加器与该数据之和，并把结果重新存贮到累加器中。数据d累加到sum的动作为：sum sum+d。,考虑该问题中涉及的数据，使用以下变量来保存这些数据：n:用来存储最后一个要加入的数。sum:累加器，用来形成并存储数据之和。i:计数器，用来表示每次要加入的数据，加入后自动增加1。,【例3】设计一个算法，求sum=1+2+3+4+n，n由使用者输入，n为正整数。,对于求和式中的每一个数，我们发现是有规律的（从1开始，后一个是前一个加1），所以不需要每个数都手工输入，使用初值为1的计数器变量就可以表示。对于计数器的当前值，应进行两项处理:（1）将计数器的当前值加到累加器里；（2）计数器自动增加1。重复上述两项处理，直到计数器的值超过使用者的输入值n时，结束这个累加和计数的过程。最后输出累加器。,1、在算法的开始阶段，首先输入n的值，设置sum的初值为0，i的初值为1；2、判断条件in是否成立，如果成立，将i的值累加入sum中(sum sum+i)，然后i增加1(i i+1)，执行步骤3；如果条件不成立，则跳到步骤4；3、转回到步骤2，4、此时i当前的值大于n，表示所有的数据均累加入sum中，则输出sum的值。,开始,结束,输入n,累加器sum0,计数器i1,in？,sumsum+i,ii+1,输出sum,Y,N,.,n个1,(n+1)个1,计数器i的作用：（1）控制循环次数（2）表示每次要加入累加器中的数据,习题3：设计一个算法，求sum=1234n，n为正整数，由使用者输入。提示：本题与例题3很相似，注意变量sum的初值应设置为多少。,习题1：课本P11，“实践体验”，提示：注意计数器的作用与使用方法。,习题2：课本P13，“实践体验”，提示：注意本题与例题2的相似之处。,作业要求：1、抄题目2、用直尺画流程图,开始,T S,结束,显示：“输入价格：”,输入价格到变量T,T S,显示：“猜小了！”,显示：“猜大了！”,显示：“猜对了！”,Y,Y,N,N,计数器c置初值，c0,计数器c计数，cc+1,输出已猜次数：c,输出已猜次数：c,输出已猜次数：c,输出已猜次数：c,考虑该问题中涉及的数据，使用以下变量来保存这些数据：n:用来存储最后一个要乘入的数。sum:累乘器，用来形成并存储数据之积。i:计数器，用来表示每次要加入的数据，加入后自动增加1。,【习题2】设计算法，求sum=1234n，n由使用者输入，为正整数。,对于求积式中的每一个数，我们发现是有规律的（从1开始，后一个是前一个加1），所以不需要每个数都手工输入，使用初值为1的计数器变量就可以表示。对于计数器的当前值，应进行两项处理:（1）将计数器的当前值乘到累乘器里；（2）计数器自动增加1。重复上述两项处理，直到计数器的值超过使用者的输入值n时，结束这个累乘和计数的过程。最后输出累乘器。,1、在算法的开始阶段，首先输入n的值，设置sum的初值为，i的初值为1；2、判断条件in是否成立，条件成立，将i的值累乘入sum中(sum sumi)，然后i增加1(i i+1)，执行步骤3；条件不成立，跳到步骤4；3、转回到步骤2，4、此时i当前的值大于n，表示所有的数据均累加入sum中，则输出sum的值。,开始,结束,输入n,累乘器sum1,计数器i1,in？,sumsumi,ii+1,输出sum,Y,N,.,n个1,(n+1)个1,1,计数器i的作用：（1）控制循环次数（2）表示每次要乘入累乘器中的数据,典型错误,考虑该问题中涉及的数据，设计适当的变量来保存这些数据：d:用来存储从键盘输入的一个数据，或存储表示输入结束的数字记号0。c1:用来记录已经输入的正数数据的个数，即正数计数器。c2:用来记录已经输入的负数数据的个数，即负数计数器。,这批数据由使用者从键盘输入，使用者预先不知道数据的个数。根据题意，计算的是非零数的平均值，所以我们以输入0表示本次计算所需的全部数据已输入完毕(即所有有效的数据，其值均不为0)。,对于输入的每一个数，如果不是0，则应进行两项处理:（1）判断这个数是否为正数；（2）如果是正数，则正数的个数应该增加1；否则，负数的个数应该增加1。重复上述两项处理，直到输入的数据为0时，结束这个分类计数的过程。最后依次输出正数的个数和负数的个数。,【习题3】设计一个算法，计算并输出一批数据中正数和负数的个数。这批数据由使用者从键盘输入，预先并不知道数据的个数，输入0时表示输入结束(所有输入的有效数据，其值均不为0)。,1、在算法的开始阶段，我们应设置正数计数器c1,负数计数器c2的初值为0；2、通过输入指令，把使用者输入的数据(也可能是表示结束的0)送到变量d中。3、判断条件d=0是否成立，若不成立，则d是有效数据，如果条件d=0成立，说明输入结束，则执行步骤4；继续判断条件d0是否成立，若条件成立，则d是正数，使正数计数器c1计数(c1 c1+1)，转回步骤2；否则，说明d是负数，使负数计数器c2计数(c 2 c2+1)，转回步骤2；,开始,结束,正数计数器c1置初值：c10,负数计数器c2置初值：c20,显示：“请输入：”,接收输入数据送到变量d,d=0？,计数器c1计数：c1c1+1,d0？,输出正数个数：c1,Y,N,N,Y,计数器c2计数：c2c2+1,输出负数个数：c2,4、输出正数的个数（正数计数器c1），负数的个数（负数计数器c2）。,2.1 解析算法,问题1：已知一个三角形一条边的长度a和该边上的高h，则该三角形的面积是多少？,问题2：在理想情况下，从h米高的楼顶让一个铁球自由落下，铁球落地时的速度是多少？,解析算法是指用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。利用数学公式中所反映的客观事务间的数量关系，以此为基础，设计出合适的算法，从而编制出正确的程序，利用计算机的高速计算能力，便能快速地获得问题的解。注意：并不是所有问题都可以找到与之相对应的数学公式。,第2章 算法实例,【例题1】计算并联电阻的总阻值（一）把2个电阻的两端分别连在一起，称为“2个电阻的并联”。,此算法应分为如下三个步骤：1.输入两个电阻的阻值；2.计算总阻值；3.输出计算结果。,开始,结束,输入R1、R2,输出R,计算：T（）,计算：R（）,计算：R（）,【例题2】一元二次方程求解一元二次方程ax2+bx+c=0（a0），输入方程系数a、b、c，求方程的解。根据一元二次方程的求解方法，首先需要判别b2-4ac的结果是大于0、小于0还是等于0，然后才能用求根公式进行计算。所以我们需要使用选择模式，根据条件判别的不同结果，输出两个解、一个解、“无解”。,此算法应分为如下步骤：1.输入方程系数a、b、c；2.计算b2-4ac的值到变量d中；3.判断条件d0是否成立，条件成立，继续判断条件d0是否成立，条件成立，计算并输出两个解；否则，计算并输出一个解。4.若条件d0不成立，则输出“无解”。,开始,输入a、b、c,db*b-4*a*c,d0？,d0？,计算并输出两个解,计算并输出一个解,输出“无解”,结束,输出、,输出,Y,Y,N,N,开始,输入a、b、c,db*b-4*a*c,d0？,d0？,输出“无解”,结束,题目改为：方程ax2+bx+c=0，输入方程系数a、b、c，求方程的解。,输出、,输出,a=0？,输出“非二次方程”,Y,Y,N,N,Y,N,【例题3】计算并联电阻的总阻值（二）把n个电阻的一端都连在一起，把这n个电阻的另一端也都连在一起，这样的连接成的电阻称为“n个电阻的并联”。此时我们从并联的n个电阻的两端A、B测得的电阻，是这n个并联电阻的“总阻值”。,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。,Y,N,4、判断条件rs=0是否成立，如果条件不成立，说明有效电阻的个数不为0，输出1/rs；否则说明没有连接电阻，输出“无电阻连接”。,N,Y,问题：步骤4是否正确？为什么？,.,计数器c1,cn?,cc+1,累乘器y1,yya,Y,N,【例题4】设计算法计算yan，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=yy0.0215=y1.0215；2年后到期的本息为：x=yy0.0215(yy0.0215)0.0215y1.02152；以此类推，m年后到期的本息为：x=y1.0215m1.0215m为高阶指数运算，计算机不能一次算出结果，应采用重复模式进行计算，让1.0215这个数做m次连乘即可。,【习题1】：设计算法完成下述功能：键盘输入三个正数，分别存储在变量a、b、c中，判断长度为a、b、c的三条线段是否能构成一个三角形，若能，计算并输出三角形的面积，否则，输出文字“不能构成三角形”。,线段a、b、c能构成一个三角形的条件是：任何两条线段长度的和应该大于第三条线段的长度，即：a+bc、b+ca、a+cb三个不等式同时成立。,使用变量a、b、c：用来分别存储构成三角形的三条线段的长度。p用来存储周长的一半，s用来存储三角形的面积。,计算的过程：1、在算法的开始阶段，首先输入变量a、b、c的值；2、判断变量a、b、c的值是否能够满足a+bc、b+ca、a+cb三个不等式同时成立；3、如果三个不等式能够同时成立，则计算并输出三角形面积s；否则，输出“不能构成三角形”。,输入：a、b、c,开始,a+bc 且b+ca且c+ab？,a+bc？,b+ca？,a+cb？,输入：a、b、c,开始,输出s,结束,输出“不能构成三角形”,输出s,结束,输出“不能构成三角形”,Y,Y,Y,Y,N,N,N,N,Y,N,在输入、输出变量的值时，该变量名不能加引号；在输出文字内容时，该文字内容两端要加引号。,利用数学公式进行解析算法设计时，不应习惯性的将公式中的等号带入使用，在算法流程图中，“”代表判断等号左右两边的表达式的值是否相等，而我们实际的操作是将公式左侧的表达式经计算机计算后将其结果（即表达式的值）送入右侧的变量中，所以必须使用“”。,【习题2】：假定某银行储蓄的年利率为2.15%，按复利计算。设计一个算法，计算y元在该银行储蓄m年后所得的本金和利息之和是多少？提示：按复利计算是指每年产生的利息与本金合计作为下一年产生利息的本金，即每年产生利息的本金是上一年的本金与利息之和。,按照复利计算，一笔数量为y元的存款，m年后的本息和为x：1年后到期的本息为：x=yy0.0215=y1.0215；2年后到期的本息为：x=yy0.0215(yy0.0215)0.0215y1.02152；以此类推，m年后到期的本息为：x=y1.0215m1.0215m为高阶指数运算，计算机不能一次算出结果，应采用重复模式进行计算，让1.0215这个数做m次连乘即可。,.,m个1相加,m个1.0215相乘,计数器c1,cm?,cc+1,累乘器t1,tt1.0215,Y,N,开始,输入本金y、存期m,输出x,结束,xyt,（m+1)个1相加,.,m个1相加,m个1.0215相乘,计数器c1,c m?,cc+1,yy1.0215,Y,N,开始,输入本金y、存期m,输出y,结束,（m+1)个1相加,典型错误,计数器c1,c=m?,cc+1,累乘器t1,xy1.0215,Y,N,开始,输入本金y、存期m,输出x,结束,2.5 递推算法,问题1：观察一串数1、2、6、24、120、找出相邻两个数的关系？,问题2：观察一串数2、5、7、12、19、31、找出31后的数应该是多少？,递推法是从头开始一步步地推出问题的最终结果的方法。递推是序列计算中的一种常用方法。它是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得到序列中指定项的结果。,例题1计算斐波那奇数列的第n项,月份,序号,兔子对数,12,1,2,3,4,5,1,2,3,4,5,6,1,1,2,3,5,8,结论:从第3个月起,每个月的兔子对数总是等于上个月的兔子对数加上前个月的兔子对数,因此我们可以得到下面的这个数列:,1,1,2,3,5,8,13,21,34,55,89,144,233,输出c,初始化：a1,b1,ca+b,k3,k=n?,项号变化 kk+1,Y,N,初始化：a1,b1,ca+b,k3,sum a+b+c,计算下一项：ab,bc,ca+b,计算下一项并累加求和：ab,bc,ca+b,sum sum+c,输出c，sum,开始,结束,输出1,n3?,输入项号n,Y,N,3,1,1,2,1,4,3,5,2,5,2,3,3,5,8,6,sum,1+1+2,1+1+2+3,1+1+2+3+5,1+1+2+3+5+8,计算出斐波那契数列的第n项（n3），并求出前n项的和。,例题3：讲义习题1,计数器c1,c n?,cc+1,tempx0,temp,Y,N,.,开始,输入x0，a，n,输出temp,结束,.,例题4：讲义习题2,.,N,temp1,计数器 c 1,s 0,c n?,cc+1,s s+temp,es+1,Y,开始,输出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，表示所有的数据均检查过了，算法结束。,开始,n1,n2008？,n mod 37=0？,输出n,nn+1,结束,Y,Y,N,N,开始,n37,n2008？,输出n,nn+37,结束,Y,N,通过观察，我们发现12008中37的倍数是从37开始，每次增加37，最大不超过2008的这些数，所以，我们可以采用n初值设置为37，每次增加37的方法枚举出这些数。相对前面的方法，效率提高。,【例题2】单据中被涂抹的数字的推算一张单据上有一个5位数的编码，其千位数和百位数处已经变得模糊不清，如右图所示。但知道这个5位数是57或67的倍数。现在请设计一个算法，输出所有满足这些条件的数，并统计这样的数的个数。,我们可以从上述数学推导中得知：n的取值由i和j的取值共同决定，当我们确定当前i和j的值之后，n的取值自然也就确定了。,.,.,n为真正解的数学判断方法,开始,结束,j9,n mod 57=0或n mod 67=0,i 9,j0,i0，计数器c0,jj+1,ii+1,输出真正解n,Y,N,Y,N,Y,N,计数器c计数，cc+1,n10047+i1000j100,输出:计数器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、.、9j的取值0、1、2、.、9,问题1：如果原题中的5位数如下图1所示，课本上的算法是否还适用？问题2：如果原题中的5位数如下图2所示，课本上的算法是否还适用？,【例题3】P23，“实践体验”，用10元与50元的两种纸币组成240元，共有几种组合方式，试用枚举算法列出所有不同的取法和种数。,设240元由x张10元、y张50元纸币组成，则必有以下方程成立：10 x+50y=240,.,.,.,开始,结束,y 4,10 x+50y=240,x 24,y0,x0,计数器c0,yy+1,xx+1,输出x、y,Y,N,Y,N,Y,N,计数器计数: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、.、24y的取值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,y1,x1,yy+1,xx+1,输出x、y,Y,N,Y,N,Y,N,对于每个符合条件的x的取值，我们让变量y从1开始逐次枚举到39，对于由x和y确定的方程，判断其是否成立。具体步骤如下：1、变量y置初值1；2、判断条件y 39是否成立 若成立，继续判断方程是否 成立 条件成立，输出x、y3、y增加1，转回步骤2；,当条件y 39不成立，说明当前x的所有可能解均完成验证。此时，应验证x的下一个取值对应的所有可能解。具体步骤如下：1、x增加1；2