Не работает рекурсия внутри al oop в C ++ - PullRequest
Новая
       7

Не работает рекурсия внутри al oop в C ++

1 голос
/ 11 апреля 2020

У меня есть проблема для решения в C ++, которая заключается в следующем: 1 + (1/2!) + (1/3!) + (1/4!) + (1/5!) ... и так на

Код, который я написал для этого кода, выглядит следующим образом 

#include <iostream>
using namespace std;

int fact(int);

int main()
{
    int n; float sum=0;
    cout<<"Enter number of terms:";
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        sum = sum + (float)(1/(fact(i)));
    }

    cout<<endl<<"The sum is :"<<sum;
    return 0;
}

int fact(int x)
{
    if(x == 0 || x == 1)
        return 1;
    else
        return x * fact(x-1);
}

Приведенный выше код не возвращает никакого вывода. Ранее я вычислял факториал без использования для l oop. И рекурсия сработала.

Ответы [ 5 ]

2 голосов
/ 11 апреля 2020

Преступник здесь Интегральное деление в C ++.

Если один из операндов является целым числом, C ++ выполняет интегральное деление, которое по своей природе отбрасывает дробную часть . Если хотя бы один из них является float или double, результат сохраняется. Например, проверьте вывод следующих операторов: 

cout<<(1/5);   // Gives 0 Umm.. weird

cout<<(1/5.0); // Gives 0.2 Umm.. works

cout<<(1.0/5)  // Gives 0.2 Umm.. also works

Теперь в вашем коде измените: 

sum = sum + 1/fact(i);

на 

sum = sum + 1/(1.f*fact(i));

или typecast явно, по крайней мере, один из операндов . 

sum += 1/(float)(fact(i));

Также обратите внимание, что: 

(float)(1/5)

не будет работать, так как приведение типов происходит после целочисленного деления, поэтому убедитесь, что в по крайней мере один из операндов - это число с плавающей запятой или двойное число перед делением.

Вы можете узнать больше о том, как работает интегральное деление в C ++.

Полный рабочий код для справки: 

#include <iostream>
#include <iomanip>  //for precision
using namespace std;

int fact(int x){
    if(x == 0 || x == 1)
        return 1;
    else
        return x * fact(x-1);
}

int main(){
    int n; 
    float sum=0;

    //to set precision upto 3 decimal places
    cout << std::fixed;
    cout << std::setprecision(3);

    cout<<"Enter number of terms: ";
    cin>>n;

    for(int i=1;i<=n;i++){
        sum = sum + 1/(1.f*fact(i));
        //sum += 1/(float)(fact(i));  or use typecasting like this
    }

    cout<<"The sum is :"<<sum<<endl;
    return 0;
}

Чтобы узнать больше о настройке точности проверки это .

1 голос
/ 11 апреля 2020

Проблема в вашем базовом случае в рекурсии: 

int fact(int x)
{
    if(x == 0 || x == 1)
        return 0;
...

, при котором все факториалы обнуляются, а затем вы делите на ноль: 1/(fact(i)) и cra sh вашей программы.

Правильный базовый случай - 1, и вам нужно избегать целочисленного деления с помощью 1.0f/fact(i).

Вы бы быстро заметили ошибку базового случая, если бы протестировали функцию fact на ее собственный первый.

0 голосов
/ 11 апреля 2020

Вы можете избежать повторного вычисления факториала, если у вас есть рабочий член внутри l oop: 

inline float inv_fseries(std::size_t lim) {
  float term = 1.f;
  float sum = 1.f;
  for (std::size_t i = 1; i <= lim; ++i) {
     term /= static_cast<float>(i);
     sum += term;
  }
  return sum;
}

Также можно избежать static_cast, используя переменную float, но осторожно должно быть дано, чтобы избежать связанных с плавающей запятой ошибочных ошибок (не каждое целое число может быть представлено float) 

inline float inv_fseries(std::size_t lim) {
  float term = 1.f;
  float sum = 1.f;
  float const bound = static_cast<float>(lim) + 0.5f;
  for (float i = 1.f; i <= bound; ++i) {
     term /= i;
     sum += term;
  }
  return sum;
}

Можно утверждать, что это имеет худшее время выполнения, потому что мы заменены целочисленные операции на операции с плавающей точкой. Но в тот момент, когда это становится проблемой, ваш предел n настолько велик, что колоссальные O (n ^ 2) в исходном алгоритме по сравнению с O (n) этого алгоритма перевешивают все накладные расходы от умножения с плавающей запятой.

На заметку по теме: никогда вставлять предоставленные пользователем числа в рекурсивные функции, если глубина рекурсии зависит от этих чисел. Буквально название этого сайта. ;)

0 голосов
/ 11 апреля 2020

Я исправил код сннипета .
1.) Вы вернули 0; в основном до печати суммы.
2.) В факториальной функции вы возвращаете 0, который даст бесконечность при делении на любое число. Это вызовет исключение. #include использование пространства имен std; 

int fact(int);

int main()
 {
  int n; float sum=0;
  cout<<"Enter number of terms:";
  cin>>n;

  for(int i=1;i<=n;i++)
  {
    sum = sum + (float)(1.0/(fact(i)));
  }
  cout<<"The sum is :"<<sum<<endl;

  return 0;
  }

 int fact(int x)
 {
    if(x == 0 || x == 1)
       return 1;
    else
       return x * fact(x-1);
 }
0 голосов
/ 11 апреля 2020

ПРОБЛЕМА

Проблема здесь заключается в отсутствии правильного приведения типов в расширяющихся примитивных преобразованиях. Любая операция между 2 операторами int будет производить int, а приведение всего выражения приведет к потере значения. В этом случае «сумма = сумма + 1 / факт (я);» Линия имеет две проблемы. fact (i), являющийся значением int, 1 / fact (i) будет возвращать int (считайте 0, для i> 1), а затем переменная sum будет int, поэтому даже если 1 / fact (i) возвращает двойное значение , sum просто сможет содержать неявно приведенное значение типа int. Пожалуйста, обратитесь https://docs.microsoft.com/en-us/cpp/cpp/type-conversions-and-type-safety-modern-cpp?view=vs-2019

РЕШЕНИЕ

Для этого возможно несколько решений.

  1. Самое простое - вы можете просто объявить сумма должна быть двойной и изменить строку внутри l oop на - sum = sum + 1.0 / fact (i);

  2. Или вы можете объявить сумму двойной и введите или объявите возвращаемый тип факта (i) как двойной.

И просто для того, чтобы я не забыл, я полагаю, что вы действительно вернете или напечатаете окончательное значение суммы чтобы проверить этот код.

Надеюсь, это полезно и понятно!

...