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

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

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

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

28.07.2013, 17:34. Просмотров 1167. Ответов 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-го числа выводится неверный результат. а именно теряется один знак. кто может, подскажите, в чём проблема.
0
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 номер
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 19:55 #17
Даниил1991, по твоей логике, если бы программа еще слетала на числах под порядковым номером 107, 873, 994, то ты бы написал "Никому не понадобится вычислять числа под номерами 107, 873, 994" ??
0
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 19:59 #18
Конечно нет, но большие числа для чего могут понадобится(приведите пример)? Высшая математика? Квантовая физика?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
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
Даниил
67 / 40 / 7
Регистрация: 14.05.2013
Сообщений: 383
28.07.2013, 20:11 #21
Где вы видели чтоб ТС писал что ему дали задачу?
Если можете то отправьте (цитата), а то может я ослеп
Он
Цитата Сообщение от BrainFuck Посмотреть сообщение
От нечего делать
написал программу
Цитата Сообщение от name? Посмотреть сообщение
1023 =
450669963367781981310438323572888604936786059621860483080302 314960003064570872139624879260914103039624487326658034501121 953020936742558101987106764609420026228520234665586889971108 9246778413354004103631553925405243
И кому понадобится узнать такое "космическое" число?
Ну ладно, не будем спорить Пусть ТС уже сам разбирается какой вариант выбирать
Может легче вручную всё вычислять?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 20:18 #22
Цитата Сообщение от Даниил1991 Посмотреть сообщение
И кому понадобится узнать такое "космическое" число?
Цель - в обучении написания таких программ, на длинную арифметику часто даются олимпиадные задачи, числа Фибоначчи используются в криптографических целях и т.д. и т.п. Этих поверхностных причин вполне достаточно.
Если ТС сам решил сделать задачу, то зачем тебе придираться к ее назначению? Зачем вообще писать программу
A+B, если проще посчитать вручную?
0
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 / 0
Регистрация: 06.02.2013
Сообщений: 43
28.07.2013, 20:22  [ТС] #24
Цитата Сообщение от name? Посмотреть сообщение
хах уменьшил число и все правильно заработало)))
C++
1
unsigned long long con = 1000000000;
Он же вроде "незначащие" нули должен игнорировать на выходе, не?
0
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
и пропускает недостающий ноль, а потом может и не правильно начать считать
1
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.07.2013, 20:29 #26
Цитата Сообщение от Даниил1991 Посмотреть сообщение
И кому понадобится узнать такое "космическое" число?
а вы почитайте
http://greenword.ru/2009/06/fibonacci-sequence.html
2
Даниил
67 / 40 / 7
Регистрация: 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
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
1
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;
0
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