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

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

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

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

####例1: nCr
```math
\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.
```

イメージ図
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/4cc96e00-eb1e-fe9d-92b0-61762a25edac.png)


####例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$

このように表される多項式関数を，次の図に示すようにとらえることで，漸化式にできる．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/e3a94c6a-e635-473d-5d79-e4582889cefd.png)

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

```math
\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.
```
これを一般化したものが次の式である．

```math
\left\{
\begin{array}{ll}
\ \ \ \  f_i = f_{i-1}x + a_{n-i}\\
\ \ \ \  f_0 = a_n\\
 
\end{array}
\right.
```

####例3: パスカルの三角形
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/48e92800-0fe1-20b8-3ec9-950652585c66.png)
この図から以下の式が導かれることが分かる．

```math
\ _nC_r=\ _{n-1}C_{r-1}+\ _{n-1}C_{r}\\
```
この式を用いて，$\ _nC_r$を求めるプログラムはまた後に学ぶこととする．


####その他の例
#####階乗
```math
\left\{
\begin{array}{ll}
\ \ \ \  n! = n・(n-1)!   \\
\ \ \ \  0! = 1\\
 
\end{array}
\right.
```
#####べき乗
```math
\left\{
\begin{array}{ll}
\ \ \ \  x^n = x・x^{n-1}\\
\ \ \ \  x^0 = 1\\
 
\end{array}
\right.
```
#####フィボナッチ数列
```math
\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!}+...$

```math
\left\{
\begin{array}{ll}
\ \ \ \  E_n = \frac{x}{n}・E_{n-1}\\
\ \ \ \  E_0 = 1\\
 
\end{array}
\right.
```

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

#####ソースコード①（nCr）
```java: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();
	}
}
```

#####出力
![キャプチャ.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/98caaf6a-76e7-2af5-23ea-03c33d83533d.png)



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

```java: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$
![キャプチャ.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/2bebb75d-bc3a-2b25-41d2-2f10a19ddfeb.png)

#####ソースコード③（パスカルの三角形）
```java: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();
	}
}
```

#####出力
![キャプチャ.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/268b711e-4e83-0ee1-9480-d4f3ed1c8537.png)


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

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