Ряд Фибоначчи в C ++: управление достигает конца не пустой функции - PullRequest
0 голосов
/ 05 марта 2012

, практикуя рекурсивные функции, я написал этот код для рядов Фибоначчи, и (факториал) программа не запускается и выдает ошибку «Управление достигает конца функции, не являющейся пустотой», я подозреваю, что это последняя итерация, достигающая нуля, и не зная, что делать в минус целых. Я пытался вернуть 0, вернуть 1, но ничего хорошего. какие-либо предложения?

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <ctime>
using namespace std;

int fib(int n) {
    int x;
        if(n<=1) {
            cout << "zero reached \n";
            x= 1;
        } else {
            x= fib(n-1)+fib(n-2);
            return x;
        }
    }




int factorial(int n){
    int x;
    if (n==0){
        x=1;
       }
    else {
            x=(n*factorial(n-1));
            return x;
        }

    }

Ответы [ 8 ]

3 голосов
/ 05 марта 2012

Изменить

else if (n==1)
        x=1;

на

else if (n==1)
        return 1;

Тогда fib() должно работать для всех неотрицательных чисел.Если вы хотите упростить это и заставить его работать для всех чисел, используйте что-то вроде:

int fib(int n) {
    if(n<=1) {
        cout << "zero reached \n";
        return 1;
    } else {
        return fib(n-1)+fib(n-2);
    }
}
1 голос
/ 05 марта 2012

«Управление достигает конца не пустой функции»

Это предупреждение времени компиляции (которое может быть обработано как ошибка с соответствующими флагами компилятора).Это означает, что вы объявили свою функцию как не-void (в данном случае int), и все же есть путь через вашу функцию, для которого нет return (в данном случае if (n == 1)).

Одна из причин, по которой некоторые программисты предпочитают иметь только один оператор return на функцию в самой последней строке функции ...

    return x;
}

... состоит в том, что онаЛегко видеть, что их функции возвращаются соответствующим образом.Это также может быть достигнуто путем сохранения очень коротких функций.

Вы также должны проверить свою логику в реализации factorial(), у вас есть бесконечная рекурсия в ней.

0 голосов
/ 19 июля 2013

Пока автор спрашивает, что технически не так с рекурсивной функцией, вычисляющей числа Фибоначчи, я хотел бы заметить, что описанная выше рекурсивная функция решит задачу во времени, экспоненциально растущем с n.Я не хочу препятствовать созданию совершенного C ++ из него.Однако известно, что задача может быть вычислена быстрее.Это менее важно для малых п.Вам нужно обновить знания умножения матриц, чтобы понять объяснение.Рассмотрим оценку степеней матрицы:

power n = 1  | 1 1 |
             | 1 0 | = M^1

power n = 2  | 1 1 |   | 1 1 |   | 2 1 |
             | 1 0 | * | 1 0 | = | 1 1 | = M^2

power n = 3  | 2 1 |   | 1 1 |   | 3 2 |
             | 1 1 | * | 1 0 | = | 2 1 | = M^3

power n = 4  | 3 2 |   | 1 1 |   | 5 3 |
             | 2 1 | * | 1 0 | = | 3 2 | = M^4

Видите ли вы, что матричные элементы результата напоминают числа Фибоначчи?Продолжить

power n = 5  | 5 3 |   | 1 1 |   | 8 5 |
             | 3 2 | * | 1 0 | = | 5 3 | = M^5

Ваше предположение верно (это подтверждается математической индукцией, попробуйте или просто используйте)

power n      | 1 1 |^n         | F(n + 1) F(n)     |
             | 1 0 |   = M^n * | F(n)     F(n - 1) |

При умножении матриц применяйте хотя бы так называемое "возведение в степень"путем возведения в квадрат ".Напомню:

      if n is odd (n % 2 != 0), then M * (M^2)^((n - 1) / 2)
M^n = 
      if n is even (n % 2 == 0), then (M^2)^(n/2)

Без этого ваша реализация получит временные свойства итерационной процедуры (которая все же лучше, чем экспоненциальный рост).Добавьте свой прекрасный C ++, и он даст достойный результат.Однако, поскольку нет предела совершенства, это также может быть улучшено.В частности, существует так называемое «быстрое удвоение» для чисел Фибоначчи.Это имело бы те же асимптотические свойства, но с лучшим временным коэффициентом для зависимости от времени.Когда кто-то скажет O (N) или O (N ^ 2), фактические постоянные коэффициенты будут определять дальнейшие различия.Один O (N) может быть еще лучше, чем другой O (n).

