0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
1

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

28.07.2013, 17:34. Показов 2120. Ответов 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
68 / 41 / 1
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 20:11 21
Author24 — интернет-сервис помощи студентам
Где вы видели чтоб ТС писал что ему дали задачу?
Если можете то отправьте (цитата), а то может я ослеп
Он
Цитата Сообщение от BrainFuck Посмотреть сообщение
От нечего делать
написал программу
Цитата Сообщение от name? Посмотреть сообщение
1023 =
450669963367781981310438323572888604936786059621860483080302 314960003064570872139624879260914103039624487326658034501121 953020936742558101987106764609420026228520234665586889971108 9246778413354004103631553925405243
И кому понадобится узнать такое "космическое" число?
Ну ладно, не будем спорить Пусть ТС уже сам разбирается какой вариант выбирать
Может легче вручную всё вычислять?
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
28.07.2013, 20:18 22
Цитата Сообщение от Даниил1991 Посмотреть сообщение
И кому понадобится узнать такое "космическое" число?
Цель - в обучении написания таких программ, на длинную арифметику часто даются олимпиадные задачи, числа Фибоначчи используются в криптографических целях и т.д. и т.п. Этих поверхностных причин вполне достаточно.
Если ТС сам решил сделать задачу, то зачем тебе придираться к ее назначению? Зачем вообще писать программу
A+B, если проще посчитать вручную?
0
201 / 172 / 52
Регистрация: 01.06.2010
Сообщений: 371
28.07.2013, 20:19 23
хах уменьшил число и все правильно заработало)))
C++
1
unsigned long long con = 1000000000;
0
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 20:22  [ТС] 24
Цитата Сообщение от name? Посмотреть сообщение
хах уменьшил число и все правильно заработало)))
C++
1
unsigned long long con = 1000000000;
Он же вроде "незначащие" нули должен игнорировать на выходе, не?
0
201 / 172 / 52
Регистрация: 01.06.2010
Сообщений: 371
28.07.2013, 20:29 25
хотя его вообще нужно до
C++
1
int con = 10;
как раз
C++
1
2
123--: 3672674 705505779255899443
right: 36726740705505779255899443
и пропускает недостающий ноль, а потом может и не правильно начать считать
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.07.2013, 20:29 26
Цитата Сообщение от Даниил1991 Посмотреть сообщение
И кому понадобится узнать такое "космическое" число?
а вы почитайте
http://greenword.ru/2009/06/fi... uence.html
2
68 / 41 / 1
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 20:32 27
Thinker, А я даже и не знал что кому-то это может понадобится
0
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 20:33  [ТС] 28
C++
1
2
123--: 3672674 705505779255899443
right: 36726740705505779255899443
и пропускает недостающий ноль, а потом может и не правильно начать считать[/QUOTE]

в этом то и проблема. как исправить?
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
28.07.2013, 20:36 29
Thinker, хм... http://www.lhup.edu/~dsimanek/pseudo/fibonacc.htm
1
201 / 172 / 52
Регистрация: 01.06.2010
Сообщений: 371
28.07.2013, 20:40 30
Цитата Сообщение от BrainFuck Посмотреть сообщение

в этом то и проблема. как исправить?
исправить ваш
C++
1
unsigned long long con = 10000000000000000000;
на
C++
1
int con = 10;
0
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
29.07.2013, 12:11  [ТС] 31
Всем спасибо за советы, поправил. работает. вроде...
Кликните здесь для просмотра всего текста
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
 
void fo (char a)
{
    cout.fill(' ');
    cout.width(a);
}
//функция формата вывода
 
 
void fvo ()
{
    cout.fill('0');
    cout.width(19);
}
//функция форматного вывода векторов
 
 
char sdiv (int a, int b)
{
    return a/b;
}
 
 
char cif (int a)
{
    if (a != 0)
    {
        a = sdiv(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--)
            {
                if (i != b.size() - 1)
                {
                    fvo(); cout << b[i];
                }
                else
                    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;
        //if (n == 11) 
        //{
        //  cout << "0";
        //}
        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;
}


Добавлено через 3 минуты
Цитата Сообщение от name? Посмотреть сообщение
исправить ваш
C++
1
unsigned long long con = 10000000000000000000;
на
C++
1
int con = 10;
так не интересно=)

Добавлено через 15 часов 22 минуты
Цитата Сообщение от name? Посмотреть сообщение
где правильный ответ будет
1023 =
450669963367781981310438323572888604936786059621860483080302 314960003064570872139624879260914103039624487326658034501121 953020936742558101987106764609420026228520234665586889971108 9246778413354004103631553925405243
Это точно? У меня почему-то
1023-45064450027469473800934478417204499789514127430685941722460697942167189183414539 95236761733850400442321287385094586670703247122923638621283990686502484775350417 373306717238735084910144774978406511354356441956670011
0
201 / 172 / 52
Регистрация: 01.06.2010
Сообщений: 371
29.07.2013, 12:20 32
сверялся с вашей программой и предыдущей что я постил, ответы были одинаковы.
еще нашел сайт там тоже можно найти число фибоначи, но у них почему-то это же число равно 1024
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
29.07.2013, 12:22 33
Цитата Сообщение от name? Посмотреть сообщение
но у них почему-то это же число равно 1024
М.б. проблема в первом\втором числе? Проверь fib(0, 1, 2, 3)
0
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
29.07.2013, 12:28  [ТС] 34
Цитата Сообщение от Dani Посмотреть сообщение
М.б. проблема в первом\втором числе? Проверь fib(0, 1, 2, 3)
Кликните здесь для просмотра всего текста
0--1
1--1
2--2
3--3
4--5
5--8
6--13
7--21
8--34
9--55
10--89
11--144
12--233
13--377
14--610
15--987
16--1597
17--2584
18--4181
19--6765
20--10946
21--17711
22--28657
23--46368
24--75025
25--121393
26--196418
27--317811
28--514229
29--832040
30--1346269
31--2178309
32--3524578
33--5702887
34--9227465
35--14930352
36--24157817
37--39088169
38--63245986
39--102334155
40--165580141
41--267914296
42--433494437
43--701408733
44--1134903170
45--1836311903
46--2971215073
47--4807526976
48--7778742049
49--12586269025
50--20365011074
51--32951280099
52--53316291173
53--86267571272
54--139583862445
55--225851433717
56--365435296162
57--591286729879
58--956722026041
59--1548008755920
60--2504730781961
61--4052739537881
62--6557470319842
63--10610209857723
64--17167680177565
65--27777890035288
66--44945570212853
67--72723460248141
68--117669030460994
69--190392490709135
70--308061521170129
71--498454011879264
72--806515533049393
73--1304969544928657
74--2111485077978050
75--3416454622906707
76--5527939700884757
77--8944394323791464
78--14472334024676221
79--23416728348467685
80--37889062373143906
81--61305790721611591
82--99194853094755497
83--160500643816367088
84--259695496911122585
85--420196140727489673
86--679891637638612258
87--1100087778366101931
88--1779979416004714189
89--2880067194370816120
90--4660046610375530309
91--7540113804746346429
92--12200160415121876738


Вот вывод этой программы от 0 до 92-х, ошибок вроде как нет
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
29.07.2013, 12:33 35
BrainFuck, вот и фигня. У них нулевое число - это ноль, а первое и второе - 1. Будь внимательнее.
0
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
29.07.2013, 12:36  [ТС] 36
Цитата Сообщение от Dani Посмотреть сообщение
BrainFuck, вот и фигня. У них нулевое число - это ноль, а первое и второе - 1. Будь внимательнее.
но 1024 с моим 1023 всё равно не совпадает.
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
29.07.2013, 12:44 37
BrainFuck, такое ощущение, что первый пост я писал для монитора, а не для вас. вы так и не исправили ошибку с переполнением
0
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
29.07.2013, 13:05  [ТС] 38
Цитата Сообщение от ya_noob Посмотреть сообщение
BrainFuck, такое ощущение, что первый пост я писал для монитора, а не для вас. вы так и не исправили ошибку с переполнением
Чёрт, прошу прощения. Поправил. Заработало. Спасибо!
0
29.07.2013, 13:05
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.07.2013, 13:05
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
38
Ответ Создать тему
Опции темы

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