Сложение двух больших чисел

@Zverit · Регистрация: 07.02.2010

Студворк — интернет-сервис помощи студентам

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
#include <vector>
#include <fstream>
#include <string>
using namespace std;
 
int main()
{
 
const int base = 1000 * 1000 * 1000;   
vector <int> n;
vector <int> a;
 
string s,m;
 
ifstream fin ("INPUT.TXT");
ofstream fout ("OUTPUT.TXT");
 
fin>>s>>m;
 
for (int i=(int)s.length(); i>0; i-=9)
    if (i < 9)
        a.push_back (atoi (s.substr (0, i).c_str()));
    else
        a.push_back (atoi (s.substr (i-9, 9).c_str()));
        
 
for (int i=(int)m.length(); i>0; i-=9)
    if (i < 9)
        n.push_back (atoi (m.substr (0, i).c_str()));
    else
        n.push_back (atoi (m.substr (i-9, 9).c_str()));
        
 
int count = 0;
 
for (size_t i = 0; i < max(n.size(), a.size())||count; ++i){
   if (i == n.size()) 
      n.push_back(0);
    n[i] += count + (i < a.size() ? a[i] : 0);
    count  = n[i] >= base;
    if (count) a[i] -= base;
}
 fout<<(n.empty() ? 0 : n.back());
for (int i = (int) n.size() - 2; i >= 0; i--)
fout<<n[i];
 
    return 0;
}

Подскажите в чем ошибка? Вроде все правильно, но не проходит 4 тест на acmp.ru

@diagon · 05.10.2011, 16:18

На тест
1000000000
1

У вас выходит 11.

@gooseim · 05.10.2011, 16:49

Почему бы не воспользоваться готовыми библиотеками для работы с большими числами благо их полно.

@Zverit · 05.10.2011, 18:02 **[ТС]**

gooseim, Да с удовольствием! Только, на олимпиаде , боюсь, не разрешат.

@diagon · 05.10.2011, 19:01

Сообщение от gooseim

Почему бы не воспользоваться готовыми библиотеками для работы с большими числами благо их полно.

Вряд ли на олимпиаде будут компиляторы с установленным бустом/gmp/etc =)
Зато возможно будет такое(все решение в 26-28 строках)

Java
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
import java.io.*;
 
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main
{
    public static void main( String[] args ) throws IOException
    {
        new Main().run();
    }    
    
    Scanner in;
    PrintWriter out;
    
    void run() throws IOException
    {
        in = new Scanner ( System.in );
        out = new PrintWriter ( System.out );
        solve();
        out.flush();
    }
    
    void solve() throws IOException
    {
        BigInteger a = in.nextBigInteger();
        BigInteger b = in.nextBigInteger();
        out.println( a.add(b) );
    }
    
}

@Zverit · 05.10.2011, 19:11 **[ТС]**

diagon, в Java не силен. Времени на изучение нет. Не такая уж и сложная эта арифметика. Да и для понятия алгоритмов пригодится.

@KeyGen · 06.10.2011, 01:25

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
#include <iostream>
using namespace std;
    
int charvint(char * mass, int *mass);
 
int main()
{
    setlocale(LC_ALL, "rus");
    
    cout << "Ââåäèòå ïåðâîå ÷èñëî: ";
    
    int l1;
    char massc[20]={};
    int massi[20]={};
    cin.get(massc,20);
    l1=charvint(massc,massi);
    cin.get();
    
    cout << "Ââåäèòå âòîðîå ÷èñëî: ";
    
    int l2;
    char massc1[20]={};
    int massi1[20]={};
    cin.get(massc1,20);
    l2=charvint(massc1,massi1);
    cin.get();
 /////////////////////////////////////////////   
    int schet=0;
    int kk;
    if(l2<l1){
    kk=l1;
    
    for (int i=0; i<kk; i++)
    if (massi1[i]!=0)
    schet++;
    schet=kk-schet;
    
    for (int i=0; i<kk; i++)
    massi1[i+schet]=massi1[i];
    for (int i=0; i<schet; i++)
    massi1[i]=0;  
    }
    else if(l2>l1){
    kk=l2;
    
    for (int i=0; i<kk; i++)
    if (massi[i]!=0)
    schet++;
    schet=kk-schet;
    
    for (int i=0; i<kk; i++)
    massi[i+schet]=massi[i];
    for (int i=0; i<schet; i++)
    massi[i]=0;  
    }
    else
    kk=l2;
 
 ///////////////////////////////////////////// 
    cout << "Ââåäèòå çíàê + : ";
    
    int massiv[20]={};
    char plus;
    cin >> plus;
    if(plus=='+')
    for(int i=kk-1; i>=0; i--){
    massiv[i]+=massi[i]+massi1[i];
    if (massiv[i]>9){
    massiv[i]-=10;
    massiv[i-1]+=1;}
    }
    
    cout << "Îòâåò: ";
    
    for(int i=0; i<kk; i++)
    cout << massiv[i];
    
    
    
    
    cout << "\n\n\n";
    system("PAUSE");
    return 0;
}
//Ïåðåâîä èç ìàññèâà char öèôðû â ìàññèâ int
int charvint(char * massc, int *massi){
     int l=0;
     for(int i=0; massc[i]!='\0'; i++,l++){
     massi[i]=int(massc[i]);
     massi[i]-=48;
     }
     return l;
}

