Одномерные массивы и работа со строками презентация

1-го курса ММФ ПГНИУ,
учебной группы ПМИ – 1 Зимин Илья

(m, n > 20).

m>20

n>20

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

Для этого я создал два массива типа Char, и назвал их таким образом: numerator[] – делимое, denominator[] - делитель

char numerator[N];

char denominator[N];

Const int N = 100000; // Заведём константу

И введём наши числа:

Input (char[], &int);

Длина числа

Int m = длина делимого

Int n = длина делителя

Для начала разберёмся с вводом) Из условия видно, что подаются два числа в виде строк

Массив для ввода

продемонстрировать алгоритм, не обязательно брать число, которое содержат >20 разрядов

Пока мы не нажмём ENTER:

Array[i] = getchar()-48;

(-48(код ‘0’)) – переделываем
из кода цифры в саму цифру

Int i =0;

i ++;

Array = {

}

0 1 2 3 4 5 6 7 8 9 10 11 12 13

m = i (устанавливаем длину числа)

5

7

3

1

8

2

5

4

9

2

5

8

3

1

деление столбиком
Предположим что мы уже заполнили два наших массива numerator = 57318254912583
denominator = 64752467899

И тут мы понимаем что нам нужен ещё один массив для хранения остатка, ведь постоянно менять делимое не так то и удобно, поэтому мы заводим ещё один массив с именем modulo

char modulo[N];

// И заполним мы его как первое уменьшаемое (то есть мы поместим в него ту часть делимого которая является минимально возможной, чтобы хотя б один раз поделить на наш делитель )

FirstMinuend (numerator,m,denominator,n,modulo,nMod);

Int nMod = размер

если длина делителя больше или равна(но при этом и само число больше) длине делимого, то у нас делимое и будет являться остатком, если это не так то мы:
Первым шагом заполняем массив, первыми n (количество цифр в ДЕЛИТЕЛЕ) цифрами

5

7

3

1

8

2

5

4

9

1

2

5

8

3

На самом деле мы в ней просто ищем то самое первое уменьшаемое
Для чего оно нужно? Узнаете позже

nMod = n

modulo = {

}

m = 14

n = 11

Дальше мы смотрим при помощи функций More и Equally, больше или равен Modulo делимому,
Если это так, то функция прекращает работу, иначе мы добавляем ещё одну цифру
в Modulo, в этом собственно и суть отдельного метода. В нашем же случае снесём ещё цифру

11

nMod = n+1

0 1 2 3 4 5 6 7 8 9 10

5

5

7

3

1

8

2

5

4

9

1

2

то не тронутые цифры в делимом, и первым делом, после завершения работы, функции с предыдущего слайда, мы запомним длину массива с остатком в переменную startIndex, чтобы мы знали с какой позиции мы будем начинать брать следующие цифры от делимого.
Мы уже выяснили что длина делителя равна 11, а длина первого уменьшаемого равна длине делителя плюс 1, то есть 12, а значит startIndex = 12

numerator = 57318254912583

startIndex

этапов работы программы, это...
Вычитание! Первое уменьшаемое готово: modulo[]=573182549125
вычитаемое есть: denominator[] = 64752467899
На самом деле всё просто, мы будем вычитать из первого, второе пока modulo[] >= denominator[]; (опять же сравнивать будем при помощи функций More и Equally) В противном случае мы не будем заходить в функцию вычитания

Subtract(char a[], int &n, char b[], int &m)

Длина уменьшаемого

Длина вычитаемого

Уменьшаемое

Вычитаемое

64752467899 Так как они поданы нам в виде массивов то вычитание придётся делать столбиком.
Если вдруг делитель всё же меньше делимого по длине то мы дополняем его нулями спереди при помощи простой функции InsertZero, в нашем примере как раз придётся добавить один нулик спереди к делителю

Subtract – разберём работу данной функции

-

< 0

Loan = -1

5

0

8

4

3

0

0

8

1

2

2

6

573182549125

________________

064752467899

+10

+

Вычитание прекратится, когда modulo станет равно 055162805933
то есть меньше 064752467899

Не сложно заметить что в начале каждого из чисел стоят нули, а значит их нужно убрать!
Для этого можно воспользоваться простой, написанной функцией DeleteZero

= 57318254912583
StartIndex = 12
А теперь как раз и пора вспомнить про StartIndex ведь теперь нам потребуются все цифры, начиная с элемента лежащего в ячейке с данным индексом массива делимого. А для этого мы будем использовать цикл от этого самого StartIndex и до m (длина делимого)
Итак в цикле нам следует добавить элемент(ещё одну цифру) справа, это будет элемент из массива делимого с индексом 12, то есть добавляется цифра 8.

551628059338
denominator = 64752467899
Как видим делитель опять меньше временного остатка, а значит можно вычитать!!!
Следовательно, мы делаем абсолютно те же действия что и на предыдущем слайде (вычитаем, пока modulo>=denominator) И так до конца цикла!
И, собственно, когда условие выхода из цикла сработает, а именно: временный итератор станет равен длине делимого – m, то в массиве modulo[] будет лежать искомый остаток!!!
Для нашего примера он равен 12320821968
И это весь алгоритм ☺