Comments 39
Много букв, вся статья сводится к одному, проверка входных данных:
public static int gcd(int a, int b) {
if (a <= 0 || b <= 0) {
throw new IllegalArgumentException();
}
...
}
-2
Зачем кидать исключение при нормальных данных?
+16
Они не нормальные. Я не знаю, почему в Википедии написано «целых чисел». В «Математическом энциклопедическом словаре (1988)» у меня значится «Наибольший общий делитель двух или нескольких натуральных чисел».
+11
Но в википедии как минимум написано
так что часть нападок ТС являются ошибочными.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
так что часть нападок ТС являются ошибочными.
+2
Но вы же исправили в Википедии, да?
+4
В Википедии всё верно написано. И преведён источник.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Вероятно, для НОД(0, 0) разумно принять значение ∞ или бросать исключение, для остальных пар целых чисел он прекрасно находится.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Вероятно, для НОД(0, 0) разумно принять значение ∞ или бросать исключение, для остальных пар целых чисел он прекрасно находится.
+2
Ещё можно INT_MAX :) Всё равно пока аргумент int ничего больше просто быть не может. Но я бы бросил исключение либо вернул −1: ±∞ существует только для чисел с плавающей запятой, выпендрёж с INT_MAX вряд ли кому‐то нужен, а −1 gcd возвращать не должен ни при каких условиях. Т.е. специальное значение (здесь — −1, т.к. я последнее время много пишу на C, но это может быть и nan (привет языкам без целых чисел) или Nothing) для языков без исключений (или где их не принято использовать для математических функций) либо исключение.
0
Лучше кинуть исключение, т.к. результат будет использоваться потом. В случае NaN исключение наверняка вылезет в другом месте, а с -1 вообще может ничего и не быть.
0
Исключений может просто не быть: тогда и кинуть их не получится. NaN взят из lua, там исключения ловятся весьма заморочным способом с pcall, а math.log(-1) возвращает NaN.
0
Но когда они есть, лучше их и кидать, благо они для этого и созданы.
А log(-1) = NaN, так это в соответствии с IEEE 754 возвращает сопроцессор, lua здесь абсолютно не причем.
А log(-1) = NaN, так это в соответствии с IEEE 754 возвращает сопроцессор, lua здесь абсолютно не причем.
0
Не сказал бы: Python и Perl кидают исключение, lua тоже не обязан выдавать то, что выдаёт сопроцессор. Высокоуровневые языки на то и высокоуровневые, что абстрагируются от железа.
0
Лучше тогда вернуть gcd(Math.Abs(a), Math.Abs(b));
0
Если уж и кидать исключение, то только если
a < 0 || b < 0
, в случае с нулем все нормально отработает-2
Чувак, не парься. Garbage in, garbage out. :)
+15
Обычно задача начинается с «Дано два натуральных числа...»
+7
На западе часто 0 считается натуральным. Лучше использовать словосочетание positive integer
0
Я на западе. Где это тут 0 считается натуральным?
+1
Peano axioms — 0 is a natural number.
Аскиомы Пеано — 1 является натуральным числом
В Agda, Coq и Idris натуральные тоже начинаются с 0.
Аскиомы Пеано — 1 является натуральным числом
В Agda, Coq и Idris натуральные тоже начинаются с 0.
+3
Хех, а в геометрии Лобачевского параллельные линии пересекаются.
Но за Пеано спасибо! Отличное чтиво на ночь :)
Но за Пеано спасибо! Отличное чтиво на ночь :)
-8
Regrettably, there seems to be no general agreement about whether to include 0 in the set of natural numbers.
(с) Wolfram MathWorld
+1
Ну это и не противоречит, ведь где как. Я просто уточнил, что в Agda, Coq, а также в Homotopy type theory таки с нуля, а это вроде как наиболее современное в программировании и математике.
+2
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
+1
> НОД существует для любых двух целых чисел.
НОД(0;0)?
НОД(0;0)?
+4
Хм. Что в таком случае тогда можно сказать про НОК?
0
Есть очень хорошая лекция А. Степанова (автора C++ STL) про алгоритм Эвклида: video.yandex.ru/users/ya-events/view/129#
Так там он описывает, как к нему на одну из предыдущих лекций пришел Дональд Кнут и сказал в стиле «Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель.» На что Степанов ответил: «Зависит от определения». В лекции по ссылке подробно описано и объяснено.
Так там он описывает, как к нему на одну из предыдущих лекций пришел Дональд Кнут и сказал в стиле «Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель.» На что Степанов ответил: «Зависит от определения». В лекции по ссылке подробно описано и объяснено.
+2
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;
}
0
А почему -5 не может быть делителем? ведь указанные числа на него делятся, и без остатка.
Может быть, такой ответ и неудобен в некоторых применениях, но чему собственно он противоречит?
Хм… разделить яблоко на -5 частей… а что, звучит!
Может быть, такой ответ и неудобен в некоторых применениях, но чему собственно он противоречит?
Хм… разделить яблоко на -5 частей… а что, звучит!
-1
Sign up to leave a comment.
Вычисление НОД — ошибка, которой не замечают