Числа Фибоначчи: иногда выводятся отрицательные значения

@Tengel · Регистрация: 08.10.2008

Author24 — интернет-сервис помощи студентам

У меня вот какая проблема: Числа Фибоначчи определяются рекуррентной формулой:

f0 = 0; f1 = 1; fn = fn-1 + fn-2;

Начало последовательности имеет вид 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... .
Входные данные:
В единственной строке находится число N (0 <= N <= 10000).
Выходные даны:
Выведите N-те число Фибоначчи.
Пример введения
7
Пример выведения
13
я програмку написал, но она мне иногда выводит отрецательные числа...подскажите что мне сделать, что бы ета программа корректно работала.
вот и она:

C++

#include <iostream>
 
using namespace std;
void main()
{
    int n;
    cout << "Введите номер числа :";
    do {cin>>n;} while ((n<0)&&(n>10000));
    long long fib[10000];
    fib[0]=0;
    fib[1]=1;
    for (int i=2;i<9999;i++)
    {
        fib[i] = fib[i-1]+fib[i-2];
    }
    cout<<"Число с номером "<<n<<"ето:";
    cout<<fib[n];
    system("pause");
}

@ABTOP · 11.10.2008, 10:42

Знакомая история... Просто переменная выходит за допустимый диапазон своего типа, вот число и отрицательное... Попробуй воспользоваться типом unsigned long int или unsigned long double... Думаю его хватит...

@Tengel · 11.10.2008, 10:55 **[ТС]**

сделал так, но числа выводятса меньшие, чем когда я напишу unsigned long long, как тип массива......но что так, что так, ответ одинаков:Неверный ответ

и что не делал уже, все равно корректно не работает....

@Lord_Voodoo · 11.10.2008, 11:23

Tengel, я недавно писал прогу по остаткам от деления чисел фибоначчи на большие числа, хватало long long, но там алгоритм очень замороченный, а вам для вычисления даже двухтысячного числа 80 бит(long double) ну никак не хватит... либо ищите библиотеки для работы с большими числами, либо ограничьтесь 1000...

14.10.2008, 21:34

Poprobuy ispolzovat' clojenie dlinnix dvux chisel' s ispolzovaniem String, Esli tebe nujn@ ya moga dat' tebe code dlya clojenita dlinnix chisel' (okolo ~ 250 cimvolov). Make that as function with 2 arguments...

@Lord_Voodoo · 15.10.2008, 09:37

вот тебе рабочий код на любой фибоначчи:

C++

#include <iostream>
#include <math.h>
using namespace std;
const int N = 220;
int ctrl = 0;
div_t t;
void add(int a[N], int b[N], int c[N]){
  memset(c, 0, sizeof(int)*N);
  int i = 0;
  for(i = N - 1; i >= 0; i--){
    if(t.quot){
      c[i]++;
      if(i < ctrl) ctrl = i;
    }
    t = div((c[i] + a[i] + b[i]),10);
    c[i] = t.rem;
  }
}
int main()
{
 int fib0[N];int fib1[N];int fib2[N];
 memset(fib0, 0, sizeof(int)*N);
 memset(fib1, 0, sizeof(int)*N);
 memset(fib2, 0, sizeof(int)*N);
 int n;
 cin>>n;
 fib0[N - 1] = 1;fib1[N - 1] = 1;
 ctrl = N - 1;
 if(n<2) fib2[N - 1] = 1;
 for (int i = 2;i <= n;i++)
 {
   add(fib0, fib1, fib2);
   memmove(fib0, fib1, sizeof(int)*N);
      memmove(fib1, fib2, sizeof(int)*N);
 }
 for(int i = ctrl; i < N; i++) cout<<fib2[i];
 return 0;
}

21.03.2014, 18:34

Зачем столько сложностей?

C++

#include <iostream>
 
using namespace std;
 
int main()
{
    int a ,b, k;
    a=0;
    b=1;
    cin >> k;
    while (k<=0)
    {
        cout << "ERROR! Enter the number greater than zero: ";
        cin >> k;
    }
    while (k!=0)
    {
        a=a+b;
        b=a-b;
        k=k-1;
        cout << a << " ";
    }
    return 0;
}

@BlackSpace · 22.03.2014, 19:31

Сообщение от LeshKing

Зачем столько сложностей?

Для расчета больших чисел Фибоначчи. Предположим надо посчитать тысячное число Фибоначчи.
Ваш код для этого не подойдет.

Lord_Voodoo, думаю, что Ваш код содержит ошибку.
Проверяя результаты программы для разных чисел нашел несоответствие с таблицами чисел Фибоначчи.

Вот работа программы
1)
100
573147844013817084101

2)
200
453973694165307953197296969697410619233826

Вот данные из таблицы чисел Фибоначчи, а также из проекта wolframalpha.
Ф(100)=354224848179261915075
Ф(200)=280571172992510140037611932413038677189525

@Lord_Voodoo · 23.03.2014, 10:47

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

@Rocko · 29.05.2017, 15:01

самый изи вариант!!! тока с большими числами не работает

C++

#include <iostream>
using namespace std;
int main ()
{
 int a,c=1,i,ans;
 float b=0;
 cin >> a;
 for (i=1;i<a;i++)
 {
    ans=c+b;
    b=c;
    c=ans;
 }
 cout << b;
    return 0;
}

@Cuellius · 29.05.2017, 16:07

C++

#include <vector>
#include <iostream>
#include <fstream>
#include <iterator>
#include <string>
#include <algorithm>
#include <exception>
#include <stdexcept>
#include <cstring>
#include <cstdio>
#include <cstdlib>
 
class BigInteger
{
public: 
    BigInteger()
    {
        _data.push_back(0);
    }
    
    BigInteger(long long x)
    {
        while(x)
        {
            _data.push_back(x % _base);
            x /= _base;
        }
        
        if(_data.empty()) _data.push_back(0);
    }
    
    BigInteger(unsigned long long x)
    {
        while(x)
        {
            _data.push_back(x % _base);
            x /= _base;
        }
        
        if(_data.empty()) _data.push_back(0);
    }
 
    BigInteger(int x) : BigInteger((long long)x) {}
    BigInteger(unsigned int x) : BigInteger((unsigned long long)x) {}
    BigInteger(short x) : BigInteger((long long)x) {}
    BigInteger(unsigned short x) : BigInteger((unsigned long long)x) {}
    BigInteger(char x) : BigInteger((long long)x) {}
    BigInteger(unsigned char x) : BigInteger((unsigned long long)x) {}
 
    BigInteger(std::string &s)
    {
        for(int i = (int)s.size(); i > 0; i -= 9)
            if(i < 9)
                _data.push_back(atoi(s.substr(0, i).data()));
            else
                _data.push_back(atoi(s.substr(i - 9, 9).data()));
        
        while(_data.size() > 1 && _data.back() == 0)
            _data.pop_back();
    }
    
    BigInteger(const char *s)  
    {
        std::string d = s;
        
        for(int i = (int)d.size(); i > 0; i -= 9)
            if(i < 9)
                _data.push_back(atoi(d.substr(0, i).data()));
            else
                _data.push_back(atoi(d.substr(i - 9, 9).data()));
        
        while(_data.size() > 1 && _data.back() == 0)
            _data.pop_back();
    }
    
    BigInteger(const BigInteger& b)
    {
        _data.resize(b._data.size());
        std::copy(b._data.begin(), b._data.end(), _data.begin());
    }
    
    void ToString(char *s) const
    {
        sprintf(s, "%d", _data.empty() ? 0 : _data.back());
        for(int i = (int)_data.size() - 2; i >= 0; i--)
            sprintf(s, "%s%09d", s, _data[i]);
    }
    
    std::string ToString() const
    {
        char *buff = (char*)malloc(20);
        
        sprintf(buff, "%d", _data.empty() ? 0 : _data.back());
        std::string res = buff;
        
        for(int i = (int)_data.size() - 2; i >= 0; i--)
        {
            sprintf(buff, "%09d", _data[i]);
            res += buff;
        }
            
        free(buff);
        
        return res;
    }
    
    friend const BigInteger operator+(BigInteger &i);
    friend const BigInteger& operator++(BigInteger &i);
    friend const BigInteger& operator--(BigInteger &i);
    friend const BigInteger operator++(BigInteger &i, int);
    friend const BigInteger operator--(BigInteger &i, int);
    
    friend const BigInteger operator+(const BigInteger &c, const BigInteger &b);
    friend const BigInteger operator-(const BigInteger &c, const BigInteger &b);
    friend const BigInteger operator*(const BigInteger &a, const BigInteger &b);
    friend const BigInteger operator/(const BigInteger &a, const BigInteger &b);
    friend const BigInteger operator%(const BigInteger &a, const BigInteger &b);
    
    friend BigInteger& operator+=(BigInteger &a, const BigInteger &b);
    friend BigInteger& operator-=(BigInteger &a, const BigInteger &b);
    friend BigInteger& operator*=(BigInteger &a, const BigInteger &b);
    friend BigInteger& operator/=(BigInteger &a, const BigInteger &b);
    friend BigInteger& operator%=(BigInteger &a, const BigInteger &b);
    
    friend bool operator==(const BigInteger &a, const BigInteger &b);
    friend bool operator<=(const BigInteger &a, const BigInteger &b);
    friend bool operator>=(const BigInteger &a, const BigInteger &b);
    friend bool operator<(const BigInteger &a, const BigInteger &b);
    friend bool operator>(const BigInteger &a, const BigInteger &b);
    friend bool operator!=(const BigInteger &a, const BigInteger &b);
    
    /*operator long long() const
    {
        long long res = 0, b = 1;
        for(size_t i = 0; i < _data.size(); i++)
        {
            res += b * _data[i];
            b *= BigInteger::_base;
        }
        return res;
    }
    
    operator unsigned long long()
    {
        unsigned long long res = 0, b = 1;
        for(size_t i = 0; i < _data.size(); i++)
        {
            res += b * _data[i];
            b *= BigInteger::_base;
        }
        return res;
    }*/
    
