Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Деление длинного числа на короткое




В младших классах в школе, все мы так же изучали деление столбиком. Мы будем рассматривать деление на короткое число b. При делении столбиком сначала выписывается старшая цифра, эту цифру делят на b. Частное дописывают к результату, а остаток пишут ниже. После этого к остатку приписывают следующую цифру, полученное значение делят на b. Аналогично, частное дописывают к ответу, а остаток пишут ниже. Процесс продолжается пока все цифры не будут использованы.

 

4531 | 7

42 ------

---- | 647

----

---

Остаток, к которому уже нельзя приписать цифру, будет остатком от деления.

function divide(var a: thuge; b: integer): integer;

{функция делит число a на короткое число b и возвращает остаток от деления}

Var

i, r: integer;

{r - обозначает текущий остаток, к которому будет приписана очередная цифра}

Begin

r:= 0;

{изначально остаток 0}

for i:= a[0] downto 1 do

{цикл от старших цифр к младшим}

Begin

r:= r * base + a[i];

{приписывание очередной цифры}

a[i]:= r div b;

{запись частного в результат}

r:= r mod b;

{пересчет остатка}

end;

{Частное может содержать меньше цифр,

поэтому нужно при необходимости уменьшить количество цифр}

while (a[0] > 1) and (a[a[0]] = 0) do

Begin

dec(a[0]);

end;

divide:= r;

end;

 

int divide(thuge &a, int b) {

/*функция делит число a на короткое число b и возвращает остаток от деления*/

/*r - обозначает текущий остаток, к которому будет приписана очередная цифра*/

int r = 0;

//изначально остаток 0

for (int i = a[0]; i >= 1; --i) {

/*цикл от старших цифр к младшим*/

r = r * base + a[i];

//приписывание очередной цифры

a[i] = r / b;

//запись частного в результат

r %= b;

//пересчет остатка

}

/*Частное может содержать меньше цифр,

поэтому нужно при необходимости уменьшить количество цифр*/

while (a[0] > 1 && a[a[0]] == 0) {

--a[0];

}

return r;

}

При умножении двух длинных чисел в столбик, первое число последовательно умножается на каждую цифру. Результат умножения на i-тую цифру прибавляется к общему результату со сдвигом на i – 1.

 

procedure multiplyHuge(var a, b: thuge);

{функция умножает число a на число b}

Var

c: thuge;

{c - результат умножения. В данном случае нельзя записывать результат в тот же массив.}

i, j, r: integer;

Begin

fillchar(c, sizeof (c), 0); //заполнение массива 0

for i:= 1 to a[0] do

Begin

r:= 0;

j:= 1;

while (j <= b[0]) or (r > 0) do

{пока есть перенос или в b есть еще цифры}

Begin

inc(c[i + j - 1], a[i] * b[j] + r);

{при умножении на предыдущие цифры в c уже записано некоторое значение,

поэтому нужно прибавлять, а не присваивать}

r:= c[i + j - 1] div base;

dec(c[i + j - 1], r * base);

inc(j);

end;

end;

c[0]:= a[0] + b[0]; {максимально возможное количество цифр в ответе}

move(c, a, sizeof (c)); {переместим ответ в массив a}

//но цифр может оказаться меньше

while (a[0] > 1) and (a[a[0]] = 0) do

Begin

dec(a[0]);

end;

end;

 

void multiply(thuge &a, thuge &b) {

//функция умножает число a на число b

thuge c;

memset(c, 0, sizeof (c)); //заполнение массива 0

/*c - результат умножения. В данном случае нельзя записывать результат в тот же массив.*/

for (int i = 1; i <= a[0]; ++i) {

int r = 0, j;

for (j = 1; j <= b[0] || r > 0; ++j) {

//пока есть перенос или в b есть еще цифры

c[i + j - 1] += a[i] * b[j] + r;

/*при умножении на предыдущие цифры в c уже записано

некоторое значение, поэтому нужно прибавлять, а не

присваивать*/

r = c[i + j - 1] / base;

c[i + j - 1] -= r * base;

}

}

c[0] = a[0] + b[0];

//максимально возможное количество цифр в ответе

memmove(a, c, sizeof (c)); //переместим ответ в массив a

//но цифр может оказаться меньше

while (a[0] > 1 && a[a[0]] == 0) {

--a[0];

}

}

 

Выбирая основание системы исчисления, нужно добиваться максимальной скорости работы, т. е. брать как можно большую систему исчисления, с одной стороны и не забывать о том, что стандартные типы представляют ограниченное множество чисел. Например, если в вашей программе используется умножение длинных чисел то, чтобы избежать переполнения число должно (base – 1) * base должно помещаться в базовый тип. При делении или умножении на короткое число b, число b * base + base должно помещаться в базовый тип. Не трудно заметить, что деление длинного числа на короткое и умножение длинного числа на короткое работает за линейное время относительно длины числа. Умножение длинных чисел работает за время пропорциональное произведению их длин.

 

Квадратный корень

Вычисление квадратного корня это достаточно сложная операция. Здесь под квадратным корнем числа y мы будем подразумевать наибольшее число x, такое, что x2 <= y. Мы делаем так, потому что работаем только с целыми числами. Функция x2 монотонно возрастает, т. е. чем больше x, тем больше x2. Поэтому для нахождения квадратного корня можно применить бинарный поиск. Рассмотрим середину m отрезка [l, r], в котором мы производим поиск (изначально можно выбрать отрезок [0, y]). Если m2 > y, то дальнейший поиск нужно проводить в отрезке [l, m - 1], иначе в отрезке [m, r]. Для реализации вычисление квадратного корня нам потребуется: сложение длинных чисел, деление длинного числа на короткое (эти операции нужны для нахождения середины отрезка), а так же произведение длинных чисел (для вычисления m2) и сравнение длинных чисел. Время работы этого алгоритма можно оценить как куб длины числа y. Если длина числа y равна l, то выполниться порядка l шагов бинарного поиска, в каждом из которых будет выполнено произведение двух длинных чисел длины порядка l.

Алгоритм Евклида

Нахождение наибольшего общего делителя с помощью классического алгоритма довольно трудно для реализации с длинными числами. При реализации классического алгоритма нам потребуется производить деление двух длинных чисел, что мы вообще не рассматривали в этой главе в связи со сложностью этого алгоритма. (Подумайте, как произвести деление с помощью бинарного поиска, и какого будет время работы такого деления). Мы же рассмотрим способ найти НОД, пользуясь лишь операциями, которые мы рассмотрели. Для этого рассмотрим 3 случая:

  • Оба числа четны (2n, 2k)
  • Оба числа нечетны (2n + 1, 2k + 1)
  • Числа разной четности (2n, 2k + 1)

В первом случае воспользуемся соображением НОД(2n, 2k) = 2 * НОД(n, k). Во втором случае НОД(2n + 1, 2k + 1) = НОД(2n – 2k, 2k + 1). В третьем случае НОД(2n, 2k + 1) = НОД(n, 2k + 1). Как мы видим при таком способе нахождения НОД нам потребуются только операции: деление на короткое (точнее на 2), вычитание, умножение на короткое (точнее на 2). Пункты 1 и 3 уменьшают хотя бы одно из чисел в 2 раза, а это может произойти не больше чем log этого числа. Log числа пропорционален его длине. Пункт 2 сразу же приводит нас в ситуацию 3, поэтому можно говорить, что каждые 2 шага алгоритма одно из чисел уменьшиться вдвое. На каждом шаге выполняется операция, требующая линейное время. Следовательно, время работы алгоритма пропорционально квадрату длины чисел.

 

 

План дальнейшего развития:

1) Попытка сложить два числа и выяснение, что хранить число перевернутым намного удобней.

2) Вычитание из большего меньшее.

3) Умножение на короткое

4) Деление на короткое

5) Умножение длинных

6) *Извлечение квадратного корня двоичным поиском.

7) ** Извлечение квадратного корня за квадрат длины числа.

8) Быстрое возведение в степень.

9) Поиск наибольшего общего делителя. Алгоритм Евклида. Бинарный алгоритм поиска НОД.

6) Сложная штука, я бы поставил звездочку.

7) Этого не было в ЛКШ, хотим ли мы это? Это еще сложней. Но это иногда рассказывают в школе. Так руками корень извлекают.

8) Это выглядит совсем не по теме. Быстрое возведение в степень имеет смысл только по модулю. В обычном случае числа растут быстро, и за счет умножения длинных чисел, такое возведение становится менее эффективным, чем линейное возведение.






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных