フィボナッチ数列とハノタ再帰

フィボナッチ数列の一般的なアルゴリズム:

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int num1=0;
        int num2=1;
        int numn=1;
        int n=10;
        for (int i = 3; i <=n; i++) {
            numn=num1+num2;
            num1=num2;
            num2=numn;
        }
        System.err.println(n+"      ："+numn);
    }

}

フィボナッチ数列の再帰アルゴリズム

 public static int fbnq(int n){

        if(n==1){
            return 0;
        }

        if(n==2){
            return 1;
        }
        return fbnq(n-1)+fbnq(n-2);
    }

再帰アルゴリズムは簡単に見えるが,実際の計算では一般アルゴリズムよりも再帰にかかる時間が多い.
ハノタ再帰:

    public static void move(char pos1,char pos2){
        System.out.println(pos1+"-->"+pos2);
    }
    public static void hanio(int n,char pos1,char pos2,char pos3){
        if(n == 1){
            move(pos1,pos3);
        }else{
            hanio(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            hanio(n-1,pos2,pos1,pos3);
        }
    }

アルゴリズムの考え方:皿が1つしかない場合は、A塔の上の皿からC塔に移すだけです.A塔に2つの皿がある場合は、まずA塔の上の1番皿(番号を上から下へ)をB塔に移動し、A塔の上の2番皿を移動するC塔に、最後にB塔の上の小皿をC塔に移動する.
Aタワーにn個の皿がある場合は、まずAタワー上の最大皿以外の皿(合計n-1個)をBタワー上(Cタワーを介して)に移動し、その後、Aタワー上の最大n号皿をCタワー上に移動し、最後にBタワー上のn-1個の皿をAタワーを介してCタワー上に移動する.