    friend std::istream& operator>>(std::istream &is, BigInteger &i)
    {
        std::string s;
        is >> s;
        i = BigInteger(s);
        return is;
    }
    
    friend std::ostream& operator<<(std::ostream &os, const BigInteger &i)
    {
        os << i.ToString();
        return os;
    }
    
private:
    static const int _base = 1000 * 1000 * 1000;
    std::vector<int> _data;
    
    int _cmp(const BigInteger &a, const BigInteger &b) const //a - b, 1 if a > b
    {
        if(a._data.size() > b._data.size()) return 1;
        if(a._data.size() < b._data.size()) return -1;
        
        for(int i = (int)a._data.size() - 1; i >= 0; i--)
        {
            if(a._data[i] > b._data[i]) return 1;
            if(a._data[i] < b._data[i]) return -1;
        }
        
        return 0;
    }
    
    BigInteger _div_short(const BigInteger &c, int b, int &mod) const
    {
        mod = 0;
        BigInteger a = c;
        for(int i = (int)a._data.size() - 1; i >= 0; i--) 
        {
            long long cur = a._data[i] + mod * 1ll * BigInteger::_base;
            a._data[i] = int(cur / b);
            mod = int(cur % b);
        }
        
        while (a._data.size() > 1 && a._data.back() == 0)
            a._data.pop_back();
        
        return a;
    }
    
    bool _is_zero() const
    {
        return _data.size() == 1 && _data[0] == 0;
    }
};
 
const BigInteger operator+(const BigInteger &i) 
{
    return BigInteger(i);
}
 
const BigInteger& operator++(BigInteger &i) 
{
    int j = 0;
    i._data[0]++;
    
    while(i._data[j] >= BigInteger::_base)
    {
        if(j == (int)i._data.size() - 1) i._data.push_back(1); else i._data[j + 1]++;
        i._data[j] -= BigInteger::_base;
        j++;
    }
    
    return i;
}
 
const BigInteger operator++(BigInteger &i, int) 
{
    BigInteger old = BigInteger(i);
    
    int j = 0;
    i._data[0]++;
    
    while(i._data[j] >= BigInteger::_base)
    {
        if(j == (int)i._data.size() - 1) i._data.push_back(1); else i._data[j + 1]++;
        i._data[j] -= BigInteger::_base;
        j++;
    }
    
    return old;
}
 
//TODO: Optimize
const BigInteger& operator--(BigInteger &i) 
{
    if(!i._is_zero()) i = i - 1;
    return i;
}
 
//TODO: Optimize
const BigInteger operator--(BigInteger &i, int) 
{
    BigInteger old = BigInteger(i);
    if(!i._is_zero()) i = i - 1;
    return old;
}
 
const BigInteger operator+(const BigInteger &c, const BigInteger &b)
{
    BigInteger a = c;
        
    int carry = 0;
    for(size_t i = 0; i < std::max(a._data.size(), b._data.size()) || carry; i++) 
    {
        if(i == a._data.size()) a._data.push_back(0);
        a._data[i] += carry + (i < b._data.size() ? b._data[i] : 0);
        carry = a._data[i] >= BigInteger::_base;
        if(carry) a._data[i] -= BigInteger::_base;
    }   
        
    return a;       
}
 
const BigInteger operator-(const BigInteger &c, const BigInteger &b)
{
    if(c < b) throw std::invalid_argument("a - b, a must b greater or equal zero");
    BigInteger a = c;
        
    int carry = 0;
    for(size_t i = 0; i < b._data.size() || carry; i++) 
    {
        a._data[i] -= carry + (i < b._data.size() ? b._data[i] : 0);
        carry = a._data[i] < 0;
        if(carry) a._data[i] += BigInteger::_base;
    }
        
    while(a._data.size() > 1 && a._data.back() == 0)
        a._data.pop_back();
            
    return a;       
}
 
const BigInteger operator*(const BigInteger &a, const BigInteger &b)
{
    BigInteger c;
    c._data.resize(a._data.size() + b._data.size());
        
    for(size_t i = 0; i < a._data.size(); i++)
        for(int j = 0, carry = 0; j < (int)b._data.size() || carry; j++) 
        {
            long long cur = c._data[i + j] + a._data[i] * 1ll * (j < (int)b._data.size() ? b._data[j] : 0) + carry;
            c._data[i + j] = int(cur % BigInteger::_base);
            carry = int(cur / BigInteger::_base);
        }
            
    while(c._data.size() > 1 && c._data.back() == 0)
        c._data.pop_back();
            
    return c;       
}
 
//TODO: Division by zero
const BigInteger operator/(const BigInteger &a, const BigInteger &b)
{
    if(b._is_zero()) throw std::invalid_argument("division by zero");
    BigInteger l = 0, r = a + 1, m;
    int t;
    while(r - l > 1)
    {
        //m = (r + l) / 2;
        m = a._div_short(r + l, 2, t);
        if(b * m <= a) l = m; else r = m;
    }
    return l;
}
 
