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
|
#include <iostream>
const size_t NUM_W = 30;
/* Помощни, за удобство */
void readNum(int num[NUM_W]) {
for (size_t i = 0; i < NUM_W; i++) {
std::cin >> num[i];
}
}
void printNum(int num[NUM_W]) {
bool pastLeadingZeroes = false;
for (size_t i = 0; i < NUM_W; i++) {
if ((!pastLeadingZeroes && num[i] != 0) || i == NUM_W - 1) {
pastLeadingZeroes = true;
}
if (pastLeadingZeroes) {
std::cout << num[i];
}
}
std::cout << std::endl;
}
/* Логика от задачата */
void sum(int num1[NUM_W], int num2[NUM_W], int onum[NUM_W]) {
/* Не забравяйте, че ако е въведено числото 9000...0358, тогава
* в нашия масив ще сме запазили цифрите в същата последователност,
* тоест най-лявата стойност е 9, тази в дясно е 0 и так. нат.
*
* Обаче, най-лявата стойност в масива е на индекс 0, докато ние
* искаме да сумираме цифри от дясно наляво, тоест въртим в обратен ред цикъла.
*
* Друг проблем - size_t е unsigned, тоест не можем да направим условието да е
* i >= 0, защото когато направим i-- при i=0, ще получим underflow и числото ще
* стане най-голямото възможно за size_t и забиваме в безкраен цикъл.
* Затова правим друго - нека запазим същата идея и 0 да означава край на цикъла.
* Тогава нашето i ще бъде между 30 и 0, като когато е между 30 и 1 индексираме в
* масива, и затова правим i-1, защото при i=1 искаме най-левия елемент в масива.
*/
for (size_t i = NUM_W; i > 0; i--) {
onum[i-1] += num1[i-1] + num2[i-1];
/* Логика за преливане:
* Ако имаме ... 0 9 + ... 0 1, трябва да получим ... 1 0
* Тоест, ако сумата на i-тите цифри е >= 10, значи преливаме в цифрата в ляво.
* Колко най-много може да бъде тази сума? Еми, една цифра може да е максимум 9,
* така че сумата на две цифри може да е максимум 9+9=18.
*
* Следователно, ако имаме примерно сума 18, искаме i-тата цифра да бъде 8 и
* цифрата в ляво от нея да бъде 1.
* Лявата винаги я правим 1, няма какво друго да бъде, а i-тата става втората
* цифра на 18, тоест 8. Това го получаваме с % 10
*/
if (onum[i-1] >= 10 && i > 1) {
onum[i-2] = 1;
onum[i-1] %= 10;
}
}
/* Преливане при най-лявата цифра:
* Какво става ако най-лявата цифра е (примерно) 18?
* В нашия цикъл няма да я преливаме, защото няма друга лява цифра, в която да прелее.
* Обаче не може да я оставим да е > 9
*
* Компоромис - пак правим преливането, обаче никъде не слагаме прелялата 1ца.
* Тоест, нашата сума ще съдържа най-десните 30 цифри от "истинската" сума.
*/
if (onum[0] >= 10) {
onum[0] %= 10;
}
}
void sub(int num1[NUM_W], int num2[NUM_W], int onum[NUM_W]) {
/* Отновно индексиране погледни в sum функцията
*/
for (size_t i = NUM_W; i > 0; i--) {
onum[i-1] += num1[i-1] - num2[i-1];
/* Логика при underflow:
* Какво става, когато трябва да вземем "на ум", тоест примерно при
* ... 1 0 - ... 0 5?
* Ако се намираме на най-дясната цифра, тогава имаме 0-5=-5
* За вземане на ум искаме от лявата цифра да извадим 1ца и сегашната да бъде
* 10-5=5 вместо 0-5=-5.
*/
if (onum[i-1] < 0 && i > 1) {
onum[i-2] = -1;
onum[i-1] += 10;
}
}
/* Underflow на най-лявата цифра:
* Какво става ако най-лявата цифра също е в underflow, примерно при 0 ... 0 0 - 0 ... 0 1?
*
* Както при сумата, предстаявме си, че сме взели от някъде единица от лявата цифра, затова
* оправяме сегашната с това in mind.
* Така отново, ние пазим най-десните 30 цифри от истинската разлика, които са коректни.
*/
if (onum[0] < 0) {
onum[0] += 10;
}
}
int main() {
int num1[NUM_W] = { 0 }, num2[NUM_W] = { 0 }, res[NUM_W] = { 0 };
readNum(num1);
readNum(num2);
char op;
std::cin >> op;
if (op == '+') {
sum(num1, num2, res);
}
else if (op == '-') {
sub(num1, num2, res);
}
printNum(res);
}
|
