С помощью какой инструкции находится остаток от деления приведите пример

Деление с остатком целых положительных чисел

Деление — это разбиение целого на равные части.

Остаток от деления — это число, которое образуется при делении с остатком. То есть то, что «влезло» и осталось, как хвостик.

Проверка деления с остатком

Пока решаешь пример, бывает всякое: то в окно отвлекся, то друг позвонил. Чтобы убедиться в том, что все правильно, важно себя проверять. Особенно ученикам 5 класса, которые только начали проходить эту тему.

Эту формулу можно использовать для проверки деления с остатком.

Пример

Рассмотрим выражение: 15 : 2 = 7 (остаток 1).

В этом выражении: 15 — это делимое, 2 — делитель, 7 — неполное частное, а 1 — остаток.

Чтобы убедиться в правильности ответа, нужно неполное частное умножить на делитель (или наоборот) и к полученному произведению прибавить остаток. Если в результате получится число, которое равно делимому, то деление с остатком выполнено верно. Вот так:

• 7 * 2 + 1 = 15;
• 2 * 7 + 1 = 15.

Чтобы научиться делить числа с остатком, нужно усвоить некоторые правила. Начнем!

Все целые положительные числа являются натуральными. Поэтому деление целых чисел выполняется по всем правилам деления с остатком натуральных чисел.

Самый удобный способ деления — это столбик.

Попрактикуемся в решении.

Пример

Разделить 14671 на 54.

Как решаем:

Выполним деление столбиком:

Неполное частное равно 271, остаток — 37.

Ответ: 14671 : 54 = 271(остаток 37).

Деление с остатком положительного числа на целое отрицательное

Чтобы легко выполнить деление с остатком положительного числа на целое отрицательное, обратимся к правилу:

Неполное частное — это результат деления с остатком. Обычно в ответе записывают целое число и рядом остаток в скобках.

Это правило можно описать проще: делим два числа со знаком «плюс», а после подставляем «минус».

Все это значит, что «хвостик», который у нас остается, когда делим положительное число на отрицательное — всегда положительное число.

Алгоритм деления положительного числа на целое отрицательное (с остатком):

• найти модули делимого и делителя;
• разделить модуль делимого на модуль делителя
• получить неполное частное и остаток;
• записать число противоположное полученному.

Пример

Разделить 17 на −5 с остатком.

Как решаем:

Применим алгоритм деления с остатком целого положительного числа на целое отрицательное.

Разделим 17 на − 5 по модулю. Отсюда получим, что неполное частное равно 3, а остаток равен 2. Получим, что искомое число от деления 17 на − 5 = − 3 с остатком 2.

Проверка : a = b * q + r, 17 = −5 * (−3) + 2.

Ответ: 17 : (− 5) = −3 (остаток 2).

Онлайн-курсы математики для детей помогут подтянуть оценки, подготовиться к контрольным, ВПР и экзаменам.

Деление с остатком целого отрицательного числа на целое положительное

Чтобы быстро разделить с остатком целое отрицательное число на целое положительное, тоже придумали правило:

Из правила делаем вывод, что при делении получается целое неотрицательное число.

Для точности решения применим алгоритм деления а на b с остатком:

• найти модули делимого и делителя;
• разделить по модулю;
• записать противоположное данному число и вычесть 1;
• использовать формулу для остатка r = a − b * q.

Рассмотрим пример, где можно применить алгоритм.

Пример

Найти неполное частное и остаток от деления −17 на 5.

Как решаем:

Разделим заданные числа по модулю.

Получаем, что при делении частное равно 3, а остаток 2.

Так как получили 3, противоположное ему −3.

Необходимо отнять единицу: −3 − 1 = −4.

Чтобы вычислить остаток, необходимо a = −17, b = 5, q = −4, тогда:

r = a − b * q = −17 − 5 * (−4) = −17 − (− 20) = −17 + 20 = 3.

Значит, неполным частным от деления является число −4 с остатком 3.

Проверка: a = b * q + r, −17 = 5 * (−4) + 3.

Ответ: (−17) : 5 = −4 (остаток 3).

Деление с остатком целых отрицательных чисел

Сформулируем правило деления с остатком целых отрицательных чисел:

Из правила следует, что неполное частное от деления целых отрицательных чисел — положительное число.

Алгоритм деления с остатком целых отрицательных чисел:

• найти модули делимого и делителя;
• разделить модуль делимого на модуль делителя;
• получить неполное частное и остаток;
• прибавить 1 к неполному частному;
• вычислить остаток, исходя из формулы r = a − b * q.

Пример

Найти неполное частное и остаток при делении −17 на −5.

Как решаем:

Применим алгоритм для деления с остатком.

Разделим числа по модулю. Получим, что неполное частное равно 3, а остаток равен 2.

Сложим неполное частное и 1: 3 + 1 = 4. Из этого следует, что неполное частное от деления заданных чисел равно 4.

Для вычисления остатка применим формулу. По условию a = −17, b = −5, c = 4, тогда получим r = a − b * q = −17 − (−5) * 4 = −17 − (−20) = −17 + 20 = 3.

Получилось, что остаток равен 3, а неполное частное равно 4.

Проверка: a = b * q + r, −17 = −5 * 4 + 3.

Ответ: (−17) : (−5) = 4 (остаток 3).

Деление с остатком с помощью числового луча

Деление с остатком можно выполнить и на числовом луче.

Пример 1

Рассмотрим выражение: 10 : 3.

Отметим на числовом луче отрезки по 3 деления. Видим, что три деления помещаются полностью три раза и одно деление осталось.

Решение: 10 : 3 = 3 (остаток 1).

Пример 2

Рассмотрим выражение: 11 : 3.

Отметим на числовом луче отрезки по 3 деления. Видим, что три деления поместились три раза и два деления осталось.

Решение: 11 : 3 = 3 (остаток 2).

Эта статья — об алгоритмах деления целых чисел. О делении столбиком см. Деление столбиком; о теореме существования единственного частного и остатка см. Деление с остатком; о делении многочленов см. Деление многочленов.

Алгоритм деления — это алгоритм, вычисляющий для двух данных целых чисел и их частное и/или остаток, результат деления с остатком. Некоторые из алгоритмов предназначены для вычислений вручную, другие реализованы в цифровых схемах и программном обеспечении.

Алгоритмы деления разбиваются на две большие категории: медленное деление и быстрое деление. Алгоритмы медленного деления дают по одному знаку результата за итерацию. Примерами медленного деления служат алгоритмы деления с восстановлением, без восстановления и SRT. Методы быстрого деления начинаются с аппроксимации конечного частного и дают вдвое больше знаков в конечном результате на каждой итерации. Алгоритмы Ньютона – Рапсона и Гольдшмидта попадают в эту категорию.

Варианты этих алгоритмов позволяют использовать быстрые алгоритмы умножения. В результате этого для больших целых чисел время вычисления, необходимое для деления, будет тем же самым (с точностью до постоянного множителя), что и время, необходимое для выполнения умножения, какой бы алгоритм из перечисленных не был применён.

Обсуждение будет использовать обозначения , где

являются входными числами, а

являются выходными данными.

Деление путём вычитаний[править | править код]

Простейший алгоритм, исторически встроенный в алгоритм поиска наибольшего общего делителя и представленный в Началах Евклида, Книга VII Предложение 1, находит остаток деления двух положительных целых чисел с помощью только вычитания и сравнения:

R := N
while R >= D do
  R := R − D
end
return R

Доказательство, что частное и остаток существуют и единственные (описано в статье Деление с остатком) дают полный алгоритм деления, основанный на сложениях, вычитаниях и сравнениях:

function divide(N, D)
  if D = 0 then error(DivisionByZero) end
  if D < 0 then (Q, R) := divide(N, −D); return (−Q, R) end
  if N < 0 then
    (Q,R) := divide(−N, D)
    if R = 0 then return (−Q, 0)
    else return (−Q − 1, D − R) end
  end
  -- Здесь N >= 0 и D >= 0
  return divide_unsigned(N, D)
end

function divide_unsigned(N, D)
  Q := 0; R := N
  while R >= D do
    Q := Q + 1
    R := R − D
  end
  return (Q, R)
end

Эта процедура всегда даёт . Будучи очень простым, алгоритм требует шагов, а потому экспоненциально медленнее, чем алгоритмы наподобие длинного деления. Алгоритм полезен, если известно, что (шагов) мало (будучи зависимым от объёма вывода).

Деление столбиком[править | править код]

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

Когда алгоритм используется по основанию 2, этот метод образует базис для деления натуральных чисел с остатком. Короткое деление^[en] является вариантом деления в столбик, пригодным для деления на одну цифру. Алгоритм уменьшения^[en], известный также как метод неполных частных, является менее эффективным видом деления столбиком, но который проще понять. Разрешение вычитать большее кратное число, чем делается на каждом шаге, даёт больше свободы для создания вариантов деления в столбик.

Деление целых чисел (без знака) с остатком[править | править код]

Приведённый алгоритм, двоичная версия известного деления в столбик, делит на , помещая частное в и остаток в . Все значения трактуются как целые числа без знака.

if D = 0 then error(DivisionByZeroException) end -- Деление на ноль
Q := 0                  -- Начальные значения частного и остатка полагаем равны 0
R := 0                     
for i := n − 1 .. 0 do  -- Здесь n равно числу бит в N
  R := R << 1           -- Сдвиг влево числа R на 1 бит
  R(0) := N(i)          -- Полагаем младший бит R равным биту i делимого
  if R >= D then
    R := R − D
    Q(i) := 1
  end
end

Пример[править | править код]

Возьмём () и ()

Шаг 1: Set R = 0 and Q = 0
Шаг 2: Take i = 3 (на единицу меньше числа бит в N)
Шаг 3: R = 00 (сдвиг влево на 1)
Шаг 4: R = 01 (полагаем R(0) равным N(i))
Шаг 5: R < D, так что пропускаем команду

Шаг 2: Set i = 2
Шаг 3: R = 010
Шаг 4: R = 011
Шаг 5: R < D, пропускаем команду

Шаг 2: Set i = 1
Шаг 3: R = 0110
Шаг 4: R = 0110
Шаг 5: R >= D, команда выполняется
Шаг 5b: R = 10 (R−D)
Шаг 5c: Q = 10 (полагаем Q(i) равным 1)

Шаг 2: Set i = 0
Шаг 3: R = 100
Шаг 4: R = 100
Шаг 5: R >= D, команда выполняется
Шаг 5b: R = 0 (R−D)
Шаг 5c: Q = 11 (полагаем Q(i) равным 1)

Конец
() и .

Методы медленного деления[править | править код]

Все методы медленного деления основываются на стандартном рекуррентном отношении^[1]

где:

Восстанавливающее деление[править | править код]

Восстанавливающее деление работает с дробными числами числами с плавающей запятой и зависит от предположения .

Цифры частного формируются из набора .

Основной восстанавливающий алгоритм для двоичного (по основанию 2):

R := N
D := D << n             -- R и D должны быть словами вдвое длиннее, чем N и Q
for i := n − 1 .. 0 do  -- Например, 31..0 для 32 бит
  R := 2 * R − D        -- Пробное вычитание из сдвинутого значения (умножение на 2 есть сдвиг в бинарной интерпретации)
  if R >= 0 then
    q(i) := 1          -- Результат - бит 1
  else
    q(i) := 0          -- Результат - бит 0
    R := R + D         -- Новый частичный остаток равен (восстановленному) сдвинутому значению
  end
end

-- Здесь: N = делимое, D = делитель, n = число бит, R = частичный остаток, q(i) = бит № i частного

Вариант алгоритма, не осуществляющий явно , сохраняет его, а потому не нужно добавлять обратно в случае .

Невосстанавливающее деление[править | править код]

Невосстанавливающее деление использует набор цифр для цифр частного вместо . Алгоритм более сложен, но имеет преимущество, когда реализуется в микросхемах, что имеется всего одно принятие решения и одно сложение/вычитание на бит частного. Нет шага восстановления после вычитания, что может сократить число операций вдвое, и позволяет выполнить алгоритм быстрее^[2]. Алгоритм невосстанавливающего деления для двоичных (по основанию 2) положительных чисел:

R := N
D := D << n            -- R и D должны быть словами вдвое длиннее, чем N и Q
for i = n − 1 .. 0 do  -- Например, 31..0 для 32 бит
  if R >= 0 then
    q[i] := +1
    R := 2 * R − D
  else
    q[i] := −1
    R := 2 * R + D
  end if
end
 
-- Здесь: N = делимое, D = делитель, n = число бит, R = частичный остаток, q(i) = бит №i частного.

Если следовать этому алгоритму, получаем частное в нестандартном формате, состоящем из цифр -1 и +1. Этот вид нужно преобразовывать в двоичную форму. Пример:

Преобразование частного к цифрам :
Старт:
1. Образуем положительный член:
2. Образуем отрицательный член:
3. Вычитаем: :
Отрицательный член представлен в бинарном обратном коде, не в дополнительном коде

Если −1 знаки запомнены как нули (0), как в обычном представлении, то является и вычисление тривиально: осуществляет побитное дополнение (бит заменяется на дополнение бита) исходного .

Q := Q − bit.bnot(Q)      -- Если цифры −1 в Q представлены как нули.

Наконец, частные, вычисляемые этим алгоритмом, всегда нечётные, а остаток R находится в пределах . Например, . Для приведения к положительному остатку делаем один шаг восстановления после того, как приведена из нестандартного вида к стандартному:

if R < 0 then
  Q := Q − 1
  R := R + D  
end if

Истинный остаток равен R >> n. Как и в варианте с восстановлением, младшие биты используются в том же порядке, как образуются биты частного , и имеет смысл использовать единый сдвиг регистра для обоих чисел одновременно.

Деление SRT[править | править код]

Деление названо по первым буквам фамилий создателей (Sweeney, Robertson, Tocher). Деление SRT является популярным методом деления во многих микропроцессорах^[3][4]. Деление подобно делению без восстановления, но использует таблицу поиска на основе делимого и делителя для определения цифры частного.

Наиболее существенная разница в том, что используется избыточное представление для частного. Например, если реализуется деление SRT по основанию 4, каждая цифра частного выбирается из пяти возможностей: . Ввиду этого выбор цифры частного не обязательно должен быть точным. Позднее цифры частного можно откорректировать. Например, пары цифр и эквивалентны, поскольку . Это допустимое отклонение позволяет выбирать цифры частного, исходя только из нескольких наиболее значащих бит делимого и делителя, вместо вычитания по полной длине. Это упрощение, в свою очередь, позволяет применять основание для чисел, большее 2.

Подобно невосстанавливающему делению конечными шагами являются вычитание по полной длине чисел, чтобы получить последний бит частного, и приведение частного к стандартному двоичному виду.

Печально известный баг плавающего деления в процессорах Intel Pentium был вызван неправильно закодированной таблицей поиска. Пять из 1066 ячеек таблицы были ошибочно опущены^[5][6].

Методы быстрого деления[править | править код]

Деление Ньютона – Рапсона[править | править код]

Деление Ньютона – Рапсона использует метод Ньютона для нахождения обратного к числа и умножает это обратное на , чтобы найти результирующее частное .

Шаги деления Ньютона – Рапсона:

1. Вычисляем приближение для обратного числа делителя .
2. Последовательно вычисляем более точные приближения обратного числа. Это место, где, собственно, и используется метод Ньютона – Рапсона.
3. Вычисляем частное путём умножения делимого на обратное к делителю: .

Чтобы применить метод Ньютона для нахождения обратного к числа, необходимо найти функцию , имеющую нуль в точке . Очевидно, что такой функцией является , но итерации Ньютона – Рапсона для неё неуспешны, поскольку не могут быть осуществлены без знания обратного к числа (более того, метод пытается вычислить точное обратное за один шаг, а не делать итеративные улучшения). Функция, которая работает – это , для которой итерация Ньютона – Рапсона даёт

что можно вычислить из , используя только умножение и вычитание или два умножения-сложения.

С точки зрения вычислений выражения и не эквивалентны. Чтобы получить точность в 2n бит при использовании второго выражения, нужно вычислить произведение между и с двойной точностью к заданной точности (n бит). В отличие от этого произведение и нужно вычислять только с точностью n бит, поскольку ведущие n бит (после двоичной точки) числа нулевые.

Если ошибка определяется как , то

Эта ошибка в квадрате на каждом шаге итерации (так называемая квадратичная сходимость метода Ньютона – Рапсона) имеет эффект такой, что число верных знаков в результате, грубо говоря, удваивается для каждой итерации, свойство, которое становится крайне важным, когда встречающиеся числа имеют много знаков. Но это также означает, что начальная сходимость метода может оказаться сравнительно медленной, особенно если значение выбрано плохо.

Для подзадачи выбора начальной оценки удобно применить сдвиг делителя , чтобы он оказался между , с применением того же самого сдвига к делимому , чтобы частное не изменилось. Тогда можно использовать линейную Аппроксимацию в виде

для инициализации метода Ньютона – Рапсона. Чтобы минимизировать максимальную абсолютную ошибку этого приближения на интервале , следует использовать

Коэффициенты линейного приближения определяются следующим образом. Абсолютное значение ошибки равно . Минимум максимального абсолютного значения ошибки определяется согласно теореме Чебышева об эквивалентных колебаниях^[en], применённой к . Локальный минимум функции будет в точке, где , что имеет решение . Функция в этом минимуме должна иметь значение с противоположным знаком по отношению к крайним точкам интервала, а именно, . Два равенства от двух неизвестных дают единственное решение и , а максимальная ошибка равна . При использовании этого приближения абсолютное значение ошибки начального значения меньше, чем

Можно образовать многочлен со степенью большей 1, вычислив коэффициенты согласно алгоритму Ремеза. Тогда начальное приближение требует больших вычислений, что может компенсироваться меньшим числом итерация Ньютона – Рапсона.

Поскольку сходимость этого метода в точности квадратичная, отсюда следует, что достаточно

шагов для вычисления значения с точностью до двоичных мест. Это эквивалентно 3 для IEEE чисел одинарной точности и 4 для чисел двойной точности и чисел расширенной двойной точности.

Псевдокод[править | править код]

Следующий псевдокод вычисляет частное от деления N и D с точностью до P двоичных знаков:

Выражаем D как , где  (стандартное представление  с плавающей запятой)
   // приводим к значению между 0,5 и 1, что можно выполнить битовым сдвигом / вычитанием экспоненты

   // заранее вычисленные константы с той же точностью, что и D
повторить  раз   // может быть вычислено заранее для фиксированного P
    
конец
возвратить 

Например, для деления двойной точности с плавающей запятой этот метод использует 10 умножений, 9 сложений и 2 сдвига.

Варианты деления Ньютона – Рапсона[править | править код]

Метод деления Ньютона – Рапсона можно модифицировать, чтобы сделать чуть быстрее. После сдвига N и D, так что D будет в интервале [0,5, 1,0], инициализируем с

.

Это лучшее квадратичное приближение к и оно даёт значение абсолютной ошибки не больше . Параметры выбраны так, чтобы выбрать ошибку равной значению третьего порядка многочлена Чебышёва первого рода. Коэффициенты должны быть вычислены заранее и жёстко закодированы в методе.

Тогда в цикле используем итерацию, которая возводит ошибку в куб.

Если цикл выполняется пока не приблизится к до ведущих бит, то число итераций будет не более

что равно числу раз возведения 99 в куб, чтобы получить . Тогда

равно частному с точностью до бит.

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

Деление Гольдшмидта[править | править код]

Деление Гольдшмидта^[7] (Robert Elliott Goldschmidt) использует итеративный процесс многократного умножения делимого и делителя на один и тот же множитель , выбранный так, что делитель сходится к 1. Это приводит к тому, что делимое сходится к частному :

Шаги деления Гольдшмидта:

1. Генерируем приближение для множителя .
2. Умножаем делимое и делитель на .
3. Если делитель достаточно близок к 1, возвращаем делимое, в противном случае возвращаемся к шагу 1.

Предполагаем, что масштабировано к значению , каждый основан на :

Умножаем делимое и делитель на множитель и получаем:

После достаточного числа итераций .

Метод Гольдшмидта используется в процессорах AMD Athlon и более поздних моделях^[8][9]. Он известен также как Anderson Earle Goldschmidt Powers (AEGP) алгоритм и реализован в различных процессорах IBM^[10][11]. Хотя сходимость метода такая же, как у реализации Ньютона – Рапмона, одно из преимуществ метода Гольдшмидта в том, что умножения в числителе и знаменателе можно делать параллельно^[11].

Биномиальная теорема[править | править код]

Метод Гольдшмидта можно использовать с множителями, которые позволяют упрощение с помощью бинома Ньютона.
Предположим, что N/D умножено на степень двойки так, что .
Мы выбираем и .
Это даёт

.

После шагов знаменатель можно округлить до с относительной ошибкой

,

которая имеет максимальную величину при , обеспечивая минимальную точность в двоичных цифр.

Методы для больших чисел[править | править код]

Методы, предназначенные для аппаратной реализации, обычно не рассчитаны на целые числа с тысячами или миллионами десятичных цифр, что часто встречается, например, при вычислениях по сравнению по модулю в криптографии. Для этих больших чисел более эффективные алгоритмы преобразуют задачу к использованию малого числа умножений, которые можно сделать с помощью асимптотически эффективных алгоритмов умножения^[en], таких как Алгоритм Карацубы, умножение Тума – Кука^[en], или алгоритм Шёнхаге — Штрассена. В результате вычислительная сложность деления будет того же порядка (с точностью до умножения на константу) как и умножения. Примеры включают сведение к умножению по методу Ньютона как описанное выше^[12], так и чуть более быстрое деление Бурникеля – Циглера^[13], алгоритмы Барета^[en] и Монтгомери^[14]. Метод Ньютона, в частности, эффективен в сценариях, где нужно делить на определённое число несколько раз, поскольку после начального нахождения обратного значения только одно (сокращённое) умножение нужно для каждого умножения.

Деление на константу[править | править код]

Деление на константу эквивалентно умножению на её обратную величину.
Поскольку знаменатель постоянен, постоянна и обратная величина . Тогда можно вычислить значение один раз и во время вычислений осуществляем умножение вместо деления . В арифметике с плавающей запятой использование вызывают небольшую проблему, связанную с оптимизацией кода компиляторами^[a], но в арифметике целых чисел остаток всегда будет равен нулю, при условии .

Нет необходимости использовать именно , можно использовать любое значение которое сводится к . Например, при делении на 3, можно использовать дроби , , или . Следовательно, когда является степенью двойки, шаг деления можно свести к быстрому правому сдвигу. Как эффект, вычисление как заменяет деление на умножение и сдвиг. Заметим, что именно такой порядок действий здесь существенен, поскольку даст в результате нуль.

Однако, если уже является степенью двойки, нет и , удовлетворяющих условиям выше. К счастью, даёт в точности тот же результат в арифметике целых чисел, что и , даже если не в точности равно , но «достаточно близко», так что ошибка, вносимая при аппроксимации находится в битах, которые уйдут после операции сдвига^{[15][16][17][b]}

В качестве конкретного примера арифметики с фиксированной запятой, для 32-битных беззнаковых целых, деление на 3 может быть заменено на умножение на , то есть умножением на 2863311531 (шестнадцатеричное 0xAAAAAAAB) с последующим сдвигом на 33 бита вправо. Значение 2863311531 вычислено как , затем округлено. Аналогично деление на 10 может быть выражено как умножение на 3435973837 (0xCCCCCCCD) с последующим делением на (или сдвигом вправо на 35 бит)^[19]. OEIS даёт последовательность констант для умножения как A346495 и для правого сдвига как A346496.

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

где

В некоторых случаев деление на константу может быть совершено даже за меньшее время путём замены «умножения на константу» в серию сдвигов и сложений или вычитаний^[20]. Особый интерес представляет деление на 10, для которого получается точное частное с остатком, если потребуется^[21].

См. также[править | править код]

• Метод галеры
• Длинная арифметика — Алгоритмы деления
• Ошибка Pentium FDIV

Примечания[править | править код]

Литература[править | править код]

Литература для дальнейшего чтения[править | править код]

• John J. G. Savard. Advanced Arithmetic Techniques. quadibloc (2018). Дата обращения: 16 июля 2018. Архивировано 3 июля 2018 года.

Многие числа нельзя разделить нацело, при делении часто присутствует остаток, отличный от нуля. В этой статье мы разберем способы деления натуральных чисел с остатком и подробно рассмотрим их применение на примерах.

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

Деление натуральных чисел столбиком с остатком

Это один из самых удобных способов деления. Подробно он описан в отдельной статье, посвященной делению натуральных чисел столбиком. Здесь мы не будем приводить всю теорию заново, но сконцентрируемся именно на случае деления с остатком.

Приведем решение примера, так как понять суть метода проще всего на практике.

Деление чисел с остатком через последовательное вычитание

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

Рассмотрим еще один пример. На этот раз, приведем только математические выкладки, не прибегая к аналогиям.

Метод последовательного вычитания непригоден, когда делимое меньше делителя. В таком случае можно сразу записать ответ: неполное частное равно нулю, а остаток равен самому делимому.

Если a<b, то a÷b=0 (остаток a).

Например:

12÷36=0 (остаток 12)47÷88=0 (остаток 47) 

Также касательно метода последовательного вычитания нужно отметить, что он удобен только в случаях, когда вся операция деления сводится к небольшому количеству вычитаний. Если делимое во много раз больше делителя, использование этого метода будет нецелесообразно и связано с множеством громоздких вычислений.

Метод подбора неполного частного

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

Во-первых, определим, среди каких чисел нужно искать неполное частное. Из самого определения процесса деления понятно, что неполное частное равно нулю, либо является одним из натуральных чисел 1, 2, 3 и т.д.

Во-вторых, установим связь между делителем, делимым, неполным частным и остатком. Рассмотрим уравнение d=a-b·c. Здесь d — остаток от деления, a — делимое, b — делитель, с — неполное частное. 

В-третьих, не будем забывать, что остаток всегда меньше делителя.

Теперь рассмотрим непосредственно процесс подбора. Делимое a и делитель b известны нам с самого начала. В качестве неполного частного с будем последовательно принимать числа из ряда 0, 1, 2, 3 и т.д. Применяя формулу d=a-b·c и вычисляя полученное значение с делителем, закончим процесс, когда остаток d будет меньше, чем делитель b. Число, взятое за с на этом шаге и будет неполным частным. 

Разберем применение этого метода на примере.

Алгоритм деления натуральных чисел с остатком

Когда рассмотренные выше методы подбора неполного частного и последовательного вычитания требуют слишком громоздких вычислений, для деления с остатком применяется следующий метод. Рассмотрим алгоритм деления натурального числа a на число b с остатком.  

Вспомним, что в случае, когда a<b, неполное частное равно нулю, а остаток равен делимомому a. Мы будем рассматривать случай, когда a>b.

Сформулируем три вопроса и ответим на них:

1. Что там известно?
2. Что нам нужно найти?
3. Как мы будем это делать?

Изначально известными являются делимое и делитель: a и b.

Найти нужно неполное частное c и остаток d. 

Приведем формулу, которая задает связь между делимым, делителем, неполным частным и остатком. a=b·c+d. Именно это соотношение мы и возьмем за основу алгоритма деления натуральных чисел с остатком. Делимое a нужно представить в виде суммы a=b·c+d, тогда мы найдем искомые величины.

Алгоритм деления, благодаря которому мы представим a в виде суммы a=b·c+d очень схож с  алгоритмом деления натуральных чисел без остатка. Приведем ниже шаги алгоритма на примере деления числа 899 на 47.

1. Первым делом смотрим на делимое и делитель. Выясняем и запоминаем, на сколько знаков число в записи делимого больше числа в делителе. В нашем конкретном примере в делимом три знака, а в делителе — два. 

3-2=1

Запомним это число.

2. Справа в записи делителя допишем число нулей, определенное разницей между количеством знаков в делимом и делителе. В нашем случае нужно дописать один нуль. Если записанное число больше делимого, то нужно из запомненного в первом пункте числа вычесть единицу. 

В нашем примере справа от 47 дописываем нуль. Так как 470<899, запомненное в предыдущем пункте число не нужно уменьшать на единицу. Таким образом, число 1 так и остается у нас в памяти.

3. Справа к цифре 1 приписываем количество нулей, равное числу, определенному в предыдущем пункте. В нашем примере, приписывая к единице один нуль, получаем число 10. В результате данного действия мы получили рабочую единицу разряда, с которым будем работать дальше.

4. Будем последовательно умножать делитель на  1, 2, 3.. и т.д. единицы рабочего разряда, пока не получим число, которое больше или равно делимому. 

Рабочий разряд в нашем примере — десятки. После умножения делителя на одну единицу рабочего разряда, получаем 470.

470<899, поэтому умножаем на еще одну единицу рабочего разряда. Получаем: 47·20=940; 940>899.

Число, которое мы получили на предпоследнем шаге (470=47·10) является первым из искомых слагаемых.

5. Найдем разность между делимым и первым найденным слагаемым. Если полученное число больше делителя, то переходим к нахождению второго слагаемого. 

Шаги 1-5 повторяем, однако в качестве делимого принимаем полученное здесь число. Если снова получаем число, большее, чем делитель, снова по-кругу повторяем пункты  1-5, но уже с новым числом в качестве делимого. Продолжаем, пока полученное здесь число не будет меньше делителя. Переходим к завершающему этапу. Забегая вперед, скажем, что последнее полученное число и будет равно остатку.

Обратимся к примеру. 899-470=429, 429>47. Повторяем шаги 1-5 алгоритма с числом 429, взятым в качестве делимого.

1. В записи числа 429 на один знак больше, чем в записи числа 47. Запоминаем разницу — число 1.

2. В записи делимого справа дописываем один нуль. Получаем число 470. Так как 470>429, из запомненного в предыдущем пункте числа 1 вычитаем 1 и получаем 1-1=0. Запоминаем 0.

3. Так как в предыдущем пункте мы получили число 0 и запомнили его, нам не нужно прибавлять ни одного нуля к единице справа. Таким образом, рабочим разрядом являются единицы

4. Последовательно умножим делитель 47 на 1, 2, 3 .. и т.д. Не будем приводить подробные выкладки, а обратим внимание на конечный результат: 47·9=423<429, 47·10=470>429. Таким образом, второе искомое слагаемое — 47·9=423.

5. Разность между 429 и 423 равна числу 6. Так как 6<47, это третье, и последнее искомое слагаемое. Перейдем к завершающему этапу алгоритма деления столбиком.

6. Целью предыдущих действий было представление делимого в виде суммы нескольких слагаемых. Для нашего примера мы получили 899=470+423+6. Вспоминаем, что 470=47·10, 423=47·9. Перепишем равенство:

899=47·10+47·9+6

Применим распределительное свойство умножения.

899=47·10+47·9+6=47·(10+9)+6

899=47·19+6.

Таким образом, мы представили делимое в виде уже данной ранее формулы a=b·c+d.

Искомые неизвестные:неполное частное с=19, остаток d=6.

Безусловно, при решении практических примеров нет нужды расписывать все действия так подробно. Покажем это:

Деление натуральных чисел с остатком. Проверка результата

Деление натуральных чисел с остатком, особенно при больших числах, довольно трудоемкий и громоздкий процесс. Допустить ошибку в вычислениях может каждый. Именно поэтому, проверка результата деления поможет понять, все ли вы сделали правильно. Проверка результата деления натуральных чисел с остатком выполняется в два этапа.

На первом этапе проверяем, не получился ли остаток больше делителя. Если нет, то все хорошо. Иначе, можно сделать вывод, что что-то пошло не так.

Остаток всегда меньше делителя!

На втором этапе проверяется справедливость равенства a=b·c+d. Если равенство после подстановки значений оказывается верным, то и деление было выполнено без ошибок.

Автор: Виктор Трофимов, МОУ гимназия №5, г. Волгодонск, Ростовская обл.

В Паскале существует возможность использования трех методов определения кратности числа.

1. С помощью оператора div (целоисчисленное деление). Как это работает?

x := 10 div 2 (переменная x получит значение 5; процессор вычисляет пример 10 / 2 и выдает результат 5)

x := 10 div 3 (переменная x получит значение 3; вычисляется 10 / 3 = 3,33 и отбрасывается дробная часть, такова природа работы оператора div)

x := 10 div 4 (переменная x получит значение 2; 10 / 4 = 2,5 – и опять отбрасывается дробная часть).

2. С помощью оператора mod (остаток от деления).

Тут и понятно, остаток от деления числа, которое полностью делится на делитель, будет равен нулю.

x := 10 mod 2 (переменная x получит значение 0; процессор вычисляет по формуле 10 – ((10 div 2) * 2) = 0, то есть оператор mod возвращает пользователю остаток, который получится в результаты вычитания из делимого числа разницы между первым в сторону уменьшения делящимся нацело на делитель… эмм, надеюсь, понятно. Еще на примерах:

x := 10 mod 3 (переменная x получит значение 1; происходит следующее 10 div 3 = 3 (целое), дальше 10 – 3 (результат) * 3 (делитель) = 1)

x := 10 mod 4 (переменная x получит значение 2; вычисляется 10 – ((10 div 4) * 4)).

Внимательно изучите работу операторов div и mod, они важны для решения задач ГИА по информатике.

3. С помощью функции отбрасывания дробной части числа (не округления, а именно отбрасывания).

trunc(z), где z – вещественное число или математическое выражение.

Примеры:

x := trunc(3.33) (x получит значение 3; «удаляется» дробная часть)

x := trunc(10 / 3) (x получит значение 3, 10 / 3 = 3.33, отбрасываем «,33»)

x := trunc(10 / 2) (x получит значение 5, 10 / 2 = 5 (целое число))

x := trunc(10 / 4) (x получит значение 2, 10 / 4 = 2.5, отбрасываем дробную часть)

Но этот метод не совсем удобен, так как дублирует более понятный в тексте программы div. Таким же образом можно проверить кратность чисел:

Если ((x mod 3) = 0), то число кратно трем (остаток от деления равен нулю).

Если ((x mod = 0), то число кратно восьми и т.д.

Как найти цифру, на которую оканчивается число? Все просто, надо найти остаток от деления числа на 10.

Примеры:

Результатом 150 mod 10 будет число 0, т.к. 150 полностью делится на 10. 0 – это последняя цифра числа.

153 mod 10 вернет 3 (153 – ((153 div 10) * 10); 3 – эта цифра, на которую оканчивается число.

87 mod 10 вернет 7 – последнюю цифру числа.

33 mod 10 вернет 3 и т.д. Попробуйте сами: writeln(33 mod 10);

Автор: