Javaで学ぶアルゴリズム 第1弾：漸化式

#Javaで学ぶアルゴリズム < 漸化式 >

はじめに

Javaは授業で触れただけで全くの初心者であり，何もわかっていない．なので，基本的なアルゴリズムをJavaで実装し，アルゴリズムの理解を深めるとともに，Javaにも慣れていきたい．
その第1弾として漸化式を扱う．

漸化式

漸化式は高校数学で習ったとおり，$n$番目を$(n-1)$番目を表すものである．これは，繰り返し数が大きくなったときのオーバーフローを防ぐ．漸化式においては，0次は既知でなければならない．

例1: nCr

\left\{
\begin{array}{ll}
\ _nC_r= \frac{n-r+1}{r}\ _nC_{r-1}& ( \geq 0) \\
\ _nC_0= 1& (x \lt 0)
\end{array}
\right.

イメージ図

例2: Hornerの方法

$f(x)=a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + ... + a_1 x + a_0$

このように表される多項式関数を，次の図に示すようにとらえることで，漸化式にできる．

漸化式は，次のようにたくさんできる．

\left\{
\begin{array}{ll}
\ \ \ \  f_n = f_{n-1}x + a_0\\
f_{n-1} = f_{n-2}x + a_0\\
...\\
\ \ \ \  f_2 = f_1x + a_{n-2}\\
\ \ \ \  f_1 = f_0x + a_{n-1}\\
\ \ \ \  f_0 = a_n\\

\end{array}
\right.

これを一般化したものが次の式である．

\left\{
\begin{array}{ll}
\ \ \ \  f_i = f_{i-1}x + a_{n-i}\\
\ \ \ \  f_0 = a_n\\

\end{array}
\right.

例3: パスカルの三角形

この図から以下の式が導かれることが分かる．

\ _nC_r=\ _{n-1}C_{r-1}+\ _{n-1}C_{r}\\

この式を用いて，$\ _nC_r$を求めるプログラムはまた後に学ぶこととする．

その他の例

階乗

\left\{
\begin{array}{ll}
\ \ \ \  n! = n・(n-1)!   \\
\ \ \ \  0! = 1\\

\end{array}
\right.

べき乗

\left\{
\begin{array}{ll}
\ \ \ \  x^n = x・x^{n-1}\\
\ \ \ \  x^0 = 1\\

\end{array}
\right.

フィボナッチ数列

\left\{
\begin{array}{ll}
\ \ \ \  F_n = F_{n-1} + F_{n-2}\\
\ \ \ \  F_1=F_2=0\\
\end{array}
\right.

テイラー展開

$e^x$のテイラー展開
$e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...$

\left\{
\begin{array}{ll}
\ \ \ \  E_n = \frac{x}{n}・E_{n-1}\\
\ \ \ \  E_0 = 1\\

\end{array}
\right.

実装

以下では，上記の例1~例3を漸化式としてJavaで実装したソースコードとそのときの出力をそれぞれ示す．

ソースコード①（nCr）

n_C_r.java

//2020/12/06
//@Yuya Shimizu
//-----------------------
//*     漸化式（nCr）  *
//-----------------------

import java.awt.*;
import java.awt.event.*;

//パネルの設定
class n_C_r_Panel extends Panel{
    //nCr計算のための関数を定義　引数:nとr
    long combi(int n, int r){
        int i;
        long p=1;

        //pの初期値を1（すなわちnC0=1）として漸化式を適用する
        for (i=1; i<=r; i++){
            p=p* (n-i+1)/i;
        }
        return p;
    }

    public void paint(Graphics g){
        int n, r;
        //n=5までのnCrを表示
        for (n=0; n<=5; n++){
            for (r=0; r<=n; r++){
                g.drawString(""+n+"C"+r+"="+combi(n,r), r*60, n*20+20);//後ろ２つの引数は表示座標で，重ならないようにずらしている
            }
        }
    }
}

//フレームの設定
class n_C_r_Frame extends Frame{
    public n_C_r_Frame(){
        setSize(400, 200);//400×200の大きさでフレームを作成
        //ボタンを押したら終了
        addWindowListener(new WindowAdapter(){
            public void windowClosing(WindowEvent e){
                System.exit(0);
            }
        });
        Panel p=new n_C_r_Panel();//パネルオブジェクトpに先ほど設定したパネルを指定
        add(p); //フレームにそのパネルを貼り付け
    }
}

//クラス
public class n_C_r{
    //メイン関数
    public static void main(String[] args){
        Frame w=new n_C_r_Frame();
        w.show();
    }
}

出力

ソースコード①（Hornerの方法）

Horner.java

//2020/12/06
//@Yuya Shimizu
//---------------------------
//*     漸化式（Horner）   *
//---------------------------

import java.awt.*;
import java.awt.event.*;

//パネルの設定
class Horner_Panel extends Panel{
    //Hornerの方法を適用のための関数を定義
    double fn(double x, double a[], int n){
        double p;
        int i;

        p=a[n];
        //pの初期値をa[n]（すなわちnC0=a_n）として漸化式を適用する
        for (i=n-1; i>=0; i--){
            p=p*x + a[i];
        }
        return p;
    }

    public void paint(Graphics g){
        double a[] = {1, 2, 3, 4, 5};
        double x;
        //4次関数におけるx=1~5までの値を表示
        for (x=1; x<=5; x++){
            g.drawString("fn("+x+")="+fn(x, a, 4), 10, (int)(x*20));//後ろ２つの引数は表示座標で，重ならないようにずらしている
        }
    }
}

//フレームの設定
class Horner_Frame extends Frame{
    public Horner_Frame(){
        setSize(300, 200);//300×200の大きさでフレームを作成
        //ボタンを押したら終了
        addWindowListener(new WindowAdapter(){
            public void windowClosing(WindowEvent e){
                System.exit(0);
            }
        });
        Panel p=new Horner_Panel();//パネルオブジェクトpに先ほど設定したパネルを指定
        add(p);//フレームにそのパネルを貼り付け
    }
}

//クラス
public class Horner{
    //メイン関数
    public static void main(String[] args){
        Frame w=new Horner_Frame();
        w.show();
    }
}

出力

$f(x)=a_4x^4+a_3x^3+a_2x^2+a_1x+a_0$
上記の式において，次の条件に基づいた出力を示す．
$a_0=1,a_1=2,a_2=3,a_3=4,a_4=5$

ソースコード③（パスカルの三角形）

Pascal.java

//2020/12/06
//@Yuya Shimizu
//-----------------------------------
//*     漸化式（Pascalの三角形）   *
//-----------------------------------

//パネルの設定
import java.awt.*;
import java.awt.event.*;

class Pascal_Panel extends Panel{
    //nCrを漸化式によって求めるための関数を定義
    long combi(int n, int r){
        int i;
        long p=1;

        //pの初期値を1（すなわちnC0=1）として漸化式を適用する
        for (i=1; i<=r; i++){
            p=p*(n-i+1)/i;
        }
        return p;
    }

    //パスカルの三角形を描画するための関数を定義
    public void paint(Graphics g){
        final int N=12;
        int n,r,t;
        for (n=0; n<=N; n++){
            for (r=0; r<=n; r++){
                g.drawString(""+combi(n, r), (N-n)*20+r*40, n*20+20);//三角形を構成するように配列
            }
        }
    }
}

//フレームの設定
class Pascal_Frame extends Frame{
    public Pascal_Frame(){
        setSize(550, 350);//550×350の大きさでフレームを作成
        //ボタンを押したら終了
        addWindowListener(new WindowAdapter(){
            public void windowClosing(WindowEvent e){
                System.exit(0);
            }
        });
        Panel p=new Pascal_Panel();//パネルオブジェクトpに先ほど設定したパネルを指定
        add(p);//フレームにそのパネルを貼り付け
    }
}

//クラス
public class Pascal{
    //メイン関数
    public static void main(String[] args){
        Frame w=new Pascal_Frame();
        w.show();
    }
}

出力

感想

今回から，Javaでアルゴリズムを学び始めた．1つの項目で，例が多くまとめた分量がPythonのときよりも少し多い気がする．また，Javaはまだ慣れておらず，全体的に学習の時間が少しかかるというのが率直な意見である．ただ，またPythonのときとは別の角度から多くのことが学べそうで，楽しみである．

参考文献

Javaによるはじめてのアルゴリズム入門　　河西 朝雄　著　技術評論社