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

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

Войти
Регистрация
Восстановить пароль
 
nuts23
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
#1

Ошибка в реализации длинной арифметики - C++

24.09.2013, 18:51. Просмотров 346. Ответов 6
Метки нет (Все метки)

Здравствуйте.
Я скопировал с e-maxx'а и объединил всё в одну программу:
C++ (Qt)
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
#include <stdio.h>
#include <math.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
const int base = 1000*1000*1000;
 
void sum(vector<int> *a, vector<int> *b) //Прибавляет к числу a число b и сохраняет результат в a
{
    int carry = 0;
    for (size_t i=0; i<max(a->size(),b->size()) || carry; ++i)
    {
        if (i == a->size())
            a->push_back (0);
        (*a)[i] += carry + (i < b->size() ? (*b)[i] : 0);
        carry = (*a)[i] >= base;
        if (carry)
            (*a)[i] -= base;
    }
    while (a->size() > 1 && a->back() == 0)
        a->pop_back();
}
void vich(vector<int> *a, vector<int> *b) //Отнимает от числа a число b число (a >= b) и сохраняет результат в a
{
    int carry = 0;
    for (size_t i=0; i<b->size() || carry; ++i)
    {
        (*a)[i] -= carry + (i < b->size() ? (*b)[i] : 0);
        carry = (*a)[i] < 0;
        if (carry)
          (*a)[i] += base;
    }
    while (a->size() > 1 && a->back() == 0)
        a->pop_back();
}
void umn_kor(vector<int> *a, int b) //Умножает длинное a на короткое b (b < base) и сохраняет результат в a
{
    int carry = 0;
    for (size_t i=0; i<a->size() || carry; ++i) {
        if (i == a->size())
            a->push_back (0);
        long long cur = carry + (*a)[i] * 1ll* b;
        (*a)[i] = int (cur % base);
        carry = int (cur / base);
    }
    while (a->size() > 1 && a->back() == 0)
        a->pop_back();
}
void delen(vector<int> *a, int b) //Делит длинное a на короткое b (b < base), частное сохраняет в a, остаток в carry
{
    int carry = 0;
    for (int i=(int)a->size()-1; i>=0; --i) {
        long long cur = (*a)[i] + carry * 1ll * base;
        (*a)[i] = int (cur / b);
        carry = int (cur % b);
    }
    while (a->size() > 1 && a->back() == 0)
        a->pop_back();
}
int main()
{
    vector<int> a;
    vector<int> b;
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    char s[10000];
    gets(s);
    // чтение
    for (int i=(int)strlen(s); i>0; i-=9)
    {
        s[i] = 0;
        a.push_back (atoi (i>=9 ? s+i-9 : s));
    }
    //лидирующие нули
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
    gets(s);
    for (int i=(int)strlen(s); i>0; i-=9)
    {
        s[i] = 0;
        b.push_back (atoi (i>=9 ? s+i-9 : s));
    }
    while (b.size() > 1 && b.back() == 0)
        b.pop_back();
    //вывод
    sum(&a, &b);
    printf ("%d", a.empty() ? 0 : a.back());
    for (int i=(int)a.size()-2; i>=0; --i)
        printf ("%09d", a[i]);
    printf("\n");
    vich(&a, &b);
    printf ("%d", a.empty() ? 0 : a.back());
    for (int i=(int)a.size()-2; i>=0; --i)
        printf ("%09d", a[i]);
    printf("\n");
    umn_kor(&a, 100);
    printf ("%d", a.empty() ? 0 : a.back());
    for (int i=(int)a.size()-2; i>=0; --i)
        printf ("%09d", a[i]);
    printf("\n");
    delen(&a, 1000);
    printf ("%d", a.empty() ? 0 : a.back());
    for (int i=(int)a.size()-2; i>=0; --i)
        printf ("%09d", a[i]);
    return 0;
}
Программа при
123456789
1000
возвращает (сумму, разность, произведение, частное)
123457789
123456789
12345678900
12345678
Проблема в том, что она делит и умножает только на b (второе число) <= 100. Т.е. при b = 10^3 или b = 10^6 она всё равно умножает и делит на 100. Если b <= 100, то она умножает на b.
Подскажите, пожалуйста, в чём проблема.
Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2013, 18:51     Ошибка в реализации длинной арифметики
Посмотрите здесь:

C++ Ошибка при выводе самой длинной строчки.
C++ Переделать функцию поиска самой длинной строки так, чтобы она правильно печатала размер произвольно длинной входной строки и воспроизводила ее
C++ Вычислить значение суммы. Задача с использованием "длинной арифметики".
C++ Выделение памяти в куче для строки для реализации длинной арифметики
Ошибка в длинной арифметике C++
C++ Класс длинной арифметики
C++ Ошибка в реализации вектора
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
VEINHORN
542 / 91 / 22
Регистрация: 16.12.2011
Сообщений: 317
24.09.2013, 19:48     Ошибка в реализации длинной арифметики #2
Что программа реализует?
nuts23
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
24.09.2013, 19:50  [ТС]     Ошибка в реализации длинной арифметики #3
Программа считывает 2 длинных числа, расположенных в 1 и 2 строчках соответственно.
Потом их складывает, вычитает 2 из суммы, полученное число умножает и делит на b.
Брал отсюда: http://e-maxx.ru/algo/big_integer
zer0mail
Нарушитель
2321 / 1947 / 192
Регистрация: 03.07.2012
Сообщений: 6,970
Записей в блоге: 1
24.09.2013, 19:55     Ошибка в реализации длинной арифметики #4
nuts23, зачем тебе сдалась эта длинная арифметика?
nuts23
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
24.09.2013, 20:00  [ТС]     Ошибка в реализации длинной арифметики #5
Олимпиадное программирование.
Если точнее, то считатать сумму факториалов, а потом разделить на сумму степеней, так что необходимо реализовать все эти операции.
zer0mail
Нарушитель
2321 / 1947 / 192
Регистрация: 03.07.2012
Сообщений: 6,970
Записей в блоге: 1
24.09.2013, 20:42     Ошибка в реализации длинной арифметики #6
nuts23, т.е. имея перед глазами код, ты не можешь понять, почему он не работает и при этом хочешь заниматься олимпиадным программированием? Прям анекдот, да и только .
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2013, 21:13     Ошибка в реализации длинной арифметики
Еще ссылки по теме:

Реализация длинной целочисленной арифметики C++
C++ Объясните код длинной арифметики
Ошибка при реализации стека C++
C++ Ищу примеры реализации длинной арифметики
C++ Ошибка в реализации связного списка

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

Или воспользуйтесь поиском по форуму:
nuts23
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
24.09.2013, 21:13  [ТС]     Ошибка в реализации длинной арифметики #7
Сложение и вычитание работает на отлично
Проблема только с делением и умножением, и то, алгоритмическая часть работает правильно.
Yandex
Объявления
24.09.2013, 21:13     Ошибка в реализации длинной арифметики
Ответ Создать тему
Опции темы

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