- Главная
- Информатика
- Одномерные массивы и работа со строками
Содержание
- 2. Условие задачи Составить программу нахождения остатка от деления m-значного числа на n–значное (m, n > 20).
- 3. Алгоритм решения задачи Разумеется, нам как то нужно хранить переданные два числа! Для этого я создал
- 4. Input() – Что делает эта функция? Предположим мы подаём на вход строку: 5 7 3 1
- 5. Последующие действия В целом мой алгоритм можно рассказать в двух словах – деление столбиком Предположим что
- 6. Что же делает функция FirstMinuend ??? У нас делитель: 64752467899, и делимое И если длина делителя
- 7. Что же происходит дальше? Как мы помним, у нас остались какие то не тронутые цифры в
- 8. Первые важные действия Вот мы и подошли уже к одному из важнейших этапов работы программы, это...
- 9. На вход пришли два числа уменьшаемое modulo=573182549125 вычитаемое denominator = 64752467899 Так как они поданы нам
- 10. Дальнейшие продвижения На данный момент мы имеем: modulo = 55162805933 denominator = 64752467899 numerator = 57318254912583
- 11. Заключительный этап Теперь мы имеем немножко другую картину: modulo = 551628059338 denominator = 64752467899 Как видим
- 13. Скачать презентацию
Условие задачи
Составить программу нахождения остатка от деления m-значного числа на n–значное
Условие задачи
Составить программу нахождения остатка от деления m-значного числа на n–значное
m>20
n>20
Длинная
арифметика!
Алгоритм решения задачи
Разумеется, нам как то нужно хранить переданные два числа!
Алгоритм решения задачи
Разумеется, нам как то нужно хранить переданные два числа!
Для этого я создал два массива типа Char, и назвал их таким образом: numerator[] – делимое, denominator[] - делитель
char numerator[N];
char denominator[N];
Const int N = 100000; // Заведём константу
И введём наши числа:
Input (char[], &int);
Длина числа
Int m = длина делимого
Int n = длина делителя
Для начала разберёмся с вводом) Из условия видно, что подаются два числа в виде строк
Массив для ввода
Input() – Что делает эта функция?
Предположим мы подаём на вход строку:
5
7
3
1
8
2
5
4
9
1
2
5
8
3
Чтобы
Input() – Что делает эта функция?
Предположим мы подаём на вход строку:
5
7
3
1
8
2
5
4
9
1
2
5
8
3
Чтобы
Пока мы не нажмём 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 = размер
Что же делает функция FirstMinuend ???
У нас делитель: 64752467899, и делимое
И
Что же делает функция FirstMinuend ???
У нас делитель: 64752467899, и делимое
И
Первым шагом заполняем массив, первыми 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
Что же происходит дальше?
Как мы помним, у нас остались какие
Что же происходит дальше?
Как мы помним, у нас остались какие
Мы уже выяснили что длина делителя равна 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)
Длина уменьшаемого
Длина вычитаемого
Уменьшаемое
Вычитаемое
На вход пришли два числа уменьшаемое modulo=573182549125 вычитаемое denominator = 64752467899
На вход пришли два числа уменьшаемое modulo=573182549125 вычитаемое denominator = 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
Дальнейшие продвижения
На данный момент мы имеем:
modulo = 55162805933
denominator = 64752467899
numerator
Дальнейшие продвижения
На данный момент мы имеем:
modulo = 55162805933
denominator = 64752467899
numerator
StartIndex = 12
А теперь как раз и пора вспомнить про StartIndex ведь теперь нам потребуются все цифры, начиная с элемента лежащего в ячейке с данным индексом массива делимого. А для этого мы будем использовать цикл от этого самого StartIndex и до m (длина делимого)
Итак в цикле нам следует добавить элемент(ещё одну цифру) справа, это будет элемент из массива делимого с индексом 12, то есть добавляется цифра 8.
Заключительный этап
Теперь мы имеем немножко другую картину:
modulo = 551628059338
denominator = 64752467899
Как
Заключительный этап
Теперь мы имеем немножко другую картину:
modulo = 551628059338
denominator = 64752467899
Как
Следовательно, мы делаем абсолютно те же действия что и на предыдущем слайде (вычитаем, пока modulo>=denominator) И так до конца цикла!
И, собственно, когда условие выхода из цикла сработает, а именно: временный итератор станет равен длине делимого – m, то в массиве modulo[] будет лежать искомый остаток!!!
Для нашего примера он равен 12320821968
И это весь алгоритм ☺