C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[4]: Fibonacci Sequence

分類:[.NET 全般]　

F0=0;
F1=1;
F2=F0+F1;
F3=F1+F2;
.
.
Fn=Fn-1 + Fn-2

このようになるプログラムを再帰的アルゴリズムを使って書きたいのですが

どうすれば良いでしょうか？

Ｃ＃です。

丸投げしないで自分で作ってみなよ。そのままぢゃん。
こう書いてみたけど＊＊＊になりました・・・だったら推敲してあげられるけど
全部作ってちょんまげ、ならお断り。

■No66423 (Sottyoru さん) に返信
> F0=0;
> F1=1;
> F2=F0+F1;
> F3=F1+F2;
> .
> .
> Fn=Fn-1 + Fn-2
>
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

なので
条件判定でn=0,1,>1のときの戻り値をそれぞれ0,1,F(n-1)+F(n-2)にすればよいです。

using System;

class Program
{
public static int Fibonacci(int n)
{
int a = 0;
int b = 1;
// In N steps compute Fibonacci sequence iteratively.
for (int i = 0; i < n; i++)
{
int temp = a;
a = b;
b = temp + b;
}
return a;
}

static void Main()
{
for (int i = 0; i < 15; i++)
{
Console.WriteLine(Fibonacci(i));
}
}
}

元となるものを作ってみたのですが、ここからどう変えればいいでしょうか・・？

■No66459 (Sottyoru さん) に返信
> 元となるものを作ってみたのですが、ここからどう変えればいいでしょうか・・？

Fibonacciの戻り値が
n=0のとき 0
n=1のとき 1
n>1のとき Fibonacci(n-1) + Fibonacci(n-2)

となればよいです。
Fibonacciの中でループはないです。

再帰って自分自身を呼び出す動作のことを言う。
初めて使うんだとすると概念が難しいかな？かといって解説＝答えそのものだったりして・・・

この例では Fibonacci() 関数の中から Fibonacci() 関数自体を呼び出すように作ると、それが再帰。
再帰の考え方を使うと、プログラム自体は簡単になることが多い。
課題文であげられているロジックをそのまま実装すればいいんだ。

あえて C# でなく C で書いてみると (ってほとんどそのまま C# で使えるんだが)
int f(int n) {
if (n==0) return 0; // f(0)=0 がこれで実現できた (*1)
if (n==1) return 1; // f(1)=1 がこれで実現できた (*2)
return f(n-1)+f(n-2); // f(n)=f(n-1)+f(n-2) が実装できた (*3)
}

(*3) の行で、自分自身を呼び出している＝再帰。
何も考えずに自分自身を呼び出し続けると永遠に終わらないので、
特定条件では自分を呼ぶ代わりに呼び出し元に戻る必要があって、それが (*1) (*2)

# で、たぶんこの次の課題として再帰はループにできる場合があってうんぬん
# 提示コードはそのループに書き換えた実装例だ。
# さらにその次の課題で再帰とループで実行回数がうんぬん、だと勝手に思う

C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[4]: Fibonacci Sequence

過去ログには書き込み不可