Qiita初投稿
学習課題のアウトプット用の記事です。
使用言語はPHP
フィボナッチ数列とは
(Fn) は、次の漸化式で定義される：
F0 = 0,
F1 = 1,
Fn+2 = Fn + Fn+1 (n ≥ 0)
第0～22項の値は次の通りである：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …
Wikipediaより参照
フィボナッチ数 - Wikipedia
課題内容
学習課題の一つで
家のお手伝いを毎日継続すると、継続日数 n 日に応じて、その日にもらえるお小遣いの金額が増えていきます。お小遣いの金額は以下の条件に従ってもらうことができます。
f(0) = 0 円
f(1) = 1 円
f(n) = f(n-1) + f(n-2) 円 (n ≧ 2)
整数 n に対して、n 日間お手伝いを継続した時のお小遣いの金額を算出する関数 fibonacci を定義してください。
という内容だった。
この時、与えられた式やWikipediaの漸化式をそのまま使おうとばかり考え、どうやってプログラムに書けばいいかと悩んでいた。
考え方
求めたいフィボナッチ数(f(n))は、フィボナッチ数列の「一つ前の数(f(n-1))」と「二つ前の数(f(n-2))」を足して求められる。
フィボナッチ数列を作るためのループ処理を考える。
- どこからどこまでか
開始は1からとして考え、引数nまでのループ処理をする。
-
一つ前の数字と二つ前の数字の表現
変数を三つ用意し、$a,$b,$cとした。-
$c= "求めたいフォボナッチ数" f(n) -
$a= "二つ前の数" f(n-2) -
$b= "一つ前の数" f(n-1)
$aには0、$bには1をそれぞれ代入しておく。(数列の最初の二つの数) -
- 処理の内容
-
$cに$b,$aを足した数が代入される -
$aは次の計算で、今の$bの数が代入される -
$bは次の計算で、今の$cの数が代入される
-
- ループ処理が終わったら出力
結果
<?php
function fibonacci($n){
if($n <= 0){
return;
}
$a = 0;
$b = 1;
$c = 1;
for($i = 1; $i < $n; $i++){
$c = $a + $b;
$a = $b;
$b = $c;
}
echo $c;
}
fibonacci(22);
?>
引数に1が入力されたとき、$cに予め1を代入しておくことで、ループ処理に入らずそのまま出力される。
引数に0以下の数が入力されたとき、returnで何も出力されず終わる。
実行結果
引数に22を入力
17711
Wikipediaにあった第22項の値と一致している。
その他の実行結果
引数に0を入力
引数に1を入力
1
引数に2を入力
1
引数に3を入力
2
引数に30を入力
832040
まとめ
見たものをそのまま使おうとするのではなく、本質を理解することで考え方を変えることができた。
結果は思ったよりシンプルなコードになった。
もっと効率のいいコードもあるかもしれないが、課題解決におけるアプローチの仕方には様々な方法があると学ぶことができた。
あと、この家のお小遣い事情は改めた方がいいと思った。