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

Длинные фиббоначи - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 17:34     Длинные фиббоначи #1
От нечего делать написал это:
Кликните здесь для просмотра всего текста
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// ConsoleApplication1.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
 
void fo (char a)
{
    cout.fill(' ');
    cout.width(a);
}
//функция формата вывода
 
 
char cif (int a)
{
    if (a != 0)
    {
        a = a/10;
        a = cif(a);
        a++;
    }
    return a;
}
//подсчёт цифр в числе
 
 
void output (unsigned long long a, vector<unsigned long long> b,char c)
{
            fo(c); cout << a;
            cout <<"--";
            for (int i = b.size()-1; i >= 0; i--)
                cout << b[i];
}
//функция вывода
 
 
unsigned long long ldiv (unsigned long long a, unsigned long long b)
{
    return a/b;
}
//целочисленное деление
 
 
 
unsigned long long lmod (unsigned long long a, unsigned long long b)
{
    unsigned long long i;
    i = ldiv (a,b);
    i = i * b;
    return a-i;
}
//остаток от деления
 
 
vector<unsigned long long> sum (vector<unsigned long long> a, vector<unsigned long long> b,vector<unsigned long long>*c,vector<unsigned long long>*d) 
{
    unsigned long long i;
    unsigned long long con = 10000000000000000000;
    unsigned int j;
    unsigned int j1 = 0;
    for (j = 0; j < a.size() && j1 < b.size(); j++)
    {
        i = a[j] + b[j1];
        if (i >= con)
        {
            if (j == a.size() - 1)
            {
                (*c).push_back (0);
                (*d).push_back (0);
                a.push_back (ldiv(i,con));
                a[j] = lmod(i,con);
            }
            else
            {
                a[j+1] += ldiv(i,con);
                a[j] = lmod(i,con);
            }
        }
        else
        {
            a[j] = i;
        }
        j1++;
    }
    return a;
}
//функция сложения
 
 
int main()
{
    vector<unsigned long long> a;
    vector<unsigned long long> b;
    unsigned long long n = 1;
    int m;
    cin >> m;
    char c;//количество символов вывода
    c = cif(m);
    a.push_back(1);
    b.push_back(1);
    fo(c); cout << "0";
    cout << "--" << "1" << endl;
    if (m <= 0)
        exit (0);
    fo(c); cout << "1";
    cout << "--" << "1" << endl;
    if (m <= 1)
        exit (0);
    while (n <= m)
    {
        int i1;
        a = sum(a,b,&a,&b);
        n++;
        output (n,a,c);
        cout << endl;
        if (n >= m)
            break;
        b = sum(b,a,&b,&a);
        n++;
        output(n,b,c);
        cout << endl;
        if (n >= m)
            break;
    }
    return 0;
}


Но что-то не так. после вывода оказывается что начиная с 123-го числа выводится неверный результат. а именно теряется один знак. кто может, подскажите, в чём проблема.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Bend3r
 Аватар для Bend3r
142 / 129 / 17
Регистрация: 29.07.2012
Сообщений: 681
28.07.2013, 17:42     Длинные фиббоначи #2
Написали бы хотя бы цель программы. А то сидеть просто так разбираться в чье-то коде, да еще и вроде как не правильном нету желания.
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 17:55     Длинные фиббоначи #3
Вам нужно чтоб выводился ряд Фибоначчи?
Не так сказал, короче алгоритм проги:
1.Юзер вводит номер числа из ряда Фибоначчи
2.Это число ему выводится
Если да то могу дать исходник, я когда-то такую писал

Добавлено через 1 минуту
Вот, смотрите:
Числа Фибоначчи

Добавлено через 3 минуты
Очень уж сильно вы код раздули
Я когда делал то получилось покороче
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 18:12  [ТС]     Длинные фиббоначи #4
весь прикол в том, что в ансигнед лонг лонг вмещаются фибоначи до 92-го. Чтобы вывести любое я воспользовался динамическими массивами и длинной арифметикой и вроде бы до 122 числа включительно программа работает правильно (проверял ручками). Но. 123 число выдаёт неверно.
Кликните здесь для просмотра всего текста
118--3311648143516982017180081
119--5358359254990966640871840
120--8670007398507948658051921
121--14028366653498915298923761
122--22698374052006863956975682
123--3672674705505779255899443


Добавлено через 2 минуты
Цитата Сообщение от Даниил1991 Посмотреть сообщение
Очень уж сильно вы код раздули
Я когда делал то получилось покороче
Всё должно быть аккуратно, все повторяющиеся действия в функции
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 18:17     Длинные фиббоначи #5
Я когда писал программу (ту же самую что и вы) то она у меня вместила 100% не больше 25-30 строк
И выводила числа из ряда Фибоначчи до 1024

Добавлено через 3 минуты
Ммм...Похвально, то что вы не обращаете внимание на длительность написания/длительность кода программы
Но я ленивый, и по этому написал как покороче
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 18:22  [ТС]     Длинные фиббоначи #6
Повторяюсь: Мне было нечего делать

У вас была длинка? или как вы вместили 1024 число? По моей задумке программа должна выдавать (благодаря динамическим массивам) в разы большие числа.
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 18:30     Длинные фиббоначи #7
Очень просто, с помощью цикла for Всё предельно просто
Но я уже забыл как я её делал, но точно знаю то что она была маленькая (исходный код)
Ну и про цикл for тоже помню
Я то вам почему ссылку на тему кинул, потому что я её (программу которую писал) оказывается удалил

Добавлено через 5 минут
Я написал и понял что это звучит немного бредово
Возможно я вспомню код, вас это интересует?Если что могу позже в личку отправить
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 18:31  [ТС]     Длинные фиббоначи #8
Да. Буду благодарен.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
28.07.2013, 18:36     Длинные фиббоначи #9
проблема в строке 78:
ULLONG_MAX =
18446744073709551615
а у вас a[j+1] может быть равно 9999999999999999999
и ldiv(i,con) тоже 9999999999999999999
что в сумме дает больше чем ULLONG_MAX

строка 66 то же самое.

возможное решение проблемы: уберите один нолик из переменной con.
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:01     Длинные фиббоначи #10
Вот, держите

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdafx.h>
#include <iostream>
#include <conio.h>
#include <clocale>
using namespace std;
 
bool fibon_elem( int pos, int &elem ) {
if ( pos <= 0 || pos > 1024 ) // вместо 1024 можно поставить любое число, т.е. это лимит, но я не пробовал ставить другое
{
elem = 0;
return false;
}
elem = 1;
int n_2 = 1, n_1 = 1;
 
for ( int ix = 3; ix <= pos; ++ix)
{
    elem = n_2 + n_1;
    n_2 = n_1; n_1 = elem;
}
return true;
}
 
bool fibon_elem( int, int& );
 
int main () {
    setlocale (0,"");
    int pos;
    cout << "Введите номер элемента из ряда Фибоначчи: ";
    cin >> pos;
    int elem;
    if ( fibon_elem( pos, elem ))
    {
        cout << "Значение элемента № " << pos << " равно " << elem << endl;
    }
    else 
        cout << "Извините, не могу вычислить значение элемента № " << pos << endl;
    getch();
    return 0;
}
#include <stdafx.h> можно удалить, если у вас не MSVS
На здоровье

P.S. Пример такой же программы есть в книге Липпмана

Добавлено через 4 минуты
Цитата Сообщение от Даниил1991 Посмотреть сообщение
На здоровье

Не по теме:

Скрытый намек на спасибо (+1)

Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 19:16  [ТС]     Длинные фиббоначи #11
Цитата Сообщение от ya_noob Посмотреть сообщение
проблема в строке 78:
ULLONG_MAX =
18446744073709551615
а у вас a[j+1] может быть равно 9999999999999999999
и ldiv(i,con) тоже 9999999999999999999
что в сумме дает больше чем ULLONG_MAX

строка 66 то же самое.

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

Добавлено через 7 минут
Цитата Сообщение от Даниил1991 Посмотреть сообщение
Вот, держите
Что-то странно... везде интеджеры, не одного массива и до 1024 числа считает? хм...
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
28.07.2013, 19:34     Длинные фиббоначи #12
Цитата Сообщение от BrainFuck Посмотреть сообщение
Делал, неточности вычислений появляются раньше
я и не говорил, что нашел все ошибки, но те баги, что я указал, точно есть в вашей программе.

вот вам еще один баг:
функция char cif (int a) непонятно что делает в строках 21-23. догадываюсь, что подсчитывает кол-во цифр в числе, но в качестве счетчика почему-то выступает переменная для хранения числа.

и еще: некоторые числа фибоначчи выводятся без некоторых нулей в середине числа.

Добавлено через 6 минут
глядите сами:
C++
1
2
3
4
121--: 14028366653498915298923761
122--: 22698374052006863956975682
123--: 3672674 705505779255899443
right: 36726740705505779255899443
name?
 Аватар для name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 368
Завершенные тесты: 1
28.07.2013, 19:37     Длинные фиббоначи #13
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:39     Длинные фиббоначи #14
Цитата Сообщение от BrainFuck Посмотреть сообщение

Что-то странно... везде интеджеры, не одного массива и до 1024 числа считает? хм...
Проверьте сами, все правильно считает
name?
 Аватар для name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 368
Завершенные тесты: 1
28.07.2013, 19:44     Длинные фиббоначи #15
Цитата Сообщение от Даниил1991 Посмотреть сообщение
Проверьте сами, все правильно считает
ответ из вашей программы
"Введите номер элемента из ряда Фибоначчи: 1023
Значение элемента № 1023 равно -1595087134"


где правильный ответ будет
1023 =
4506699633677819813104383235728886049367860596218604830803023149600030645708721396248792609141030396244873266580345011219530209367425581019871067646094200262285202346655868899711089246778413354004103631553925405243
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:50     Длинные фиббоначи #16
Ахах Как вы посчитали это? *сарказм*
Ну при вводе 1000 вроде бы ответ правильный, по крайней мере без -
Значит сфейлился я
Ну я думаю что никому не нужно узнавать 1023 номер
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 19:55     Длинные фиббоначи #17
Даниил1991, по твоей логике, если бы программа еще слетала на числах под порядковым номером 107, 873, 994, то ты бы написал "Никому не понадобится вычислять числа под номерами 107, 873, 994" ??
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:59     Длинные фиббоначи #18
Конечно нет, но большие числа для чего могут понадобится(приведите пример)? Высшая математика? Квантовая физика?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 20:06     Длинные фиббоначи #19
Даниил1991, тогда по твоей логике, зачем вообще находить числа Фибоначчи, если они не влазят в int? Зачем мне приводить пример? Если у него такое задание и ты не можешь его правильно выполнить, то будешь придираться к назначению этого задания? Может это и надо в высшей математике, тебе какое дело до этого? Это дело ТС, раз есть такое задание, то его нужно выполнить, а не придираться к нему.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2013, 20:11     Длинные фиббоначи
Еще ссылки по теме:

Найти число Фиббоначи с помощью рекурсии C++
Числа Фиббоначи через динамический массив C++
C++ Число Фиббоначи

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

Или воспользуйтесь поиском по форуму:
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 20:11  [ТС]     Длинные фиббоначи #20
Цитата Сообщение от ya_noob Посмотреть сообщение
я и не говорил, что нашел все ошибки, но те баги, что я указал, точно есть в вашей программе.

вот вам еще один баг:
функция char cif (int a) непонятно что делает в строках 21-23. догадываюсь, что подсчитывает кол-во цифр в числе, но в качестве счетчика почему-то выступает переменная для хранения числа.

и еще: некоторые числа фибоначчи выводятся без некоторых нулей в середине числа.

Добавлено через 6 минут
глядите сами:
C++
1
2
3
4
121--: 14028366653498915298923761
122--: 22698374052006863956975682
123--: 3672674 705505779255899443
right: 36726740705505779255899443
Этот то баг я и искал! подскажите как поправить? (всё остальное на работоспособность программы не влияет. там беззнаковые переменные.)

ЗЫ функция cif влияет только на вывод.
Yandex
Объявления
28.07.2013, 20:11     Длинные фиббоначи
Ответ Создать тему
Опции темы

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