Деление с остатком
Деление c остатком (деление по модулю) — арифметическая операция, играющая большую роль в арифметике, теории чисел и алгебре. Чаще всего эта операция определяется для целых или натуральных чисел следующим образом[1]. Пусть <math>a</math> и <math>b</math> — целые числа, причём <math>b \ne 0.</math> Деление с остатком <math>a</math> («делимого») на <math>b</math> («делитель») означает нахождение таких целых чисел <math>q</math> и <math>r</math>, что выполняется равенство:
- <math>a = b \cdot q+r</math>
Таким образом, результатами деления с остатком являются два целых числа: <math>q</math> называется неполным частным от деления, а <math>r</math> — остатком от деления. На остаток налагается дополнительное условие: <math>0 \leqslant r < |b|,</math> то есть остаток от деления должен быть неотрицательным числом и по абсолютной величине меньше делителя. Это условие обеспечивает однозначность результатов деления с остатком для всех целых чисел. Если остаток равен нулю, говорят, что <math>a</math> нацело делится на <math>b.</math>
Примеры.
- При делении с остатком положительного числа <math>a = 78</math> на <math>b = 33</math> получаем неполное частное <math>q = 2</math> и остаток <math>r = 12</math>.
- Проверка: <math>78 = 33 \cdot 2 + 12.</math>
- При делении с остатком отрицательного числа <math>a = -78</math> на <math>b = 33</math> получаем неполное частное <math>q = -3</math> и остаток <math>r = 21</math>.
- Проверка: <math>-78 = 33 \cdot (-3) + 21.</math>
- При делении с остатком числа <math>a = 78</math> на <math>b = 26</math> получаем неполное частное <math>q = 3</math> и остаток <math>r = 0</math>, то есть деление выполняется нацело..
Операция деления с остатком может быть определена не только для целых чисел, но и для других математических объектов (например, для многочленов), см. ниже.
Содержание
Определение
Натуральные и целые числа
Оставаясь строго в рамках натуральных чисел, приходится различать деление с остатком и деление нацело, поскольку нулевой остаток не является натуральным числом; кроме того, неполное частное при делении меньшего числа на большее должно равняться нулю, что тоже выводит за рамки натуральных чисел. Все эти искусственные ограничения неоправданно усложняют формулировки, поэтому в источниках обычно либо рассматривается расширенный натуральный ряд, включающий ноль[2], либо теория сразу формулируется для целых чисел, как указано выше.
Для практического выполнения целочисленного деления <math>a</math> на <math>b</math> с остатком следует разделить (в обычном смысле) <math>a</math> на <math>b</math> как вещественные числа и округлить результат до ближайшего целого в меньшую сторону, это будет неполное частное <math>q</math>:
- <math>q = \left\lfloor \frac{a}{b}\right\rfloor</math>
Здесь скобки <math>\left\lfloor \frac{a}{b}\right\rfloor</math> означают округление до ближайшего целого в меньшую сторону. Далее найдём остаток от деления:
- <math>r = a - b \cdot q</math>
Обобщения
Вещественные числа
Если два числа <math>a</math> и <math>b</math> (отличное от нуля) относятся к множеству вещественных чисел, <math>a</math> может быть поделено на <math>b</math> без остатка, и при этом частное также является вещественным числом. Если же частное по условию должно быть целым числом, в этом случае остаток будет вещественным числом, то есть может оказаться дробным.
Формально:
- если <math>a,b\in \mathbb{R}, b\ne 0</math>, то <math>a = bq+r</math>, где <math>0\leqslant r< |b|</math>
Пример:
- <math>7{,}9 : 2{,}1 = 3</math> (остаток 1,6)
Гауссовы целые числа
Гауссово число — это комплексное число вида <math>a+bi</math>, где <math>a, b</math> — целые числа. Для них можно определить деление с остатком: любое гауссово число <math>u</math> можно разделить с остатком на любое ненулевое гауссово число <math>v</math>, то есть представить в виде:
- <math>u = vq + r</math>
где частное <math>q</math> и остаток <math>r</math> — гауссовы числа, причём <math>|r|<|v|.</math> Однако, в отличие от целых чисел, остаток от деления определяется неоднозначно. Например, <math>7+2i</math> можно разделить на <math>3-i</math> тремя способами:
- <math>7+2i = (3-i)(2+i)+i = (3-i)(1+i)+3 = (3-i)(2+2i)+(-1-2i)</math>
Многочлены
При делении с остатком двух многочленов <math>f(x)</math> и <math>g(x)</math> для однозначности результата вводится условие: степень многочлена-остатка должна быть строго меньше степени делителя:
- <math>f(x) = q(x) g(x) + r(x) \quad</math>, причём <math>\quad \deg(r) < \deg(g).</math>
Пример:
- <math>\frac{2x^2 + 4x + 5}{x+1} = 2x + 2</math> (остаток 3), так как 2x² + 4x + 5 = (x + 1)(2x + 2) + 3
В программировании
| Язык | Неполное частное |
Остаток | Знак остатка |
|---|---|---|---|
| ActionScript | % |
Делимое | |
| Ada | mod | Делитель | |
| rem | Делимое | ||
| ASP | Mod |
Не определено | |
| Бейсик | \ |
MOD |
Не определено |
| Си (ISO 1990) | / |
% |
Не определено |
| Си (ISO 1999) | / |
% |
Делимое[3] |
| C++ (ISO 2003) | / |
% |
Не определено[4] |
| C++ (ISO 2011) | / |
% |
Делимое[5] |
| C# | / |
% |
Делимое |
| ColdFusion | MOD |
Делимое | |
| Common Lisp | mod |
Делитель | |
rem |
Делимое | ||
| Delphi | div |
mod |
Делимое |
| Eiffel | // |
\\ |
Делимое |
| Erlang | div |
rem |
Делимое |
| Euphoria | remainder |
Делимое | |
| Microsoft Excel (англ.) | QUOTIENT() |
MOD()
|
Делитель |
| Microsoft Excel (рус.) | ЧАСТНОЕ() |
ОСТАТ()
| |
| FileMaker | Div() |
Mod() |
Делитель |
| Fortran | mod |
Делимое | |
modulo |
Делитель | ||
| GML (Game Maker) | div |
mod |
Делимое |
| Go | / |
% |
Делимое |
| Haskell | div
|
mod |
Делитель |
quot
|
rem |
Делимое | |
| J | |~ |
Делитель | |
| Java | /
|
%
|
Делимое[6] |
Math.floorDiv
|
Math.floorMod
|
Делитель (1.8+) | |
| JavaScript | % |
Делимое | |
| Lua | % |
Делитель | |
| Mathematica | Mod |
Делитель | |
| MATLAB | idivide(?, ?, 'floor') |
mod |
Делитель |
idivide |
rem |
Делимое | |
| MySQL | DIV |
MOD% |
Делимое |
| Objective Caml | mod |
Не определено | |
| Pascal | div |
mod |
Делимое[7] |
| Perl | Нет | % |
Делитель |
| PHP | Нет[8] | % |
Делимое |
| PL/I | mod |
Делитель (ANSI PL/I) | |
| Prolog (ISO 1995) | mod | Делитель | |
| PureBasic | / |
Mod% |
Делимое |
| Python | // |
% |
Делитель |
| QBasic | \ |
MOD | Делимое |
| R | %% | Делитель | |
| RPG | %REM | Делимое | |
| Ruby | % | Делитель | |
| Scheme | modulo | Делитель | |
| SenseTalk | modulo | Делитель | |
| rem | Делимое | ||
| Tcl | % | Делитель | |
| Verilog (2001) | % | Делимое | |
| VHDL | mod | Делитель | |
| rem | Делимое | ||
| Visual Basic | \ |
Mod |
Делимое |
Нахождение остатка от деления часто используется в компьютерной технике и телекоммуникационном оборудовании для создания контрольных чисел и получении случайных чисел в ограниченном диапазоне, например в конгруэнтном генераторе случайных чисел.
Обозначения операции взятия остатка в различных языках программирования представлены в таблице справа.
Например, в Паскале операция mod вычисляет остаток от деления, а операция div осуществляет целочисленное деление, при котором остаток от деления отбрасывается:
78 mod 33 = 12
78 div 33 = 2Знак остатка
Важно отметить, что операция взятия остатка в языках программирования может возвращать отрицательный результат (для отрицательного делимого или делителя). Тут есть два варианта:
- Знак остатка совпадает со знаком делимого: неполное частное округляет к нулю.
- Знак остатка совпадает со знаком делителя: неполное частное округляет к −∞.
Если в языке есть оба типа остатков, каждому из них соответствует своя операция неполного частного. Обе операции имеют жизненный смысл.
- Есть сумма n копеек, положительная или отрицательная. Перевести её в рубли и копейки. —
n div 100иn mod 100. Знак остатка совпадает со знаком делимого. - Есть бесконечное клеточное поле, каждая клетка — 16×16 пикселей. В какую клетку попадает точка (x, y), и каковы координаты относительно верхнего левого угла клетки? —
(x div 16, y div 16)и(x mod 16, y mod 16)соответственно. Знак остатка совпадает со знаком делителя.
Как запрограммировать, если такой операции нет?
Неполное частное можно запрограммировать как <math>q = \left[\frac{a}{b}\right]</math> (с тем или иным видом округления к целому). Однако деление получается дробное, которое намного медленнее целого. Такой алгоритм используется в языках, в которых нет целых типов (отдельные электронные таблицы, программируемые калькуляторы и математические программы), а также в скриптовых языках, в которых издержки интерпретации намного превышают издержки дробной арифметики (Perl, PHP).
При отсутствии команды mod остаток программируется как <math>a - qb</math>.
Если b положительно, а знак r совпадает со знаком делимого, не определён или неизвестен, для нахождения минимального неотрицательного остатка можно воспользоваться формулой <math>r' = (b+(a \operatorname{mod} b)) \operatorname{mod} b</math>.
См. также
Напишите отзыв о статье "Деление с остатком"
Примечания
- ↑ Деление // [eqworld.ipmnet.ru/ru/library/books/Vinogradov_MatEnc_t2.djvu Математическая энциклопедия (в 5 томах)]. — М.: Советская Энциклопедия, 1979. — Т. 2.
- ↑ Потапов М. К., Александров В. В., Пасиченко П. И. Алгебра и анализ элементарных функций. М.: Наука, 1981, 560 с., С. 9.
- ↑ ISO/IEC 9899:TC2: When integers are divided, the result of the
/operator is the algebraic quotient with any fractional part discarded. [This is often called “truncation toward zero”.]; в списке изменений 1999→TC1 и TC1→TC2 данное изменение не числится. - ↑ «ISO/IEC 14882:2003 : Programming languages -- C++», 5.6.4: International Organization for Standardization, International Electrotechnical Commission, 2003. «the binary % operator yields the remainder from the division of the first expression by the second. …. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined».
- ↑ N3242=11-0012 (Working draft), текст совпадает с C99
- ↑ К. Арнолд, Дж. Гослинг, Д. Холмс. Язык программирования Java. — 3-е изд. — М., СПб., Киев: Вильямс, 2001. — С. 173—174. — ISBN 5-8459-0215-0.
- ↑ Стандарт 1973 года: div — division with truncation.
- ↑ [php.net/manual/en/language.operators.arithmetic.php PHP: Arithmetic Operators - Manual]
Ссылки
- [www.fxyz.ru/формулы_по_математике/арифметика/арифметические_действия/деление/ Деление с остатком: онлайн-калькулятор]
Отрывок, характеризующий Деление с остатком
– Так, так, – проговорил Багратион, что то соображая, и мимо передков проехал к крайнему орудию.В то время как он подъезжал, из орудия этого, оглушая его и свиту, зазвенел выстрел, и в дыму, вдруг окружившем орудие, видны были артиллеристы, подхватившие пушку и, торопливо напрягаясь, накатывавшие ее на прежнее место. Широкоплечий, огромный солдат 1 й с банником, широко расставив ноги, отскочил к колесу. 2 й трясущейся рукой клал заряд в дуло. Небольшой сутуловатый человек, офицер Тушин, спотыкнувшись на хобот, выбежал вперед, не замечая генерала и выглядывая из под маленькой ручки.
– Еще две линии прибавь, как раз так будет, – закричал он тоненьким голоском, которому он старался придать молодцоватость, не шедшую к его фигуре. – Второе! – пропищал он. – Круши, Медведев!
Багратион окликнул офицера, и Тушин, робким и неловким движением, совсем не так, как салютуют военные, а так, как благословляют священники, приложив три пальца к козырьку, подошел к генералу. Хотя орудия Тушина были назначены для того, чтоб обстреливать лощину, он стрелял брандскугелями по видневшейся впереди деревне Шенграбен, перед которой выдвигались большие массы французов.
Никто не приказывал Тушину, куда и чем стрелять, и он, посоветовавшись с своим фельдфебелем Захарченком, к которому имел большое уважение, решил, что хорошо было бы зажечь деревню. «Хорошо!» сказал Багратион на доклад офицера и стал оглядывать всё открывавшееся перед ним поле сражения, как бы что то соображая. С правой стороны ближе всего подошли французы. Пониже высоты, на которой стоял Киевский полк, в лощине речки слышалась хватающая за душу перекатная трескотня ружей, и гораздо правее, за драгунами, свитский офицер указывал князю на обходившую наш фланг колонну французов. Налево горизонт ограничивался близким лесом. Князь Багратион приказал двум баталионам из центра итти на подкрепление направо. Свитский офицер осмелился заметить князю, что по уходе этих баталионов орудия останутся без прикрытия. Князь Багратион обернулся к свитскому офицеру и тусклыми глазами посмотрел на него молча. Князю Андрею казалось, что замечание свитского офицера было справедливо и что действительно сказать было нечего. Но в это время прискакал адъютант от полкового командира, бывшего в лощине, с известием, что огромные массы французов шли низом, что полк расстроен и отступает к киевским гренадерам. Князь Багратион наклонил голову в знак согласия и одобрения. Шагом поехал он направо и послал адъютанта к драгунам с приказанием атаковать французов. Но посланный туда адъютант приехал через полчаса с известием, что драгунский полковой командир уже отступил за овраг, ибо против него был направлен сильный огонь, и он понапрасну терял людей и потому спешил стрелков в лес.
– Хорошо! – сказал Багратион.
В то время как он отъезжал от батареи, налево тоже послышались выстрелы в лесу, и так как было слишком далеко до левого фланга, чтобы успеть самому приехать во время, князь Багратион послал туда Жеркова сказать старшему генералу, тому самому, который представлял полк Кутузову в Браунау, чтобы он отступил сколь можно поспешнее за овраг, потому что правый фланг, вероятно, не в силах будет долго удерживать неприятеля. Про Тушина же и баталион, прикрывавший его, было забыто. Князь Андрей тщательно прислушивался к разговорам князя Багратиона с начальниками и к отдаваемым им приказаниям и к удивлению замечал, что приказаний никаких отдаваемо не было, а что князь Багратион только старался делать вид, что всё, что делалось по необходимости, случайности и воле частных начальников, что всё это делалось хоть не по его приказанию, но согласно с его намерениями. Благодаря такту, который выказывал князь Багратион, князь Андрей замечал, что, несмотря на эту случайность событий и независимость их от воли начальника, присутствие его сделало чрезвычайно много. Начальники, с расстроенными лицами подъезжавшие к князю Багратиону, становились спокойны, солдаты и офицеры весело приветствовали его и становились оживленнее в его присутствии и, видимо, щеголяли перед ним своею храбростию.
Князь Багратион, выехав на самый высокий пункт нашего правого фланга, стал спускаться книзу, где слышалась перекатная стрельба и ничего не видно было от порохового дыма. Чем ближе они спускались к лощине, тем менее им становилось видно, но тем чувствительнее становилась близость самого настоящего поля сражения. Им стали встречаться раненые. Одного с окровавленной головой, без шапки, тащили двое солдат под руки. Он хрипел и плевал. Пуля попала, видно, в рот или в горло. Другой, встретившийся им, бодро шел один, без ружья, громко охая и махая от свежей боли рукою, из которой кровь лилась, как из стклянки, на его шинель. Лицо его казалось больше испуганным, чем страдающим. Он минуту тому назад был ранен. Переехав дорогу, они стали круто спускаться и на спуске увидали несколько человек, которые лежали; им встретилась толпа солдат, в числе которых были и не раненые. Солдаты шли в гору, тяжело дыша, и, несмотря на вид генерала, громко разговаривали и махали руками. Впереди, в дыму, уже были видны ряды серых шинелей, и офицер, увидав Багратиона, с криком побежал за солдатами, шедшими толпой, требуя, чтоб они воротились. Багратион подъехал к рядам, по которым то там, то здесь быстро щелкали выстрелы, заглушая говор и командные крики. Весь воздух пропитан был пороховым дымом. Лица солдат все были закопчены порохом и оживлены. Иные забивали шомполами, другие посыпали на полки, доставали заряды из сумок, третьи стреляли. Но в кого они стреляли, этого не было видно от порохового дыма, не уносимого ветром. Довольно часто слышались приятные звуки жужжанья и свистения. «Что это такое? – думал князь Андрей, подъезжая к этой толпе солдат. – Это не может быть атака, потому что они не двигаются; не может быть карре: они не так стоят».
Худощавый, слабый на вид старичок, полковой командир, с приятною улыбкой, с веками, которые больше чем наполовину закрывали его старческие глаза, придавая ему кроткий вид, подъехал к князю Багратиону и принял его, как хозяин дорогого гостя. Он доложил князю Багратиону, что против его полка была конная атака французов, но что, хотя атака эта отбита, полк потерял больше половины людей. Полковой командир сказал, что атака была отбита, придумав это военное название тому, что происходило в его полку; но он действительно сам не знал, что происходило в эти полчаса во вверенных ему войсках, и не мог с достоверностью сказать, была ли отбита атака или полк его был разбит атакой. В начале действий он знал только то, что по всему его полку стали летать ядра и гранаты и бить людей, что потом кто то закричал: «конница», и наши стали стрелять. И стреляли до сих пор уже не в конницу, которая скрылась, а в пеших французов, которые показались в лощине и стреляли по нашим. Князь Багратион наклонил голову в знак того, что всё это было совершенно так, как он желал и предполагал. Обратившись к адъютанту, он приказал ему привести с горы два баталиона 6 го егерского, мимо которых они сейчас проехали. Князя Андрея поразила в эту минуту перемена, происшедшая в лице князя Багратиона. Лицо его выражало ту сосредоточенную и счастливую решимость, которая бывает у человека, готового в жаркий день броситься в воду и берущего последний разбег. Не было ни невыспавшихся тусклых глаз, ни притворно глубокомысленного вида: круглые, твердые, ястребиные глаза восторженно и несколько презрительно смотрели вперед, очевидно, ни на чем не останавливаясь, хотя в его движениях оставалась прежняя медленность и размеренность.
Полковой командир обратился к князю Багратиону, упрашивая его отъехать назад, так как здесь было слишком опасно. «Помилуйте, ваше сиятельство, ради Бога!» говорил он, за подтверждением взглядывая на свитского офицера, который отвертывался от него. «Вот, изволите видеть!» Он давал заметить пули, которые беспрестанно визжали, пели и свистали около них. Он говорил таким тоном просьбы и упрека, с каким плотник говорит взявшемуся за топор барину: «наше дело привычное, а вы ручки намозолите». Он говорил так, как будто его самого не могли убить эти пули, и его полузакрытые глаза придавали его словам еще более убедительное выражение. Штаб офицер присоединился к увещаниям полкового командира; но князь Багратион не отвечал им и только приказал перестать стрелять и построиться так, чтобы дать место подходившим двум баталионам. В то время как он говорил, будто невидимою рукой потянулся справа налево, от поднявшегося ветра, полог дыма, скрывавший лощину, и противоположная гора с двигающимися по ней французами открылась перед ними. Все глаза были невольно устремлены на эту французскую колонну, подвигавшуюся к нам и извивавшуюся по уступам местности. Уже видны были мохнатые шапки солдат; уже можно было отличить офицеров от рядовых; видно было, как трепалось о древко их знамя.
– Славно идут, – сказал кто то в свите Багратиона.
Голова колонны спустилась уже в лощину. Столкновение должно было произойти на этой стороне спуска…
Остатки нашего полка, бывшего в деле, поспешно строясь, отходили вправо; из за них, разгоняя отставших, подходили стройно два баталиона 6 го егерского. Они еще не поровнялись с Багратионом, а уже слышен был тяжелый, грузный шаг, отбиваемый в ногу всею массой людей. С левого фланга шел ближе всех к Багратиону ротный командир, круглолицый, статный мужчина с глупым, счастливым выражением лица, тот самый, который выбежал из балагана. Он, видимо, ни о чем не думал в эту минуту, кроме того, что он молодцом пройдет мимо начальства.
С фрунтовым самодовольством он шел легко на мускулистых ногах, точно он плыл, без малейшего усилия вытягиваясь и отличаясь этою легкостью от тяжелого шага солдат, шедших по его шагу. Он нес у ноги вынутую тоненькую, узенькую шпагу (гнутую шпажку, не похожую на оружие) и, оглядываясь то на начальство, то назад, не теряя шагу, гибко поворачивался всем своим сильным станом. Казалось, все силы души его были направлены на то,чтобы наилучшим образом пройти мимо начальства, и, чувствуя, что он исполняет это дело хорошо, он был счастлив. «Левой… левой… левой…», казалось, внутренно приговаривал он через каждый шаг, и по этому такту с разно образно строгими лицами двигалась стена солдатских фигур, отягченных ранцами и ружьями, как будто каждый из этих сотен солдат мысленно через шаг приговаривал: «левой… левой… левой…». Толстый майор, пыхтя и разрознивая шаг, обходил куст по дороге; отставший солдат, запыхавшись, с испуганным лицом за свою неисправность, рысью догонял роту; ядро, нажимая воздух, пролетело над головой князя Багратиона и свиты и в такт: «левой – левой!» ударилось в колонну. «Сомкнись!» послышался щеголяющий голос ротного командира. Солдаты дугой обходили что то в том месте, куда упало ядро; старый кавалер, фланговый унтер офицер, отстав около убитых, догнал свой ряд, подпрыгнув, переменил ногу, попал в шаг и сердито оглянулся. «Левой… левой… левой…», казалось, слышалось из за угрожающего молчания и однообразного звука единовременно ударяющих о землю ног.