//TODO: Division by zero
const BigInteger operator%(const BigInteger &a, const BigInteger &b)
{
    if(b._is_zero()) throw std::invalid_argument("division by zero");
    BigInteger l = 0, r = a + 1, m;
    int t;
    while(r - l > 1)
    {
        //m = (r + l) / 2;
        m = a._div_short(r + l, 2, t);
        if(b * m <= a) l = m; else r = m;
    }
    return a - b * l;
}
 
BigInteger& operator+=(BigInteger &a, const BigInteger &b)
{
    int carry = 0;
    for(size_t i = 0; i < std::max(a._data.size(), b._data.size()) || carry; i++) 
    {
        if(i == a._data.size()) a._data.push_back(0);
        a._data[i] += carry + (i < b._data.size() ? b._data[i] : 0);
        carry = a._data[i] >= BigInteger::_base;
        if(carry) a._data[i] -= BigInteger::_base;
    }   
    return a;
}
 
BigInteger& operator-=(BigInteger &a, const BigInteger &b)
{
    int carry = 0;
    for(size_t i = 0; i < b._data.size() || carry; i++) 
    {
        a._data[i] -= carry + (i < b._data.size() ? b._data[i] : 0);
        carry = a._data[i] < 0;
        if(carry) a._data[i] += BigInteger::_base;
    }
        
    while(a._data.size() > 1 && a._data.back() == 0)
        a._data.pop_back();
            
    return a;
}
 
BigInteger& operator*=(BigInteger &a, const BigInteger &b)
{
    a = a * b;
    return a;
}
 
BigInteger& operator/=(BigInteger &a, const BigInteger &b)
{
    a = a / b;
    return a;
}
 
BigInteger& operator%=(BigInteger &a, const BigInteger &b)
{
    a = a % b;
    return a;
}
 
bool operator==(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) == 0;
}
 
bool operator<=(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) <= 0;
}
 
bool operator>=(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) >= 0;
}
 
bool operator<(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) < 0;
}
 
bool operator>(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) > 0;
}
 
bool operator!=(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) != 0;
}
 
int main()
{
    int n;
    std::cin >> n;
    std::vector<BigInteger> f = { BigInteger(0), BigInteger(1) };
    for(int i = 2; i <= n; i++) f.push_back(f[i - 1] + f[i - 2]);
    std::cout << f[n].ToString() << std::endl;
    return 0;
}

@fedos1994 · 24.02.2018, 18:00

Я конечно не специалист, но по-моему проблема только в том, что в скобках условия указано N<0 N>10000
А по условию надо N>0 и N <10000. Тогда не будет отрицательных чисел

zer0mail · 24.02.2018, 19:18

Сообщение от fedos1994

Я конечно не специалист,

Еще какой не специалист

ТС пытался отсечь некорректный ввод. Правда, сделал он это криво

А отрицательные числа возникают из-за переполнения, о чем выше писали.

@Georgiy1108 · 07.02.2019, 09:25

C++

#include<stdio.h>
main()
{
    int a=0,b=1,c,n;
    scanf("%d",&n);
    if(n==0)printf("0");
    else if(n==1)printf("1");
    else
    {
        for(int i=2;i<=n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        printf("%d",c);
    }
}

Всё проще намного.

@BlackSpace · 07.02.2019, 13:10

Georgiy1108, проще в каком отношении?
Если внимательно прочитаете условие ТС и сообщения из данной темы, то увидите, что подход аналогичный Вашему уже предлагался и пояснялось почему такой подход не способствует решению задания ТС.

Ваш код никак не подходит для решения задания, поставленного ТС.
Ваша программа выдаст абсолютно неверный результат, если попробовать найти, к примеру сотое число Фибоначчи.
Настоящее сотое число Фибоначчи = 354224848179261915075.
Ответ Вашей программы = -980107325.

@Georgiy1108 · 08.02.2019, 19:49

Ну тут либо длинная арифметика, либо на питоне писать, я это написал к тому, что не обязательно хранить весь массив.

Добавлено через 48 секунд
Да точно было такое

@Crabintron · 13.02.2019, 02:22

Ужасный язык... Строки адекватно перезаписывать не хочет, зато написал немного по другому - стал перезаписывать (но тоже самое).
На этапе теста запустил с n=200 - код отработал 2 секунды и закончился, ничего не получив. Пару раз так запустил - ничего.
Подождал минутку - начал запускать по порядку:
100 - работает.
120 - работает.
150 - работает.
180 - работает.
190 - работает.
200 - работает.
9999 - работает.
Оп, что? 200 уже работает? Вот как это обьяснить? Почему он сразу не захотел работать?
Вообще интересно, что скажет знающий человек по поводу такого кода.

C++

#include <iostream>
#include <cstring>
using namespace::std;
    string sum(string p1, string p2)
    {
        if(p1.length()!=p2.length())
        {
            p1="00"+p1; 
        }
        else
        {
            p1="0"+p1;
        }
        p2="0"+p2;
        char* arr1=new char[p1.length()];
        strcpy(arr1, p1.c_str());
        char* arr2=new char[p2.length()];
        strcpy(arr2, p2.c_str());
        char* arr3 =new char[p2.length()];
        strcpy(arr3, p2.c_str());
        
        int it=p2.length(), opit=it-1, tmp=0, op1=0, op2=0;
        while(it!=0)
        {
            op1=(int)arr1[opit]-48;
            op2=(int)arr2[opit]-48;
            
            tmp+=(op1+op2);
            
            arr3[opit]=(tmp%10)+48;
            tmp/=10;
            
            it--;
            opit--;
            
        }
        string h;
        if(arr3[0]=='0')
        {
            for(int i=0;i<(p2.length()-1);i++)
            {
                arr3[i]=arr3[i+1];
            }
            h = string(arr3, p2.length()-1);
        }
        else
        {
            return arr3;
        }
        return h;
    }
    
int main()
{
    string a,b,c;
    int n;
    do
    {
        cin>>n;
    }while(n<1);
    if(n==1)
    {
        cout <<0;
        return 0;
    }
    else{
        if(n==2)
        {
            cout<<1;
            return 0;   
        }   
    }
    a = "1";
    b = "1";
    for(int i=2; i<n; i++)
    {
        c = sum(a, b);
        a=b;
        b=c;
                
    }
    cout <<c;
    return 0;
}

@COKPOWEHEU · 13.02.2019, 14:06

Сообщение от Crabintron

Вообще интересно, что скажет знающий человек по поводу такого кода.

Что его писал извращенец, причем в плохом смысле.
Сложение идет через представление чисел строками. Ладно бы еще массивом цифр, но строками!
Внутри функции сложения выделяется память аж под 3 строки (зачем???), а потом не освобождается. У вас что, память девать некуда?

Добавлено через 1 час 8 минут
Вариант с ручной реализацией длинных целых:

C

#include <stdio.h>
#include <inttypes.h>
#include <string.h>
 
#define LONG_SIZE 1000
 
typedef struct LongNum{
  uint8_t data[LONG_SIZE];
}LongNum_t;
 
void LongSet( LongNum_t *x, uint8_t val){
  memset( &(x->data), 0, LONG_SIZE);
  x->data[0] = val;
}
 
void LongSum( LongNum_t *a, LongNum_t *b, LongNum_t *res ){
  uint16_t temp = 0;
  for(uint16_t i=0; i<LONG_SIZE; i++){
    temp += a->data[i] + b->data[i];
    res->data[i] = temp & 0xFF;
    temp >>= 8;
  }
  if(temp != 0)fprintf(stderr, "OVF!!!\n");
}
 
uint8_t LongDivMod10( LongNum_t *a, LongNum_t *res, uint8_t *num){
  uint16_t temp = 0;
  uint8_t zero = 1;
  for(int16_t i=(LONG_SIZE-1); i>=0; i--){
    temp = (temp << 8) | a->data[i];
    res->data[i] = temp / 10;
    temp %= 10;
    if(res->data[i] != 0)zero = 0;
  }
  *num = temp;
  return zero;
}
//рекурсивный вывод: мне лень было переводить в строку по-человечески
void LongOut(LongNum_t *x){
  uint8_t num = 0;
  if(!LongDivMod10(x, x, &num)){
    LongOut(x);
  }
  printf("%i", num);
}
 
int main(){
  LongNum_t a, b;
  LongNum_t *x=&a, *y=&b, *t;
  LongSet(x, 0);
  LongSet(y, 1);
  int n;
  scanf("%i", &n);
  for(int i=0; i<n; i++){
    LongSum(x, y, x);
    t=x; x=y; y=t;
  }
 
  printf("%i -> ", n);
  LongOut(x);
  printf("\n");
}

Результаты:

1 -> 1
3 -> 2
6 -> 8
10 -> 55
20 -> 6765
50 -> 12586269025
100 -> 354224848179261915075
500 -> 13942322456169788013972438287040728395007025658769730726410896294832557162286329 0691557658876222521294125
1000 -> 43466557686937456435688527675040625802564660517371780402481729089536555417949051 89040387984007925516929592259308032263477520968962323987332247116164299644090653 3187938298969649928516003704476137795166849228875
2000 -> 42246963333923048787067256023414827825798528402506810980102801373143085843701307 07224123599639141511088446087538909603607640194711643596029271983312598737326253 55580260699158591522949245390499872225679531698287448247299226390183371677806060 70116154978867198798583114688708762645973690867228840236544222952433479644801395 15349562972087652656069529806499841977448720155612802665404554171717881930324025 204312082516817125
5000 -> 38789684543883256337019163083259053120821277146462451061605972148955501390440370 97010822916462210669479293452858882973813483102008954982940361430156911478938364 21656394410691021450563413370655865623825465670071252592990385493381392883637834 75189087629707120333370529231076930085180938498018038478139967488817655546537882 91644268912980384613778969021502293082475666346224923071883324803280375039130352 90330450584270114763524227021093463769910400671417488329842289149127310405432875 32980442736768229772449877498745556919077038806370468327948113589737399931101062 19308149018570815397854379195305617510761053075688783766033667355445258844886241 61921055345749367589784902798823435102359984466393485325641195222185956306047536 46454707603309024208063825849291564528762915757591423438091423029174910889841552 09854432486594079793571316841692868039545309545388698114665082066862897420639323 43848846524098874239587380197699382031717420893226546887936400263079778005875912 96713896342142525791168727556003603113705477547246046399875880469851784086743828 63125
10000 -> 33644764876431783266621612005107543310302148460680063906564769974680081442166662 36815559551363373402558206533268083615937373479048386526826304089246305643188735 45443695598274916066020998841839338646527313000888302692356736131351175792974378 54413752130520504347701602264758318906527890855154366159582987279682987510631200 57542878345321551510387081829896979161312785626503319548714021428753269818796204 69360978799003509623022910263681314931952756302278376284415403605844025721143349 61180023091208287046088923962328835461505776583271252546093591128203925285393434 62090424524892940390170623388899108584106518317336043747073790855263176432573399 37128719375877468974799263058370657428301616374089691784263786242128352581128205 16370298089332099905707920064367426202389783111470054074998459250360633560933883 83192338678305613643535189213327973290813373264265263398976392272340788292817795 35805709936910491754708089318410561463223382174656373212482263830921032977016480 54726243842374862411453093812206564914032751086643394517512161526545361333111314 04243685480510676584349352383695965342807176877532834823434555736671973139274627 36291082106792807847180353291311767789246590899386354593278945237776744061922403 37638674004021330343297496902028328145933418826817683893072003634795623117103101 29195316979460763273758925353077255237594378843450406771555577905645044301664011 94625809722167297586150269684431469520346149322911059706762432685159928347098912 84706740862008587135016260312071903172086094081298321581077282076353186624611278 24553720853236530577595643007251774431505153960090516860322034916322264088524885 24331580515348496224348482993809050704834824493274537326245677558790891871908036 62058009594743150052402532709746995318770724376825907419939632265984147498193609 28522394503970716544315642132815768890805878318340491743455627052022356484649519 61124602683139709750693826487066132645076650746115126775227486215986425307112984 41182622661057163515069260029861704945425047491378115154139941550671256271197133 25276363193960690289565028826860836224108205056243070179497617112123306607331005 9947366875
11520 -> 15421644146544573240648490074420338482468504978285591203051598191082686363546688 98516933830683327529773429250716699313039448167692494794733440820258925344931644 80020801885433987941344474599385422864704198217404236962599412356972215288007581 05386966362091100205839421912230431316316338188752194734223960595814563195209121 50542269472240452680196442605978751352258418071465708666978776973519605700169615 23788348661915643225612361533220015220393035540320009848011968537270513428883848 28852933286067960629182687527469468553387120574575090336630024193142123702671783 41577383260353319976515244425923718747374194816328351349810119571810881940752819 99761581650309196763302769566989089256319981383522697595355103161721037512524840 32537383661500857334999341962222998710403331730870822386838310124191774907896299 13601127349197357555922177964401952206672557099441577792728191695707572159770312 01629531597753753971926101538704601980557805335730848786477787555780813264476413 20231077739784908889632160557773885819791838828585288633960149407149762231870302 70040492911543824618522823019143542706820697932912576838692937765925591966333077 68369258325142995445635552783669147467034874894184091602283676672014018372183936 22894895115814890337730051619948584199366444937730017675270578128929568737521499 84112320949266088839348825895132765366268137749787850504104556006212201416969622 27742667280326224747856456761452979386409586052547801310449370348312848023895031 99000698168978112779203386206941213670488174982387652299142800104730310417558977 75710493712504552084567474701352688065047753757387603885290410004455723489244642 74136265210288108911370182913299934845775092162680306771482238953314869212084948 23234991515009830940400543823523145336723691659997496849683340482900633458756261 33588615115461065652395529391579597971083332749980802849034501945876063222319746 57857145110549924186825889627305159900990210947634112268335351174766137930261587 60546683420139785941762869356191094557114258579382252536275536184158938464408766 83834331279086142519555086599870418567997546015639902517964045318753410823683186 18495354249212450577920639967983740417752168118221540587848947542385319019482858 46025121473878315672431608201734945822527840702203148083582355034601357343113930 11371825681665128883431833644908789847852659561711408182043541528957625297134796 50760783773829636093823530463139281643984591917298202089512502878318405260451485 50896640
Выше 11524 начинается переполнение.

Код

$ time ./a.out <<< "10000" > /dev/null

real    0m0,074s
user    0m0,074s
sys     0m0,000s

Добавлено через 5 минут
Проверяем код Crabintron'а:

Код

$ g++ main.cpp -Os -Wall -Wextra -Wpedantic
main.cpp: In function ‘std::__cxx11::string sum(std::__cxx11::string, std::__cxx11::string)’:
main.cpp:40:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<(p2.length()-1);i++)

