[导入]Hanoi塔问题(C)

1 引言 在计算机算法设计中,使用递归技术往往使函数的定义和算法的描述简捷且易于理解.有些数据结构如二叉树等由于其本身固有的递归特性,特别适合用递归的形式来描述.还有一些问题,虽然其本身并没有明显的递归结构,但用递归技术来求解使设计出的算法简洁.易懂.因此深入掌握递归技术在算法设计过程中可以设计出更加有效的算法[1]. 简单地说,递归就是用自己定义自己.使用递归方法构造算法的基本思路是:当求解规模为n的问题时,先将其分解成若干个规模较小的与原问题具有相同特征的子问题,并找出子问题与原问题之间的组

Hanoi塔问题--递归方法求解     假设有三个分别命名为x.y.z的圆柱形塔座,在塔座x上插有n个半径大小各不相同,以小到大由上而下编号为1,2,····,n,如图所示.现在要求将X轴上的n个圆盘移至塔Z上并仍按原来的顺序叠放,圆盘移动时必须遵循以下规则: 1.每次只能移动一个圆盘 2.圆盘可以插在X.Y.Z任意一个塔座上 3.任何时刻都不能将一个较大的圆盘压在较小圆盘之上 如何实现圆盘的移动呢?这就要用到我们强大的递归思想.设一个变量n用来调用任意一个圆盘,当n=1时,只要将一号圆盘从X

程序如下: 复制代码 代码如下: View Code  /*  * Hanoi塔游戏 问题描述:  * 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.  * 大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照  * 大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小  * 顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在  * 三根柱子之间一次只能移动一个圆盘.  *   * fuction:实现 hanoi塔  *       

/** * 汉诺塔大学的时候就学过,但是根本没搞明白,唯一知道的就是要用递归的方法来求解. * 问题描述: * 有三根杆子A,B,C.A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小. * 要求按下列规则将所有圆盘移至C杆: * 1.每次只能移动一个圆盘: * 2.大盘不能叠在小盘上面. * 提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆, * 但都必须尊循上述两条规则. * 问:如何移?最少要移动多少次? * 解决方法: * 假设只有2个盘子,柱子分别是A, B, C柱

函数的递归调用 一个函数在它的函数体内调用它自身称为递归调用. 这种函数称为递归函数.C语言允许函数的递归调用.在递归调用中, 主调函数又是被调函数.执行递归函数将反复调用其自身. 每调用一次就进入新的一层.例如有函数f如下:int f (int x){int y;z=f(y);return z;}这个函数是一个递归函数. 但是运行该函数将无休止地调用其自身,这当然是不正确的.为了防止递归调用无终止地进行, 必须在函数内有终止递归调用的手段.常用的办法是加条件判断, 满足某种条件后就不再作递归调

一个函数在它的函数体内调用它自身称为递归调用.这种函数称为递归函数.C语言允许函数的递归调用.在递归调用中,主调函数又是被调函数.执行递归函数将反复调用其自身,每调用一次就进入新的一层   一.基本内容: C语言中的函数可以递归调用,即:可以直接(简单递归)或间接(间接递归)地自己调自己. 要点: 1.C语言函数可以递归调用. 2.可以通过直接或间接两种方式调用.目前只讨论直接递归调用. 二.递归条件 采用递归方法来解决问题,必须符合以下三个条件: 1.可以把要解决的问题转化为一个新问题,而这个

递归的概念与基本思想 一个函数.过程.概念或数学结构,如果在其定义或说明内部又直接或间接地出现有其本身的引用,则称它们是递归的或者是递归定义的.在程序设计中,过程或函数直接或者间接调用自己,就被称为递归调用. 递归的实现方法 递归是借助于一个递归工作栈来实现:递归=递推+回归: 递推:问题向一极推进,这一过程叫做递推:这一过程相当于压栈. 回归:问题逐一解决,最后回到原问题,这一过程叫做回归.这一过程相当于弹栈. 例如:用递归算法求 n! 定义:函数 fact(n)=n!   fact(n-1)

3.3栈与递归实现 3.3.1递归的定义 栈还有一个重要应用是在程序设计语言中实现递归.一个直接调用自己或通过一系列的调用语句间接调用自己的函数,称为递归函数.其中直接调用自己的函数称为直接递归.间接调用自己的函数称为间接递归. 递归是算法设计中最重要的手段.它通常把一个大型的复杂问题转化为一个与原问题相似的规模较小的问题来求解.下面是常见的使用递归的三种情况. (1)定义是递归的 现实中,有许多定义是递归定义的,以n!为例来说明,其定义如下: fact(n)=1n=0//递归终止条件 n*fa

递推法是一种重要的数学方法,在数学的各个领域中都有广泛的运用,也是计算机用于数值计算的一个重要算法.这种算法特点是:一个问题的求解需一系列 的计算,在已知条件和所求问题之间总存在着某种相互联系的关系,在计算时,如果可以找到前后过程之间的数量关系(即递推式),那么,从问题出发逐步推到已 知条件,此种方法叫逆推.无论顺推还是逆推,其关键是要找到递推式.这种处理问题的方法能使复杂运算化为若干步重复的简单运算,充分发挥出计算机擅长于重 复处理的特点. 递推算法的首要问题是得到相邻的数据项间的关系(即递推