请问递推是?回溯是? 请讲一下他们的的概念好吗?如果举例子能用QBASIC举吗?我最近要考竞赛,用QB,谢了! 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 递归算法程序调用自身的编程技巧称为递归(recursion)。一个比较经典的描述是老和尚讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在讲故事,他说从前有座山,……。这样没完没了地反复讲故事,直到最后老和尚烦了停下来为止。反复讲故事可以看成是反复调用自身,但如果不能停下来那就没有意义了,所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有,最后老和尚烦了停下来这样的递归的终止条件也要有。阶乘的算法可以定义成函数 n*f(n-1) (n>0)f(n)= f(n)=1 (n=0)当n>0时,用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……,这是对递归形式的描述。当n=0时,f(n)=1,这是递归结束的条件。递归算法一般用于解决三类问题:⑴. 数据的定义形式是按递归定义的。比如阶乘的定义。 例1 又如裴波那契数列的定义:f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2对应的递归程序为:var n:integer;function f(n:integer):longint;begin case n of 0:f:=1; {递归结束条件} 1:f:=2; else f:=f(n-1)+f(n-2) {递归调用} endend;begin readln(n); writeln(f(n))end.这类递归问题往往又可转化成递推算法,递归边界作为递推的边界条件。⑵. 问题解法按递归算法实现。例如回溯等。⑶. 数据的结构形式是按递归定义的。如树的遍历, 图的搜索等。递归解决实际问题的例子很多,如经典的梵塔问题。例2 梵塔问题:有n个半径各不相同的圆盘,按半径从大到小,自下而上依次套在A柱上,另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去,每次只能搬动一个盘子,且必须始终保持每根柱子上是小盘在上,大盘在下。在移动盘子的过程当中发现要搬动n个盘子,必须先将n-1个盘子从A柱搬到B柱去,再将A柱上的最后一个盘子搬到C柱,最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的,当盘子搬到只剩一个时,递归结束。程序如下:var a,b,c,number:integer;procedure move(n,a,b,c:integer);begin if n=1 then writeln(a,'->',c) else begin move(n-1,a,c,b); writeln(a,'->',c); move(n-1,b,a,c) end;end;begin write('the number of dish:'); readln(number); move(number,1,2,3); readlnend.自然数的拆分,数字的拆分等都可以用到递归算法。例3 要求找出具有下列性质的数的个数(包含输入的自然数n):先输入一个自然数n(n<=500),然后对此自然数按照如下方法进行处理:①. 不作任何处理;②. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;③. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.样例: 输入: 6满足条件的数为 6 16 26 126 36 136输出: 6这道题只需求出满足条件的数的个数,在n值不大的情况下用递归求解比较方便,因为它本身题目的条件就是递归定义的。递归的样例程序如下:var n,i:integer; s:real;procedure qiu(x:integer);var k:integer;begin if x<>0 then begin s:=s+1; for k:=1 to x div 2 do qiu(k) endend;begin readln(n); s:=0; qiu(n); writeln(s:2:0)end.递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。 新手求助 VB和RDO连接数据库的例子 Winsock 为什么得不到服务器的响应 请问用什么方法(或者控件)可以检测 是否已经连接到网络(Internet)? 对不住各位英雄了。惨就一个字啊 求救高手 关于下列函数的写法:急!! 请问vb怎样与其它计算机连接 高分求解答:请vb高手指点 利用CommonDialog控件的保存问题 如何移动Datagrid的滚动条? 新手请教:关于VB和SQL的 抛物线的化法
递归算法程序调用自身的编程技巧称为递归(recursion)。一个比较经典的描述是老和尚讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在讲故事,他说从前有座山,……。这样没完没了地反复讲故事,直到最后老和尚烦了停下来为止。反复讲故事可以看成是反复调用自身,但如果不能停下来那就没有意义了,所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有,最后老和尚烦了停下来这样的递归的终止条件也要有。阶乘的算法可以定义成函数 n*f(n-1) (n>0)f(n)= f(n)=1 (n=0)当n>0时,用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……,这是对递归形式的描述。当n=0时,f(n)=1,这是递归结束的条件。递归算法一般用于解决三类问题:⑴. 数据的定义形式是按递归定义的。比如阶乘的定义。 例1 又如裴波那契数列的定义:f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2对应的递归程序为:var n:integer;function f(n:integer):longint;begin case n of 0:f:=1; {递归结束条件} 1:f:=2; else f:=f(n-1)+f(n-2) {递归调用} endend;begin readln(n); writeln(f(n))end.这类递归问题往往又可转化成递推算法,递归边界作为递推的边界条件。⑵. 问题解法按递归算法实现。例如回溯等。⑶. 数据的结构形式是按递归定义的。如树的遍历, 图的搜索等。递归解决实际问题的例子很多,如经典的梵塔问题。例2 梵塔问题:有n个半径各不相同的圆盘,按半径从大到小,自下而上依次套在A柱上,另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去,每次只能搬动一个盘子,且必须始终保持每根柱子上是小盘在上,大盘在下。在移动盘子的过程当中发现要搬动n个盘子,必须先将n-1个盘子从A柱搬到B柱去,再将A柱上的最后一个盘子搬到C柱,最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的,当盘子搬到只剩一个时,递归结束。程序如下:var a,b,c,number:integer;procedure move(n,a,b,c:integer);begin if n=1 then writeln(a,'->',c) else begin move(n-1,a,c,b); writeln(a,'->',c); move(n-1,b,a,c) end;end;begin write('the number of dish:'); readln(number); move(number,1,2,3); readlnend.自然数的拆分,数字的拆分等都可以用到递归算法。例3 要求找出具有下列性质的数的个数(包含输入的自然数n):先输入一个自然数n(n<=500),然后对此自然数按照如下方法进行处理:①. 不作任何处理;②. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;③. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.样例: 输入: 6满足条件的数为 6 16 26 126 36 136输出: 6这道题只需求出满足条件的数的个数,在n值不大的情况下用递归求解比较方便,因为它本身题目的条件就是递归定义的。递归的样例程序如下:var n,i:integer; s:real;procedure qiu(x:integer);var k:integer;begin if x<>0 then begin s:=s+1; for k:=1 to x div 2 do qiu(k) endend;begin readln(n); s:=0; qiu(n); writeln(s:2:0)end.递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。