Лекция 4 (Дл.ар)

1. Длинная арифметика

1

2. Дек

Структура данных, в которой в любой конец можно
добавить элемент и из любого конца взять элемент
2

3. Пример

поле
целочисленного
типа
a=15238
8
3
2
5
1
NULL
NULL
:next
:prev
Ссылки
3

4. Описание структуры данных

struct Node
{
int data;
Node *next, *prev;
};
struct LongNumber
{
typedef Node* Long;
LongNumber a;
Long first = nullptr;
Long last = nullptr;
};
4

5.

a=15238
first
last
8
3
2
5
1
NULL
NULL
5

6. Вывод длинного числа на экран

void PrintLong(LongNumber x)
{
Long temp = x.last;
while (temp!=NULL)
{
cout << temp->data;
temp = temp->prev;
}
cout << endl;
}
6

7. Формирование длинного числа

void Init(LongNumber &a)
{
string s;
cin >> s;
for (int i = 0; i < s.length(); i+=1)
InsertBegin(a, int(s[i]) - int('0'));
}
7

8. Вставка в начало дека

void InsertBegin(LongNumber &a, int x)
{
Long temp = new Node();
temp->data = x;
temp->next = a.first;
temp->prev = nullptr;
if (a.first == nullptr) a.last = temp;
else a.first->prev = temp;
a.first = temp;
}
8

9. Вставка в конец дека

void InsertEnd(LongNumber &a, int x)
{
Long temp = new Node();
temp->data = x;
temp->next = nullptr;
temp->prev = a.last;
if (a.last == nullptr) a.first = temp;
else a.last->next = temp;
a.last = temp;
}
9

10. Задачи

Сложение двух длинных чисел.
Умножение длинного числа на число типа byte.
Сравнение двух длинных чисел.
Умножение двух длинных чисел.
Найти 100!
Деление длинных чисел.
10

11. Задача 1

Найти сумму двух длинных чисел
11

12.

LongNumber Sum(LongNumber number1, LongNumber number2) {
Long a = number1.first; Long b = number2.first;
LongNumber result;
int z = 0, x, y;
while ((a != nullptr) or (b != nullptr) or (z != 0))
{
if (a != nullptr) {
x = a->data; a = a->next; }
else x = 0;
if (b != nullptr) {
y = b->data; b = b->next; }
else y = 0;
InsertEnd(result, (x + y + z) % 10);
z = int((z + x + y) / 10);
}
return result;
}
12

13. Задача 2

Умножить длинное число на число типа Byte
13

14.

LongNumber Mult(LongNumber number1, int y){
Long a = number1.first;
LongNumber result;
int z = 0, x;
while ((a != nullptr) or (z != 0))
{
if (a != nullptr) {
x = a->data; a = a->next; }
else x = 0;
InsertEnd(result, (x * y + z) % 10);
z = int((z + x * y) / 10);
}
return result;
}
14

15. Задача 3

Написать функцию сравнения
двух длинных чисел
15

16.

int Compare(LongNumber number1, LongNumber number2) {
int r = 0;
Long a = number1.first;
Long b = number2.first;
while ((a != nullptr) and (b != nullptr))
{
if (a->data > b->data) r = 1;
else if (a->data < b->data) r = -1;
a = a->next;
b = b->next;
}
if (a != nullptr) r = 1; else if (b != nullptr) r = -1;
return r;
}
16

17. Задача 4

Найти произведение двух длинных чисел
17

18. Алгоритм

(число x должно быть больше числа y)
Пока не закончилась длина y берем последнюю
цифру
Операция умножения длинного числа на эту цифру
Добавляем в начало (i-1) нулей
Выполняем сложение этого длинного числа с
результатом
18

19. Задача 5

Найти 100!
19

20. Задача 6

Деление двух длинных чисел
(необходимы процедура вычитания из большего
числа меньшего и функция поиска очередной
цифры результата деления методом бинарного
поиска)
20