Одномерные массивы и работа со строками

1. Индивидуальное задание №1

«ОДНОМЕРНЫЕ МАССИВЫ И РАБОТА СО СТРОКАМИ»
Работу выполнял: Студент 1-го курса ММФ ПГНИУ,
учебной группы ПМИ – 1 Зимин Илья

2. Условие задачи

Составить программу нахождения остатка от
деления m-значного числа на n–значное (m, n > 20).
Длинная
арифметика!

3. Алгоритм решения задачи

Для начала разберёмся с вводом) Из условия видно, что подаются два числа в виде строк
Разумеется, нам как то нужно хранить переданные два числа!
Для этого я создал два массива типа Char, и назвал их таким образом:
numerator[] – делимое, denominator[] - делитель
Const int N = 100000; // Заведём константу
char numerator[N];
Int m = длина делимого
char denominator[N];
Int n = длина делителя
Массив для ввода
И введём наши числа:
Input (char[], &int);
Длина числа

4. Input() – Что делает эта функция?

Чтобы продемонстрировать алгоритм, не обязательно брать число,
которое содержат >20 разрядов
Предположим мы подаём на вход строку:
5731825491
12583
2583
Пока мы не нажмём ENTER:
Int i =0;
(-48(код ‘0’)) – переделываем
из кода цифры в саму цифру
Array[i] = getchar()-48;
i ++;
Array = {
0
1
2
3
4
5
6
7
8
9
10
m = i (устанавливаем длину числа)
11
12
13
}

5. Последующие действия

В целом мой алгоритм можно рассказать в двух словах – деление столбиком
Предположим что мы уже заполнили два наших массива numerator = 57318254912583
denominator = 64752467899
И тут мы понимаем что нам нужен ещё один массив для хранения остатка, ведь
постоянно менять делимое не так то и удобно, поэтому мы заводим ещё один
массив с именем modulo
char modulo[N];
Int nMod = размер
// И заполним мы его как первое уменьшаемое
(то есть мы поместим в него ту часть делимого
которая является минимально возможной, чтобы
хотя б один раз поделить на наш делитель )
FirstMinuend (numerator,m,denominator,n,modulo,nMod);

6. Что же делает функция FirstMinuend ???

Что же делает функция FirstMinuend
самом деле мы в ней просто ищем то самое первое уменьшаемое
??? На
Для чего оно нужно? Узнаете позже
У нас делитель: 64752467899,
n = 11
57318254912
12583
5
и делимое
m = 14
И если длина делителя больше или равна(но при этом и само число больше) длине
делимого, то у нас делимое и будет являться остатком, если это не так то мы:
Первым шагом заполняем массив, первыми
nMod = n
modulo = {
0
1
2
3
4
5
6
n (количество цифр в ДЕЛИТЕЛЕ) цифрами
7
8
9
10 11
}
nMod = n+1
Дальше мы смотрим при помощи функций More и Equally, больше или равен Modulo делимому,
Если это так, то функция прекращает работу, иначе мы добавляем ещё одну цифру
в Modulo, в этом собственно и суть отдельного метода. В нашем же случае снесём ещё цифру

7. Что же происходит дальше?

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

8. Первые важные действия

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

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

На вход пришли два числа уменьшаемое modulo=573182549125
вычитаемое denominator = 64752467899 Так как они поданы нам в виде
массивов то вычитание придётся делать столбиком.
Если вдруг делитель всё же меньше делимого по длине то мы дополняем
его нулями спереди при помощи простой функции InsertZero, в нашем
примере как раз придётся добавить один нулик спереди к делителю
-
573182549125
064752467899
________________
50843 0 081226
+10
<0
+
Loan = -1
Вычитание прекратится, когда
modulo станет равно 055162805933
то есть меньше
064752467899
Не сложно заметить что в начале каждого из чисел стоят нули, а значит их нужно убрать!
Для этого можно воспользоваться простой, написанной функцией DeleteZero

10. Дальнейшие продвижения

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

11. Заключительный этап

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

12. А теперь результаты которые показала программа