最近正准备找工作呢，熟悉下递归算法，做了几个递归的例子包括汉诺塔问题

package junit.test;

import java.util.Arrays;

import org.junit.Test;


public class excise {
    
    private int[] initArray = {8,2,56,23,14,3,29,88,23,36};
    
    //递归的应用求年龄问题
    /*
     * 用递归算法算出第1个人的年龄为10，第8个人的年龄是多少
     */
    @Test
    public void testLoop() {
        //调用算第8个人的年龄的函数
        int age = getAge(8);
        System.out.println(age);
    }
    /**
     * 算法：第n个人的年龄是第8个人的年龄（getAge(7)）+2
     * 所以可知：第n个人的年龄是第n-1个人的年龄（getAge(n-1)）+2
     * 知道最后返回第一个人的年龄为10
     * @param index
     * @return
     */
    public int getAge(int index) {
        if(index == 1) return 10;
        return getAge(index - 1) + 2;
    }
    
    
    //递归算1-105的和
    @Test
    public void recursionTest() {
        System.out.println(recursion(105));
    }
    
    public int recursion(int num) {
        if(num == 1) return 1;
        return num + recursion(num-1);
    }
    
    //递归算一个数的2进制编码
    @Test 
    public void recirsionTest2() {
        System.out.println(binary(0));
    }
    
    public String binary(int arg) {
        if(arg < 2) return String.valueOf(arg);
        int temp = arg % 2;
        return binary(arg / 2) + String.valueOf(temp);
    }
    
    //汉诺塔问题
    /*
     * 汉诺塔问题是典型的应用递归的问题
     * 题目：桌面上有三个放盘子的地方，其中1号位置放了n个盘子，并且每个上面的盘子都比下面的盘子小，其他两个
     * 地方是空的，要求把1号位置上的盘子全部搬到3号位置上，每次只能搬一个，并且，大盘子不能放到小盘子上。可
     * 以借用2号位置。
     * 
     * 我们假设已经把1号上面的n-1个盘子搬到2号位置上了
     * 接着我们把n盘子搬到3号位置上
     * 然后把2号位置的盘子搬到3号位置上就完成任务了
     * 
     * 
     */
    private int[] hnotaArray = {2, 3, 8, 14, 23, 23, 29, 36, 56, 88};
    @Test
    public void testHnota() {
        int[] hA = hnotaArray;
        try {
            hnota(hnotaArray, 'f', 't', 'l');
        } catch (RuntimeException e) {
            e.printStackTrace();
        }
    }
    public void hnota(int[] x, char a, char b, char c) {
        // 当只有一个盘子的时候直接把盘子从1号盘子直接把到3号盘子上
        if(x.length == 1) { 
            move(x[0], a, c);
            return;
        }
        //把上面的n-1个盘子截取出来
        int[] y = new int[x.length - 1];
        for(int i=0; i<y.length; i++) {
            y[i] = x[i];
        }
        //把1号上面的n-1个盘子搬到2号位置上了
        hnota(y, a, c, b);
        //把n盘子搬到3号位置上
        move(x[y.length], a, c);
        //把2号位置的盘子搬到3号位置上就完成任务了
        hnota(y, b, c, a);
    }
    
    //把一个盘子从src搬到desc上
    public void move(int z, char src, char desc) {
        System.out.println("move " + z + " from " + src + " to " + desc);
    }
}

评论

1 楼 fenshen6046 2010-06-29  

hnota(y, b, c, a); 
这句话错了
应该是
hnota(y, b, a, c);