Форум программистов, компьютерный форум CyberForum.ru

Поиск чисел Фибоначчи - C++

Восстановить пароль Регистрация
 
h8er
15 / 15 / 5
Регистрация: 20.11.2013
Сообщений: 92
20.11.2013, 02:33     Поиск чисел Фибоначчи #1
Доброго времени суток!
Написал программку, которая находит значение n-элемента в последовательности Фибоначчи.
Изначально в ней содержалась ошибка (в последствии исправил). Когда я решил проверить программу, то получилось, что при поиске 20 элемента программа ошибалась на один элемент и показывала значение 19 элемента(но при этом корректно отображала значения). Но если я вводил <= 17 или > 21, то естественно отображался мусор. Объясните, пожалуйста, почему такое происходит?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
 
int main()
{
    int input = 0;
    cout << "Element: ";
    cin >> input;
    int fib[input-1];
    fib[0]=0;
    fib[1]=1;    
    for(int i = 3; i < input; ++i)
    {
            fib[i] = fib[i-1] + fib[i-2];
            }
            
    for(int i = 0; i < input; ++i)
    {
            cout << fib[i] << endl;
            }
            
    cout << "Element " << input << " is " << fib[input-1]<<endl;
    system("pause");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zewer
 Аватар для zewer
1022 / 713 / 72
Регистрация: 07.01.2011
Сообщений: 5,369
20.11.2013, 03:07     Поиск чисел Фибоначчи #2
возможно так:
23 строчка коду:
C++
1
cout << "Element " << input << " is " << fib[i]<<endl;
Добавлено через 9 минут
Мне кажется вы что то путаете с инициализацией и работой с масивой.
При работе в цикле, например, вы должны двигатся от 0 елемента до размер-1. А вот при инициализации - просто размер.
Т.е. вместо
C++
1
int fib[input-1];
надо
C++
1
int fib[input];
вместо
C++
1
cout << "Element " << input << " is " << fib[input-1]<<endl;
надо
C++
1
cout << "Element " << input << " is " << fib[input]<<endl;
h8er
15 / 15 / 5
Регистрация: 20.11.2013
Сообщений: 92
20.11.2013, 03:18  [ТС]     Поиск чисел Фибоначчи #3
Я, наверное, криво поставил вопрос =) Проблема заключается не в том, что вы озвучили. Сейчас программа корректно работает. Изначально, ошибка была в этом
C++
1
2
3
4
for(int i = 3; i < input; ++i)
{
      fib[i] = fib[i-1] + fib[i-2];
      }
То есть при первом проходе цикла шло обращение к 3 элементу массива, который не инициализирован. Следовательно, там мусор. Но что интересно, что при запуске такой программы и при поиске 20 элемента(input == 20) она отображала корректные данные, а при поиске, например 15 элемента она уже отображала вполне логичный мусор. Я просто не понимаю как так.
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
20.11.2013, 03:30     Поиск чисел Фибоначчи #4
У вас массив статический и самый большой размер 1,а чисел много вот и будет мусор.Создайте динамический массив
C++
1
2
3
4
    int *fib,input;
    cout << "Element: ";
    cin >> input;
     fib=new int[input];
и не забывайте очищать память
C++
1
delete [] fib;
Добавлено через 7 минут
Вот рабочий код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
using namespace std;
 
