raptor软件使用.ppt

RAPTOR程序设计基础程序设计基础可视化计算可视化计算循环控制循环控制循环（循环（loop）控制语句允）控制语句允许重复执行一个或多个语许重复执行一个或多个语句，直到某些条件变为真句，直到某些条件变为真值（值（True）。菱形符号中的表达式结果为菱形符号中的表达式结果为“No”，则执行，则执行“No”的分的分支，这将导致循环语句和重支，这将导致循环语句和重复复。要重复执行的语句可以放在要重复执行的语句可以放在菱形符号上方或下方菱形符号上方或下方。循环控制结构在英语环境循环控制结构在英语环境中被称为中被称为“While-doWhile-do”结构结构。典型的循环错误典型的循环错误未修改未修改Count的值的值Count的值永远为的值永远为1Count的值永远不会等于的值永远不会等于-100计数控制计数控制循环循环之一之一求一个正整数的累加。计数控制计数控制循环循环之二之二一张纸折几下可以比珠穆朗玛峰高一张纸折几下可以比珠穆朗玛峰高。（。（0.5mm0.5mm，8848m8848m）RAPTOR子程序子程序的的定义与调用定义与调用在计算机科学中，将实际问题抽象化是解决问题的关键要素之一。为了解决复杂的问题，必须能够研究问题的“主要方面（big issues）”。组合数求解组合数求解很容易看到，求组合数需要多次求阶乘，这会造成许多重复的代码。可以将求阶乘代码独立出主程序，定义为一个子程序，在主程序运行时，需要计算某数的阶乘时就调用子程序，从而简化整个软件的组成，使结构更清晰。子程序子程序子程序如同一个加工厂，输入原材料，然后按设计要求处理原材料，输出产成品。子程序的原材料就是一些变量,例如（in:m）,为统计子程序输入测试样本。子程序的产成品也是变量，例如（out:s）,向调用它的程序返回统计结果。其中，in,out表示子程序的输入输出参数。创建创建RAPTOR子程序子程序点击“模式”菜单，选择“中级”。在在“main”上点鼠标右上点鼠标右键，选择键，选择“增加一个子增加一个子程序程序”。子程序定义子程序定义子程序定义的参数称为“形式参数”。RAPTOR的子程序参数不得超过6个。子程序参数可以是单个变量，也可以是数组。求求阶阶乘乘的的子子程程序序过程调用语句过程调用语句在“main”或其它子程序中添加过程调用语句。双击定义该语句。JC(m,m1)实参实参子程序的调用子程序的调用如要调用子程序，可以通过调用语句并给子程序的接口赋予“实际参数”进行。实际参数的名名与形式参数的可以不同。实际参数的数据类型数据类型则必须与形式参数的相同。五、五、算法算法示例示例1迭代迭代算法算法（递推法）让计算机对一组指令进行重复执行，在每次执行这组指令时，都从变量的原值推出它的一个新值。在数学中，迭代经常被用来进行数值计算，累加与累乘问题是最典型、最基本的一类算法，实际应用中很多问题都可以归结为累加与累乘问题。累加：累加：S=0input nFor j=1 to ns=s+j 累乘：累乘：F=1input nFor k=1 to nF=F*k 具体方法是：具体方法是：如左图：先给一个近如左图：先给一个近似根的一个初值似根的一个初值x1，过，过A点点(f(x1)作作切线交切线交x轴于轴于x2点。实际上是找出点。实际上是找出x2,再由再由x2找出找出x3,x4，直到满足精度，直到满足精度为为10-6的根的根(解解)。由点斜式方程得由点斜式方程得斜率斜率k：【例】求一元高次方程2x3-4x2+3x-6=0在x=1.5附近的近似根，要求精度为10-6。分析：分析：“迭代法”又称“递推法”，其基本思想是把一个复杂的计算过程简化为简单过称的多次重复。每次的重复都是从旧值的基础上递推出新值，直至满足精度要求。f(x1)=0-f(x1)/(x2-x1)x2=x1-f(x1)/f(x1)得递推公式：得递推公式：xn+1 =xn f(xn)/f(xn)本题本题中，我们用中，我们用 f 表示表示f(xn)，f1 表示表示 f(xn)19k=y=f(x)A点初的切线在点初的切线在x轴上的轴上的x2处处 有有 y2=0 而而【思思考考题题】小小猴猴有有桃桃若若干干，第第一一天天吃吃掉掉一一半半多多一一个个；第第二二天天吃吃剩剩下下桃桃子子的的一一半半多多一一个个；以以后后每每天天都都吃吃尚尚存存桃桃子子的的一一半半多多一个，到第一个，到第7天要吃时只剩一个，问小猴原有桃多少？天要吃时只剩一个，问小猴原有桃多少？分分析析：也也是是递递推推(迭迭代代)问问题题。用用后后一一天天的的数数推推出出前前一一天天的的桃桃子数子数。设设第第n天天的桃子为的桃子为xn，是前一天的桃子的二分之一减去，是前一天的桃子的二分之一减去1。2穷举算法穷举算法穷举法也叫枚举法，是对众多可能解，通过多重循环一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能的解是否是问题的真正解，若是，就采用这个解，否则抛弃它。穷举的计算量是相当大的，但对于计算机来说，做起来很容易。采用穷举法解题的基本思想：（1）明确问题要求，确定枚举对象，用合适类型的变量表示枚举对象。）明确问题要求，确定枚举对象，用合适类型的变量表示枚举对象。（2）明确枚举对象的取值范围。）明确枚举对象的取值范围。（3）根据题目要求，写出有关的条件表达式。这里条件表达式可以是数）根据题目要求，写出有关的条件表达式。这里条件表达式可以是数学表达式、关系表达式或逻辑表达式。学表达式、关系表达式或逻辑表达式。（4）用）用循环语句枚举出可能的解，在循环体内验证各种条件表达式是否循环语句枚举出可能的解，在循环体内验证各种条件表达式是否满足。满足。（5）根据问题背景，优化程序，以便缩小搜索范围，减少程序运行时间）根据问题背景，优化程序，以便缩小搜索范围，减少程序运行时间。例1：从110中找出所有是3倍数的数。用流程图描述解决此数学问题的算法如右图所示。例例2 2：百：百元买百鸡。公鸡元买百鸡。公鸡5 5块钱块钱一只，母鸡一只，母鸡三块钱三块钱一只、小一只、小鸡鸡一块钱一块钱三只，编程求解购鸡方案。三只，编程求解购鸡方案。分析：分析：(1)(1)设母鸡、公鸡、设母鸡、公鸡、小鸡的数量各小鸡的数量各为为x x、y y、z z，列出方程，列出方程为：为：x x+y y+z z=100=1005 5x x+3+3y y+z/3z/3=100=100三个未知数，两个方程，此三个未知数，两个方程，此题有若干题有若干个整数解。个整数解。(2)(2)计算机求解此类问题，采用试凑法计算机求解此类问题，采用试凑法(也称穷举法也称穷举法)来实来实现，即将可能出现的各种情况一一罗列测试，判断是否现，即将可能出现的各种情况一一罗列测试，判断是否满足条件，采用循环结构来实现满足条件，采用循环结构来实现。11233排序算法排序算法排序（Sort），就是将一组数据元素按照某个关键字递增或递减的次序排列起来。选择法选择法排序：排序：找出表中关键字最小的元素，将其与第找出表中关键字最小的元素，将其与第一个元素进行交换，再在其余元素中找出关键字最小的一个元素进行交换，再在其余元素中找出关键字最小的元素，将其与第二个元素进行交换。依次类推，直到将元素，将其与第二个元素进行交换。依次类推，直到将表中所有关键字按由小到大的顺序排列好为止。表中所有关键字按由小到大的顺序排列好为止。选择法排序选择法排序For i=1 To 5 Step 1Min=a(i)For j=i+1 To 6 Step 1 If Min a(j)Then Min=a(j)p=j End If Next jn=a(i)a(i)=a(p)a(p)=nNext iVB程序段冒泡法排序：从第一个开始，对数组中两两相邻的元素比较，值较小的放在前面，值较大的放在后面，一轮比较完毕，一个最大的数沉底成为数组中的最后一个元素，一些较小的数如同气泡一样上浮一个位置。n个数，经过n-1轮比较后完成排序。a(1)a(1)a(2)a(2)a(3)a(3)a(4)a(4)a(5)a(5)a(6)a(6)第第1 1轮比较轮比较6 8 3 2 7 6 8 3 2 7 9 9 9 9a(1)a(1)a(2)a(2)a(3)a(3)a(4)a(4)a(5)a(5)第第2 2轮比较轮比较6 3 2 7 6 3 2 7 8 8 8 8 9 9a(1)a(1)a(2)a(2)a(3)a(3)a(4)a(4)第第3 3轮比较轮比较3 2 6 3 2 6 7 7 7 7 8 9 8 9a(1)a(1)a(2)a(2)a(3)a(3)第第4 4轮比较轮比较2 3 2 3 6 6 6 6 7 8 9 7 8 9a(1)a(1)a(2)a(2)第第5 5轮比较轮比较2 2 3 3 3 3 6 7 8 9 6 7 8 9 原始数据原始数据8 6 9 3 2 78 6 9 3 2 7a(1)a(1)a(2)a(2)a(3)a(3)a(4)a(4)a(5)a(5)a(6)a(6)4.递归算法：程序调用自身的编程技巧称为递归（recursion）。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。注意：(1)递归就是在过程或函数里调用自身;(2)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。递归的原理，其实就是使用栈(stack).栈是限定在一端进行插入和删除的线性表。栈是按照“先进后出”或者“后进先出”的原则组织数据的。入栈入栈出栈出栈栈顶栈顶栈底栈底栈示意图栈示意图例1：递归法求N!【解题】递归过程在自身定义的内部调用自己，fac(n)=n!的递归函数：进进栈栈出出栈栈当当n=4n=4时，求解过程：时，求解过程：Functionfac(nAsInteger)AsLongIfn=1Thenfac=1Elsefac=n*fac(n-1)EndIfEndFunction递归函数程序段：递归函数程序段：例2：汉诺塔问题汉诺塔问题源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定：在在小圆盘上不能放大圆盘小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘在三根柱子之间一次只能移动一个圆盘。不论白天黑夜，总有一个僧侣在按照上面的法则移动这些金片。僧侣们预言，当所有的金片都从梵天穿好的那根柱上移到另外一根柱上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。原柱原柱x辅助辅助柱柱y目标目标柱柱z三三个个盘盘子子汉汉诺诺塔塔问问题题的的递递归归求求解解示示意意图图如如下下图图所所示示。34原柱原柱x辅助辅助柱柱y目标目标柱柱z四四四四个个个个盘盘盘盘子子子子汉汉诺诺塔塔问问题题的的递递归归求求解解示示意意图图如如下下图图所所示示。5查找查找算法算法查找是根据给定的某个“值”，在查找表中确定一个其关键字等于给定“值”的数据元素，若表中存在称此查找是成功的。若表中不存在称此查找不成功的。顺序查找顺序查找插入数据基本思想是：1）首先查找待插入数据在数组中的位置k；2）然后从最后一个元素开始往前直到下标为k的元素依次往后移动一个位置；3)第k个元素的位置腾出，将数据插入。删除数据基本思想是：a)删除操作首先也是要找到欲删除的元素的位置k；b)然后从k+1到n个位置开始向前移动；c)最后将数组元素减1。