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

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

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

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

24.09.2013, 18:51. Просмотров 367. Ответов 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++
Здравствуйте! Скиньте пожалуйста примеры решения задач на тему &quot;Длинная арифметика&quot;! Желательно с подробным пояснением! Язык C++. Очень...

Выделение памяти в куче для строки для реализации длинной арифметики - C++
Доброго времени суток, пишу класс string, на основе которого потом хочу реализовать класс для длинной арифметики. Поэтому мне понадобился...

Класс длинной арифметики - C++
Дайте класс длинной арифметики - хотелось бы разобраться в этой штуке, а то какие исходники не найду - то не рабочие, то еще что-то( ...

Реализация длинной целочисленной арифметики - C++
Добрый день! Возникла такая проблема: была поставлена задача реализовать детерминированный тест Миллера на простоту. С этим более-менее...

Объясните код длинной арифметики - C++
Не могу понять синтаксиса этого кода void add(vlong *op1, vlong *op2, vlong *res) { vlong *mxop, *mnop; int i, flag=0, st; mxop =...

Вычислить значение суммы. Задача с использованием "длинной арифметики". - C++
Тема: «Задачи на длинную арифметику» Задача: Вычислить точное значение суммы 1^2 + 2^2 + 3^2 + ... + n^2 (n ≥ 20000). Пожалуйста,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
VEINHORN
543 / 92 / 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
2332 / 1958 / 192
Регистрация: 03.07.2012
Сообщений: 7,021
Записей в блоге: 1
24.09.2013, 19:55 #4
nuts23, зачем тебе сдалась эта длинная арифметика?
nuts23
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
24.09.2013, 20:00  [ТС] #5
Олимпиадное программирование.
Если точнее, то считатать сумму факториалов, а потом разделить на сумму степеней, так что необходимо реализовать все эти операции.
zer0mail
2332 / 1958 / 192
Регистрация: 03.07.2012
Сообщений: 7,021
Записей в блоге: 1
24.09.2013, 20:42 #6
nuts23, т.е. имея перед глазами код, ты не можешь понять, почему он не работает и при этом хочешь заниматься олимпиадным программированием? Прям анекдот, да и только .
nuts23
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
24.09.2013, 21:13  [ТС] #7
Сложение и вычитание работает на отлично
Проблема только с делением и умножением, и то, алгоритмическая часть работает правильно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2013, 21:13
Привет! Вот еще темы с ответами:

Ошибка в длинной арифметике - C++
Помогите найти ошибку в программе. Задача сводится к тому, чтобы просумировать числа ввода и вычислить их среднее арифметическое. Немогу...

Ошибка при выводе самой длинной строчки. - C++
#include&lt;iostream.h&gt; #include&lt;conio.h&gt; #include&lt;string.h&gt; using namespace std; void main() {string s;int n,k,min; ...

Ошибка в реализации вектора - C++
здравствуйте, прошу помочь найти ошибку в простой реализации вектора. ошибка возникает когда вызывается pop_back(), однако совершенно не...

Переделать функцию поиска самой длинной строки так, чтобы она правильно печатала размер произвольно длинной входной строки и воспроизводила ее - C++
Переделать головную функцию поиска самой длинной строки так, чтобы она правильно печатала размер произвольно длинной входной строки...


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

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

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