Fibonacci数のプログラム

2015 April 26
Mizutani Masahiro

Fibonacci数列 (Subscript[f, 0]), (Subscript[f, 1]), (Subscript[f, 2]), (Subscript[f, 3]), ...., 
 (Subscript[f, 0])=0,(Subscript[f, 1])=1, 
 (Subscript[f, n+2])= (Subscript[f, n+1])+(Subscript[f, n])(n≥0) 
を求めてみよう。ここでの0から始める添字の使い方には意味がある（Fibonacci数列{(Subscript[f, n])}の母関数を考える歳に都合が良い）。

逐次的にFibonacci数を求める

3 つのメモリ f0, f1, f を使ってn番目のFibonacci数 (Subscript[f, n])を計算できる。おそらく、もっとも高速に計算することが可能であるが、繰り返し処理を書かねばならない（面倒なだけではない可能性がある）

たとえばIf文（2条件分岐）を使うアルゴリズムは以下のようである。
fibonacci(n)
	if n == 0
		f = 0
	else if n == 1
		f = 1
	else n > 0
		f0 = 0;
		f1 = 1; 
		for (i = 2, i <= n, i++) 
			f = f0 + f1;
			f0 = f1;
			f1 = f
	end of if
	print(f)

Mathematicaで複数の条件分岐をするためには、 If, Which をつかって実行できる

Mathematicaでは、一連の処理をまとめてモジュール化し、その内部で使った変数（局所変数）や処理をモジュールの外部から隠蔽してブラックボックス化することによって新たな関数を定義できる。

NewFunction[x_, y_, ...] := Module[{局所変数の並び},
	処理；
   	.......;
	 処理;
     ]

Whichを使う

fibonacciNumberWhich[n_]:=Module[{f0=0,f1=1,f,i},
Which[
n==0,f0,
n==1,f1,
n>1,
For[i=2,i≤n,i++,
f=f0+f1;
f0=f1;
f1=f;
];
f]
]

fibonacciNumberWhich[7]

Ifを使う

fibonacciNumberIf[n_]:=Module[{f0=0,f1=1,f,i},
If[
n==0,f0,
If[n==1,f1,
	For[i=2,i≤n,i++,
	f=f0+f1;
	f0=f1;
	f1=f;
	];
	f]
]
]

fibonacciNumberIf[7]

Piecewiseを使う

fibonacciNumberPiecewise[n_]:=Module[{f0=0,f1=1,f,i},
Piecewise[{
{f0,n==0},
{f1,n==1},
{(For[i=2,i≤n,i++,
f=f0+f1;
f0=f1;
f1=f;
];
f),n>1}}]
]

fibonacciNumberPiecewise[5]

演習

SwitchをつかってFibonacci数を求めることができるだろうか？

Fibonacci数列リストを求める

指定したn番目までのFibonacci数列のリスト {(Subscript[f, 0]), (Subscript[f, 1]), (Subscript[f, 2]), (Subscript[f, 3]),..(Subscript[f, n
])}を返す関数を考えよう。

空リストF={} に逐次的に要素を追加する。(Subscript[新しい要素f, n
])をリストF={(Subscript[f, 0]), (Subscript[f, 1]), (Subscript[f, 2]), (Subscript[f, 3]),..(Subscript[f, n-1
])}の最後に追加（append）していく。

Whichを使う

fibonacciNumberListWhich[n_]:=Module[{f0=0,f1=1,f,flist},
Which[
n==0,flist={f0},
n==1,flist={f0,f1},
n>1,
flist={f0,f1};
For[i=2,i≤n,i++,
f=f0+f1;
flist=Append[flist,f];
f0=f1;
f1=f;
]
];
flist
]

fibonacciNumberListWhich[7]

演習

IfおよびPiecewiseをつかって指定したn番目までのFibonacci数リストを返す関数 fibonacciNumberListIf[n] および fibonacciNumberListPiecewise[n] を書いて実行しなさい。

演習: Mathematicaのリスト要素指定

Mathematicaではリスト要素指定は1から始まる。
リスト lst の先頭からk番目要素は、Part[lst,k]　または lst[[i]] のように、[[ と ]] で添字指定する。

f=fibonacciNumberListWhich[8]

Part[f,5]

f[[5]]

f[[1]]

j番目からk番目の連続した要素をリストで返す

f[[2;;5]]

指定した番目リストの要素をリストで返す

Part[f,{2,6,5}]

0番目はMathematica表式の頭部（とても大切）

f[[0]]

FullForm[f]

First

リストの先頭要素を返す

First[f]

Last

リストの末尾（最後の）要素を返す

Last[f]

最後から n 番目の要素は -n で指定

-1 番目とLastは同じ結果

Part[f,-1]

f[[-1]]

再帰的にFibonacci数を求める

漸化式が与えられていれば、関数値を再帰的に求めることが可能。
左辺にある引数 n_ に注意（underbarが付いている）

fibonacciNumberRecursion[0]:=0;
fibonacciNumberRecursion[1]:=1;
fibonacciNumberRecursion[n_]:=fibonacciNumberRecursion[n-1]+fibonacciNumberRecursion[n-2]

fibonacciNumberRecursion[8]