0 голосов
/ 19 июля 2013

В выражениях if-else нет ничего плохого. Код C ++, применяющий их, похож на другие языки. Чтобы подчеркнуть выразительность C ++, можно написать для факториала (как пример):

int factorial (int n) {return (n> 1)? n * факториал (n - 1): 1;}

Эта иллюстрация, использующая «истинно» условный оператор C / C ++ ?:, и другие предложения, приведенные выше, лишены производственной силы. Было бы необходимо принять меры против переполнения заполнителя (int или unsigned int) для результата и с рекурсивными решениями, переполняющими стек вызовов. Понятно, что максимальное n для факториала может быть вычислено заранее и служит для защиты от «плохих входов». Тем не менее, это может быть сделано на других уровнях косвенности, контролирующих поступление n в функцию факториала. Версия выше возвращает 1 для любого отрицательного n. Использование unsigned int предотвратит обработку отрицательных входных данных. Однако это не предотвратит возможную ситуацию преобразования, созданную пользователем. Таким образом, меры против отрицательных входных данных также могут быть желательны.

0 голосов
/ 05 марта 2012

Иногда ваш компилятор не может сделать вывод, что ваша функция на самом деле имеет нет пропущенного возврата. В таких случаях существует несколько решений:

Пусть

if (foo == 0) {
    return bar;
} else {
    return frob;
}

Перестрой свой код

if (foo == 0) {
    return bar;
}
return frob;

Это хорошо работает, если вы можете интерпретировать оператор if как своего рода брандмауэр или предварительное условие.

преждевременное прекращение ()

(см. Комментарий Дэвида Родригеса.)

if (foo == 0) {
    return bar;
} else {
    return frob;
}
abort(); return -1; // unreachable

Верните что-нибудь еще соответственно. Комментарий говорит вам и другим программистам, почему это так.

бросок

#include <stdexcept>

if (foo == 0) {
    return bar;
} else {
    return frob;
}

throw std::runtime_error ("impossible");

Не контрмер: Точка выхода из одной функции

Не используйте один возврат-на-функцию a.k.a. одиночная точка-выход-точка в качестве обходного пути. Это устарело в C ++, потому что вы почти никогда не знаете, куда выйдет функция:

void foo(int&);

int bar () {
    int ret = -1;
    foo (ret);
    return ret;
}

Выглядит красиво и похоже на SFEP, но обратное проектирование сторонней проприетарной libfoo показывает:

void foo (int &) {
    if (rand()%2) throw ":P";
}

Кроме того, это может привести к ненужной потере производительности:

Frob bar ()
{
    Frob ret;
    if (...) ret = ...;
    ...
    if (...) ret = ...;
    else if (...) ret = ...;
    return ret;
}

потому что:

class Frob { char c[1024]; }; // copy lots of data upon copy

И каждая изменяемая переменная увеличивает цикломатическую сложность вашего кода. Это означает, что больше кода и больше состояния для тестирования и проверки, в свою очередь, означает, что вы высасываете больше состояния из мозга сопровождающих, в свою очередь, означает меньшее качество мозга сопровождающего.

Последнее, что не менее важно: некоторые классы не имеют конструкции по умолчанию, и вам, возможно, придется написать действительно поддельный код, если это вообще возможно:

File mogrify() {
    File f ("/dev/random"); // need bogus init
    ...
}

Не делай этого.

0 голосов
/ 05 марта 2012

Запускается раздел else вашей функции factorial():

    x=(factorial(n)*factorial(n-1));

Это приводит к бесконечной рекурсии.Должно быть:

    x=(n*factorial(n-1));
0 голосов
/ 05 марта 2012

Предположительно, факториальная функция должна возвращать n * factorial (n-1) для n> 0.

x=(factorial(n)*factorial(n-1)) следует читать x = n * factorial(n-1)

0 голосов
/ 05 марта 2012

В вашем втором базовом случае (n == 1) вы никогда не return x; или 'return 1;'

...