Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
Много букв, вся статья сводится к одному, проверка входных данных:
public static int gcd(int a, int b) {
if (a <= 0 || b <= 0) {
throw new IllegalArgumentException();
}
...
}
Зачем кидать исключение при нормальных данных?
Они не нормальные. Я не знаю, почему в Википедии написано «целых чисел». В «Математическом энциклопедическом словаре (1988)» у меня значится «Наибольший общий делитель двух или нескольких натуральных чисел».
Но в википедии как минимум написано
так что часть нападок ТС являются ошибочными.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
так что часть нападок ТС являются ошибочными.
Но вы же исправили в Википедии, да?
В Википедии всё верно написано. И преведён источник.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Вероятно, для НОД(0, 0) разумно принять значение ∞ или бросать исключение, для остальных пар целых чисел он прекрасно находится.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Вероятно, для НОД(0, 0) разумно принять значение ∞ или бросать исключение, для остальных пар целых чисел он прекрасно находится.
Ещё можно INT_MAX :) Всё равно пока аргумент int ничего больше просто быть не может. Но я бы бросил исключение либо вернул −1: ±∞ существует только для чисел с плавающей запятой, выпендрёж с INT_MAX вряд ли кому‐то нужен, а −1 gcd возвращать не должен ни при каких условиях. Т.е. специальное значение (здесь — −1, т.к. я последнее время много пишу на C, но это может быть и nan (привет языкам без целых чисел) или Nothing) для языков без исключений (или где их не принято использовать для математических функций) либо исключение.
Лучше кинуть исключение, т.к. результат будет использоваться потом. В случае NaN исключение наверняка вылезет в другом месте, а с -1 вообще может ничего и не быть.
Исключений может просто не быть: тогда и кинуть их не получится. NaN взят из lua, там исключения ловятся весьма заморочным способом с pcall, а math.log(-1) возвращает NaN.
Но когда они есть, лучше их и кидать, благо они для этого и созданы.
А log(-1) = NaN, так это в соответствии с IEEE 754 возвращает сопроцессор, lua здесь абсолютно не причем.
А log(-1) = NaN, так это в соответствии с IEEE 754 возвращает сопроцессор, lua здесь абсолютно не причем.
Лучше тогда вернуть gcd(Math.Abs(a), Math.Abs(b));
Если уж и кидать исключение, то только если
a < 0 || b < 0, в случае с нулем все нормально отработает
Чувак, не парься. Garbage in, garbage out. :)
Обычно задача начинается с «Дано два натуральных числа...»
На западе часто 0 считается натуральным. Лучше использовать словосочетание positive integer
Я на западе. Где это тут 0 считается натуральным?
Peano axioms — 0 is a natural number.
Аскиомы Пеано — 1 является натуральным числом
В Agda, Coq и Idris натуральные тоже начинаются с 0.
Аскиомы Пеано — 1 является натуральным числом
В Agda, Coq и Idris натуральные тоже начинаются с 0.
Хех, а в геометрии Лобачевского параллельные линии пересекаются.
Но за Пеано спасибо! Отличное чтиво на ночь :)
Но за Пеано спасибо! Отличное чтиво на ночь :)
Regrettably, there seems to be no general agreement about whether to include 0 in the set of natural numbers.
(с) Wolfram MathWorld
Ну это и не противоречит, ведь где как. Я просто уточнил, что в Agda, Coq, а также в Homotopy type theory таки с нуля, а это вроде как наиболее современное в программировании и математике.
There is no universal agreement about whether to include zero in the set of natural numbers: some define the natural numbers to be the positive integers {1, 2, 3, ...}, while for others the term designates the non-negative integers {0, 1, 2, 3, ...}. The former definition is the traditional one, with the latter definition having first appeared in the 19th century.
Natural Numbers
Natural Numbers
> НОД существует для любых двух целых чисел.
НОД(0;0)?
НОД(0;0)?
Хм. Что в таком случае тогда можно сказать про НОК?
Есть очень хорошая лекция А. Степанова (автора C++ STL) про алгоритм Эвклида: video.yandex.ru/users/ya-events/view/129#
Так там он описывает, как к нему на одну из предыдущих лекций пришел Дональд Кнут и сказал в стиле «Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель.» На что Степанов ответил: «Зависит от определения». В лекции по ссылке подробно описано и объяснено.
Так там он описывает, как к нему на одну из предыдущих лекций пришел Дональд Кнут и сказал в стиле «Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель.» На что Степанов ответил: «Зависит от определения». В лекции по ссылке подробно описано и объяснено.
int ans = gcd(Math.abs(a), Math.abs(b));
У этого решения могут быть проблемы, когда одно из чисел a или b равно int.MinValue (для него Abs не работает). Справится ли второе решение
(if(b==0) return Math.Abs(a)) для всех случаев, кроме (int.MinValue,0) и (int.MinValue, int.MinValue), я не проверял (подозрение вызывает (int.MinValue,-1) — будет ли там считаться без ошибки и исключений остаток от деления?)
Думаю, что безопаснее было бы сразу перевести аргументы в uint (или в ulong, если мы пишем gcd(long,long)), а в конце преобразовать ответ обратно. Как-нибудь так:
long gcd(long x,long y){
ulong a=x,b=y;
if(x<0) a=-a;
if(y<0) b=-b;
while(b!=0){
ulong t=a%b;
a=b;
b=t;
}
return (long)a;
}
А почему -5 не может быть делителем? ведь указанные числа на него делятся, и без остатка.
Может быть, такой ответ и неудобен в некоторых применениях, но чему собственно он противоречит?
Хм… разделить яблоко на -5 частей… а что, звучит!
Может быть, такой ответ и неудобен в некоторых применениях, но чему собственно он противоречит?
Хм… разделить яблоко на -5 частей… а что, звучит!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вычисление НОД — ошибка, которой не замечают