この問題も、標準入力から整数を1つだけ受け取ります。
<?php
fscanf(STDIN, "%d", $N);
リュカ数を、再帰呼び出しで計算してみましょう。
再帰呼び出しとは、関数自身を呼び出して処理を行う手法です。
$L[0]は、2です。
$L[1]は、1です。
$L[i]は、$L[i-1]と$L[i-2]を足したものです。
これをそのまま、実装して行きます。
function calcL($n) {
switch ($n) {
case 0:
return 2;
break;
case 1:
return 1;
break;
default:
return calcL($n - 1) + calcL($n - 2);
}
}
完成しました。それでは、paiza.ioで試しに実行してみます。
やってみると、入力例2の「86」でタイムアウトになってしまいます。
なぜでしょうか？
これは、calcL(86)実行時にcalcL(85)とcalcL(84)が呼び出され、calcL(85)の処理でcalcL(84)とcalcL(83)が呼び出され……となるのですが、1回計算されたcalcL(84)などがあったとしても、それを無視してまた別にcalcL(84)の計算をしようとするので、膨大な量の計算が発生してしまうからです。
……という訳で、一度計算した結果はとっておき、それを利用するように改造します。
function calcL($n) {
global $array;
$array[0] = 2;
$array[1] = 1;
if (isset($array[$n])) {
return $array[$n];
} else {
$array[$n] = calcL($n - 1) + calcL($n - 2);
return $array[$n];
}
}
関数のローカル変数は再帰呼び出しの際にスコープの違いにより参照されなくなってしまいますので、グローバルの変数（配列） $array を設定しています。
さきほどのプログラムでは1分経っても答えは返ってきませんが、改造した方のプログラムでは、0.03秒ほどで計算結果が表示されます。