Согласен, не самая критичная ошибка, попробуем запустить (изменил вывод аналогично своему для удобства копипаста из консоли):

Код

5 -> 5
10 -> 55
20 -> 6765
100 -> 354224848179261915075

Пока все нормально, но ведь ограничение до 10000

Код

$ ./a.out 
185
185 -> 205697230343233228174223751303346572685
$ ./a.out 
186
free(): invalid pointer
Аварийный останов

Вот и все. Выше 185 оно не считает. Хотя это связано скорее всего с размером доступной памяти, но все равно далеко до 10000

@Crabintron · 14.02.2019, 02:49

COKPOWEHEU, Хм, но в первый раз, по стичению каких-то обстоятельств, результат на n=9999 был получен. Интересно, как такое вообще получилось .) Но суть вашей мысли я понял, благодарю.

Добавлено через 10 часов 29 минут
Хм, вроде бы все легко, но почему temp >>= 8; выполняет роль сдвига на 1 разряд в 10ричноый системе?

Добавлено через 42 минуты
Вообще у вас странный код, вы тоже извращенец, хоть и другой масти. Ваш код излишне перебирает ненужные элементы.
Я тут немного переделал код, с учетом ваших замечаний.

C++

#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace::std;
int flag=1;
    int* sum(int* arr1, int* arr2)
    {
        int tmp=0;
        int i=0;
        
        for(; i<flag;i++)
        {
            tmp+=(arr1[11100-i]+arr2[11100-i]);
            
            arr1[11100-i]=tmp%10;
            tmp/=10;
        }
        if(tmp)
        {
            arr1[11100-i]=tmp;
            flag++;
        }
        
        return arr1;
    }
    