Да вот только 99 и 99 уже не сложить, (198) 1-ка выходит за приделы куда-то)). Но это, в принципе, можно исправить.

@KeyGen · 06.10.2011, 19:55

Переписал. Все исправил. Все чудно работает. Размер цифр зависит только от размера массивов.

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
#include <iostream>
using namespace std;
 
const int Size=41;
    
int charvint(char *, int *);
 
void Sum(char *,char *);
 
int main()
{
    setlocale(LC_ALL, "rus");
    
    cout << "Ââåäèòå ïåðâîå ÷èñëî: ";
    char massc[Size];
    cin.get(massc,Size);
    cin.get();
    
    cout << "Ââåäèòå âòîðîå ÷èñëî: ";
    char massc1[Size];
    cin.get(massc1,Size);
    cin.get();
    
    Sum(massc,massc1);
    
    
    cout << "\n\n\n";
    system("PAUSE");
    return 0;
}
//Ïåðåâîä èç ìàññèâà char öèôðû â ìàññèâ int
int charvint(char * massc, int *massi){
     int l=0;
     for(int i=0; massc[i]!='\0'; i++,l++){
     massi[i]=int(massc[i]);
     massi[i]-=48;
     }
     return l;
}
 
//Âûïîëíåíèå ñëîæåíèÿ
void Sum(char *massc,char *massc1){
     
    int l1;
    int massi[Size];
    for (int i=0; i<Size; i++)
    massi[i]=22;
    
    l1=charvint(massc,massi);
    
    int l2;
    int massi1[Size];
    for (int i=0; i<Size; i++)
    massi1[i]=22;
    
    l2=charvint(massc1,massi1);
     
    int schet=0;
    int kk;
    if(l2<l1){
    kk=l1;
    
    for (int i=0; i<kk; i++)
    if (massi1[i]!=22)
    schet++;
    schet=kk-schet;
    
    for (int i=kk; i>=0; i--)
    massi1[i+schet]=massi1[i];
    for (int i=0; i<schet; i++)
    massi1[i]=0;  
    }
    else if(l2>l1){
    kk=l2;
    
    for (int i=0; i<kk; i++)
    if (massi[i]!=22)
    schet++;
    schet=kk-schet;
    
    for (int i=kk; i>=0; i--)
    massi[i+schet]=massi[i];
    for (int i=0; i<schet; i++)
    massi[i]=0;  
    }
    else
    kk=l2; 
 
 for (int i=kk; i>=0; i--){
    massi[i+1]=massi[i];
    massi1[i+1]=massi1[i];
}
    massi[0]=0;
    massi1[0]=0;
 
    
    int massiv[Size]={};
    
    
    for(int i=kk; i>0; i--){
    massiv[i]+=massi[i]+massi1[i];
    if (massiv[i]>9){
    massiv[i]-=10;
    massiv[i-1]+=1;}
    }
    
    cout << "               Îòâåò: ";
    if(massiv[0]==0)
    for(int i=1; i<=kk; i++)
    cout << massiv[i];
    else
    for(int i=0; i<=kk; i++)
    cout << massiv[i];
 
}

@KeyGen · 06.10.2011, 20:03

Нашел ошибку... Потом как нибудь исправлю. После 23-х значное число не суммируется с меньшим числом. В остальном вроде порядок.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	05.10.2011, 16:18
	На тест 1000000000 1 У вас выходит 11. 1

@gooseim 516 / 421 / 92 Регистрация: 23.09.2010 Сообщений: 1,165
	05.10.2011, 16:49
	Почему бы не воспользоваться готовыми библиотеками для работы с большими числами благо их полно. 0

@Zverit Уничтожитель печенек 281 / 209 / 49 Регистрация: 07.02.2010 Сообщений: 724
	05.10.2011, 18:02 [ТС]
	gooseim, Да с удовольствием! Только, на олимпиаде , боюсь, не разрешат. 0

@Zverit Уничтожитель печенек 281 / 209 / 49 Регистрация: 07.02.2010 Сообщений: 724
	05.10.2011, 19:11 [ТС]
	diagon, в Java не силен. Времени на изучение нет. Не такая уж и сложная эта арифметика. Да и для понятия алгоритмов пригодится. 1

@KeyGen 388 / 295 / 21 Регистрация: 07.08.2011 Сообщений: 790 Записей в блоге: 1
	06.10.2011, 20:03
	Нашел ошибку... Потом как нибудь исправлю. После 23-х значное число не суммируется с меньшим числом. В остальном вроде порядок. 1