Member 12959092 Ответов: 3

Получение ошибки времени выполнения. Пожалуйста, помогите.

Дана формула для вычисления F как
F=F(n-1)+F(n-2)+F(n-1)*F (n-2).
мы должны найти F для значений n.
Для небольших значений . формула работает, но для больших значений мне придется манипулировать ею.

Что я уже пробовал:

#include<bits/stdc++.h>
using namespace std;
int f(long long int F0, long long int F1,long long int n);

#define M 1000000007
int main()
{
    long long int F1,F0,F, T,N;

    cin >> T;
    while(T--)
    {
        cin>>F0>>F1>>N;

        F=f(F0,F1,N);
        cout << F%M << endl;
    }
    return 0;
}

int f(long long int F0, long long int F1,long long int n)
{
     if (n==0)
         return F0%M;
     else if(n==1)
         return F1%M;
     else
     {
         return (int)(((int)pow(F0,f(F0,F1,n-1))%M)
                    * ((int)pow(F1,f(F0,F1,n)))%M)%M;
     }
}

Patrice T

"Ошибка времени выполнения" не является информативной.
Что такое сообщение об ошибке?

nv3

Название "Фибоначчи" вводит в заблуждение. Это не Числа Фибоначчи, у которых нет термина "+ Fn-1 * Fn-2". Следовательно, числовые ряды растут даже быстрее, чем ряды Фибоначчи! Значение: N не может быть выбрано очень большим, и вы придете к пределам представления чисел в 32-битном int.

Member 12959092

хорошо, я обновил код, но он не работает даже для небольших значений. код ошибки не отображается . ideone выдает только ошибку времени выполнения.

Richard MacCutchan

Пожалуйста, не ждите, что мы догадаемся, что происходит. Какая строка кода выдает ошибку, на каких значениях переменных и каков точный текст сообщения об ошибке?

Richard MacCutchan

Написание такого заявления, как
return (int)(((int)pow(F0,f(F0,F1,n-1))%M) * ((int)pow(F1,f(F0,F1,n)))%M)%M;
действительно напрашивается на неприятности.

3 Ответов

Рейтинг:
1

Patrice T

Первая проблема:

Цитата:
Дана формула для вычисления F как
F=F(n-1)+F(n-2)+F(n-1)*F (n-2).

Эта формула не та, что в вашей программе, и ни одна из них не является Фибоначчи.
Итак, утверждение, программа и Фибоначчи - это 3 разные вещи, сделайте свой ум и выберите 1 из них.

---------
Когда вы не понимаете, что делает ваш код или почему он делает то, что делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Он позволяет вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения, это невероятный инструмент обучения.

Отладчик-Википедия, свободная энциклопедия[^]
Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]

Отладчик здесь для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.

Совет:
return (int)(((int)pow(F0,f(F0,F1,n-1))%M)*((int)pow(F1,f(F0,F1,n)))%M)%M;

Разделите эту строку с помощью временных переменных и 1 операции на строку.
Это позволит вам увидеть, что происходит с отладчиком.

Вопрос:
Цитата:
я получаю ошибку времени выполнения в этом коде.

Так как это не стандартный способ вещей. Какой компилятор вы используете? вы запускаете это на своем компьютере ? Какое именно сообщение вы получаете?

0x01AA

Мне нравится этот ответ-5.

Patrice T

Спасибо

Рейтинг:
1

nv3

Итак, вы пытаетесь сделать рекурсию через N. Но тогда вы не должны вызывать свою функцию f с тем же N, что и получили, а только с N-1 и N-2! Вызов f с тем же N вызовет бесконечно глубокую вложенность вызовов f, и вы в конечном итоге получите переполнение стека!

Кроме того, я не вижу, что призывы к военнопленным должны быть хороши. Если вы хотите реализовать функцию, указанную в вашем описании, то эта строка в функции f должна быть:

int fnm1, fnm2;
...
fnm1 = f(F0, F1, n-1);
fnm2 = f(F0, F1, n-2);
return fnm1 + fnm2 + fnm1*fnm2;

Как вы видите, я разделил выражение на два подвыражения, чтобы избежать многократных избыточных вызовов f.

И вообще вся эта история с %M-полная чушь. Просто убери это.

Member 12959092

Спасибо за помощь.

nv3

Добро пожаловать. Не забудьте принять одно или несколько решений, которые помогли вам.

Рейтинг:
0

KarstenK

Цифры фибуначи становятся действительно Хью, так что где-то есть граница. Я думаю, что около 40 его становится проблематичным с размером int. Сделать какой-то вывод для отладки.

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

Я знаю это как:

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