Javaの課題丸投げコミュのフィボナッチ数列～再帰を用いたプログラム～

Algorithm BinaryFib(k):
Input: Nonnegative integer k
Output: The kth Fibonacci number Fk
　　　if k = 0 or 1 then return k
else return BinaryFib(k - 1) + BinaryFib(k - 2)

上の擬似コードはよく見るフィボナッチ数列のアルゴリズムで、理解できるのですが、下の擬似コードは理解できません。なんでも連続的に再帰を使うらしいです。よろしくお願いします。

Algorithm LinearFibonacci(k):
Input: A nonnegative integer k
Output: Pair of Fibonacci numbers (Fk, Fk-1)
if k = 1 then return (k, 0)
else (i, j) ← LinearFibonacci(k - 1)
　　　　　　　　return (i +j, i)

コメント(6)

最初
全て
最新の40件

[1] mixiユーザー 05月03日 05:25

Javaでもなんでもないなぁ…
しかも、どんな答えを求めているのかもわからない。　『理解できない』と主張されても、『私は理解できる』と主張し返すことしか……

んで、どの辺がわからないんでしょうか？
普通に、フィボナッチ数列の定義通りに値を返しているようにしか見えませんけども。

LinearFibonacciは(k) -> (Fk, Fk-1)という関数だから

(i, j) <- LinearFibonacci(k-1)
とすると

i = Fk-1
j = Fk-2
となる

フィボナッチ数列の定義から
Fk = Fk-1 + Fk-2
Fk = i + j

LinearFibonacci(k)は(Fk, Fk-1)のペアを返すので

return (i+j, i)

[2] mixiユーザー 05月03日 10:21

>1
seraphさん申し訳ございません。引数ひとつに対して戻り値２つというのが理解できない部分です。

[3] mixiユーザー 05月03日 12:58

単純なこと過ぎて、どういう意味で理解できないのかわからないですね。

・２つの戻り値を返すという概念そのものがわからない
・２つの戻り値を実現する方法がわからない

前者であれば、『そういうものである』と思うしかありません。　この疑似コードは、関数が複数の戻り値を持つことを許しています。

後者は、言語によって実現方法はいろいろでしょうが、Javaであれば以下のような方法が考えられます。 Javaは、戻り値を複数持てないため、複数の値を持つオブジェクトを返してやります。

・長さが2の配列を返す

public int[] LinearFibonacci(int k){
// 中略
return new int[]{i+j, i};
}

・値を二つ持つ構造体を定義し、そのインスタンスを返す

class Result{
public Result(int aF1, int aF2){
mF1 = aF1;
mF2 = aF2;
}

private int mF1
private int mF2

public int getF1(){ return mF1; }
public int getF2(){ return mF2; }
}

というクラスを定義しておいて

public Result LinearFibonacci(int k){
// 中略
return new Result(i+j, i);
}

その他、C言語であれば、戻り値を受け取る変数へのポインタを引数として渡す、という方法もありますし、Rubyであれば、そもそも複数の戻り値を返すことができたりします。

[4] mixiユーザー 05月03日 13:11

>2: D.D.＠ハードの壁が…さん
> 引数ひとつに対して戻り値２つ

これがどう理解できていないのかが分からないと何とも……。
とりあえず有り得そうな問いと回答を列挙。

「そのような言語を知らない」
→ Common Lisp に多値という機能があります。

「Java でそのような操作をどう実装すればいいか分からない」
→構造体のような自作のクラスのインスタンスか、適当な List の実装クラスのインスタンスを返せば良いです。

[5] mixiユーザー 05月03日 18:18

横からだけど初心者だから勉強になったｗ
ありがとうございます。

ログインすると、みんなのコメントがもっと見れるよ