35

なぜか理解に苦しむ

#include <iostream>

using namespace std;

int fib(int x) {
    if (x == 1) {
        return 1;
    } else {
        return fib(x-1)+fib(x-2);
    }
}

int main() {
    cout << fib(5) << endl;
}

セグメンテーション違反が発生します。x が 1 になると、最終的には返されませんか?

4

13 に答える 13

150

あなたx==2が呼び出すfib(1)とfib(0)：

return fib(2-1)+fib(2-2);

が評価されたときに何が起こるかを考えてみましょうfib(0)...

于 2009-10-05T07:52:49.447 に答える
40

その理由は、フィボナッチ数列が0と1の2つの既知のエンティティで始まるためです。コードは、そのうちの1つ（1つ）のみをチェックします。

コードを次のように変更します

int fib(int x) {
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2);
}

0と1の両方を含める。

于 2009-10-05T07:56:34.467 に答える
11

反復アルゴリズムを使用しないのはなぜですか?

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}
于 2009-10-05T08:14:08.113 に答える
7

定義上、フィボナッチ数列の最初の 2 つの数値は 1 と 1、または 0 と 1 です。したがって、それを処理する必要があります。

#include <iostream>
using namespace std;

int Fibonacci(int);

int main(void) {
    int number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer.\n";
    else
        cout << number << " Fibonacci is: " << Fibonacci(number) << endl;
}

int Fibonacci(int x) 
{
    if (x < 2){
     return x;
    }     
    return (Fibonacci (x - 1) + Fibonacci (x - 2));
}
于 2014-08-12T18:03:40.683 に答える
3

このソリューションは短く、見栄えが良いと思います：

long long fib(int n){
  return n<=2?1:fib(n-1)+fib(n-2);
}

編集: jweyrich が述べたように、真の再帰関数は次のようになります。

long long fib(int n){
      return n<2?n:fib(n-1)+fib(n-2);
    }

(なぜなら fib(0) = 0. ただし、上記の再帰式に基づくと、fib(0) は 1 になります)

再帰アルゴリズムを理解するには、紙に描く必要があります。最も重要なことは、「通常どおりに考える」ことです。

于 2012-07-07T04:54:24.463 に答える
3

これは、再帰によるフィボナッチ問題に対する私の解決策です。 

#include <iostream>
using namespace std;

int fibonacci(int n){
    if(n<=0)
        return 0;
    else if(n==1 || n==2)
        return 1;
    else
        return (fibonacci(n-1)+fibonacci(n-2));
}

int main() {
    cout << fibonacci(8);
    return 0;
}
于 2016-03-15T13:13:24.390 に答える
2 
int fib(int n) {
    if (n == 1 || n == 2) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

フィボナッチ数列では、最初の 2 つの数は常に 1 に続き、値が 1 または 2 になるたびに 1 を返さなければなりません

于 2013-03-03T15:00:34.157 に答える
1 
if(n==1 || n==0){
    return n;
}else{     
    return fib(n-1) + fib(n-2);
}

ただし、再帰を使用してフィボナッチ数を取得することは、関数が受け取った数よりも約 8.5 回呼び出されるため、悪い習慣です。たとえば、30 のフィボナッチ数 (1346269) を取得するには、関数が 7049122 回呼び出されます。

于 2013-12-10T09:19:24.233 に答える
1 
int fib(int x) 
{
    if (x == 0)
      return 0;
    else if (x == 1 || x == 2) 
      return 1;
    else 
      return (fib(x - 1) + fib(x - 2));
}
于 2013-04-29T07:10:00.327 に答える
1 
int fib(int x) 
{
    if (x < 2)
      return x;
    else 
      return (fib(x - 1) + fib(x - 2));
}
于 2013-09-17T12:38:41.187 に答える
0

私の解決策は次のとおりです。

#include <iostream>


    int fib(int number);

    void call_fib(void);

    int main()
    {
    call_fib();
    return 0;
    }

    void call_fib(void)
    {
      int input;
      std::cout<<"enter a number\t";
      std::cin>> input;
      if (input <0)
      {
        input=0;
        std::cout<<"that is not a valid input\n"   ;
        call_fib();
     }
     else 
     {
         std::cout<<"the "<<input <<"th fibonacci number is "<<fib(input);
     }

    }





    int fib(int x)
    {
     if (x==0){return 0;}
     else if (x==2 || x==1)
    {
         return 1;   
    }

    else if (x>0)
   {
        return fib(x-1)+fib(x-2);
    }
    else 
     return -1;
    }

fib(0)=0 を返し、負の場合はエラーを返します

于 2016-11-02T21:18:04.527 に答える