Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
1

Длинные фиббоначи

28.07.2013, 17:34. Показов 2125. Ответов 37
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
От нечего делать написал это:
Кликните здесь для просмотра всего текста
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-го числа выводится неверный результат. а именно теряется один знак. кто может, подскажите, в чём проблема.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.07.2013, 17:34
Ответы с готовыми решениями:

Фиббоначи.
Верно ли, что сумма первых n членов последовательности Фибоначчи есть четное число. Решите...

Число Фиббоначи
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; int main() { int a, b, k; a =...

Посчитать число N Фиббоначи
Здравствуйте, есть задача: нужно посчитать число N Фиббоначи по модулю 10^9+7(ограничение до...

Число Фиббоначи (ломается на 46-м)
#include &lt;iostream&gt; using namespace std; int main() { int f1=0,f2=1; unsigned long...

37
150 / 137 / 35
Регистрация: 29.07.2012
Сообщений: 709
28.07.2013, 17:42 2
Написали бы хотя бы цель программы. А то сидеть просто так разбираться в чье-то коде, да еще и вроде как не правильном нету желания.
0
68 / 41 / 1
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 17:55 3
Вам нужно чтоб выводился ряд Фибоначчи?
Не так сказал, короче алгоритм проги:
1.Юзер вводит номер числа из ряда Фибоначчи
2.Это число ему выводится
Если да то могу дать исходник, я когда-то такую писал

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

Добавлено через 3 минуты
Очень уж сильно вы код раздули
Я когда делал то получилось покороче
1
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 Посмотреть сообщение
Очень уж сильно вы код раздули
Я когда делал то получилось покороче
Всё должно быть аккуратно, все повторяющиеся действия в функции
0
68 / 41 / 1
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 18:17 5
Я когда писал программу (ту же самую что и вы) то она у меня вместила 100% не больше 25-30 строк
И выводила числа из ряда Фибоначчи до 1024

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

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

Добавлено через 5 минут
Я написал и понял что это звучит немного бредово
Возможно я вспомню код, вас это интересует?Если что могу позже в личку отправить
1
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 18:31  [ТС] 8
Да. Буду благодарен.
0
_
317 / 151 / 27
Регистрация: 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.
0
68 / 41 / 1
Регистрация: 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) :D

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 числа считает? хм...
0
_
317 / 151 / 27
Регистрация: 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
0
201 / 172 / 52
Регистрация: 01.06.2010
Сообщений: 371
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;
}
0
68 / 41 / 1
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:39 14
Цитата Сообщение от BrainFuck Посмотреть сообщение

Что-то странно... везде интеджеры, не одного массива и до 1024 числа считает? хм...
Проверьте сами, все правильно считает
0
201 / 172 / 52
Регистрация: 01.06.2010
Сообщений: 371
28.07.2013, 19:44 15
Цитата Сообщение от Даниил1991 Посмотреть сообщение
Проверьте сами, все правильно считает
ответ из вашей программы
"Введите номер элемента из ряда Фибоначчи: 1023
Значение элемента № 1023 равно -1595087134"


где правильный ответ будет
1023 =
45066996336778198131043832357288860493678605962186048308030231496000306457087213 96248792609141030396244873266580345011219530209367425581019871067646094200262285 202346655868899711089246778413354004103631553925405243
0
68 / 41 / 1
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:50 16
Ахах Как вы посчитали это? *сарказм*
Ну при вводе 1000 вроде бы ответ правильный, по крайней мере без -
Значит сфейлился я
Ну я думаю что никому не нужно узнавать 1023 номер
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
28.07.2013, 19:55 17
Даниил1991, по твоей логике, если бы программа еще слетала на числах под порядковым номером 107, 873, 994, то ты бы написал "Никому не понадобится вычислять числа под номерами 107, 873, 994" ??
0
68 / 41 / 1
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:59 18
Конечно нет, но большие числа для чего могут понадобится(приведите пример)? Высшая математика? Квантовая физика?
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
28.07.2013, 20:06 19
Даниил1991, тогда по твоей логике, зачем вообще находить числа Фибоначчи, если они не влазят в int? Зачем мне приводить пример? Если у него такое задание и ты не можешь его правильно выполнить, то будешь придираться к назначению этого задания? Может это и надо в высшей математике, тебе какое дело до этого? Это дело ТС, раз есть такое задание, то его нужно выполнить, а не придираться к нему.
0
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 влияет только на вывод.
0
28.07.2013, 20:11
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.07.2013, 20:11
Помогаю со студенческими работами здесь

Задачка на числа Фиббоначи
Ребят, задача такая Числа Фибоначчи u(0), u(1), ... получили название в честь итальянского...

Определение К-го числа последовательности Фиббоначи
Помогите написать программу (паскаль ИЛИ С++) реализующую определение К-го числа последовательности...

Числа Фиббоначи через динамический массив
Среди первых N-чисел Фибоначчи найти такие, которые начинаются или заканчиваются на М....

Найти число Фиббоначи с помощью рекурсии
найти число фиббоначи с помощью рекурсии. заранее спасибо


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru