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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Мозготрёп
0 / 0 / 0
Регистрация: 06.02.2013
Сообщений: 43
#1

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

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

От нечего делать написал это:
Кликните здесь для просмотра всего текста
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-го числа выводится неверный результат. а именно теряется один знак. кто может, подскажите, в чём проблема.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2013, 17:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Длинные фиббоначи (C++):

Фиббоначи. - C++
Верно ли, что сумма первых n членов последовательности Фибоначчи есть четное число. Решите пожалуйста):)

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:50 #16
Ахах Как вы посчитали это? *сарказм*
Ну при вводе 1000 вроде бы ответ правильный, по крайней мере без -
Значит сфейлился я
Ну я думаю что никому не нужно узнавать 1023 номер
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 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
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 20:06 #19
Даниил1991, тогда по твоей логике, зачем вообще находить числа Фибоначчи, если они не влазят в int? Зачем мне приводить пример? Если у него такое задание и ты не можешь его правильно выполнить, то будешь придираться к назначению этого задания? Может это и надо в высшей математике, тебе какое дело до этого? Это дело ТС, раз есть такое задание, то его нужно выполнить, а не придираться к нему.
Мозготрёп
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 влияет только на вывод.
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 20:11 #21
Где вы видели чтоб ТС писал что ему дали задачу?
Если можете то отправьте (цитата), а то может я ослеп
Он
Цитата Сообщение от BrainFuck Посмотреть сообщение
От нечего делать
написал программу
Цитата Сообщение от name? Посмотреть сообщение
1023 =
450669963367781981310438323572888604936786059621860483080302 314960003064570872139624879260914103039624487326658034501121 953020936742558101987106764609420026228520234665586889971108 9246778413354004103631553925405243
И кому понадобится узнать такое "космическое" число?
Ну ладно, не будем спорить Пусть ТС уже сам разбирается какой вариант выбирать
Может легче вручную всё вычислять?
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 20:18 #22
Цитата Сообщение от Даниил1991 Посмотреть сообщение
И кому понадобится узнать такое "космическое" число?
Цель - в обучении написания таких программ, на длинную арифметику часто даются олимпиадные задачи, числа Фибоначчи используются в криптографических целях и т.д. и т.п. Этих поверхностных причин вполне достаточно.
Если ТС сам решил сделать задачу, то зачем тебе придираться к ее назначению? Зачем вообще писать программу
A+B, если проще посчитать вручную?
name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 371
Завершенные тесты: 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?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 371
Завершенные тесты: 1
28.07.2013, 20:29 #25
хотя его вообще нужно до
C++
1
int con = 10;
как раз
C++
1
2
123--: 3672674 705505779255899443
right: 36726740705505779255899443
и пропускает недостающий ноль, а потом может и не правильно начать считать
Thinker
Эксперт C++
4225 / 2199 / 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
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 20:36 #29
Thinker, хм... http://www.lhup.edu/~dsimanek/pseudo/fibonacc.htm
name?
198 / 169 / 18
Регистрация: 01.06.2010
Сообщений: 371
Завершенные тесты: 1
28.07.2013, 20:40 #30
Цитата Сообщение от BrainFuck Посмотреть сообщение

в этом то и проблема. как исправить?
исправить ваш
C++
1
unsigned long long con = 10000000000000000000;
на
C++
1
int con = 10;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2013, 20:40
Привет! Вот еще темы с ответами:

Вывести первые 100 чисел Фиббоначи - C++
на вывести на с++ первые 100 чисел фиббаначи

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

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

Через рекурсию посчитать сумму элементов фиббоначи - C++
Есть последовательность Фиббоначи: 1 1 2 3 5 8 13 Посчитать сумму послед-сти до данного n-ого числа с помощью рекурсивной функции. Вот...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
28.07.2013, 20:40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru