欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java递归算法的使用分析

程序员文章站 2024-02-11 14:09:22
递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。 问题1:一列数的规则如下: 1...

递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。

问题1:一列数的规则如下: 1、1、2、3、5、8、13、21、34 ,求第30位数是多少?使用递归实现

复制代码 代码如下:

public class fibonaccisequence {
    public static void main(string[] args){
        system.out.println(fribonacci(9));

    }
    public static int fribonacci(int n){
        if(n<=2)
            return 1;
        else
            return fribonacci(n-1)+fribonacci(n-2);

    }
}

问题2:汉诺塔问题

汉诺塔(又称河内塔)问题其实是印度的一个古老的传说。

开天辟地的神勃拉玛(和中国的盘古差不多的神吧)在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一 个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上 面。计算结果非常恐怖(移动圆片的次数)18446744073709551615,众僧们即便是耗尽毕生精力也不可能完成金片的移动了。

要求:输入一个正整数n,表示有n个盘片在第一根柱子上。输出操作序列,格式为“移动 t从 x 到 y”。每个操作一行,表示把x柱子上的编号为t的盘片挪到柱子y上。柱子编号为a,b,c,你要用最少的操作把所有的盘子从a柱子上转移到c柱子上。

复制代码 代码如下:

public class hanio {
    public static void main(string[] args){
        int i=3;
        char a ='a',b='b',c='c';
        hanio(i,a,b,c);
    }
    public static void hanio(int n,char a,char b,char c){
        if(n==1)
            system.out.println("移动"+n+"号盘子从"+a+"到"+c);
        else{
            hanio(n-1,a,c,b);//把上面n-1个盘子从a借助b搬到c
            system.out.println("移动"+n+"号盘子从"+a+"到"+c);//紧接着直接把n搬动c
            hanio(n-1,b,a,c);//再把b上的n-1个盘子借助a搬到c
        }
    }
}