int main()
{
   int n,fib = 0,x =1,y = 1;
   cout<<"N=";
   cin>>n;
 
   for (int i=1;i<=n;i++)
{
    if (i <=2)
    fib = x;
    else
       fib = x + y;
       x = y;
       y = fib;
       cout<<"Fibonachi = "<<fib<<"\n";
}
  return 0;
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
20.11.2013, 03:38     Поиск чисел Фибоначчи #5
h8er, у тебя массив не статический, а вообще фиг пойми какой. Массивы объявляются только постоянного размера!
int fib[input] выдаст ошибку!
h8er
15 / 15 / 5
Регистрация: 20.11.2013
Сообщений: 92
20.11.2013, 04:00  [ТС]     Поиск чисел Фибоначчи #6
Ребят, спасибо вам за помощь в решении, но вопрос немного в другом. В целом, программа работает корректно. Проблема в том, что в моем листинге изначально ошибка заключалась в том, что первый цикл начинал записывать в 3 элемент массива, вместо положенного второго. Из-за того, что 3 элемент не инициализирован, там содержится мусор и дальнейшие действия идут с мусором. Вопрос - почему при поиске 20 элемента программа отображает корректные значения(6765), а при поиске 15 элемента там уже содержится мусор(62600312)? То есть одинаковые действия, но результат разный?

Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
h8er, у тебя массив не статический, а вообще фиг пойми какой. Массивы объявляются только постоянного размера!
int fib[input] выдаст ошибку!
Ошибку не выдает и компилируется нормально.

Добавлено через 20 минут
Если кого-нибудь не затруднит, не могли бы вы скомпилировать код из первого сообщения и ввести в программе сначала 20, а затем 15 и посмотреть на результат. Может быть это только у меня такое, а я тут всем мозг выношу зазря =))
takeneo
3 / 3 / 3
Регистрация: 16.08.2013
Сообщений: 22
20.11.2013, 04:19     Поиск чисел Фибоначчи #7
H8er, когда компилятор не выдаёт ошибку это ещё не значит что он понял что вы хотели сосчитать.
Обратите внимание: ваш мусор при каждом новом запуске программы должен быть разным,хотя может и не меняться.
Это из-за того что ваш массив вылез сам из себя.
Так вот ваш массив из трёх элементов представим в виде трёх домов стоящих в ряд на очень длинной улице. Очень длинная улица - это вся оперативная память вашего компьютера. Эти три дома стоят в одном квартале(ваш массив), когда адрес массива вылезает за пределы этого массива (меньше 0, или больше 2), то программа берёт адрес дома из соседнего квартала. C++ это почему-то разрешает, поймёте это когда научитесь работать с арифметикой указателей на адреса.
Ошибку не выдаёт,потому-что считает что вы супер-мега программист.
h8er
15 / 15 / 5
Регистрация: 20.11.2013
Сообщений: 92
20.11.2013, 04:48  [ТС]     Поиск чисел Фибоначчи #8
Цитата Сообщение от takeneo Посмотреть сообщение
H8er, когда компилятор не выдаёт ошибку это ещё не значит что он понял что вы хотели сосчитать.
Обратите внимание: ваш мусор при каждом новом запуске программы должен быть разным,хотя может и не меняться.
Это из-за того что ваш массив вылез сам из себя.
Так вот ваш массив из трёх элементов представим в виде трёх домов стоящих в ряд на очень длинной улице. Очень длинная улица - это вся оперативная память вашего компьютера. Эти три дома стоят в одном квартале(ваш массив), когда адрес массива вылезает за пределы этого массива (меньше 0, или больше 2), то программа берёт адрес дома из соседнего квартала. C++ это почему-то разрешает, поймёте это когда научитесь работать с арифметикой указателей на адреса.
Ошибку не выдаёт,потому-что считает что вы супер-мега программист.
Спасибо за информацию, я прекрасно понимаю, о чем вы говорите, но поймите, вопрос не в этом.
Мое непонимание в том, что работа заведомо ошибочной программы дает верные результаты(пусть и со смещением -1), но только в том случае, если водить значения >17 и < 21. В этом диапазоне значений программа дает корректные результаты, в случае других значений(например 15), соответственно, неправильные результаты. Вот и вопрос - из-за чего такое поведение?

Добавлено через 8 минут
Откуда взялись эти цифры(17-21) почему только с ними отображает нормальный результат, а в других случаях - мусор? Может быть проблема в компиляторе? Я использую Dev-C++ и компилятор gcc (MinGW я так понимаю)
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
20.11.2013, 12:25     Поиск чисел Фибоначчи #9
Ваша программа показывает только 2 верных числа 0 и 1 все остальное работа с мусором.
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
20.11.2013, 12:27     Поиск чисел Фибоначчи #10
Результат работы вашей программы.
Миниатюры
Поиск чисел Фибоначчи  
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
20.11.2013, 12:50     Поиск чисел Фибоначчи #11
Variable length array в C++ вообще нет, тут это работает как фича gcc. Память под такой массив выделяется в стеке, а он по адресам растёт сверху вниз. Соответственно, адрес этого массива и мусор, который там окажется, при прочих равных условиях зависят от размеров. А описанное поведение подходит под случай, когда в f[2] оказывается 0.
maxim12345
2 / 2 / 0
Регистрация: 28.09.2013
Сообщений: 72
20.11.2013, 13:16     Поиск чисел Фибоначчи #12
C++
1
2
3
4
5
6
7
int Fib (int x)
{
    if (x==1||x==2)
        return 1;
    else
    { return Fib(x-2)+Fib(x-1); }
}
рекурсивная ф-я поиска чисел фибоначчи
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2013, 13:19     Поиск чисел Фибоначчи
Еще ссылки по теме:

поиск числа в массиве типа int методом Фибоначчи C++
Сумма чисел Фибоначчи C++
Сумма чисел Фибоначчи C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
20.11.2013, 13:19     Поиск чисел Фибоначчи #13
Если нужна не последовательность чисел Фибоначчи, а только n-элемент, то думаю стоит воспользоваться алгоритмом нахождения за O(log N).
Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll fib(ll n)
{
    ll a=1,b=1,
        c=1,d=0,
        ta,tb,tc,td,rc=0,rd=1;
    while(n)
    {
        if(n & 1)
        {
            tc=rc*a+rd*c;
            td=rc*b+rd*d;
            rc=tc;rd=td;
        }
        ta=a*a+b*c;
        tb=a*b+b*d;
        tc=c*a+d*c;
        td=c*b+d*d;
        a=ta;b=tb;c=tc;d=td;
        n>>=1;
    }
    return rc;
}
Yandex
Объявления
20.11.2013, 13:19     Поиск чисел Фибоначчи
Ответ Создать тему
Опции темы

Текущее время: 17:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru