Форум программистов, компьютерный форум 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-го числа выводится неверный результат. а именно теряется один знак. кто может, подскажите, в чём проблема.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 20:11     Длинные фиббоначи #21
Где вы видели чтоб ТС писал что ему дали задачу?
Если можете то отправьте (цитата), а то может я ослеп
Он
Цитата Сообщение от BrainFuck Посмотреть сообщение
От нечего делать
написал программу
Цитата Сообщение от name? Посмотреть сообщение
1023 =
450669963367781981310438323572888604936786059621860483080302 314960003064570872139624879260914103039624487326658034501121 953020936742558101987106764609420026228520234665586889971108 9246778413354004103631553925405243
И кому понадобится узнать такое "космическое" число?
Ну ладно, не будем спорить Пусть ТС уже сам разбирается какой вариант выбирать
Может легче вручную всё вычислять?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 20:18     Длинные фиббоначи #22
Цитата Сообщение от Даниил1991 Посмотреть сообщение
И кому понадобится узнать такое "космическое" число?
Цель - в обучении написания таких программ, на длинную арифметику часто даются олимпиадные задачи, числа Фибоначчи используются в криптографических целях и т.д. и т.п. Этих поверхностных причин вполне достаточно.
Если ТС сам решил сделать задачу, то зачем тебе придираться к ее назначению? Зачем вообще писать программу
A+B, если проще посчитать вручную?
name?
 Аватар для name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 368
Завершенные тесты: 1
28.07.2013, 20:19     Длинные фиббоначи #23
хах уменьшил число и все правильно заработало)))
C++
1
unsigned long long con = 1000000000;
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 20:22  [ТС]     Длинные фиббоначи #24
Цитата Сообщение от name? Посмотреть сообщение
хах уменьшил число и все правильно заработало)))
C++
1
unsigned long long con = 1000000000;
Он же вроде "незначащие" нули должен игнорировать на выходе, не?
name?
 Аватар для name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 368
Завершенные тесты: 1
28.07.2013, 20:29     Длинные фиббоначи #25
хотя его вообще нужно до
C++
1
int con = 10;
как раз
C++
1
2
123--: 3672674 705505779255899443
right: 36726740705505779255899443
и пропускает недостающий ноль, а потом может и не правильно начать считать
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.07.2013, 20:29     Длинные фиббоначи #26
Цитата Сообщение от Даниил1991 Посмотреть сообщение
И кому понадобится узнать такое "космическое" число?
а вы почитайте
http://greenword.ru/2009/06/fibonacci-sequence.html
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 20:32     Длинные фиббоначи #27
Thinker, А я даже и не знал что кому-то это может понадобится
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 20:33  [ТС]     Длинные фиббоначи #28
C++
1
2
123--: 3672674 705505779255899443
right: 36726740705505779255899443
и пропускает недостающий ноль, а потом может и не правильно начать считать[/QUOTE]

в этом то и проблема. как исправить?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 20:36     Длинные фиббоначи #29
Thinker, хм... http://www.lhup.edu/~dsimanek/pseudo/fibonacc.htm
name?
 Аватар для name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 368
Завершенные тесты: 1
28.07.2013, 20:40     Длинные фиббоначи #30
Цитата Сообщение от BrainFuck Посмотреть сообщение

в этом то и проблема. как исправить?
исправить ваш
C++
1
unsigned long long con = 10000000000000000000;
на
C++
1
int con = 10;
Мозготрёп
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-4506445002746947380093447841720449978951412743068594172246069794216718918341453995236761733850400442321287385094586670703247122923638621283990686502484775350417373306717238735084910144774978406511354356441956670011
name?
 Аватар для name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 368
Завершенные тесты: 1
29.07.2013, 12:20     Длинные фиббоначи #32
сверялся с вашей программой и предыдущей что я постил, ответы были одинаковы.
еще нашел сайт там тоже можно найти число фибоначи, но у них почему-то это же число равно 1024
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
29.07.2013, 12:22     Длинные фиббоначи #33
Цитата Сообщение от name? Посмотреть сообщение
но у них почему-то это же число равно 1024
М.б. проблема в первом\втором числе? Проверь fib(0, 1, 2, 3)
Мозготрёп
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-х, ошибок вроде как нет
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
29.07.2013, 12:33     Длинные фиббоначи #35
BrainFuck, вот и фигня. У них нулевое число - это ноль, а первое и второе - 1. Будь внимательнее.
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
29.07.2013, 12:36  [ТС]     Длинные фиббоначи #36
Цитата Сообщение от Dani Посмотреть сообщение
BrainFuck, вот и фигня. У них нулевое число - это ноль, а первое и второе - 1. Будь внимательнее.
но 1024 с моим 1023 всё равно не совпадает.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
29.07.2013, 12:44     Длинные фиббоначи #37
BrainFuck, такое ощущение, что первый пост я писал для монитора, а не для вас. вы так и не исправили ошибку с переполнением
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2013, 13:05     Длинные фиббоначи
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
29.07.2013, 13:05  [ТС]     Длинные фиббоначи #38
Цитата Сообщение от ya_noob Посмотреть сообщение
BrainFuck, такое ощущение, что первый пост я писал для монитора, а не для вас. вы так и не исправили ошибку с переполнением
Чёрт, прошу прощения. Поправил. Заработало. Спасибо!
Yandex
Объявления
29.07.2013, 13:05     Длинные фиббоначи
Ответ Создать тему
Опции темы

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