int main()
{
    clock_t t;
    t=clock();
    int* arr1;
    int* arr2;
    int* arr3;
    int n;
    /*do
    {
        cin>>n;
    }while(n<1);*/
    n=10000;
    if(n==1)
    {
        cout <<0;
        return 0;
    }
    else{
        if(n==2)
        {
            cout<<1;
            return 0;   
        }   
    }
    arr1=(int*)malloc(11101*sizeof(int));
    arr2=(int*)malloc(11101*sizeof(int));
    arr3=(int*)malloc(11101*sizeof(int));
    arr1[11100]=1;
    arr2[11100]=1;
    for(int i=2; i<n; i++)
    {
        arr3 = sum(arr1, arr2);   
        arr1=arr2;
        arr2=arr3; 
    }
    cout<<(float)(clock()-t)/CLOCKS_PER_SEC<<endl;
    for(int i=(11101-flag); i<11101; i++)
    {
        cout<<arr3[i];
    }
    return 0;
}

PS: Знаю, забыл освободить память.
А еще можно выдиление памяти поменять с 11101 на n и тогда код будет работать для всех значений, пока физическая память позволяет и при этом на низких значениях будет экономия памяти, под вычисление 10 числа не будет выделяться столько памяти .) А поменять именно на n потому-что при сложении 2 чисел длинна выходного числа может быть длиннее только на 1 разряд. Может есть и более точные алгоритмы вычисления количества цифл в числе фибаначчи, но я такого не знаю.

@COKPOWEHEU · 14.02.2019, 09:35

Сообщение от Crabintron

Хм, вроде бы все легко, но почему temp >>= 8; выполняет роль сдвига на 1 разряд в 10ричноый системе?

Я не в десятичной системе считаю, а в двоичной, точнее в 256-ричной. Один элемент массива - одна цифра от 0 до 255. Потому и сдвиг на 8 бит это сдвиг на 1 разряд.

Сообщение от Crabintron

arr3=(int*)malloc(11101*sizeof(int));
...
arr3 = sum(arr1, arr2);

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

Сообщение от Crabintron

Ваш код излишне перебирает ненужные элементы.

Где? Если речь про сложение, то функции обязаны перебирать все элементы, они же не знают что им подсунут.

Сообщение от Crabintron

А еще можно выдиление памяти поменять с 11101 на n и тогда код будет работать для всех значений, пока физическая память позволяет и при этом на низких значениях будет экономия памяти, под вычисление 10 числа не будет выделяться столько памяти .)

У вас выделяется 260 кБ. Ну ладно, если убрать выделение для arr3, которое здесь не нужно, будет 173 кБ.
Для сравнения, в моей версии выделяется примерно 2 кБ - на два порядка (десятичных) меньше!
По скорости счета мой метод тоже чуть лучше: за одну операцию складываются две 8-битных цифры, в то время как в вашем одна 10-ричная, это примерно в 2.5 раза разница. Вот при вводе-выводе ваш метод проще, поскольку нет необходимости деления.

@ABTOP 36 / 36 / 4 Регистрация: 09.06.2008 Сообщений: 324
	11.10.2008, 10:42	2
	Знакомая история... Просто переменная выходит за допустимый диапазон своего типа, вот число и отрицательное... Попробуй воспользоваться типом unsigned long int или unsigned long double... Думаю его хватит... 0

@Tengel 2 / 2 / 0 Регистрация: 08.10.2008 Сообщений: 17
	11.10.2008, 10:55 [ТС]	3
	сделал так, но числа выводятса меньшие, чем когда я напишу unsigned long long, как тип массива......но что так, что так, ответ одинаков:Неверный ответ и что не делал уже, все равно корректно не работает.... 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	11.10.2008, 11:23	4
	Tengel, я недавно писал прогу по остаткам от деления чисел фибоначчи на большие числа, хватало long long, но там алгоритм очень замороченный, а вам для вычисления даже двухтысячного числа 80 бит(long double) ну никак не хватит... либо ищите библиотеки для работы с большими числами, либо ограничьтесь 1000... 0

V.A.M
	14.10.2008, 21:34	5
	Poprobuy ispolzovat' clojenie dlinnix dvux chisel' s ispolzovaniem String, Esli tebe nujn@ ya moga dat' tebe code dlya clojenita dlinnix chisel' (okolo ~ 250 cimvolov). Make that as function with 2 arguments...

@BlackSpace 205 / 181 / 112 Регистрация: 15.03.2014 Сообщений: 392
	22.03.2014, 19:31	8
	Сообщение от LeshKing Зачем столько сложностей? Для расчета больших чисел Фибоначчи. Предположим надо посчитать тысячное число Фибоначчи. Ваш код для этого не подойдет. Lord_Voodoo, думаю, что Ваш код содержит ошибку. Проверяя результаты программы для разных чисел нашел несоответствие с таблицами чисел Фибоначчи. Вот работа программы 1) 100 573147844013817084101 2) 200 453973694165307953197296969697410619233826 Вот данные из таблицы чисел Фибоначчи, а также из проекта wolframalpha. Ф(100)=354224848179261915075 Ф(200)=280571172992510140037611932413038677189525 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	23.03.2014, 10:47	9
	BlackSpace, ну спорить не буду, но код тоже проходил тестирование и на скорость, и на емкость... не помню, как ресурс называется... если есть ошибка, то извиняйте... 0

@fedos1994 0 / 0 / 0 Регистрация: 22.11.2012 Сообщений: 16
	24.02.2018, 18:00	12
	Я конечно не специалист, но по-моему проблема только в том, что в скобках условия указано N<0 N>10000 А по условию надо N>0 и N <10000. Тогда не будет отрицательных чисел 0

zer0mail 2663 / 2238 / 240 Регистрация: 03.07.2012 Сообщений: 8,141 Записей в блоге: 1
	24.02.2018, 19:18	13
	Сообщение от fedos1994 Я конечно не специалист, Еще какой не специалист ТС пытался отсечь некорректный ввод. Правда, сделал он это криво А отрицательные числа возникают из-за переполнения, о чем выше писали. 0

@BlackSpace 205 / 181 / 112 Регистрация: 15.03.2014 Сообщений: 392
	07.02.2019, 13:10	15
	Georgiy1108, проще в каком отношении? Если внимательно прочитаете условие ТС и сообщения из данной темы, то увидите, что подход аналогичный Вашему уже предлагался и пояснялось почему такой подход не способствует решению задания ТС. Ваш код никак не подходит для решения задания, поставленного ТС. Ваша программа выдаст абсолютно неверный результат, если попробовать найти, к примеру сотое число Фибоначчи. Настоящее сотое число Фибоначчи = 354224848179261915075. Ответ Вашей программы = -980107325. 0

@Georgiy1108 0 / 0 / 0 Регистрация: 19.06.2017 Сообщений: 20
	08.02.2019, 19:49	16
	Ну тут либо длинная арифметика, либо на питоне писать, я это написал к тому, что не обязательно хранить весь массив. Добавлено через 48 секунд Да точно было такое 0

@COKPOWEHEU 3881 / 2479 / 418 Регистрация: 09.09.2017 Сообщений: 10,873
	14.02.2019, 09:35	20
	Сообщение от Crabintron Хм, вроде бы все легко, но почему temp >>= 8; выполняет роль сдвига на 1 разряд в 10ричноый системе? Я не в десятичной системе считаю, а в двоичной, точнее в 256-ричной. Один элемент массива - одна цифра от 0 до 255. Потому и сдвиг на 8 бит это сдвиг на 1 разряд. Сообщение от Crabintron arr3=(int)malloc(11101sizeof(int)); ... arr3 = sum(arr1, arr2); Так делать нельзя. Вы выделили память, но тут же меняете указатель на arr1. В результате к памяти, выделенной изначально, нет никакого доступа. Ну и да, не забывайте проверять успешность выделения памяти и освобождать вовремя. Сообщение от Crabintron Ваш код излишне перебирает ненужные элементы. Где? Если речь про сложение, то функции обязаны перебирать все элементы, они же не знают что им подсунут. Сообщение от Crabintron А еще можно выдиление памяти поменять с 11101 на n и тогда код будет работать для всех значений, пока физическая память позволяет и при этом на низких значениях будет экономия памяти, под вычисление 10 числа не будет выделяться столько памяти .) У вас выделяется 260 кБ. Ну ладно, если убрать выделение для arr3, которое здесь не нужно, будет 173 кБ. Для сравнения, в моей версии выделяется примерно 2 кБ - на два порядка (десятичных) меньше! По скорости счета мой метод тоже чуть лучше: за одну операцию складываются две 8-битных цифры, в то время как в вашем одна 10-ричная, это примерно в 2.5 раза разница. Вот при вводе-выводе ваш метод проще, поскольку нет необходимости деления. 0