Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.53/15: Рейтинг темы: голосов - 15, средняя оценка - 4.53
15 / 15 / 7
Регистрация: 20.11.2013
Сообщений: 92

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

20.11.2013, 02:33. Показов 3090. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток!
Написал программку, которая находит значение 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");
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
20.11.2013, 02:33
Ответы с готовыми решениями:

Набрать с чисел Фибоначчи в интервале от 1 до 100, только просто числа, а также их порядковые номера в ряду Фибоначчи
Помогите с задачкой Набрать с чисел Фибоначчи в интервале от 1 до 100, только просто числа, а также их порядковые номера в ряду...

Определить в заданной последовательности целых чисел количество чисел Фибоначчи
Выполнить задания, если задана последовательность целых чисел длиной n. Определить в заданной последовательности целых чисел количество...

Составить программу поиска первых n четных чисел (n - с клавы), в последовательности чисел Фибоначчи
Нужно составить программу используя do while. У меня не получается, это всё что смог написать. int main() { int n; int i, i1 =...

12
 Аватар для zewer
2356 / 1774 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
20.11.2013, 03:07
возможно так:
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;
0
15 / 15 / 7
Регистрация: 20.11.2013
Сообщений: 92
20.11.2013, 03:18  [ТС]
Я, наверное, криво поставил вопрос =) Проблема заключается не в том, что вы озвучили. Сейчас программа корректно работает. Изначально, ошибка была в этом
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 элемента она уже отображала вполне логичный мусор. Я просто не понимаю как так.
0
413 / 250 / 118
Регистрация: 26.12.2012
Сообщений: 787
20.11.2013, 03:30
У вас массив статический и самый большой размер 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;
}
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
20.11.2013, 03:38
h8er, у тебя массив не статический, а вообще фиг пойми какой. Массивы объявляются только постоянного размера!
int fib[input] выдаст ошибку!
0
15 / 15 / 7
Регистрация: 20.11.2013
Сообщений: 92
20.11.2013, 04:00  [ТС]
Ребят, спасибо вам за помощь в решении, но вопрос немного в другом. В целом, программа работает корректно. Проблема в том, что в моем листинге изначально ошибка заключалась в том, что первый цикл начинал записывать в 3 элемент массива, вместо положенного второго. Из-за того, что 3 элемент не инициализирован, там содержится мусор и дальнейшие действия идут с мусором. Вопрос - почему при поиске 20 элемента программа отображает корректные значения(6765), а при поиске 15 элемента там уже содержится мусор(62600312)? То есть одинаковые действия, но результат разный?

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

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

Добавлено через 8 минут
Откуда взялись эти цифры(17-21) почему только с ними отображает нормальный результат, а в других случаях - мусор? Может быть проблема в компиляторе? Я использую Dev-C++ и компилятор gcc (MinGW я так понимаю)
0
413 / 250 / 118
Регистрация: 26.12.2012
Сообщений: 787
20.11.2013, 12:25
Ваша программа показывает только 2 верных числа 0 и 1 все остальное работа с мусором.
0
413 / 250 / 118
Регистрация: 26.12.2012
Сообщений: 787
20.11.2013, 12:27
Результат работы вашей программы.
Миниатюры
Поиск чисел Фибоначчи  
1
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
20.11.2013, 12:50
Variable length array в C++ вообще нет, тут это работает как фича gcc. Память под такой массив выделяется в стеке, а он по адресам растёт сверху вниз. Соответственно, адрес этого массива и мусор, который там окажется, при прочих равных условиях зависят от размеров. А описанное поведение подходит под случай, когда в f[2] оказывается 0.
1
2 / 2 / 0
Регистрация: 28.09.2013
Сообщений: 72
20.11.2013, 13:16
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); }
}
рекурсивная ф-я поиска чисел фибоначчи
0
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
167 / 167 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
20.11.2013, 13:19
Если нужна не последовательность чисел Фибоначчи, а только 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;
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
20.11.2013, 13:19
Помогаю со студенческими работами здесь

Поиск с использованием ряда Фибоначчи
Помогите, пожалуйста в предоставлении алгоритма. Весь интернет облазил - ничего нету. Хотя я уверен, что такой поиск существует. ...

поиск числа в массиве типа int методом Фибоначчи
расскажите, пожалуйста, на примере. я вообще не могу понять :((

Сумма чисел Фибоначчи
Надо сделать программу: вводится число с клавиатуры, это число должно быть ровно, как бы, количеству чисел Фибоначчи (это числа, начиная с...

Сформировать n чисел Фибоначчи (a1=1, a2=1,ai=ai-1+ai-2)
помогите пожалуйста

Последовательность чисел Фибоначчи
Помогите, пожалуйста, с заданием. Последовательность чисел Фибоначчи U0,U1,... получается по закону U0=0; U1=1; Ui=Ui-1+Ui-2;...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru