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

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

20.11.2013, 02:33. Показов 3100. Ответов 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
Ответ Создать тему
Новые блоги и статьи
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru